Abstract
The team orienteering problem (TOP) is a generalization of the orienteering problem. A limited number of vehicles is available to visit customers from a potential set. Each vehicle has a predefined running-time limit, and each customer has a fixed associated profit. The aim of the TOP is to maximize the total collected profit. In this paper we propose a simple hybrid genetic algorithm using new algorithms dedicated to the specific scope of the TOP: an Optimal Split procedure for chromosome evaluation and local search techniques for mutation. We have called this hybrid method a memetic algorithm for the TOP. Computational experiments conducted on standard benchmark instances clearly show our method to be highly competitive with existing ones, yielding new improved solutions in at least 5 instances.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Archetti C, Hertz A, Speranza M (2006) Metaheuristics for the team orienteering problem. J Heuristics 13(1): 49–76
Beasley JE (1983) Route-first cluster-second methods for vehicle routing. Omega 11: 403–408
Belenguer J-M, Benavent E, Lacomme P, Prins C (2006) Lower and upper bounds for the mixed capacitated arc routing problem. Comput Oper Res 33(12): 3363–3383
Bellman R (1957) Dynamic Programming. Princeton University Press, Princeton
Bouly H, Dang D-C, Moukrim A (2008) A memetic algorithm for the team orienteering problem. In EvoWorkshops
Boussier S, Feillet D, Gendreau M (2007) An exact algorithm for team orienteering problems. 4OR 5(3): 211–230
Butt S, Cavalier T (1994) A heuristic for the multiple tour maximum collection problem. Comput Oper Res 21: 101–111
Chao I-M, Golden B, Wasil E (1996) The team orienteering problem. Eur J Oper Res 88: 464–474
Feillet D, Dejax P, Gendreau M (2005) Traveling salesman problems with profits. Transp Sci 39(2): 188–205
Ke L, Archetti C, Feng Z (2008) Ants can solve the team orienteering problem. Comput Ind Eng 54(3): 648–665 ISSN 0360-8352
Khemakhem M, Chabchoub H, Semet F (2007) Heuristique basée sur la mémoire adaptative pour le problème de tournées de véhicules sélectives. In Logistique & Transport, pp 31–37, Sousse, Tunisie
Lacomme P, Prins C, Ramdane-Cherif W (2004) Competitive memetic algorithms for arc routing problems. Ann Oper Res 131(1–4): 159–185
Moscato P (1999) New ideas in optimization. chapter Memetic Algorithms: a short introduction. McGraw-Hill, UK, pp 219–234
Prins C (2004) A simple and effective evolutionary algorithm for the vehicle routing problem. Comput Oper Res 31(12): 1985–2002
Ruiz R Stützle T (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem. EJOR 177: 2033–2049
Solomon M (1987) Algorithms for the vehicle routing and scheduling problems with time window constraints. Oper Res 35: 254–265
Tang H, Miller-Hooks E (2005) A tabu search heuristic for the team orienteering problem. Comput Oper Res 32: 1379–1407
Ulusoy G (1985) The fleet size and mixed problem for capacitated arc routing. Eur J Oper Res 22: 329–337
Author information
Authors and Affiliations
Corresponding author
Additional information
This paper is an extension of a preliminary work published in EvoWorkshops 2008 proceedings (Bouly et al. 2008).
Rights and permissions
About this article
Cite this article
Bouly, H., Dang, DC. & Moukrim, A. A memetic algorithm for the team orienteering problem. 4OR-Q J Oper Res 8, 49–70 (2010). https://doi.org/10.1007/s10288-008-0094-4
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10288-008-0094-4
Keywords
- Selective vehicle routing problem
- Memetic algorithm
- Optimal split
- Metaheuristic
- Destruction/construction