Bir Lojistik Firmasının En Kısa Yol Problemine Düğüm Kombinasyonu Algoritmasının Uygulanması

Year 2022, Volume: 7 Issue: 2, 289 - 302, 16.01.2023

Kevser Arman , Ayşegül Tuş

https://doi.org/10.26650/JTL.2022.1092188

Abstract

Lojistik; ürünlerin taşınması, depolanması ve nihai varış noktasına ulaşması ile ilgili tüm süreçlerin yönetimidir. Lojistik faaliyetlerinin son derece karmaşık süreci, ürünlerin başlangıç noktasından varış noktasına kadar doğru bir şekilde koordinasyonunu gerektirir. Bu çalışmada, bir lojistik firması için Düzce-Artvin arasındaki toplam mesafeyi ve süreyi en aza indiren bir rota belirleme problemi, şebeke analiz yöntemlerinden biri olan En Kısa Yol (EKY) problemi olarak ele alınmıştır. Çalışmanın amacı, lojistik firmasının dağıtım faaliyetlerini optimize ederek daha yüksek düzeyde kârlılık ve müşteri hizmeti sunmaktır. Problemin çözümünde düğüm kombinasyonu algoritması kullanılmış, mesafe ve süre dikkate alınarak iki farklı rota elde edilmiştir. Bulgular, toplam minimum mesafenin 1152 km ve toplam minimum sürenin 16 saat 33 dakika olduğunu göstermektedir. Çalışmada toplam minimum mesafe dikkate alınarak elde edilen rota, Google Haritalar’ın sunduğu iki rotadan daha kısa mesafede ve sürede alternatif bir rota sunmaktadır. Ayrıca toplam minimum süre dikkate alınarak elde edilen rotanın, Google Haritalar’ın sunduğu alternatifler arasından en kısa mesafe ve süreye ait olan rota ile uyumlu olması, düğüm kombinasyonu algoritmasının uygulanabilirliğini göstermesi açısından önemlidir.

Keywords

En Kısa Yol Problemi, Düğüm Kombinasyonu Algoritması, Şebeke Analizi

Applying the Node Combination Algorithm to the Shortest Path Problem for a Logistics Firm

Abstract

Logistics entails the management of all processes related to products’ transportation, storage, and arrival at their destination. The highly complex process of logistics activities requires products to be accurately coordinated from their starting point to their destination. This study considers a route determination problem that minimizes the total distance and time between the cities of Düzce and Artvin in Turkey for a logistics company in terms of the shortest path problem (SPP), a network analysis method. The aim of the study is to provide a higher level of profitability and customer service by optimizing the distribution activities of a logistics company. The node combination algorithm has been used to solve the problem, with two different routes being obtained by considering distance and time. The study’s findings show the total minimum distance to be 1,152 km and the total minimum time to be 16 hours and 33 minutes. The route the study obtained by considering the total minimum distance offers an alternative route in terms of both shorter distance and time compared to the two routes offered by Google Maps. In addition, having the route obtained by considering the total minimum time be compatible with the route with the shortest distance and time that is found among the alternatives offered by Google Maps is important in terms of demonstrating the applicability of the node combination algorithm used in the study. 

Keywords

Network Analysis, Shortest Path Problem, Node Combination Algorithm, Şebeke Analizi, En Kısa Yol Problemi, Düğüm Kombinasyonu Algoritması

References

• Amaliah, B., Fatichah, C., & Riptianingdyah, O. (2016). “Finding the Shortest Paths Among Cities in Java Island Using Node Combination Based on Dijkstra Algorithm”. International Journal on Smart Sensing & Intelligent Systems, 9(4), 2219-2236.
• Bulut, F., & Erol, H. M. (2018). “A Real-Time Dynamic Route Control Approach on Google Maps Using Integer Programming Methods”. International Journal of Next-Generation Computing, 189-202.
• Climaco, J. C. N., & Martins, E. Q. V. (1982). “A Bicriterion Shortest Path Algorithm”. European Journal of Operational Research, 11(4), 399-404.
• Deng, Y., Chen, Y., Zhang, Y., & Mahadevan, S. (2012). “Fuzzy Dijkstra Algorithm for Shortest Path Problem Under Uncertain Environment”. Applied Soft Computing, 12(3), 1231-1237.
• Dermawan, T. S. (2019). “Comparison of Dijkstra dan Floyd-Warshall Algorithm to Determine the Best Route of Train”. IJID (International Journal on Informatics for Development), 7(2), 54-58.
• Dijkstra EW. (1959) “A Note on Two Problems in Connexion with Graphs”. Numerische Mathematik, 1(1), 269-271.
• Düzce’den Artvin’e Alternatif Rotalar, https://www.google.com/maps (09.03.2022).
• Ekmen, D. E. (2020). “A Study on Performance Evaluation of Optimization Algorithms in the Shortest Path Problem”, (Unpublished Master Thesis), Ankara Yıldırım Beyazıt University Graduate School of Natural and Applied Sciences, Ankara.
• Erol, M. H., & Bulut, F. (2017, April). “Real-Time Application of Travelling Salesman Problem Using Google Maps API”. In 2017 Electric Electronics, Computer Science, Biomedical Engineerings’ Meeting (EBBT) (pp. 1-5). IEEE.
• F.S. Hillier, & G.L. Lieberman (2001). Introduction to Operations Research, (Seventh Edition), McGraw-Hill.
• Fitro, A., P Sulistio Ilham, A., B Saeful, O., & Frendianata, I. (2018). “Shortest Path Finding in Geographical Information Systems Using Node Combination and Dijkstra Algorithm”. International Journal of Mechanical Engineering and Technology, 9(2), 755-760.
• Gencer C., & Karamanaoğlu Y. E. (2020). Şebeke Optimizasyonu. Nobel Yayınevi, Ankara.
• Hall, R. W. (1986). “The Fastest Path Through a Network with Random Time-Dependent Travel Times”. Transportation Science, 20(3), 182-188.
• Karslı, N. (2010). “Akıllı Ulaşım Sistemleri için Yapay Bağışıklık Sistemleri ve Genetik Algoritma ile Yeni Stokastik En Kısa Yol Algoritmalarının Geliştirilmesi”, (Yayınlanmamış Doktora Tezi), Atatürk Üniversitesi Fen Bilimleri Enstitüsü, Erzurum.
• Klein, C. M. (1991). “Fuzzy Shortest Paths”. Fuzzy Sets and Systems, 39(1), 27-41.
• Kosif, B., & Ekmekçi, İ. (2012). “Araç Rotalama Sistemleri ve Tasarruf Algoritması Uygulaması”. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 11(21), 41-51.
• Lu, X., & Camitz, M. (2011). “Finding the Shortest Paths by Node Combination”. Applied Mathematics and Computation, 217(13), 6401-6408.
• Mirino, A. E. (2017). “Best Routes Selection Using Dijkstra and Floyd-Warshall Algorithm”. In 2017 11th International Conference on Information & Communication Technology and System (ICTS) (pp. 155-158). IEEE.
• Ojekudo, N. A., & Akpan, N. P. (2017). “An Application of Dijkstra’s Algorithm to Shortest Route Problem”. IOSR Journal of Mathematics (IOSR-JM), 13(3), 20-32.
• Opasanon, S., & Miller-Hooks, E. (2005). “Adjustable Preference Path Strategies for Use in Multicriteria, Stochastic, and Time-Varying Transportation Networks”. Transportation Research Record, 1923(1), 137-143.
• Özdemir, S., Sacar, Ö., & Özcan, E. “Dijkstra Algoritması Kullanılarak İpek Yolu Koridorları Arasında En Kısa Ulaştırma Güzergâhının Belirlenmesi”. Demiryolu Mühendisliği, (13), 97-105.
• Öztürk, A. (2009). Yöneylem Araştırması, (12. Baskı). Ekin Basım Yayın Dağıtım, Bursa.
• Render, B., Stair Jr, R. M., Hanna, M. E. & Trevor, S. T. (2015). Quantitative Analysis for Management, 13e. Pearson Education.
• Rosita, Y. D., Rosyida, E. E., & Rudiyanto, M. A. (2019). “Implementation of Dijkstra Algorithm and Multi- Criteria Decision-Making for Optimal Route Distribution”. Procedia Computer Science, 161, 378-385.
• Shu-Xi, W. (2012). “The Improved Dijkstra’s Shortest Path Algorithm and Its Application”. Procedia Engineering, 29, 1186-1190.
• Taha, H. A. (2017). Operations Research: An Introduction. Pearson Education Limited.
• Tirastittam, P., & Waiyawuththanapoom, P. (2014). “Public Transport Planning System by Dijkstra Algorithm: Case Study Bangkok Metropolitan Area. World Academy of Science, Engineering and Technology International Journal of Social, Behavioral, Educational, Economic”, Business and Industrial Engineering, 8(1), 54-59.
• Uslu, M. F., Uslu, S., & Bulut, F. (2020). “An Adaptive Hybrid Approach: Combining Genetic Algorithm and Ant Colony Optimization for Integrated Process Planning and Scheduling”. Applied Computing and Informatics, 18 (1/2), 101-112.
• Winston, W. L., & Goldberg, J. B. (2004). Operations Research: Applications and Algorithms (Fourth Edition). Belmont: Thomson Brooks/Cole.
• Yuan, Y., & Wang, D. (2009). “Path Selection Model and Algorithm for Emergency Logistics Management”. Computers & Industrial Engineering, 56(3), 1081-1094.
• Zulfiqar, O.M., Isnanto, R.R. & Nurhayati, O.D. (2018). “Optimal Distribution Route Planning Based on Collaboration of Dijkstra and Sweep Algorithm”, 10th International Conference on Information Technology and Electrical Engineering (ICITEE) Information Technology and Electrical Engineering, Bali, Indonesia.