Skip to Main content Skip to Navigation
Journal articles

Variable neighborhood search for the travelling deliveryman problem

Abstract : 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.
Document type :
Journal articles
Complete list of metadata
Contributor : Aurélien Vicentini Connect in order to contact the contributor
Submitted on : Wednesday, March 2, 2022 - 4:43:11 PM
Last modification on : Monday, March 28, 2022 - 1:00:35 PM




Nenad Mladenovic, Dragan Urošević, Said Hanafi. Variable neighborhood search for the travelling deliveryman problem. 4OR-A Quarterly J of Operations Research, 2013, 11 (1), pp.57-73. ⟨10.1007/s10288-012-0212-1⟩. ⟨hal-03594522⟩



Record views