An Algorithm for Tourist Personal Trip Planning Considering Traffic Condition and Time Windows (Case Study: City of Shiraz)

Document Type : Research Article


1 PhD student in Civil Engineering, North University, Amol, Iran

2 Assistant Professor of Materials and Industries, Noshirvani University of Technology, Babol, Iran

3 Assistant Professor of Civil Engineering, North University, Amol, Iran


Extended abstract
Nowadays, the tourism industry is one of the key components of economic and social development in the world. At the same time, with the growth of information and communication technology (ICT), based on e-tourism and smart tourism approach, launching websites and producing mobile applications that assist tourists in personal trip planning (based on personal profits and preferences, attractions’ information, and network traffic condition) have been considered for the tourism development and promotion of the competitive power of tourism destinations. In Operations Research (OR), the challenge of planning a tourist personal trip is a discrete optimization problem that is called the Orienteering Problem (OP). Researchers, by modeling and solving the various Ops, have tried to provide an optimal trip plan for the tourist to visit attractions considering various constraints.
In this descriptive-analytical and development research, the time-dependent orienteering problem with time windows (TDOPTW) was addressed. An Iterated Local Search (ILS) algorithm to solve the TDOPTW was proposed in the research. The algorithm was based on a number of specific neighborhood structures designed to locally improve the response that insertion, displacement, and replacement movements were used during the local search phase. In fact, in the study, in order to perceive the traffic conditions and delays on the travel time of the pass network, the travel time of the network arcs was considered as a discrete variable and a function of the day time.
The proposed algorithm was coded in C++ and was evaluated by performing on a realistic dataset of the city of Shiraz. The required information can be divided into three general categories: Attractions’ information (including location, opening time, closing time, visit time, and score), road network information (including link travel time between each origin-destination pair at each time slot)  and tourists consideration. The required information was collected for 38 points as POIs of Shiraz. For considering the travel time variations during the day, the time interval from 6 am to 10 pm was divided into 65 time slots with a length of 15 minutes, and at each time slot, a travel time matrix of 38 by 38 dimensions was collected by using of the online traffic map from The assumption was that the travel times were constant during each time slot.
Results and discussion
By implementing the proposed algorithm on the real data of Shiraz, the tourist trip plan was designed in less than 30 seconds. This tour was proposed that the tourist should spend around 13.9 hours and visit 12 POIs out of 38 available ones.
In order to analyze the performance of the proposed solution algorithm, different scenarios were executed on the case study. In these scenarios, changes were made to some of the input parameters of the model including opening and closing times, visit times, POI scores, the available time budget and travel times and their effect on the proposed solution was investigated. The analysis of the effect of changing the input parameters of the problem indicated that the solution algorithm was sensitive to these parameters. So that even with a minor change in one of these parameters, it redesigns and proposes the optimal solution in order to maximize the total score.
Nowadays, research in tourist trip planning concentrate on solving two main issues: a more realistic model as well as a more practical solution method. From the point of a more realistic model, this research studied the OP with Time Windows and Time Dependent travel times (TDOPTW). Moreover, the proposed solution algorithm (ILS) is able to solve the problem instances in a short computation time, while benefits from a simple and flexible structure. Therefore, in real and practical applications, by using of the proposed method for tourist personal trip enables users to find the desired route in a short amount of computation time, considering the traffic congestion in the road network as well as the service time of POIs.
Based on the results evaluation of applying the proposed method on the real data of Shiraz, the high quality of the solution and short amount of computational time were considered as the advantages of the proposed method. It should be mentioned that solving such a complex optimization problem via an exact method or mathematical programming techniques might need several hours of computations on high power computers. As a result, the proposed solution strategy can be implemented in websites or mobile Apps where tourists may use to get a personal trip plan.
According to the proposed method of the research, using websites and mobile apps that help in tourist trip planning, can be of an important role in the sustainable development of the tourism industry in our country and therefore attractive for public and private investments. This is a good suggestion especially for more touristic cities such as Shiraz, Isfahan and Yazd. In fact, this is a significant step toward the smart tourism in the country.


1)  افصح حسینی، فاطمه السادات؛ ذبیحی، حسین؛ جهانشاهلو، لعلا (1398) بررسی زیرساخت‌های گردشگری و رقابت مکانی مقصدهای گردشگری در مناطق خشک (مطالعه موردی: کویر مرنجاب)، نشریه گردشگری شهری، پاییز 1398، دوره 6، شماره 2، صص. 139-125.
2)  رزقی، مریم؛ شهابیان، پویان؛ مدیری، آتوسا؛ احمدیان، رضا (1397) ارزیابی شاخص‌های مؤثر بر ارزش ویژه برند مقصد در شهرهای تاریخی ایران از منظر گردشگران خارجی، نشریه گردشگری شهری، زمستان 1397، دوره 5، شماره 4، صص. 137-152.
3)  زیاری، کرامت­الله؛ اشنویی، امیر؛ مولایی قلیچی، محمد (1393) سنجش رضایت گردشگران از کیفیت خدمات هتلداری با استفاده از شاخص CSM (مطالعه موردی: کلان‌شهر شیراز)، نشریه گردشگری شهری، زمستان 1393، دوره 1، شماره 1، صص. 15-1.
4)  شفیعی، ساناز؛ رجب‌زاده قطری، علی؛ حسن‌زاده، علیرضا؛ جهانیان، سعید (1396) بررسی تأثیر فناوری اطلاعات بر توسعه پایدار مقاصد گردشگری به‌منظور توسعه مقاصد گردشگری هوشمند (با استفاده از رویکرد فرا ترکیب)، فصلنامه تحقیقات بازاریابی نوین، زمستان 1396، سال 7، شماره 4، شماره پیاپی (27)، صص. 116-95.
5)  کمانداری، محسن و مستوفی‌الممالکی، رضا (1395) بررسی و تحلیل فضای گردشگری شهری به‌منظور ارائه مسیرهای ویژه گردشگری (مورد شناسی: شهر کرمان)، جغرافیا و آمایش شهری – منطقه‌ای، بهار 1395، دوره 6، شماره 18، صص. 152-135.
6)  مهرگان، محمدرضا (1384) پژوهش عملیاتی: برنامه‌ریزی خطی و کاربردهای آن، ویرایش سوم، چاپ 22، تهران: نشر کتاب دانشگاهی.
7)     Abbaspour, R. A, & Samadzadegan, F. (2011) Time-dependent personal tour planning and scheduling in metropolises, Expert Systems with Applications, Vol.38, No.10, pp.12439–12452.
8)     Chao, I.-M, & Golden, B, & Wasil, E. A. (1996) The team orienteering problem, European Journal of Operational Research, Vol.88, No. 3, pp.464–474.
9)     Divsalar, A, & Vansteenwegen, P, & Cattrysse, D. (2013) A variable neighborhood search method for the orienteering problem with hotel selection, International Journal of Production Economics, Vol.145, No.1, pp.150–160.
10)  Divsalar, A, & Vansteenwegen, P, & Cattrysse, D. (2013) A variable neighborhood search method for the orienteering problem with hotel selection, International Journal of Production Economics, Vol.145, No.1, pp.150–160.
11)  Divsalar, A, & Vansteenwegen, P, & Sörensen, K, & Cattrysse, D. (2014) A memetic algorithm for the orienteering problem with hotel selection, European Journal of Operational Research, Vol.237, No.1, pp.29–49.
12)  Fomin, F. V. & Lingas, A. (2002) Approximation algorithms for time-dependent orienteering, Information Processing Letters, Vol.83, No.2, pp.57–62.
13)  Garcia, A. & Linaza, M. T. & Arbelaitz, O. & Vansteenwegen, P. (2009) Intelligent Routing System for a Personalised Electronic, the International Conference on Information and communication technologies in tourism 2009, Netherlands, pp.185–197.
14)  Garcia, A. & Vansteenwegen, P. & Arbelaitz, O. & Souffriau, W. & Linaza, M. T. (2013) Integrating public transportation in personalised electronic tourist guides, Computers and Operations Research, Vol.40, No.3, pp.758–774.
15)  Gavalas, D. & Konstantopoulos, C. & Mastakas, K. & Pantziou, G. (2014) A survey on algorithmic approaches for solving tourist trip design problems, Journal of Heuristics, Vol.20, No.3, pp.291–328.
16)  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 Operation Research, Vol.62, pp.36–50.
17)  Golden, B. L. & Levy, L. & Vohra, R. (1987) The Orienteering Problem, Naval Research Logistics, Vol.34, pp.307–318.
18)  Gunawan, A. & Lau, H. C. & Vansteenwegen, P. (2016) Orienteering Problem: A survey of recent variants, solution approaches and applications, European Journal of Operational Research, Vol.255, No.2, pp.315–332.
19)  Javaheri, H. (2011) Optimal tourism route in historical urban areas - a case study of Tehran's down town, Iran, South asian journal of tourism and heritage, Vol.4, No.1, pp.34-43.
20)  Li, J. (2011) Model and Algorithm for Time-Dependent Team Orienteering Problem. the International Conference on Advanced Research on Computer Education, Simulation and Modeling, Communications in Computer and Information Science (CESM 2011), China, Vol.175, pp.1–7.
21)  Li, J. & Wu, Q. & Li, X. & Zhu, D. (2010) Study on the Time-dependent Orienteering Problem. the 2010 International Conference on E-Product E-Service and E-Entertainment (ICEEE’2010), China, pp.1–4.
22)  Peng, G. & Dewil, R. & Verbeeck, C. & Gunawan, A. & Xing, L. & Vansteenwegen, P. (2019) Agile earth observation satellite scheduling : An orienteering problem with time-dependent profits and travel times, Computers and Operations Research, Vol.111, pp.84–98.
23)  Tsiligirides, T. (1984) Heuristic methods applied to orienteering, The Journal of the Operational Research Society, Vol.35, No.9, pp.797–809.
24)  Vansteenwegen, P. & Souffriau, W. & Oudheusden, D. Van. (2011) The orienteering problem: A survey. European Journal of Operational Research, Vol.209, No.1, pp.1–10.
25)  Verbeeck, C. & Aghezzaf, E.-H. & Vansteenwegen, P. (2014a).Solving the stochastic time-dependent orienteering problem with time windows, European Journal of Operational Research, Vol.255, No.3, pp.699–718.
26)  Verbeeck, C. & Sörensen, K. & Aghezzaf, E.-H. & Vansteenwegen, P. (2014b) A fast solution method for the time-dependent orienteering problem, European Journal of Operational Research, Vol.236, No.2, pp.419–432.
27)  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, Vol.254, pp.481–505.
28)  Yu, A. V. F. & Jewpanya, P. & Ting, C. & Redi, A. A. N. P. (2017) Two-level Particle Swarm Optimization for the Multi-Modal Team Orienteering Problem with time windows, Applied Soft Computing Journal, Vol.61, pp.1022–1040.
29)  Zenkar, B. & Ludwig, B. (2009) ROSE: Assisting Pedestrians to Find Preferred Events and Comfortable Public Transport Connections. the 6th international conference on mobile technology, application & systems (Mobility’09), France, No.16, pp.1–5.