Solving four-index transportation problem with the use of a genetic algorithm

• Autorzy: Skitsko Volodymyr , Voinikov Mykola

Identyfikatory

DOI

10.17270/J.LOG.2020.493

Warianty tytułu

PL

Rozwiązania czteroczynnikowego problemu transportowego przy pomocy algorytmu genetycznego

• Języki publikacji: EN

Abstrakty

EN

Background: Under conditions of digital transformation, the effective decision-making process should involve the usage of different mathematical models and methods, one of which is the transportation problem. The transportation problem, as the problem of resource allocation, is applicable in such domains as manufacturing, information technologies, etc. To get more precise solutions, the multi-index transportation problem can be applied, which allows taking into account several variables. Methods: This paper develops an approach for applying the genetic algorithm for solving four-index transportation problems. Results: The steps of the genetic algorithm for solving four-index transportation problems are outlined. The research has proved the steps of the genetic algorithm to be the same for all four-index transportation problem types, except for the first step (initialization), which is described for every type of transportation problem separately. Based on the theoretical results, the program implementation of the genetic algorithm for solving four-index symmetric transportation problems has been developed with the open-source programming language typescript. Conclusions: The paper promotes the application of the genetic algorithm for solving multi-index transportation problems. The investigated problem requires comprehensive studies, specifically, on the influence of change different parameters of the genetic algorithm (population size, the mutation, and crossover rates, etc.) on the efficiency of the algorithm in solving four-index transportation problems.

PL

Wstęp: W warunkach komputerowej transformacji, efektywny proces podejmowania decyzji powinien obejmować wykorzystania modeli metod matematycznych. Przykładem takiej sytuacji jest problem transportowy, który jest problemem alokacji zasobów, występujący w takich obszarach jak produkcji, technologie informatyczne, itp. W celu uzyskania precyzyjniejszych rozwiązań, można zastosować wieloczynnikowy problem transportowy, który umożliwia uwzględnienie wielu zmiennych. Metody: W pracy zastosowano algorytm genetyczny dla rozwiązania czteroczynnikowych problemów transportowych. Wyniki: Wyszczególniono kroki algorytmu genetycznego dla czteroczynnikowego problem transportowego. Udowodnione, że kroki algorytmu genetycznego są takie same dla wszystkich typów czteroczynnikowych problemów transportowych, z wyjątkiem pierwszego kroku (inicjalizacji), który został opisany osobno dla każdego z typów problemu transportowego. W oparciu o wyniki teoretyczne, utworzono programowanie dla algorytmu genetycznego dla rozwiązywania czteroczynnikowych problemów transportowych przy użyciu opensourcowego języka typescript. Wnioski: W pracy zaproponowano zastosowanie algorytmu genetycznego dla rozwiązywania wieloczynnikowych problemów transportowych. Analizowany problem wymaga dalszych badań, szczególnie w zakresie wpływu zmian poszczególnych parametrów algorytmu genetycznego (wielkości populacji, mutacji, współczynnika podziału, itp.) na efektywność algorytmu w rozwiązywaniu czteroczynnikowych problemów transportowych.

Słowa kluczowe

EN

four-index transportation problem; symmetric transportation problem; genetic algorithm; program implementation

PL

czteroczynnikowy problem transportowy; symetryczny problem transportowy; algorytm genetyczny; wdrożenie programu

• Wydawca: Wyższa Szkoła Logistyki
• Czasopismo: LogForum
• Rocznik: 2020
• Tom: Vol. 16, no. 3
• Strony: 397--408
• Opis fizyczny: Bibliogr. 19 poz.

Twórcy

autor

Skitsko Volodymyr

• Kyiv National Economic University named after Vadym Hetman, Institute Information Technologies in Economics, Kyiv, Ukraine

autor

Voinikov Mykola

• Kyiv National Economic University named after Vadym Hetman, Institute Information Technologies in Economics, Kyiv, Ukraine

Bibliografia

• 1. Dimov Yu. S., Lukyanov N.D., 2016. Genetic algorithm application for solving a multi-index transportation problem. Proceedings of Irkutsk State Technical University, 7, 73-79. http://doi.org/10.21285/1814-3520-2016-7-73-79
• 2. El-Shorbagy M., Mousa A., ALoraby H., Abo-Kila T., 2020. Evolutionary algorithm for multi-objective multi-index transportation problem under fuzziness. Journal of Applied Research on Industrial Engineering, 7 (1), 36-56. http://doi.org/0.22105/jarie.2020.214142.1119
• 3. Goldberg D. E., 1988. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley Publishing, Inc. 432 pages.
• 4. Indra Z., Chairunisah, Refisis N.R., 2020. Application Genetic Algorithm in solving three-level supply chain distribution problems. Journal of Physics: Conference Series. 1462. 012035. http://doi.org/10.1088/1742-6596/1462/1/012035
• 5. Javadi A., Tarokh M. J., Piroozfar S., 2014. Solving a multi-objective vehicle scheduling-routing of interurban transportation fleet with the purpose of minimizing delays by Using the Differential Evolutionary Algorithm. Uncertain Supply Chain Management, 2 (3), 125-136. http://doi.org/10.5267/j.uscm.2014.5.005
• 6. Kaedure Bakhuet A.-J., 2016. Solving bi-objective 4-dimensional transportation problem by using PSO. AGK Bakhat. Sci.Int (Lahor.), 28 (3), 2403-2410. http://www.sci-int.com/pdf/636551900738439387.pdf
• 7. Karthy T., Ganesan K., 2018. Multi Objective Transportation Problem - Genetic Algorithm Approach. International Journal of Pure and Applied Mathematics. Volume 119 No. 9, 343-350. https://acadpubl.eu/jsi/2018-119-9/articles/9/33.pdf
• 8. Kumar A., Yadav S. P., 2012. A Survey of Multi-index Transportation Problems and Its Variants with Crisp and Fuzzy Parameters. K. Proceedings of the International Conference on Soft Computing for Problem Solving (SocProS 2011) December 20-22, 2011. 919-932. http://doi.org/10.1007/978-81-322-0487-9_86
• 9. Luke S., 2013. Essentials of Metaheuristics. Lulu, second edition. 242 pages., Cite this document as: Sean Luke, 2009, Essentials of Metaheuristics, available at http://cs.gmu.edu/~sean/book/metaheuristics/
• 10. Raskin, L. G., Kirichenko, I. O., 1982. Mnogoindeksnye zadachi lineinogo programmirovaniya (Multi-index Problems of Linear Programming), Moscow: Radio i Svyaz'.
• 11. Ritha W., Vinotha. M. J., 2012. Heuristic algorithm for multi-index fixed charge fuzzy transportation problem. Elixir Comp. Sci. Engg. 46, 8346-8353. https://www.elixirpublishers.com/articles/1351162502_46%20(2012)%208346-8353.pdf
• 12. Senapati. S., 2018. Multi-Index Bi-Criterion Transportation Problem: A Fuzzy Approach. International Journal of Advanced Engineering, Management and Science, 4 (7), 550-556. http://doi.org/10.22161/ijaems.4.7.8
• 13. Singh S., Chauhan S.K., Kuldeep., 2018. A Bi-Criteria Multi-Index Bulk Transportation Problem. Annals of Pure and Applied Mathematics, 16 (2), 479-485. http://doi.org/10.22457/apam.v16n2a26
• 14. Singh S., Tuli R., Sarode D., 2016. A review on fuzzy and stochastic extensions of the Multi Index transportation problem. Yugoslav Journal of Operations Research, 27 (1), 3-29. http://doi.org/10.2298/YJOR150417007S
• 15. Skitsko V.I., Voinikov M. Yu., 2018. Solving a Three-Index Transportation Problem under Risk Conditions Using a Genetic Algorithm. The Problems of Economy, 3, 246-252. https://www.problecon.com/export_pdf/problems-of-economy-2018-3_0-pages-246_252.pdf
• 16. Thu Huyen N., Luong Sy Uoc, Rosaly B. Alday, 2013. Genetic Algorithm for Solving Balanced Transportation Problem. International Journal of Innovative Technology and Exploring Engineering. (IJITEE), 3 (4), 24-27. http://www.ijitee.org/wp-content/uploads/papers/v3i4/D1163093413.pdf
• 17. Tuyet-Hoa P., Philippe D., 2013. An Exact Method for Solving the Four Index Transportation Problem and Industrial Application. American Journal of Operational Research, 3 (2), 28-44. http://article.sapub.org/10.5923.j.ajor.20130302.02.html
• 18. TypeScript programming language, 2020. https://www.typescriptlang.org/
• 19. Yun Y., Chuluunsukh A., Gen M., 2020. Sustainable closed-loop supply chain design problem: A hybrid genetic algorithm approach. Mathematics, 8 (1), 84. http://doi.org/10.3390/math8010084

Uwagi

PL

Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2020).