Scientific Program > Talks by Speaker > Sadykov Ruslan

This work deals with the vehicle routing problem (VRP) with backhauls (VRPB), a classical VRP variant with two types of customers: linehaul (delivery) and backhaul (pickup) ones. The linehaul customers have a delivery demand that is loaded at the depot and the backhaul customers have a pickup demand to be transported to the depot. A route must visit at least one linehaul customer and may visit backhaul ones. After visiting a backhaul customer, linehaul customers cannot to be visited. At any moment vehicle capacity should be respected. Despite the large number of works on heuristics for the VRPB, we were able to identify only a couple works on exact algorithms for the problem published in the 1990s. We thus propose two branch-cut-and-price (BCP) algorithms for the VRPB. The first of them follows the classic approach with one pricing subproblem. The second one exploits the linehaul/backhaul customer partitioning and defines two pricing subproblems. The algorithms 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 benchmark instances with up to 200 customers, many of them for the first time. In addition, the approach involving two pricing subproblems is more efficient than the classic one. New instances for the problem are also proposed.