Abstract
We propose an effective metaheuristic for the Team Orienteering Problem with Time Windows. The metaheuristic is based on the principle of Large Neighborhood Search and can outperform the performance of algorithms available in the literature. We provide computational experiments for well known benchmark instances and are able to compute new best solutions for 17 of these instances. On average, the gap between our results and best known solutions so far is below 1%, and our solution approach yields 70% of the best known solutions available in the literature. The new results can serve as benchmarks for future computational studies.
Access provided by CONRICYT-eBooks. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Butt, S.E., Cavalier, T.M.: A heuristic for the multiple tour maximum collection problem. Computers & Operations Research 21, 101–111 (1994)
Chao, I., Golden, B., Wasil, E.: The team orienteering problem. European Journal of Operational Research 88, 475–489 (1996)
Cordeau, J.F., Gendreau, M., Laporte, G.: A tabu search heuristic for periodic and multi-depot vehicle routing problems. Networks 30, 105–119 (1997)
Gendreau, M., Laporte, G., Semet, F.: A tabu search heuristic for the undirected selective travelling salesman problem. European Journal of Operational Research 106, 539–545 (1998)
Golden, B., Levy, L., Vohra, R.: The orienteering problem. Naval Research Logistics 34, 307–18 (1987)
Gunawan, A., Lau, H.C., Lu, K.: Sails: hybrid algorithm for the team orienteering problem with time windows. In: Proceedings of the 7th Multidisciplinary International Scheduling Conference (MISTA 2015), Prague, Czech Republic, pp. 276–295 (2015)
Gunawan, A., Lau, H.C., Lu, K.: Well-tuned ils for extended team orienteering problem with time windows. LARC Technical Report Series (2015). http://centres.smu.edu.sg/larc/files/2015/09/Well-Tuned-ILS-for-Extended-Team-Orienteering-Problem-with-Time-WindowsTR-01-15.pdf
Gunawan, A., Lau, H.C., Vansteenwegen, P.: Orienteering problem: A survey of recent variants, solution approaches and applications. European Journal of Operational Research 255(2), 315–332 (2016)
Hu, Q., Lim, A.: An iterative three-component heuristic for the team orienteering problem with time windows. European Journal of Operational Research 232, 276–286 (2014)
Labadie, N., Mansini, R., Melechovsky, J., Wolfler Calvo, R.: The team orienteering problem with time windows: An lp-based granular variable neighborhood search. European Journal of Operational Research 220, 15–27 (2012)
Labadie, N., Melechovský, J., Wolfler Calvo, R.: Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics 17, 729–753 (2011)
Lin, S.W., Yu, V.F.: A simulated annealing heuristic for the team orienteering problem with time windows. European Journal of Operational Research 217, 94–107 (2012)
Mansini, R., Pelizzari, M., Wolfler Calvo, R.: A granular variable neighborhood search heuristics for the tour orienteering problem with time windows. Technical Report 2008–02-52, Dipartimento di Elettronica per l’Automazione, Università di Brescia (2008)
Montemanni, R., Gambardella, L.: Ant colony system for team orienteering problems with time windows. Foundations of Computing and Decision Sciences 34 (2009)
Pisinger, D., Ropke, S.: Large neighborhood search. In: Gendreau, M., Potvin, J.-Y. (eds.) Handbook of Metaheuristics, pp. 399–419. Springer (2010)
Righini, G., Salani, M.: Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers & Operations Research 36, 1191–1203 (2009)
Savelsbergh, M.: The vehicle routing problem with time windows: Minimizing route duration. INFORMS Journal on Computing 4, 146–154 (1992)
Schmid, V.: Hybrid metaheuristic for the team orienteering problem with time windows and service time dependent profits. Presentation at VeRoLog 2014, Oslo, Norway (2014)
Schmid, V., Gómez Rodríuez, J.S.: On solving routing problems with time windows given dynamic service times and profits. Presentation at 26th European conference on operational research, Rome, Italy (2013)
Schrimpf, G., Schneider, J., Stamm-Wilbrandt, H., Dueck, G.: Record breaking optimization results using the ruin and recreate principle. Journal of Computational Physics 159, 139–171 (2000)
Solomon, M.: Algorithms for the vehicle routing and scheduling problems with time window constraints. Operations Research 53, 254–265 (1987)
Tang, H., Miller-Hooks, H.: A tabu search heuristic for the team orienteering problem. Computers & Operations Research 32, 1379–1407 (2005)
Tricoire, F., Romauch, M., Doerner, K.F., Hartl, R.F.: Heuristics for the multi-period orienteering problem with multiple time windows. Computers & Operations Research 37, 351–367 (2010)
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: Iterated local search for the team orienteering problem with time windows. Computers & Operations Research 36, 3281–3290 (2009)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2017 Springer International Publishing AG
About this paper
Cite this paper
Schmid, V., Ehmke, J.F. (2017). An Effective Large Neighborhood Search for the Team Orienteering Problem with Time Windows. In: Bektaş, T., Coniglio, S., Martinez-Sykora, A., Voß, S. (eds) Computational Logistics. ICCL 2017. Lecture Notes in Computer Science(), vol 10572. Springer, Cham. https://doi.org/10.1007/978-3-319-68496-3_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-68496-3_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-68495-6
Online ISBN: 978-3-319-68496-3
eBook Packages: Computer ScienceComputer Science (R0)