Variable neighborhood search for the travelling deliveryman problem

A travelling deliveryman needs to find a tour such that the total waiting time of all the customers he has to visit 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 data structure to store and update the incumbent solution efficiently. In this way, we are able to explore neighborhoods as efficiently as when solving the travelling salesman problem. Computational results obtained on usual test instances show that our approach outperforms recent heuristics from the literature.