The Orienteering Problem with Time Windows for Optimizing Trabzon City’s Tourism Route

Year 2023, , 285 - 302, 18.01.2024

Betül Kara , Ezgi Öztürk , Minel Canbaz , Ertuğrul Ayyıldız

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

Abstract

This study focuses on the optimization problem known as the orienteering problem (OP). Orienteering is a sport in which participants use a map and compass to find checkpoints in a remote urban terrain as fast as possible. OP is defined as a problem that tries to maximize the score obtained without having to visit each node. This problem has many applications in real life, such as personnel routing and disaster relief routing, and is also used in different provinces for tourism applications. When considering the increasing interest in the Black Sea region, this study considers optimizing the tourism routes in Trabzon city a suitable topic. The study considers the orienteering problem with time windows (OPTW) for creating a tourism route that provides the highest utility and benefit regarding the city of Trabzon within the specified time interval by starting from the designated starting point and stopping at the subsequent locations, thus aiming to end the tour at some other point. This study utilizes the analytical hierarchy process (AHP) and the technique for order preference by similarity to an ideal solution (TOPSIS), which are widely used multi-criteria decision-making (MCDM) methods, to determine the benefit scores of the visitation points. In addition, the optimal time interval for each node to be visited is integrated into the model as a time window. A mixed integer mathematical model was created for solving the tourism route in the problem using CPLEX software. This study provides an important step in allowing tourists to create the most efficient and enjoyable tourism route by considering the touristic points and other locations that can be visited in Trabzon city over the most appropriate time intervals.

Keywords

orienteering problem, time windows, Trabzon, Tourism, multi-criteria decision making

Project Number

FLÖ-2023-10653

Trabzon Şehri Turizm Rotası Optimizasyonu için Zaman Pencereli Oryantiring Problemi

Abstract

Bu çalışma, Oryantiring Problemi (OP) olarak adlandırılan bir optimizasyon problemine odaklanmaktadır. Oryantiring, katılımcıların harita ve pusula kullanarak şehirden uzak bir arazide kontrol noktalarını en hızlı şekilde bulmaya çalıştığı bir spordur. OP, her düğüme uğrama zorunluluğu olmaksızın elde edilen skoru en büyüklemeye çalışan bir problem olarak tanımlanmaktadır. Bu problemin gerçek hayatta personel yönlendirme ve afet yardımı yönlendirme gibi birçok uygulaması bulunmaktadır ve turizm uygulamalarında da farklı iller için kullanılmaktadır. Bu çalışma, Karadeniz bölgesine olan artan ilgi göz önünde bulundurularak Trabzon şehrindeki turizm rotası optimizasyonu için uygun görülmüştür. Trabzon şehri için belirlenen zaman aralığında, turistlerin belirlenmiş başlangıç noktasından başlayarak sıradaki konumlara uğramasıyla en yüksek karı/faydayı sağlayan bir turizm rotası oluşturma problemi Zaman Pencereli Oryantiring Problemi (ZP-OP) olarak ele alınmıştır. Bu şekilde, turun başka bir noktada sonuçlanması hedeflenmiştir. Bu çalışmada, ziyaret noktalarının fayda puanları (skorları) belirlenirken, yaygın kullanılan Çok Kriterli Karar Verme (ÇKKV) yöntemlerinden olan Analitik Hiyerarşi Prosesi (AHP) ve Technique For Order Preference By Similarity To An Ideal Solution (TOPSIS) yöntemlerinden faydalanılmıştır. Ayrıca, her bir düğüm noktası için ziyaret edilebileceği en uygun zaman aralığı modele zaman penceresi olarak entegre edilmiştir. Problemdeki turizm rotasının çözümü için Karışık Tamsayılı Matematiksel Model oluşturulmuş ve CPLEX programı kullanılarak çözümlenmiştir. Bu çalışma, Trabzon şehrinde bulunan turistik noktaların ve ziyaret edilebilecek diğer konumların en uygun zaman aralıklarında dikkate alınarak turistlerin en verimli ve keyifli turizm rotası oluşturması için önemli bir adım sağlamaktadır.

Keywords

Oryantiring Problemi, Zaman penceresi, Trabzon, Turizm, ÇKKV

Supporting Institution

Karadeniz Teknik Üniversitesi

Project Number

FLÖ-2023-10653

Thanks

Bu çalışma Karadeniz Teknik Üniversitesi Bilimsel Araştırma Projeleri Koordinasyon Birimi tarafından desteklenmektedir. Proje Numarası: FLÖ-2023-10653

References

• Ayyildiz, E., & Taskin, A. (2022). Humanitarian relief supply chain performance evaluation by a SCOR based Trapezoidal type-2 fuzzy multi-criteria decision making methodology: An application to Turkey. Scientia Iranica, 29(4), 2069-2083. https://doi.org/10.24200/sci.2020.52592.2786 google scholar
• Bayliss, C., Juan, A. A., Currie, C. S. M., & Panadero, J. (2020). A learnheuristic approach for the team orienteering problem with aerial drone motion constraints. Applied Soft Computing Journal, 92. https://doi.org/10.1016/j.asoc.2020.106280 google scholar
• Bertolini, M., Esposito, G., & Romagnoli, G. (2020). A TOPSIS-based approach for the best match between manufacturing technologies and product specifications. Expert Systems with Applications, 159, 113610. https://doi.org/10.1016/J.ESWA.2020.113610 google scholar
• Bianchessi, N., Mansini, R., & Speranza, M. G. (2018). A branch-and-cut algorithm for the Team Orienteering Problem. International Transactions in Operational Research, 25(2). https://doi.org/10.1111/itor.12422 google scholar
• Biscaia, R. V. B., Braghini Junior, A., & Colmenero, J. C. (2021). Selection of projects for automotive assembly structures using a hybrid method composed of the group-input compatible, best-worst method for criteria weighting and TrBF-TOPSIS. Expert Systems with Applications, 184, 115557. https://doi.org/10.1016/J.ESWA.2021.115557 google scholar
• Campbell, A. M., Gendreau, M., & Thomas, B. W. (2011). The orienteering problem with stochastic travel and service times. Annals of Operations Research, 186(1). https://doi.org/10.1007/s10479-011-0895-2 google scholar
• Chao, I. M., Golden, B. L., & Wasil, E. A. (1996). The team orienteering problem. European Journal of Operational Research, 88(3), 464-474. https://doi.org/10.1016/0377-2217(94)00289-4 google scholar
• Choachaicharoenkul, S., Coit, D., & Wattanapongsakorn, N. (2022). Multi-Objective Trip Planning With Solution Ranking Based on User Preference and Restaurant Selection. IEEE Access, 10. https://doi.org/10.1109/ACCESS.2022.3144855 google scholar
• Chou, X., Gambardella, L. M., & Montemanni, R. (2018). Monte Carlo Sampling for the Probabilistic Orienteering Problem. Içinde AIRO Springer Series (C. 1). https://doi.org/10.1007/978-3-030-00473-6_19 google scholar
• Çolak, S. (2010). Genetik Algoritmalar Yardımı İle Gezgin Satıcı Probleminin Çözümü Üzerine Bir Uygulama. Ç.Ü. Sosyal Bilimler Enstitüsü Dergisi, 19(3). google scholar
• Demange, M., Ellison, D., & Jouve, B. (2021). Orienteering problem with time-windows and updating delay. Theoretical Computer Science, 863. https://doi.org/10.1016/j.tcs.2021.01.003 google scholar
• Deveci Kocakoç, İ., & Pulat, M. (2019). Gezgin Satıcı Probleminin Genetik Algoritmalar Kullanarak Çözümünde Çaprazlama Operatörlerinin Örnek Olaylar Bazlı İncelenmesi. Dokuz Eylul Üniversitesi iktisadi ve Idari Bilimler Dergisi, 34(2). https://doi.org/10.24988/ye.2019342825 google scholar
• Dündar, A. O., & Öztürk, R. (2020). Kargo dağıtım operasyonunun gezgin satıcı problemi ve çoklu gezgin satıcı problemi kullanılarak yeniden düzenlenmesi üzerine bir uygulama. Erciyes Üniversitesi Sosyal Bilimler Enstitüsü Dergisi, (49), 41-54. google scholar
• Elibal, K., & Özceylan, E. (2022). Comparing industry 4.0 maturity models in the perspective of TQM principles using Fuzzy MCDM methods. Technological Forecasting and Social Change, 175, 121379. https://doi.org/10.1016/J.TECHFORE.2021.121379 google scholar
• Gavalas, D., Konstantopoulos, C., Mastakas, K., & Pantziou, G. (2014). A survey on algorithmic approaches for solving tourist trip design problems. Journal of Heuristics, 20(3), 291-328. https://doi.org/10.1007/s10732-014-9242-5 google scholar
• Gavalas, D., Konstantopoulos, C., Mastakas, K., Pantziou, G., & Vathis, N. (2015). Heuristics for the time dependent team orienteering problem: Application to tourist route planning. Computers and Operations Research, 62, 36-50. https://doi.org/10.1016/j.cor.2015.03.016 google scholar
• Gunawan, A., Lau, H. C., & Lu, K. (2018). ADOPT: Combining parameter tuning and Adaptive Operator Ordering for solving a class of Orienteering Problems. Computers and Industrial Engineering, 121. https://doi.org/10.1016/j.cie.2018.05.016 google scholar
• Gunawan, A., Lau, H. C., & Vansteenwegen, P. (2016). Orienteering Problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research, 255(2), 315-332. https://doi.org/10.1016/j.ejor.2016.04.059 google scholar
• Hashim, Z., Ismail, W. R., & Ahmad, N. (2013). Determination of optimal self-drive tourism route using the orienteering problem method. AIP Conference Proceedings, 1522. https://doi.org/10.1063/1.4801296 google scholar
• Hezer, S., Gelmez, E., & Özceylan, E. (2021). Comparative analysis of TOPSIS, VIKOR and COPRAS methods for the COVID-19 Regional Safety Assessment. Journal of Infection and Public Health, 14(6), 775-786. https://doi.org/10.1016/J.JIPH.2021.03.003 google scholar
• Hwang, C.-L., & Yoon, K. (1981). Methods for Multiple Attribute Decision Making. https://doi.org/10.1007/978-3-642-48318-9_3 google scholar
• Kadar, A., Shahjalal, M., Faisal, M., & Iqbal, M. (2011). Solving the Vehicle Routing Problem using Genetic Algorithm. International Journal of Advanced Computer Science and Applications, 2(7). https://doi.org/10.14569/yacsa.2011.020719 google scholar
• Karabulut, K., & Tasgetiren, M. F. (2020). An evolution strategy approach to the team orienteering problem with time windows. Computers and Industrial Engineering, 139(October 2019), 106109. https://doi.org/10.1016/j.cie.2019.106109 google scholar
• Ke, L., Archetti, C., & Feng, Z. (2008). Ants can solve the team orienteering problem. Computers & Industrial Engineering, 54(3), 648-665. https://doi.org/10.1016/J.CIE.2007.10.001 google scholar
• Khodadadian, M., Divsalar, A., Verbeeck, C., Gunawan, A., & Vansteenwegen, P. (2022). Time dependent orienteering problem with time windows and service time dependent profits. Computers and Operations Research, 143. https://doi.org/10.1016/j.cor.2022.105794 google scholar
• Kolaee, M. H., Mirzapour Al-e-Hashem, S. M. J., & Jabbarzadeh, A. (2023). A local search-based non-dominated sorting genetic algorithm for solving a multi-objective medical tourism trip design problem considering the attractiveness of trips. Engineering Applications of Artificial Intelligence, 124. https://doi.org/10.1016/j.engappai.2023.106630 google scholar
• Laporte, G. (1992). The vehicle routing problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59(3). https://doi.org/10.1016/0377-2217(92)90192-C google scholar
• Laporte, G., & Martello, S. (1990). The selective travelling salesman problem. Discrete Applied Mathematics, 26(2-3), 193-207. https://doi.org/10.1016/0166-218X(90)90100-Q google scholar
• Li, Z., & Hu, X. (2011). The orienteering problem with compulsory nodes and time window. 8th International Conference on Service Systems and Service Management - Proceedings of ICSSSM’11. https://doi.org/10.1109/ICSSSM.2011.5959526 google scholar
• Lin, S. W., & Yu, V. F. (2017). Solving the team orienteering problem with time windows and mandatory visits by multi-start simulated annealing. Computers and Industrial Engineering, 114(October), 195-205. https://doi.org/10.1016/j.cie.2017.10.020 google scholar
• Mann, M., Zion, B., Rubinstein, D., Linker, R., & Shmulevich, I. (2016). The Orienteering Problem with Time Windows Applied to Robotic Melon Harvesting. Journal of Optimization Theory and Applications, 168(1). https://doi.org/10.1007/s10957-015-0767-z google scholar
• Moosavi Heris, F. S., Ghannadpour, S. F., Bagheri, M., & Zandieh, F. (2022). A new accessibility based team orienteering approach for urban tourism routes optimization (A Real Life Case). Computers and Operations Research, 138. https://doi.org/10.1016/j.cor.2021.105620 google scholar
• Mufliq, A., & Utamima, A. (2023). Genetic Algorithm and Local Search for Optimization of Tourism Trips as an Orienteering Problem. ISDFS 2023 - 11th International Symposium on Digital Forensics and Security. https://doi.org/10.1109/ISDFS58141.2023.10131734 google scholar
• Nuraiman, D., & Ozlen, M. (2022). A decomposition approach for the prioritised home health care problem with synchronised visits and multi-period planning. Computers and Industrial Engineering, 174. https://doi.org/10.1016/j.cie.2022.108722 google scholar
• Ömürbek, N. (2014). Analitik Hiyerarşi Süreci ve Analitik Ağ Süreci Yöntemleri ile Online Alışveriş Site Seçimi. Journal of Management and Economics Research, (22), 306-306. https://doi.org/10.11611/jmer214 google scholar
• Paulavicius, R., Stripinis, L., Sutaviciute, S., Kocegarov, D., & Filatovas, E. (2023). A novel greedy genetic algorithm-based personalized travel recommendation system. Expert Systems with Applications, 230. https://doi.org/10.1016/j.eswa.2023.120580 google scholar
• Saaty, T. L. (1977). A scaling method for priorities in hierarchical structures. Journal of Mathematical Psychology, 15(3), 234-281. https://doi.org/10.1016/0022-2496(77)90033-5 google scholar
• Sohrabi, S., Ziarati, K., & Keshtkaran, M. (2020). A Greedy Randomized Adaptive Search Procedure for the Orienteering Problem with Hotel Selection. European Journal of Operational Research, 283(2), 426-440. https://doi.org/10.1016/j.ejor.2019.11.010 google scholar
• Su, X., & Nan, H. (2023). An enhanced heuristic for the team orienteering problem with time windows considering multiple deliverymen. Soft Computing, 27(6). https://doi.org/10.1007/s00500-022-07577-9 google scholar
• Tenemaza, M., Lujan-Mora, S., De Antonio, A., & Ramirez, J. (2020). Improving itinerary recommendations for tourists through metaheuristic algorithms: An optimization proposal. IEEE Access, 8. https://doi.org/10.1109/ACCESS.2020.2990348 google scholar
• URL-1. (2022). Trabzon’a turizmin o dalında da ilgi var! 117 ülkeden turist geldi - Haber61. Tarihinde 20 Temmuz 2023, adresinden erişildi https://www.haber61.net/trabzon-haber/trabzona-turizmin-o-dalinda-da-ilgi-var-117-ulkeden-turist-geldi-h463232.html google scholar
• Vansteenwegen, P., Souffriau, W., & Oudheusden, D. Van. (2011). The orienteering problem: A survey. European Journal of Operational Research, 209(1), 1-10. https://doi.Org/10.1016/j.ejor.2010.03.045 google scholar
• Verbeeck, C., Vansteenwegen, P., & Aghezzaf, E. H. (2017). The time-dependent orienteering problem with time windows: a fast ant colony system. Annals of Operations Research, 254(1-2), 481-505. https://doi.org/10.1007/s10479-017-2409-3 google scholar
• Vu, D. M., Kergosien, Y., Mendoza, J. E., & Desport, P. (2022). Branch-and-check approaches for the tourist trip design problem with rich constraints. Computers and Operations Research, 138. https://doi.org/10.1016/j.cor.2021.105566 google scholar
• Wang, Y. W., Lin, C. C., & Lee, T. J. (2018). Electric vehicle tour planning. Transportation Research Part D: Transport and Environment, 63. https://doi.org/10.1016/j.trd.2018.04.016 google scholar
• Westerlund, A., Göthe-Lundgren, M., & Larsson, T. (2006). A stabilized column generation scheme for the traveling salesman subtour problem. Discrete Applied Mathematics, 154(15), 2212-2238. https://doi.org/10.1016/j.dam.2005.04.012 google scholar
• Wibowo, B. S., & Handayani, M. (2019). A Genetic Algorithm for Generating Travel Itinerary Recommendation with Restaurant Selection. IEEE International Conference on Industrial Engineering and Engineering Management, 2019-Decem. https://doi.org/10.1109/IEEM.2018.8607677 google scholar
• Yadav, N., & Tanksale, A. (2022). An integrated routing and scheduling problem for home healthcare delivery with limited person-to-person contact. European Journal of Operational Research, 303(3). https://doi.org/10.1016/j.ejor.2022.03.022 google scholar
• Yildiz, A., Guneri, A. F., Ozkan, C., Ayyildiz, E., & Taskin, A. (2022). An integrated interval-valued intuitionistic fuzzy AHP-TOPSIS methodology to determine the safest route for cash in transit operations: a real case in Istanbul. Neural Computing and Applications, 34(18), 15673-15688. https://doi.org/10.1007/s00521-022-07236-y google scholar
• Yorulmaz, Ö., Yıldırım, S. K., & Yıldırım, B. F. (2021). Robust Mahalanobis Distance based TOPSIS to Evaluate the Eco-nomic Development of Provinces. Operational Research in Engineering Sciences: Theory and Applications, 4(2), 102-123. https://doi.org/10.31181/ORESTA20402102Y google scholar