A New Model for Field Studies of Geological Engineering: Travelling Salesman Problem and Application

Abstract

Travelling Salesman Problem (TSP), minimizing total travel distances during visits among predefined number of locations, plays an important role to model and solve problems in many areas, especially health, security, and logistic. Geology, hydrogeology, mining, and environmental engineers collected many samples from different fields during their research spend long times during travelling among locations. Modelling and optimizing routes constructed based on visited locations create many benefits for researchers in terms of times and costs. In this study, the route of a geology engineer that collects water samples for hydrochemical analysis from 25 different locations in Saraykent and Akdagmadeni provinces, Yozgat, Turkey, is examined and the optimum route giving the shortest distance is found by a mixed integer linear programming and the nearest neighbourhood search algorithm used for solving TSPs frequently. A-hundred and thirty-five-km difference between the calculated optimum route and the route the engineer followed at the beginning is observed. Particularly, this difference tends to increase in studies that include more visits and larger areas. Raising awareness of TSP to all researchers involved in field studies, primarily geology, hydrogeology, environment, mining engineers and demonstrating advantages of TSP based on a real-life example are targeted in this study.

Keywords

• Geological (Hydrogeological) Engineering
• Field Study
• Travelling Salesman Problem
• Mixed Integer Linear Programming
• Nearest Neighbourhood Search Algorithm

Jeoloji Mühendisliği Saha Çalışmaları için Yeni Bir Model: Gezgin Satıcı Problemi ve Uygulaması

Abstract

Bir kişinin veya aracın, belirli sayıda noktayı ziyareti sırasında geçen toplam seyahat mesafesinin en küçüklenmesini konu alan Gezgin Satıcı Problemi (GSP), uzun yıllardır başta sağlık, güvenlik ve lojistik alanlarında olmak üzere birçok alanda ortaya çıkan problemlerin modellenmesinde ve çözülmesinde önemli rol oynamıştır. Araştırmaları sırasında farklı sahalardan çok sayıda örnekler toplayan jeoloji, hidrojeoloji, maden ve çevre mühendisleri bu ziyaretleri sırasında uzun mesafeler kat etmektedir. Ziyaret edilen noktalardan oluşan rotaların GSP kapsamında modellenmesi ve optimize edilmesi, araştırmacılara zaman ve maliyet açısından önemli kazanımlar sağlayacaktır. Bu kapsamda, araştırmaları sırasında Yozgat İli Saraykent ve Akdağmadeni İlçe’lerinde yer alan 25 farklı lokasyondan hidrojeokimyasal analizler için su örnekleri toplayan bir jeoloji mühendisinin izlediği rota incelenmiş ve GSP’lerinin çözümünde sıkça kullanılan Karışık Tamsayılı Doğrusal Programlama ve En Yakın Komşu Arama Sezgiseli kullanılarak, en kısa mesafeyi veren rota belirlenmiştir. Jeoloji mühendisinin takip ettiği rota ile hesaplanan optimum rota arasında yaklaşık 135 kilometrelik fark olduğu tespit edilmiştir. Özellikle daha geniş alanlarda daha fazla nokta ziyaretini içeren çalışmalarda fark daha fazla olacaktır. Bu çalışma kapsamında özellikle saha araştırmalarıyla iç içe olan başta jeoloji, hidrojeoloji, maden ve çevre mühendisleri olmak üzere tüm araştırmacılara GSP farkındalığı kazandırmak ve incelenen örnek doğrultusunda avantajlarını göstermek hedeflenmiştir.

Keywords

• Jeoloji (Hidrojeoloji) Mühendisliği
• Saha Çalışması
• Gezgin Satıcı Problemi
• Karışık Tamsayılı Doğrusal Programlama
• En Yakın Komşu Arama Sezgiseli

References

1. Akıllı, H. ve Mutlu, H. (2018). “Polatlı ve Haymana (Ankara) sıcak sularının kökenine yönelik kimyasal ve izotopik sınırlamalar (Geochemical and isotopic constraints on the evolution of Polatlı and Haymana (Ankara) thermal waters).”, Yerbilimleri 39,1, 41-64.
2. Bazrafshan, R., Hashemkhani Zolfani, S. ve Al-e-hashem, S. M. J. (2021). “Comparison of the Sub-Tour Elimination Methods for the Asymmetric Traveling Salesman Problem Applying the SECA Method.”, Axioms, 10, 1, 19.
3. Bektaş, T. ve Elmastaş, S. (2007). “Solving school bus routing problems through integer programming.”, Journal of the Operational Research Society 58, 12, 1599-1604.
4. Celmen, O. ve Celik, M. (2009). “Hydrochemistry and environmental isotope study of the geothermal water around Beypazarı granitoids, Ankara, Turkey.”, Environmental Geology 58, 8, 1689-1701.
5. Chang, T. S. ve Yen, H. M. (2012). “City-courier routing and scheduling problems.”, European Journal of Operational Research 223, 2, 489-498.
6. Dantzig G. B. ve Ramser J. H. (1959). “The Truck Dispatching Problem”, Management Science 6, 1, 80-91.
7. Demirbilek, M. (2020). “A tactical/strategic level cost analysis based on visit time preferences for vehicle routing problem with simultaneous pickup and delivery.”, European Journal of Technique 10, 2, 301-312.
8. Demirbilek, M., Branke, J., Strauss ve A. K. (2021). “Home healthcare routing and scheduling of multiple nurses in a dynamic environment.”, Flexible Services and Manufacturing Journal 33, 1, 253-280.

9. Demirbilek, M. (2021). “A-Static-Periodic Solution Strategy for Dynamic Vehicle Routing Problem with Simultaneous Pickup and Delivery.”, Acta Infologica, 5(1).
10. Dewinter, M., Vandeviver, C., Vander Beken, T. ve Witlox, F. (2020). “Analysing the police patrol routing problem: A review.”, ISPRS International Journal of Geo-Information 9, 3, 157.
11. Elal Muş, T. ve Çetinkaya, F., (2017). “Bursa’da İçme ve Kullanma Sularında İndikatör ve Bazı Patojen Bakterilerin Varlığının Araştırılması”, Toprak Su Dergisi, 6, 1, 1-6.
12. Fikar, C. ve Hirsch, P. (2017). “Home health care routing and scheduling: A review.” Computers ve Operations Research, 77, 86-95.
13. Güneş, C. (2006). “Gediz Kaplıcaları’nın (Kütahya) Hidrojeolojik ve Hidrojeokimyasal Değerlendirilmesi.” Dokuz Eylül Üniversitesi, Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, İzmir.
14. Keskin, B. B., Li, S. R., Steil, D. ve Spiller, S., (2012). “Analysis of an integrated maximum covering and patrol routing problem.” Transportation Research Part E: Logistics and Transportation Review 48, 1, 215-232.
15. Laporte G. (2009). “Fifty years of vehicle routing”, Transportation Science 43, 4, 408–416.
16. Montané, F. A. T., & Galvão, R. D. (2006). “A tabu search algorithm for the vehicle routing problem with simultaneous pick-up and delivery service.”, Computers and Operations Research, 33(3), 595–619.
17. Özulukale, S. (2017). “Saraykent ve Akdağmadeni (Yozgat) Sıcak ve Mineralli Sularının Hidrojeokimyasal ve İzotopik İncelemesi”, Doktora Tezi, Hacettepe Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.
18. Özulukale, S. ve Şimşek, Ş. (2015). “Saraykent (Yozgat) Jeotermal Sularının Hidrojeokimyasal Değerlendirilmesi (Hydrogeochemical Assessment of Saraykent (Yozgat) Geothermal Waters)”, MÜHJEO’2015: Ulusal Mühendislik Jeolojisi Sempozyumu, 3-5 Eylül 2015, KTÜ, Trabzon, 513-520.
19. Park, J. ve Kim, B. I. (2010). “The school bus routing problem: A review.” European Journal of Operational Research 202, 2, 311-319.
20. Şener, Ş. ve Şener, E. (2021). “Şefaatli (Yozgat) Doğusu Su Kaynaklarının Hidrojeolojik ve Hidrojeokimyasal İncelemesi.” Mühendislik Bilimleri ve Tasarım Dergisi (Journal of Engineering Sciences and Design), 9(1), e-ISSN: 1308-6693, DOI: 10.21923/jesd.745641, 126 – 138.
21. Talarico, L. ve Meisel, F., Sörensen, K. (2015). “Ambulance routing for disaster response with patient groups.” Computers and Operations Research 56, 120-133.
22. Tlili, T., Harzi, M., ve Krichen, S. (2017). “Swarm-based approach for solving the ambulance routing problem.” Procedia Computer Science 112, 350-357.
23. Yurdakul, K., Alakaş, H. M., Eren, T., & Gür, Ş. (2020). Yaşlılara Evde Bakım Hizmetinde Bulunan Ekiplerin Rotalanması: Büyükşehir Belediyesinde Bir Uygulama. Niğde Ömer Halisdemir Üniversitesi Mühendislik Bilimleri Dergisi, 9(1), 206-223.