An Effective Hybrid Evolutionary Local Search for Orienteering and Team Orienteering Problems with Time Windows

Nacima Labadie (1) , Jan Melechovský (2, 1) , Roberto Wolfler Calvo (3)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels
2 VSE - Prague University of Economics and Business
3 LIPN - Laboratoire d'Informatique de Paris-Nord

The orienteering problem (OP) consists in finding an elementary path over a subset of vertices. Each vertex has associated 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). The ELS generates multiple distinct child solutions using a mutation mechanism and a local search. The GRASP provides multiple starting solutions to the ELS. The method is able to improve several best known results on available benchmark instances.

Domaines: Recherche opérationnelle [math.OC]

Nacima Labadie, Jan Melechovský, Roberto Wolfler Calvo. An Effective Hybrid Evolutionary Local Search for Orienteering and Team Orienteering Problems with Time Windows. 11th International Conference on Parallel Problem Solving from Nature (PPSN), Sep 2010, Kraków, Poland. pp.219-228, ⟨10.1007/978-3-642-15871-1_23⟩. ⟨hal-02736100⟩