Coğrafi Bilgi Sistemleri Kapsamında Akıllı Ulaşım Sistemlerinde Asimetrik Gezgin Satıcı Problemine R Programlama Dili TSP, MAPSAPI ve LEAFLET Paketleri ile Çözüm Yaklaşımı

Year 2020, Volume: 3 Issue: 2, 168 - 175, 30.11.2020

Ufuk Çelik

Abstract

Gezgin satıcı problemi, kombinatoryal optimizasyon kapsamında öncelikli olarak ulaşım sektöründe sıklıkla çalışılan önemli bir araştırma alanıdır. Belirli bir liste dâhilindeki her koordinatı bir kez ziyaret edip başlangıca geri dönen en kısa turu bulmak amaçlanır. Özellikle rota planlamada görülen asimetrik gezgin satıcı problemindeki farklılık ise koordinat çiftleri arasındaki mesafenin veya yolculuk süresinin eşit olmamasıdır. Gerçek hayatta özellikle büyük şehirlerde görülen tek yönlü yollar sebebiyle iki koordinat arasındaki mesafenin gidiş ve gelişte farklı olması veya trafik sıkışıklığına bağlı olarak gidiş ve geliş arasında farklı sürelerin geçmesi maliyet ve zaman problemleri ortaya çıkarmaktadır. Bu çalışmada otomatik rota planlamasında dikkate alınması gereken asimetrik gezgin satıcı problemi için R programlama dilinde geliştirilen bazı paketler kullanılmıştır. Problem çözümü için “TSP:Travelling Salesperson Problem” paketi, coğrafi bilgi sistemlerinde başvurulan yön bulma, süre ve mesafe matrisleri oluşturmak ile koordinatları belirlemek için “mapsapi: 'sf'-Compatible Interface to 'Google Maps' APIs” Google Haritaları ara yüz paketi ve görselleştirme için ise “leaflet” paketi kullanılarak interaktif bir Google haritası oluşturulmuştur. Problemde örneklem olarak Bandırma ilçesinde rastgele 10 adet koordinat alınmıştır. Elde edilen sonuçlara göre tekrarlayan en yakın komşuluk (repetitive-nn) algoritması en kısa tur hesaplamasını gerçekleştirmiştir. Hesaplamalar tur mesafesi ve ayrıca tur süresi bazında yapılmıştır.

Keywords

coğrafi bilgi sistemleri, akıllı ulaşım sistemleri, asimetrik gezgin satıcı problemi, en yakın komşuluk algoritması, R programlama dili

References

• Ahmed, O. M. A., & Kahramanlı, H. (2018). Meta-Heuristic Solution Approaches for Traveling Salesperson Problem. International Journal of Applied Mathematics Electronics and Computers, 6(3), 21–26.
• Aksaraylı, M., & Pala, O. (2018). A Proposed Approach For Solving Asymmetric Travelling Salesman Problem by Fuzzy Ant Colony Optimization Algorithm. Journal of Transportation and Logistics, 3(1), 25–34. https://doi.org/10.26650/JTL.2018.03.01.03
• Altman, N. S. (1992). An Introduction to Kernel and Nearest-Neighbor Nonparametric Regression. The American Statistician, 46(3), 175–185.
• Basu, S., Sharma, M., & Ghosh, P. S. (2017). Efficient preprocessing methods for tabu search: an application on asymmetric travelling salesman problem. INFOR: Information Systems and Operational Research, 55(2), 134–158.
• Beardwood, J., Halton, J. H., & Hammersley, J. M. (1959). The shortest path through many points. Mathematical Proceedings of the Cambridge Philosophical Society, 55(4), 299–327.
• Biggs, N., Lloyd, E. K., & Wilson, R. J. (1986). Graph Theory, 1736-1936. Clarendon Press.
• Chalkias, C., & Lasaridi, K. (2009). A GIS based model for the optimisation of municipal solid waste collection: The case study of Nikea, Athens, Greece. WSEAS Transactions on Environment and Development, 5(10), 640–650.
• Cheng, J., Karambelkar, B., & Xie, Y. (2019). leaflet: Create Interactive Web Maps with the JavaScript “Leaflet” (R package version 2.0.3). R-CRAN. https://cran.r-project.org/package=leaflet
• Curtin, K. M., Voicu, G., Rice, M. T., & Stefanidis, A. (2014). A Comparative Analysis of Traveling Salesman Solutions from Geographic Information Systems. Transactions in GIS, 18(2), 286–301.
• Dorman, M. (2020). mapsapi: ’sf’-Compatible Interface to “Google Maps” APIs (R package version 0.4.7). https://cran.r-project.org/package=mapsapi
• Erdem, Y., & Keskintürk, T. (2011). Kangaroo Algorithm and Travelling Salesman Problem Application. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi, 10(19), 51–63.
• Ertuğrul, İ., & Özçil, A. (2016). Siyasi Parti Mitinglerinin Gezgin Satıcı Problemi Yaklaşımı ile Analizi. Siyaset, Ekonomi ve Yönetim Araştırmaları Dergisi, 4(4), 223–238.
• Hahsler, M., & Hornik, K. (2007). TSP - Infrastructure for the Traveling Salesperson Problem. Journal of Statistical Software, 23(2), 1–21.
• Ihaka, R., & Gentleman, R. (1996). R: a language for data analysis and graphics. Journal of Computational and Graphical Statistics, 5(3), 299–314.
• İlkuçar, M., & Çetinkaya, A. (2018). Mobil Telefon ve Google Harita Destekli Yerel Seyahat Rotası Optimizasyonu: Burdur Örneği. Mehmet Akif Ersoy Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 5(1), 64–74.
• Jayawant, Y. A., Joshi, N., & Vyawahare, S. (2016). Service Scheduling Using an Agent Based Model with GIS Integration. INCOSE International Symposium, 26(s1), 193–203.
• Jitt-Aer, K. (2018). The integration of Geographic Information Systems and Capacitated Vehicle Routing Problem for humanitarian logistics : a case study of preparedness for a tsunami in Phuket, Thailand. University of Portsmouth.
• Karabulut, K. (2016). An Evolutionary Strategy Algorithm fort he Asymmetric Travelling Salesman Problem / Asimetrik Gezgin Satıcı Problemi İçin Bir Evrimsel Strateji Algoritması. Celal Bayar Üniversitesi Fen Bilimleri Dergisi, 12(3), 561–568.
• Karadimas, N. V., Doukas, N., Kolokathi, M., & Defteraiou, G. (2008). Routing optimization heuristics algorithms for urban solid waste transportation management. WSEAS Transactions on Computers, 7(12), 2022–2031.
• Karadimas, N. V., Papatzelou, K., & Loumos, V. G. (2007). Optimal solid waste collection routes identified by the ant colony system algorithm. Waste Management & Research, 25(2), 139–147.
• Karp, R. M. (1972). Reducibility among Combinatorial Problems. Içinde R. E. Miller, J. W. Thatcher, & J. D. Bohlinger (Ed.), Complexity of Computer Computations (ss. 85–103). Springer US.
• Klarreich, E. (2013). Computer Scientists Find New Shortcuts for Infamous Traveling Salesman Problem. WIRED. https://www.wired.com/2013/01/traveling-salesman-problem/
• Kowalik, Ł., & Majewski, K. (2020). The Asymmetric Travelling Salesman Problem in Sparse Digraphs. 1–26.
• Lawler, E. L., Lenstra, J. K., Kan, A. H. G. R., & Shmoys, D. B. (1985). The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization (1st edition). John Wiley & Sons Ltd.
• Padberg, M., & Rinaldi, G. (1989). A Branch-and-Cut Approach to a Traveling Salesman Problem with Side Constraints. Management Science, 35(11), 1393–1412.
• Prasetyo, S. E., Utomo, A. B., & Hudallah, N. (2018). Implementation of Google Maps API 3 with Haversine Algorithm in the Development of Geographic Information System Boarding House Finder. Proceedings of the 7th Engineering International Conference on Education, Concept and Application on Green Technology, Eic 2018, 227–233.
• Reinelt, G. (1991). TSPLIB—A Traveling Salesman Problem Library. ORSA Journal on Computing, 3(4), 376–384.
• Rosenkrantz, D. J., Stearns, R. E., & Lewis, P. M. (2009). An analysis of several heuristics for the traveling salesman problem. Içinde Fundamental Problems in Computing (C. 6, Sayı 3, ss. 45–69). Springer Netherlands.
• Santoso, H., & Sanuri, R. (2019). Implementasi Algoritma Genetika dan Google Maps API Dalam Penyelesaian Traveling Salesman Problem with Time Window (TSP-TW) Pada Penjadwalan Rute Perjalanan Divisi Pemasaran STMIK El Rahma. Teknika, 8(2), 110–118.
• Urquhart, M. E., & Viera, O. (2002). A Vehicle Routing System Supporting Milk Collection. OPSEARCH, 39(1), 46–54.