Authors: Almoustafa, Samira
Hanafi, Said
Mladenović, Nenad 
Title: New exact method for large asymmetric distance-constrained vehicle routing problem
Journal: European Journal of Operational Research
Volume: 226
Issue: 3
First page: 386
Last page: 394
Issue Date: 1-May-2013
Rank: M21a
ISSN: 0377-2217
DOI: 10.1016/j.ejor.2012.11.040
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.
Keywords: Assignment | Branch and bound | Combinatorial optimization | Vehicle routing problem
Publisher: Elsevier

Show full item record


checked on Jun 13, 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.