A general variable neighborhood search for the one‐commodity pickup‐and‐delivery travelling salesman problem

A general variable neighborhood search for the one‐commodity pickup‐and‐delivery travelling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor20122438
Volume: 220
Issue: 1
Start Page Number: 270
End Page Number: 285
Publication Date: Jul 2012
Journal: European Journal of Operational Research
Authors: , , ,
Keywords: combinatorial optimization, supply & supply chains, heuristics: local search
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.