AN EFFECTIVE METAHEURISTIC FOR TOURIST TRIP PLANNING IN PUBLIC TRANSPORT NETWORKS

Krzysztof  OSTROWSKI

doi:10.23743/acs-2018-09

Open full text

pdf

Published: Jun 30, 2018

DOI: https://doi.org/10.23743/acs-2018-09

Issue Vol. 14 No. 2 (2018)

Articles

AN EFFECTIVE METAHEURISTIC FOR TOURIST TRIP PLANNING IN PUBLIC TRANSPORT NETWORKS
Krzysztof OSTROWSKI

5-19
GRAPHICAL REPRESENTATIONS OF MULTITHREADED APPLICATIONS
Damian GIEBAS, Rafał WOJSZCZYK

20-37
INTERMITTENT DEMAND FORECASTING USING DATA MINING TECHNIQUES
Gamze Ogcu KAYA, Ali TURKYILMAZ

38-47
NEURAL CONTROLLER FOR THE SELECTION OF RECYCLED COMPONENTS IN POLYMER-GYPSY MORTARS
Grzegorz KŁOSOWSKI, Tomasz KLEPKA, Agnieszka NOWACKA

48-59
POSSIBILITIES OF RENOVATION FUNCTIONAL SURFACES OF EQUIPMENTS IN THE MECHANICAL ENGINEERING INDUSTRY
Janette BREZINOVÁ, Ján VIŇÁŠ, Dagmar DRAGANOVSKÁ, Anna GUZANOVÁ, Jakub BREZINA

60-68
THE INFLUENCE OF THE INJECTION TIMING ON THE PERFORMANCE OF TWO-STROKE OPPOSED-PISTON DIESEL ENGINE
Paweł KARPIŃSKI

69-81
HIGH SPEED MILLING IN THIN-WALLED AIRCRAFT STRUCTURES
Paweł BAŁON, Edward REJMAN, Robert SMUSZ, Janusz SZOSTAK, Bartłomiej KIEŁBASA

82-95
IDENTIFICATION OF THE MASS INERTIA MOMENT IN AN ELECTROMECHANICAL SYSTEM BASED ON WAVELET–NEURAL METHOD
Marcin TOMCZYK, Barbara BOROWIK, Bohdan BOROWIK

96-111

DOI

https://doi.org/10.23743/acs-2018-09

Authors

Krzysztof OSTROWSKI

k.ostrowski@pb.edu.pl

Faculty 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 planning

References

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

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

Dean, B.C. (2004). Shortest paths in FIFO time-dependent networks: theory and algorithms. Technical report, MIT Department of Computer Science.

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

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

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

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

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.

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.

Ostrowski, K. (2015). Parameters Tuning of Evolutionary Algorithm for the Orienteering Problem. Advances in Computer Science Research, 12, 53–78.

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

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

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

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.

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

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

OSTROWSKI, K. . (2018). AN EFFECTIVE METAHEURISTIC FOR TOURIST TRIP PLANNING IN PUBLIC TRANSPORT NETWORKS. Applied Computer Science, 14(2), 5–19. https://doi.org/10.23743/acs-2018-09

AN EFFECTIVE METAHEURISTIC FOR TOURIST TRIP PLANNING IN PUBLIC TRANSPORT NETWORKS

Issue Vol. 14 No. 2 (2018)

Archives

DOI

Authors

Abstract

Keywords:

References

License

Article Sidebar

Issue Vol. 14 No. 2 (2018)

Archives

Main Article Content

DOI

Authors

Abstract

Keywords:

References

Article Details

License