Skip to Main content Skip to Navigation
Journal articles

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

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
Document type :
Journal articles
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03479494
Contributor : Frédéric Pruvost Connect in order to contact the contributor
Submitted on : Tuesday, December 14, 2021 - 1:03:02 PM
Last modification on : Tuesday, August 30, 2022 - 5:14:20 PM

Identifiers

Collections

Citation

Samira Almoustafa, Said Hanafi, Nenad Mladenovic. New exact method for large asymmetric distance-constrained vehicle routing problem. European Journal of Operational Research, Elsevier, 2013, 226, pp.386-394. ⟨10.1016/j.ejor.2012.11.040⟩. ⟨hal-03479494⟩

Share

Metrics

Record views

10