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

Samira Almoustafa (1) , Said Hanafi (2) , Nenad Mladenovic (1)

1 BrunelUniversity Uxbridge
2 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201

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.

Mots clés: Maximum Distance Constraint; Lower Bounding Procedure; Upper Tolerance (UT); Infeasible Tours; Vehicle Routing Problem With Time Windows (VRPTW)

Domaines: Informatique [cs]

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⟩