|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||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:||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 Sep 16, 2022
checked on Sep 15, 2022
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.