On the exact solution of vehicle routing problems with backhauls

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.