Skip to Main content Skip to Navigation
Book sections

Multistart Branch and Bound for Large Asymmetric Distance-Constrained Vehicle Routing Problem

Abstract : In this chapter 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. It is based on reformulating distance-constrained vehicle routing problem into a travelling salesman problem and use of 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 was 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. In that way we get multistart branch-and-bound method. As far as we know instances we solved exactly (up to 1,000 customers) are much larger than instances considered for other VRP models from the recent literature. So, despite 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 in solving other types of vehicle routing problems.
Document type :
Book sections
Complete list of metadata

https://hal-uphf.archives-ouvertes.fr/hal-03430265
Contributor : Kathleen Torck Connect in order to contact the contributor
Submitted on : Tuesday, November 16, 2021 - 10:36:35 AM
Last modification on : Wednesday, November 17, 2021 - 4:01:11 AM

Links full text

Identifiers

Collections

Citation

Samira Almoustafa, Said Hanafi, Nenad Mladenovic. Multistart Branch and Bound for Large Asymmetric Distance-Constrained Vehicle Routing Problem. Optimization Theory, Decision Making, and Operations Research Applications, 31, Springer New York, pp.15-38, 2013, Springer Proceedings in Mathematics & Statistics, ⟨10.1007/978-1-4614-5134-1_2⟩. ⟨hal-03430265⟩

Share

Metrics

Record views

9