The Orienteering Problem with Time Windows for Optimizing Trabzon City’s Tourism Route
Betül Kara, Ezgi Öztürk, Minel Canbaz, Ertuğrul AyyıldızThis 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.
Trabzon Şehri Turizm Rotası Optimizasyonu için Zaman Pencereli Oryantiring Problemi
Betül Kara, Ezgi Öztürk, Minel Canbaz, Ertuğrul AyyıldızBu ç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.
This study addresses an optimization problem known as the orienteering problem (OP). In orienteering sports, participants use maps and compasses to locate checkpoints in remote areas outside the city as quickly as possible. Each checkpoint has a specific score, and competitors aim to achieve the highest score. The OP is an optimization problem where the objective is to maximize the obtained score without having to visit every node. Such problems have various real-life applications in different areas, such as personnel routing, disaster management, and tourism. This research focuses on orienteering problem with time windows (OPTW) for optimizing tourism routes in Trabzon city by considering the increased interest in the Black Sea region. OPTW aims to design a mathematical model that allows tourists to start from a predetermined point and visit subsequent locations, maximizing their benefit while finishing the tour at a different endpoint. The study explores an efficient travel route for both domestic and foreign tourists to achieve maximum utility in a minimum amount of time. Trabzon city has been chosen for tourism route optimization due to its popularity in the Black Sea region. The starting point has been set as a hotel, and the endpoint is the airport, with the assumption being that the route will be completed within a single day. A time window has been integrated into the model for each node to represent the most feasible visiting time. The OPTW formulation ensures that tourists obtain the highest benefit and utility by visiting sequential locations starting from the designated initial point and ending the tour at a different location. Multicriteria decision making (MCDM) methods, including the analytic hierarchy process (AHP) and technique for order preference by similarity to an ideal solution (TOPSIS), are employed to determine the benefit scores for visiting each location. The solution utilizes the CPLEX program to construct a mixed integer mathematical model that yields a route including four mandatory nodes out of the 19 designated locations in Trabzon city.
Nowadays, Trabzon is one of the most important stopping points where local and foreign guests leave feeling satisfied. With its popular attractions, natural beauties that are still preserved, and hospitality of the Black Sea people, the number of tourists who consider Trabzon a stopover point increases constantly. The solution to the OP is obtained by coding the mixed integer mathematical model in the program CPLEX. In addition to the start node (i.e., hotel) and the end node (i.e., the airport), the model has 17 visitation point nodes. According to the optimal route plan, visiting 10 of the 19 nodes within the tour provides the greatest benefit. Of these 10 points, four (Nodes 2,4,9, and 18) are mandatory visitation points. As a result of the constraints that were created, Node 4 was determined as the second stopover point where individuals can have breakfast after the hotel. In addition, Node 18 must be visited before the airport, and this is stated in the constraints. The generated route complies with the given time windows and involves visiting 8 nodes after departing from the hotel and before concluding with the airport. The objective function has been formed by adding up the scores of the visited locations. Moreover, the locations visited during the route are illustrated on the map. This study represents a significant step in determining the most effective and efficient tourist route in Trabzon city by considering the time constraints and benefit scores during tourism route planning.
The problem addressed in this study can be diversified and adapted to different cities; the number of visitation points can be increased or reduced, or even evaluated using different utility scores based on different criteria in order to create an OP with a different structure. A tour can be planned by choosing different starting and ending nodes instead of the hotel and airport requirements specified in the constraints. Alternatively, the structure of the OP can also be created so that it allows sub-tours. The target audience of the tour can be divided into groups based on such factors as age, gender, and trip preference, and different tours can be obtained among the same visitation points using specific constraints. While the objective in the current OP is to find the maximum utility score, the overall distance traveled can also be minimized with the help of goal programming alongside the maximum utility score.
