Authors: Mladenović, Nenad 
Urošević, Dragan 
Hanafi, Saïd
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: Variable neighborhood search for the travelling deliveryman problem
Journal: 4OR : A Quarterly Journal of Operations Research
Volume: 11
Issue: 1
First page: 57
Last page: 73
Issue Date: 1-Jan-2013
Rank: M22
ISSN: 1619-4500
DOI: 10.1007/s10288-012-0212-1
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: Combinatorial optimization | Metaheuristics | Routing | Travelling deliveryman problem | Variable neighborhood search
Publisher: Springer Link
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 
Development of new information and communication technologies, based on advanced mathematical methods, with applications in medicine, telecommunications, power systems, protection of national heritage and education 

Show full item record


checked on Jun 21, 2024

Page view(s)

checked on May 9, 2024

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.