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ı

Ufuk Çelik

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ı

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

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.

Details

Primary Language

Turkish

Subjects

Engineering

Journal Section

Research Article

Authors

Ufuk Çelik ^*
0000-0003-3063-6272
Türkiye

Publication Date

November 30, 2020

Submission Date

October 20, 2020

Acceptance Date

November 16, 2020

Published in Issue

Year 2020 Volume: 3 Number: 2

IZ

https://izlik.org/JA26SS67BC

Cite

RIS / Bibtex

APA

Çelik, U. (2020). 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ı. Akıllı Ulaşım Sistemleri Ve Uygulamaları Dergisi, 3(2), 168-175. https://izlik.org/JA26SS67BC

AMA

1.Çelik U. 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ı. Jitsa. 2020;3(2):168-175. https://izlik.org/JA26SS67BC

Chicago

Çelik, Ufuk. 2020. “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ı”. Akıllı Ulaşım Sistemleri Ve Uygulamaları Dergisi 3 (2): 168-75. https://izlik.org/JA26SS67BC.

EndNote

Çelik U (November 1, 2020) 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ı. Akıllı Ulaşım Sistemleri ve Uygulamaları Dergisi 3 2 168–175.

IEEE

[1]U. Çelik, “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ı”, Jitsa, vol. 3, no. 2, pp. 168–175, Nov. 2020, [Online]. Available: https://izlik.org/JA26SS67BC

ISNAD

Çelik, Ufuk. “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ı”. Akıllı Ulaşım Sistemleri ve Uygulamaları Dergisi 3/2 (November 1, 2020): 168-175. https://izlik.org/JA26SS67BC.

JAMA

1.Çelik U. 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ı. Jitsa. 2020;3:168–175.

MLA

Çelik, Ufuk. “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ı”. Akıllı Ulaşım Sistemleri Ve Uygulamaları Dergisi, vol. 3, no. 2, Nov. 2020, pp. 168-75, https://izlik.org/JA26SS67BC.

Vancouver

1.Ufuk Çelik. 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ı. Jitsa [Internet]. 2020 Nov. 1;3(2):168-75. Available from: https://izlik.org/JA26SS67BC