Groupe d’études et de recherche en analyse des décisions

G-2011-49

Variable Neighborhood Search for the Travelling Deliveryman Problem

, et

A travelling deliveryman needs to find a tour, such that the total waiting time of all his customers is minimum. The Deliveryman starts his tour at a depot, travelling at constant velocity. In this paper we suggest a general variable neighborhood search based heuristic to solve this NP-hard combinatorial optimization problem. We combine several classical neighborhood structures and design the data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as for solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.

, 20 pages