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: | Mladenovic Nenad, Hanafi Sad, Uroevic Dragan, Ilic Aleksandar |
Keywords: | combinatorial optimization, supply & supply chains, heuristics: local search |
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,