Authors: Mladenović, Nenad 
Urošević, Dragan 
Hanafi, Saïd
Ilić, Aleksandar
Affiliations: Mathematical Institute of the Serbian Academy of Sciences and Arts 
Title: A general variable neighborhood search for the one-commodity pickup-and-delivery travelling salesman problem
Journal: European Journal of Operational Research
Volume: 220
Issue: 1
First page: 270
Last page: 285
Issue Date: 1-Jul-2012
Rank: M21a
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2012.01.036
We present a variable neighborhood search approach for solving the one-commodity pickup-and-delivery travelling salesman problem. It is characterized by a set of customers such that each of the customers either supplies (pickup customers) or demands (delivery customers) a given amount of a single product, and by a vehicle, whose given capacity must not be exceeded, that starts at the depot and must visit each customer only once. The objective is to minimize the total length of the tour. Thus, the considered problem includes checking the existence of a feasible travelling salesman's tour and designing the optimal travelling salesman's tour, which are both NP-hard problems. We adapt a collection of neighborhood structures, k-opt, double-bridge and insertion operators mainly used for solving the classical travelling salesman problem. A binary indexed tree data structure is used, which enables efficient feasibility checking and updating of solutions in these neighborhoods. Our extensive computational analysis shows that the proposed variable neighborhood search based heuristics outperforms the best-known algorithms in terms of both the solution quality and computational efforts. Moreover, we improve the best-known solutions of all benchmark instances from the literature (with 200 to 500 customers). We are also able to solve instances with up to 1000 customers.
Keywords: Combinatorial optimization | Metaheuristics | Pickup-and-delivery travelling salesman problem | Variable neighborhood search
Publisher: Elsevier
Project: Mathematical Modelas and Optimization Methods on Large-Scale Systems 

Show full item record


checked on May 23, 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.