Skip to Main content Skip to Navigation
Journal articles

Hybridized evolutionary local search algorithm for the team orienteering problem with time windows

Abstract : The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex is associated with a profit that is collected on the visitor’s first visit. The objective is to maximize the collected profit with respect to a limit on the path’s length. The team orienteering problem (TOP) is an extension of the OP where a fixed number m of paths must be determined. This paper presents an effective hybrid metaheuristic to solve both the OP and the TOP with time windows. The method combines the greedy randomized adaptive search procedure (GRASP) with the evolutionary local search (ELS). ELS generates multiple distinct child solutions using a mutation mechanism. Each child solution is further improved by a local search procedure. GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02494247
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, February 28, 2020 - 3:19:49 PM
Last modification on : Tuesday, October 20, 2020 - 1:44:44 PM

Links full text

Identifiers

Collections

Citation

Nacima Labadie, Jan Melechovský, Roberto Wolfler Calvo, Roberto Wolfler Calvo. Hybridized evolutionary local search algorithm for the team orienteering problem with time windows. Journal of Heuristics, Springer Verlag, 2011, 17 (6), pp.729-753. ⟨10.1007/s10732-010-9153-z⟩. ⟨hal-02494247⟩

Share

Metrics

Record views

66