Abstract
In the Orienteering Problem (OP), a set of linked vertices, each with a score, is given. The objective is to find a route, limited in length, over a subset of vertices that maximises the collective score of the visited vertices. In this paper, we present a new, efficient genetic algorithm (nGA) that solves the OP. We use a special grouping during selection, which results in better-adapted routes in the population. Furthermore, we apply a searching crossover to each generation, which uses the common vertices between distinct routes in the population; we also apply a searching mutation. Computer experiments on the nGA are conducted on popular data sets. In some cases, the nGA yields better results than well-known heuristics.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Archetti, C., Hertz, A., Speranza, M.: Metaheuristics for team orienteering problem. Journal of Heuristics 13, 49–76 (2007)
Balas, E.: The prize collecting traveling salesman problem. Networks 19, 797–809 (1989)
Chao, I.M., Golden, B.L., Wasil, E.A.: A fast and effective heuristic for the orienteering. European Journal of Operational Research 88, 475–489 (1996)
Fischetti, M., Salazar, J.J., Toth, P.: Solving the orienteering problem through branch-and-cut. INFORMS Journal on Computing 10, 133–148 (1998)
Feillet, D., Dejax, P., Gendreau, M.: Traveling Salesman Problems With Profits: An Overview. Transportation Science 38, 188–205 (2001)
Garcia, A., Arbelaitz, O., Vansteenwegen, P., Souffriau, W., Linaza, M.T.: Hybrid approach for the public transportation time dependent orienteering problem with time windows. In: Corchado, E., Graña Romay, M., Manhaes Savio, A. (eds.) HAIS 2010, Part II. LNCS, vol. 6077, pp. 151–158. Springer, Heidelberg (2010)
Gendreau, M., Laporte, G., Semet, F.: A branch-and-cut algorithm for the undirected selective traveling salesman problem. Networks 32(4), 263–273 (1998)
Jaen, J., Mocholi, J.A., Catala, A.: Digital ants as the best cicerones for museum visitors. Applied Soft Computing 11, 111–119 (2011)
Laporte, G., Martello, S.: The selective travelling salesman problem. Discrete Applied Matheuristics 26, 193–207 (1990)
Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K., Zabielski, P.: Genetic algorithm solving orienteering problem in large networks. Frontiers in Artificial Intelligence and Applications 243, 28–38 (2012)
Kataoka, S., Morito, S.: An algorithm for single constraint maximum collection problem. Journal of the Operations Research Society of Japan 31(4), 515–31 (1988)
Piwońska, A., Koszelew, J.: A memetic algorithm for a tour planning in the selective travelling salesman problem on a road network. In: Kryszkiewicz, M., Rybinski, H., Skowron, A., Raś, Z.W. (eds.) ISMIS 2011. LNCS, vol. 6804, pp. 684–694. Springer, Heidelberg (2011)
Sevkli, Z., Sevilgen, E.: Discrete particle swarm optimization for the orienteering Problem. In: Evolutionary Computation (CEC) IEEE Congress, pp. 1–8 (2010)
Tang, H., Miller-Hooks, E.: A tabu search heuristic for the team orienteering problem. Computers & Operational Research 32(6), 1379–1407 (2005)
Tsiligirides, T.: Heuristic methods applied to orienteering. Journal of the Operational Research Society 35(9), 797–809 (1984)
Tasgetiren, M.F.: A genetic algorithm with an adaptive penalty function for the orienteering problem. Journal of Economic and Social Research 4(2), 20–40 (2002)
Vansteenwegen, P., Souffriau, W., 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.: Iterated local search for the team orienteering problem with time windows. Computers & Operational Research 36, 3281–3290 (2009)
Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The City Trip Planner: An expert system for tourists. Expert Systems with Applications 38(6), 6540–6546 (2011)
Vansteenwegen, P., Souffriau, W., Van Oudheusden, D.: The Orienteering Problem: A survey. European Journal of Operational Research 209(1), 1–10 (2011)
Author information
Authors and Affiliations
Corresponding authors
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Zabielski, P., Karbowska-Chilinska, J., Koszelew, J., Ostrowski, K. (2015). A Genetic Algorithm with Grouping Selection and Searching Operators for the Orienteering Problem. In: Nguyen, N., Trawiński, B., Kosala, R. (eds) Intelligent Information and Database Systems. ACIIDS 2015. Lecture Notes in Computer Science(), vol 9012. Springer, Cham. https://doi.org/10.1007/978-3-319-15705-4_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-15705-4_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-15704-7
Online ISBN: 978-3-319-15705-4
eBook Packages: Computer ScienceComputer Science (R0)