Authors: Almoustafa, Samira
Hanafi, Said
Mladenović, Nenad 
Title: Multistart branch and bound for large asymmetric distance-constrained vehicle routing problem
Journal: Optimization Theory, Decision Making, and Operations Research Applications
Series/Report no.: Springer Proceedings in Mathematics & Statistics
Volume: 31
First page: 15
Last page: 38
Issue Date: 1-Jan-2013
ISBN: 978-1-461-45133-4
ISSN: 2194-1009
DOI: 10.1007/978-1-4614-5134-1_2
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.
Publisher: Springer Link

Show full item record


checked on Sep 26, 2021

Page view(s)

checked on Sep 26, 2021

Google ScholarTM




Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.