AN EFFECTIVE METAHEURISTIC FOR TOURIST TRIP PLANNING IN PUBLIC TRANSPORT NETWORKS
Krzysztof OSTROWSKI
k.ostrowski@pb.edu.plFaculty of Computer Science, Białystok University of Technology, Wiejska 45A, 15-001 Białystok (Poland)
Abstract
The Time-Dependent Orienteering Problem with Time Windows (TDOPTW) is a combinatorial optimization problem defined on graphs. Its real life applications are particularly associated with tourist trip planning in trans-port networks, where travel time between two points depends on the moment of travel start. In the paper an effective TDOPTW solution (evolutionary algorithm with local search operators) was presented and applied to gen-erate attractive tours in real public transport networks of Białystok and Athens. The method achieved very high-quality solutions in a short execution time.
Keywords:
time-dependent orienteering problem with time-windows, evolutionary algorithm, public transport network, tourist trip planningReferences
Campos, V., Marti, R., Sanchez-Oro, J., & Duarte, A. (2014). Grasp with Path Relinking for the Orienteering Problem. Journal of the Oper. Res. Society, 65(12), 1800–1813. https://doi.org/10.1057/jors.2013.156
DOI: https://doi.org/10.1057/jors.2013.156
Google Scholar
Chao, I., Golden, B., & Wasil, E. (1996). Theory and methodology - a fast and effective heuristic for the orienteering problem. European Journal of Operational Research, 88(3), 475–489. https://doi.org/10.1016/0377-2217(95)00035-6
DOI: https://doi.org/10.1016/0377-2217(95)00035-6
Google Scholar
Dean, B.C. (2004). Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, MIT Department of Computer Science.
Google Scholar
Garcia, A., Vansteenwegen, P., Arbelaitz, O., Souffriau, W., & Linaza, M. T. (2013). Integrating public transportation in personalised electronic tourist guides. Computers and Operations Research, 40(3), 758–774. https://doi.org/10.1016/j.cor.2011.03.020
DOI: https://doi.org/10.1016/j.cor.2011.03.020
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 Operation Research, 62, 36-50. https://doi.org/10.1016/j.cor.2015.03.016
DOI: https://doi.org/10.1016/j.cor.2015.03.016
Google Scholar
Gendreau, M., Laporte, G., & Semet, F. (1998). A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research, 106(2–3), 539–545. https://doi.org/10.1016/S0377-2217(97)00289-0
DOI: https://doi.org/10.1016/S0377-2217(97)00289-0
Google Scholar
Golden, B., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics, 34, 307-318. https://doi.org/10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0. CO;2-D
DOI: https://doi.org/10.1002/1520-6750(198706)34:3<307::AID-NAV3220340302>3.0.CO;2-D
Google Scholar
Gunawan, A., Yuan, Z., & Lau, H. C. (2014). A Mathematical Model and Metaheuristics for Time Dependent Orienteering Problem. In PATAT 2014: Proceedings of the 10th International Conference of the Practice and Theory of Automated Timetabling, 26–29 August 2014 (pp. 202–217). Research Collection School Of Information Systems.
Google Scholar
Mahfoud, S. W. (1992). Crowding and preselection revisited. In Proceedings of the 2nd International Conference on Parallel Problem Solving from Nature (PPSN II), Brussels, Belgium, 1992 (pp. 27–36). Amsterdam: Elsevier.
Google Scholar
Ostrowski, K. (2015). Parameters Tuning of Evolutionary Algorithm for the Orienteering Problem. Advances in Computer Science Research, 12, 53–78.
Google Scholar
Ostrowski, K., Karbowska-Chilinska, J., Koszelew, J., & Zabielski, P. (2017). Evolution-inspired local improvement algorithm solving orienteering problem. Annals of Operations Research, 253(1), 519-543. https://doi.org/10.1007/s10479-016-2278-1
DOI: https://doi.org/10.1007/s10479-016-2278-1
Google Scholar
Ostrowski, K. (2017). Evolutionary Algorithm for the Time-Dependent Orienteering Problem. In K. Saeed, W. Homenda, & R. Chaki (Eds.), Computer Information Systems and Industrial Management. CISIM 2017, Lecture Notes in Computer Science (10244, pp. 50–62). Cham: Springer. https://doi.org/10.1007/978-3-319-59105-6_5
DOI: https://doi.org/10.1007/978-3-319-59105-6_5
Google Scholar
Schilde, M., Doerner, K., Hartl, R., & Kiechle, G. (2009). Metaheuristics for the biobjective orienteering problem. Swarm Intelligence, 3(3), 179–201. https://doi.org/10.1007/s11721-009-0029-5
DOI: https://doi.org/10.1007/s11721-009-0029-5
Google Scholar
Tasgetiren, M. (2001). A genetic algorithm with an adaptive penalty function for the orienteering problem. Journal of Economic and Social Research, 4(2), 1–26.
Google Scholar
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., & Oudheusden, D.V. (2009). A guided local search metaheuristic for the team orienteering problem. European Journal of the Operational Research, 196(1), 118–127. https://doi.org/10.1016/j.ejor.2008.02.037
DOI: https://doi.org/10.1016/j.ejor.2008.02.037
Google Scholar
Verbeeck, C., Sörensen, K., Aghezzaf, E.H., & Vansteenwegen, P. (2013). A fast solution method for the time-dependent orienteering problem. European Journal of Operational Research, 236(2), 419–432. https://doi.org/10.1016/j.ejor.2013.11.038
DOI: https://doi.org/10.1016/j.ejor.2013.11.038
Google Scholar
Authors
Krzysztof OSTROWSKIk.ostrowski@pb.edu.pl
Faculty of Computer Science, Białystok University of Technology, Wiejska 45A, 15-001 Białystok Poland
Statistics
Abstract views: 117PDF downloads: 37
License
![Creative Commons License](http://i.creativecommons.org/l/by/4.0/88x31.png)
This work is licensed under a Creative Commons Attribution 4.0 International License.
All articles published in Applied Computer Science are open-access and distributed under the terms of the Creative Commons Attribution 4.0 International License.
Similar Articles
- Robert KARPIŃSKI, KNEE JOINT OSTEOARTHRITIS DIAGNOSIS BASED ON SELECTED ACOUSTIC SIGNAL DISCRIMINANTS USING MACHINE LEARNING , Applied Computer Science: Vol. 18 No. 2 (2022)
- Miguel Angel BELLO RIVERA, Carlos Alberto REYES GARCÍA, Tania Cristal TALAVERA ROJAS, Perfecto Malaquías QUINTERO FLORES, Rodolfo Eleazar PÉREZ LOAIZA, AUTOMATIC IDENTIFICATION OF DYSPHONIAS USING MACHINE LEARNING ALGORITHMS , Applied Computer Science: Vol. 19 No. 4 (2023)
- Anna MACHROWSKA, Robert KARPIŃSKI, Józef JONAK, Jakub SZABELSKI, NUMERICAL PREDICTION OF THE COMPONENT-RATIO-DEPENDENT COMPRESSIVE STRENGTH OF BONE CEMENT , Applied Computer Science: Vol. 16 No. 3 (2020)
- Anna MACHROWSKA, Robert KARPIŃSKI, Przemysław KRAKOWSKI, Józef JONAK, DIAGNOSTIC FACTORS FOR OPENED AND CLOSED KINEMATIC CHAIN OF VIBROARTHROGRAPHY SIGNALS , Applied Computer Science: Vol. 15 No. 3 (2019)
- Ferra Arik TRIDALESTARI, Hanung Nindito PRASETYO, THE EFFECT OF INFORMATION TECHNOLOGY AND ENTREPRENEURSHIP ON THE E-SERVICES QUALITY THAT HAVE AN IMPACT ON CUSTOMER VALUE: EVIDENCE FROM INDONESIA SMEs , Applied Computer Science: Vol. 19 No. 4 (2023)
- Michał TOMCZYK, Anna PLICHTA, Mariusz MIKULSKI, APPLICATION OF WAVELET – NEURAL METHOD TO DETECT BACKLASH ZONE IN ELECTROMECHANICAL SYSTEMS GENERATING NOISES , Applied Computer Science: Vol. 15 No. 4 (2019)
- Błażej CZAJKA, Patryk RÓŻYŁO, Hubert DĘBSKI, STABILITY AND FAILURE OF THIN-WALLED COMPOSITE STRUCTURES WITH A SQUARE CROSS-SECTION , Applied Computer Science: Vol. 18 No. 2 (2022)
- Dariusz Plinta, Karolina Kłaptocz, VIRTUAL REALITY IN PRODUCTION LAYOUT DESIGNING , Applied Computer Science: Vol. 17 No. 1 (2021)
- Paweł BAŁON, Edward REJMAN, Robert SMUSZ, Janusz SZOSTAK, Bartłomiej KIEŁBASA, HIGH SPEED MILLING IN THIN-WALLED AIRCRAFT STRUCTURES , Applied Computer Science: Vol. 14 No. 2 (2018)
- Mouna TARIK, Ayoub MNIAI, Khalid JEBARI, HYBRID FEATURE SELECTION AND SUPPORT VECTOR MACHINE FRAMEWORK FOR PREDICTING MAINTENANCE FAILURES , Applied Computer Science: Vol. 19 No. 2 (2023)
You may also start an advanced similarity search for this article.