On the exact solution of vehicle routing problems with backhauls

Eduardo Queiroga, Yuri Frota, Ruslan Sadykov, Anand Subramanian, Eduardo Uchoa, Thibaut Vidal

Abstract

Highlights • We propose two exact algorithms for the problem. • Optimal solutions are reported for open instances. • New benchmark instances ranging from 100 to 1000 customers are introduced. Abstract In this paper, we are interested in the exact solution of the vehicle routing problem with backhauls (VRPB), a classical vehicle routing variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. We propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first one follows the traditional approach with one pricing subproblem, whereas the second one exploits the linehaul/backhaul customer partitioning and defines two pricing subproblems. The methods incorporate elements of state-of-the-art BCP algorithms, such as rounded capacity cuts, limited-memory rank-1 cuts, strong branching, route enumeration, arc elimination using reduced costs and dual stabilization. Computational experiments show that the proposed algorithms are capable of obtaining optimal solutions for all existing instances with up to 200 customers, many of them for the first time. The approach involving two pricing subproblems appears to be more efficient than the traditional one. We introduce new large instances and find tight bounds for them. We finally evaluate the performance of the algorithms on benchmark instances of the heterogeneous fixed fleet VRPB and the VRPB with time windows.
BibTeX
@article{queiroga2020exact,
  author = {Eduardo Queiroga and Yuri Frota and Ruslan Sadykov and Anand Subramanian and Eduardo Uchoa and Thibaut Vidal},
  title = {{On the exact solution of vehicle routing problems with backhauls}},
  journal = {Eur. J. Oper. Res.},
  year = {2020},
  doi = {10.1016/j.ejor.2020.04.047},
}

Loading related content...

Figure