New exact method for large asymmetric distance‐constrained vehicle routing problem

New exact method for large asymmetric distance‐constrained vehicle routing problem

0.00 Avg rating0 Votes
Article ID: iaor2013857
Volume: 226
Issue: 3
Start Page Number: 386
End Page Number: 394
Publication Date: May 2013
Journal: European Journal of Operational Research
Authors: , ,
Keywords: programming: travelling salesman, heuristics, programming: branch and bound
Abstract:

In this paper we revise and modify an old branch‐and‐bound method for solving the asymmetric distance–constrained vehicle routing problem suggested by Laporte et al. in 1987. Our modification is based on reformulating distance–constrained vehicle routing problem into a travelling salesman problem, and on using assignment problem as a lower bounding procedure. In addition, our algorithm uses the best‐first strategy and new tolerance based branching rules. Since our method is fast but memory consuming, it could stop before optimality is proven. Therefore, we introduce the randomness, in case of ties, in choosing the node of the search tree. If an optimal solution is not found, we restart our procedure. As far as we know, the instances that we have solved exactly (up to 1000 customers) are much larger than the instances considered for other vehicle routing problem models from the recent literature. So, despite of its simplicity, this proposed algorithm is capable of solving the largest instances ever solved in the literature. Moreover, this approach is general and may be used for solving other types of vehicle routing problems.

Reviews

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