|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||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.
|Keywords:||Assignment | Branch and bound | Combinatorial optimization | Vehicle routing problem||Publisher:||Elsevier|
Show full item record
checked on Dec 2, 2023
checked on Dec 3, 2023
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.