Abstract
The last decade a large number of applications in logistics, tourism and other fields have been studied and modeled as Orienteering Problems (OPs). In the orienteering problem, a standard amount of nodes are given, each with a specific score. The goal is to determine a path, limited in length, from the start point to the end point through a subset of locations in order to maximize the total path score. In this paper, we present a new hybrid evolutionary algorithm for the solution of the Orienteering Problem. The algorithm combines a Greedy Randomized Adaptive Search Procedure (GRASP), an Evolutionary Algorithm and two local search procedures. The algorithm was tested in a number of benchmark instances from the literature and in most of them the best known solutions were found.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Chao, I.: Algorithms and solutions to multi-level vehicle routing problems. Ph.D. Dissertation, Applied Mathematics Program, University of Maryland, College Park, USA (1993)
Chao, I.M., Golden, B.L., Wasil, E.: A fast and effective heuristic for the Orienteering Problem. European Journal of Operational Research 88, 475–489 (1996)
Chao, I.M., Golden, B.L., Wasil, E.: The team orienteering problem. European Journal of Operational Research 88, 464–474 (1996)
Feo, T.A., Resende, M.G.C.: Greedy randomized adaptive search procedure. Journal of Global Optimization 6, 109–133 (1995)
Golden, B., Levy, L., Vohra, R.: The orienteering problem. Naval Research Logistics 34, 307–318 (1987)
Keller, C.P.: Algorithms to solve the orienteering problem: A comparison. European Journal of Operational Research 41, 224–231 (1989)
Montemanni, R., Gambardella, L.: Ant colony system for team orienteering problems with time windows. Foundations of Computing and Decision Sciences 34(4), 287–306 (2009)
Moscato, P., Cotta, C.: A gentle introduction to memetic algorithms. In: Glover, F., Kochenberger, G.A. (eds.) Handbooks of Metaheuristics, pp. 105–144. Kluwer Academic Publishers, Dordrecht (2003)
Righini, G., Salani, M.: Decremental state space relaxation strategies and initialization heuristics for solving the orienteering problem with time windows with dynamic programming. Computers and Operations Research 4, 1191–1203 (2009)
Sevkli, Z., Sevilgen, F.E.: Discrete particle swarm optimization for the orienteering problem. In: 2010 IEEE Congress on Evolutionary Computation (CEC), Barcelona, Spain (2010), doi:10.1109/CEC.2010.5586532
Souffriau, W., Vansteenwegen, P., Vertommen, J., Vanden Berghe, G., Van Oudheusden, D.: A personalized tourist trip design algorithm for mobile tourist guides. Applied Artificial Intelligence 22(10), 964–985 (2008)
Tang, H., Miller-Hooks, E.: A TABU search heuristic for the team orienteering problem. Computer and Industrial Engineering 32, 1379–1407 (2005)
Tsiligirides, T.: Heuristic methods applied to orienteering. Journal of Operational Research Society 35, 797–809 (1984)
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: Metaheuristics for tourist trip planning. In: Geiger, M., Habenicht, W., Sevaux, M., Sorensen, K. (eds.) Metaheuristics in the Service Industry. Lecture Notes in Economics and Mathematical Systems, vol. 624, pp. 15–31 (2009)
Vansteenwegen, P., Souffriau, W., Vanden Berghe, G., Van Oudheusden, D.: A guided local search metaheuristic for the team orienteering problem. European Journal of Operational Research 196, 118–127 (2009)
Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The orienteering problem: A survey. European Journal of Operational Research 209, 1–10 (2011)
Yu, V.F., Lin, S.W., Chou, S.Y.: The museum visitor routing problem. Applied Mathematics and Computation 216, 719–729 (2010)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Marinakis, Y., Politis, M., Marinaki, M., Matsatsinis, N. (2015). A Memetic-GRASP Algorithm for the Solution of the Orienteering Problem. In: Le Thi, H., Pham Dinh, T., Nguyen, N. (eds) Modelling, Computation and Optimization in Information Systems and Management Sciences. Advances in Intelligent Systems and Computing, vol 360. Springer, Cham. https://doi.org/10.1007/978-3-319-18167-7_10
Download citation
DOI: https://doi.org/10.1007/978-3-319-18167-7_10
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-18166-0
Online ISBN: 978-3-319-18167-7
eBook Packages: EngineeringEngineering (R0)