Floyd-Warshall Algorithm in Shortest Path Optimizations: Example of Logistics Centers

Year 2023, Issue: 17, 82 - 92, 31.01.2023

Bekir Keskin , Evrencan Özcan

https://doi.org/10.47072/demiryolu.1187884

Abstract

Logistics centers are important facilities which served possible transportation methods together and and carried out activities in harmony with each other such as transportation, storage, handling, distribution, consolidation, customs clearance, sorting, import, export and transit transactions, insurance and banking, infrastructure services, consultancy and production, etc. Due to the continuous demand for freight, freight transportation must be realized uninterrupted, in the shortest way, and optimal in terms of fuel consumption and transportation time. In this study, the problem of transportation of freight trains to logistics centers by the shortest route is discussed. When the literature on logistics villages is scanned; The contributions of logistics centers to the logistics sector have been examined, their strengths and weaknesses have been tried to be revealed, and studies on suggestions for effective and efficient operation have been observed. But in this study; with an engineering applications approach to the subject, it is aimed to obtain the most appropriate result for the route selection among the logistics centers by including twelve logistics centers operating throughout the country as well as seven logistics centers that are in the construction and tender stages, in the scope of the study. In generally the application area of the shortest path problems is to determine the shortest distance between the points in a network, the Floyd-Warshall Algorithm is preferred in this study in terms of determining the shortest path between any two nodes in the network. For this purpose, a graph consisting of a total of 33 nodes was created for the national railway network and the Floyd-Warshall algorithm was coded in the Python programming language to calculate the shortest route and the shortest route were determined between a total of nineteen logistics centers.

Keywords

Railway transportation, Shortest path, Logistics center, Floyd-Warshall

En Kısa Yol Optimizasyonlarında Floyd-Warshall Algoritması: Lojistik Merkezler Örneği

Abstract

Lojistik merkezler taşımacılık, depolama, elleçleme, dağıtım, gümrükleme, ayrıştırma, ithalat, ihracat ve transit işlemler, sigorta ve bankacılık, altyapı hizmetleri, danışmanlık ve üretim vb. faaliyetlerin birbiriyle uyumlu bir şekilde yürütülmesine ve olası taşıma yöntemlerinin bir arada sunulmasına hizmet eden önemli tesislerdir. Yük talebinin sürekli olması nedeniyle yük taşımacılığının da kesintisiz, en kısa yoldan, yakıt tüketimi ve taşıma süresi açısından da optimal bir şekilde gerçekleştirilmesi gerekmektedir. Bu çalışmada yük trenlerinin lojistik merkezlere en kısa yoldan ulaşması problemi ele alınmıştır. Literatürde lojistik köylerle ilgili yazın taraması yapıldığında; lojistik merkezlerin, lojistik sektörüne yapmış olduğu katkılar incelenmiş, güçlü ve zayıf yönleri ortaya konmaya çalışılmış, etkin ve verimli çalışması hakkında önerilerle ilgili çalışmalar gözlemlenmiştir. Fakat bu çalışmada; konuya mühendislik uygulamaları yaklaşımıyla, ülke genelinde faaliyet gösteren on iki lojistik merkezin yanı sıra yapım ve ihale aşamasında yer alan yedi adet lojistik merkez de çalışma kapsamına dâhil edilerek, lojistik merkezler arasında güzergâh seçimi için en uygun sonuç elde etme amacı güdülmüştür. En kısa yol problemlerinin uygulama alanı genellikle bir şebekede/ağda yer alan noktalar arasında en kısa mesafenin belirlenmesi olup, çalışmada şebekedeki herhangi iki düğüm arasındaki en kısa yolun belirlemesi açısından Floyd-Warshall Algoritması tercih edilmiştir. Bu amaçla ulusal demiryolu ağı için toplam 33 düğümden oluşan bir çizge oluşturulmuş ve en kısa yolun hesaplanması için Floyd-Warshall algoritması Python programlama dilinde kodlanarak çözülmüştür ve toplam on dokuz adet lojistik merkez arasında en kısa yol/yollar tespit edilmiştir.

Keywords

Demiryolu taşımacılığı, En kısa yol, Lojistik merkez, Floyd-Warshall

References

• [1] Ş. Demiroğlu, “Küresel lojistik köyleri ve bu kapsamda Türkiye’de lojistik köyleri üzerine bölgesel bir inceleme,” Doktora Tezi, Dumlupınar Üniversitesi Sosyal Bilimler Enstitüsü, Kütahya, 2013.
• [2] T.C. Ulaştırma Denizcilik ve Haberleşme Bakanlığı,Ulaşan ve Erişen Türkiye, Türkiye, 2017.
• [3] Y. Wang and C. Lu, “Railway route optimisation from Romania to Poland based on an analysis of China’ s ‘ one belt and one road ’ initiative,” International Journal of Internet Manufacturing and Services, vol. 6, no. 1, pp. 1–18, 2019.
• [4] S.D. Pandey, “Railway route optimization system using dijikstra method,” Int. J. Recent Innov. Trends Comput. Commun., vol. 2, no.3, pp. 435–440, 2014.
• [5] L.Liu, Y. Xia and Y. Han, “Research on three-dimensional modelling of railway route in railway route selection,” Int. Conf. Mech. Autom. Control Eng. no. 1, pp. 2907–2911, 2010.
• [6] L. Wang et al., “A two-layer optimization model for high-speed railway line planning,” J. Zhejiang Univ. Sci. A, vol. 12, no. 12, pp. 902–912, 2011.
• [7] H. Zhang et al., “A risk assessment based optimization method for route selection of hazardous liquid railway network,” Railway safety, vol. 110, pp. 217–229, 2018.
• [8] M. Kosijer et al., “Multicriteria decision-making in railway route planning and design,” Građevinar, vol. 64, pp. 195–205, 2012.
• [9] M.Y. Kankavi, “Demir ipekyolunda Türkiye geçişi için en uygun güzergâh seçimi,” Yüksek Lisans Tezi, Maltepe Üniversitesi, İstanbul, 2019.
• [10] M.R Saat and J.A. Serrano, “Multicriteria high-speed rail route selection: application to Malaysia’s high-speed rail corridor prioritization,” Transp. Plan. Technol., vol. 38, no. 2, pp. 200–213, 2015.
• [11] S. Özdemir, “Modern ipek yolu koridorlarında rota optimizasyonu için hibrit model önerisi,” Yüksek Lisans Tezi, Kırıkkale Üniversitesi, Kırıkkale, 2021.
• [12] T.S. Dermawan, “Comparison of dijkstra dan floyd-warshall algorithm to determine the best route of train,” IJID (International Journal on Informatics for Development), vol. 7, no. 2, pp.54-58, 2019.
• [13] S. Özdemir, Ö. Sacar and E. Özcan, “Dijkstra algoritması kullanılarak ipek yolu koridorları arasında en kısa ulaştırma güzergâhının belirlenmesi” Demiryolu Mühendisliği, vol. 13, pp. 97-105, 2021.
• [14] A. Pradhan and G. Mahinthakumar, “Finding all-pairs shortest path for a large-scale transportation network using parallel Floyd-Warshall and parallel Dijkstra algorithms,” Journal of computing in civil engineering, vol. 27, no. 3, pp. 263-273, 2013.
• [15] M. Hamurcu and T. Eren, “An Application of multicriteria decision-making for the evaluation of alternative monorail routes,” Mathematics, vol. 7 no.1, pp. 16, 2019.
• [16] J. Hanzl et al., “Application of floyd's algorithm on transport network of south bohemian region,” Komunikacie: Communications (Scientific Letters of the University of Žilina), vol. 18, no. 2, 2016.
• [17] Z. Yanwei et al., “Optimal coordination path selecting method for conduction transformation based on floyd algorithm,” Procedia Computer Science, vol.162, pp.227-234, 2019.
• [18] D. Pandika, B. Irawan and C. Setianingsih, “Application of optimization heavy traffic path with floyd-warshall algorithm,” In 2018 International Conference on Control, Electronics, Renewable Energy and Communications (ICCEREC), pp. 57-62, 2018.
• [19] A.S. Risald, "Best routes selection using dijkstra and floyd-warshall algorithm," 11th International Conference on Information & Communication Technology and System (ICTS), Indonesia, 2017.
• [20] Y.S. Triana and I. Syahputri, “Implementation floyd-warshall algorithm for the shortest path of garage,” International Journal of Innovative Science and Research Technology, vol.3, no. 2, 871-878, 2018.
• [21] K. Tang, C. Pan and M. Qian, “Manufacturing/remanufacturing logistics network optimization based on floyd algorithm,” In Journal Of Physics: Conference Series, 2019.
• [22] T. Danışan, E.Özcan and T. Eren, “Bakım ekiplerinin en kısa yoldan santrallara ulaşımı: hidroelektrik santral örneği,” Journal of Turkish Operations Management,. pp. 576-587, 2021.
• [23] Z. Ramadhan, A.P.U. Siahaan and M. Mesran, “Prim and floyd-warshall comparative algorithms in shortest path problem,” In Proceedings Of The Joint Workshop Ko2pi And The 1st International Conference On Advance & Scientific Innovation, pp. 47-58, 2018.
• [24] M.E. Çakır et al., "Katı atıklar için optimum güzergâh tespiti ve alansal dağılım haritalarının cbs ortamında oluşturulması: Suruç (Şanlıurfa) örneği," BEÜ Fen Bilimleri Dergisi BEU Journal of Science, vol. 8, no. 2, pp. 595-603, 2019.
• [25] K. Sungkwan et al., "Optimal path planning of automated guided vehicle using dijkstra algorithm under dynamic conditions," 1th International Conference on Robot Intelligence Technology and Applications (RiTA) Robot Intelligence Technology and Applications Robot Intelligence Technology and Applications, Daejeon, Korea, 2019.
• [26] E .D. Ekmen, “A Study on performance evaluation of optimization algorithms in the shortest path problem,” Yüksek Lisans Tezi, Yıldırım Beyazıt Üniversitesi, Ankara, 2020.
• [27] K. Magzhan and H. Jani, “A review and evaluations of shortest path algorithms,” Int. J. Sci. Technol. Res., vol. 2, no. 6, pp. 99–104, 2013.
• [28] A. A. Tamimi, “Comparison studies for different shortest path algorithms,” Int. J. Comput. Technol., vol. 14, no. 8, pp. 5979–5986, 2015.
• [29] B. Golden, “Shortest-path algorithms: a comparison,” Operations Research, vol. 24, no. 6, 1976.
• [30] M. Alkan and M. Aydin, “Simulation and comparison of pathfinding algorithms using real Turkey data.” Int. Conf. Artif. Intell. Data Process, 2019.
• [31] M. A. Djojo and A. Karyono, “Computational load analysis of dijkstra, A*, and floyd-warshall algorithms in mesh network,” Proc. 2013 Int. Conf. Robot. Biomimetics, Intell. Comput. Syst, 2013.
• [32] X. Z. Wang, “The comparison of three algorithms in shortest path issue,” J. Phys. Conf. Ser., vol. 1087, no. 2, 2018.
• [33] Ö. N. Çam and H. K. Sezen, “Toplam bekleme süresini enküçükleme amaçlı bir araç rotalama problemi,” International Journal of Social Inquiry, vol. 11, no. 2, pp. 47–60, 2018.
• [34] M. Timör, “Medyan en kısa yol problemi: maliyet erişilebilirlik hedeflerine yönelik bir çok amaçlı taşımacılık problemi uygulaması,” İstanbul Üniversitesi İşletme Fakültesi Dergisi, Cilt: 34, no: 2, pp. 31–56, 2005.
• [35] E. Fendoğlu and H. Söyler, “Route optimization of Malatya metropolitan municipality pesticide vehicles,” Alphanumeric J., vol. 6, no. 1, 2017.
• [36] F. Nuriyeva and G. Kizilates, “Gezgin satıcı problemi için merkezden kenarlara hipersezgisel yöntem,” Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, vol. 20, no. 2, pp. 319–323, 2016.
• [37] Ö. Saçar. “İpek yolu güzergahında yapılan lojistik etkinliklerin günümüz lojistik faaliyetleri ile Karşilaştirilmasi,” Yüksek Lisans Tezi, Balıkesir Üniversitesi, 2018.
• [38] S. Özdemir et al., “Türkiye’deki lojistik merkezleri yatirim önceliklerinin değerlendirilmesinde çok kriterli karar modeli önerisi,” Demiryolu Mühendisliği Dergisi, no. 12, pp. 83–94, 2020.
• [39] E.R. Zieyel, “Operations research: applications and algorithms.” Technometrics, vol. 30, no. 3, pp. 361–362, 1988.
• [40] TCDD “2016-2020 İstatistik Yıllığı” pp.18-19, 2021. [Online]. Available: ttps://static.tcdd.gov.tr/ webfiles/userfiles/files/istrapor/20162020ist.pdf [Accessed Oct 21, 2022].
• [41] Rome2Rio, "Railway Map", [Online]. Available:https://www.rome2rio.com/map/. [Accessed Sep 13, 2022].
• [42] Türkiye Cumhuriyeti Strateji ve Bütçe Başkanlığı. (2019). “On Birinci Kalkınma Planı (2019-2023)”.Available:https://www.sbb.gov.tr/wp-content/uploads/2019/07/OnbirinciKalkinmaPlani.pdf [Accessed Sep 21, 2021].