Variable neighborhood search for the travelling deliveryman problem |
| |
Authors: | Nenad Mladenovi? Dragan Uro?evi? Saïd Hanafi |
| |
Institution: | 1. School of Mathematics, Brunel University, Uxbridge, UK 2. Mathematical Institute, Belgrade, Serbia 3. LAMIH-Université de Valenciennes, Valenciennes, France
|
| |
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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|