Branch-cut-and-price algorithms for the vehicle routing problem with backhauls
Eduardo Queiroga  1, *@  , Yuri Frota  1@  , Ruslan Sadykov  2, 3, *@  , Anand Subramanian  4@  , Eduardo Uchoa  1, *@  , Thibaut Vidal  5@  
1 : Universidade Federal Fluminense  (UFF)  -  Website
2 : Institut de Mathématiques de Bordeaux  (IMB)  -  Website
CNRS : UMR5251, Université Sciences et Technologies - Bordeaux I, Université Victor Segalen - Bordeaux II, Université Sciences et Technologies Bordeaux I, Université Victor Segalen – Bordeaux II
351 cours de la Libération 33405 TALENCE CEDEX -  France
3 : RealOpt  (INRIA Bordeaux - Sud-Ouest)
Université Sciences et Technologies - Bordeaux I, INRIA
200 avenue de la Vieille Tour 33405 Talence -  France
4 : Universidade Federal da Paraíba  (UFPB)
Departamento de Engenharia de Produção, Centro de Tecnologia, Campus I - Bloco G, Cidade Universitária, João Pessoa-PB, 58051-970 -  Brazil
5 : PUC-Rio
* : Corresponding author

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. 

Online user: 1 RSS Feed