An improved Branch-Cut-and-Price algorithm for heterogeneous vehicle routing problems
Artur Pessoa  1@  , Ruslan Sadykov  2, 3, *@  , Eduardo Uchoa  1, *@  
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
* : Corresponding author

This work considers a family of VRP variants that generalizes the classical Capacitated Vehicle Routing Problem by taking into account the existence of a number of vehicle types differ by capacity, costs, depot allocation, or even by the set of customers that they can visit. Those problems are very important in practice, since fleets are likely to be heterogeneous in most real- world situations.

The proposed Branch-Cut-and-Price algorithm combines several state-of-the-art techniques known to be efficient for routing problems : bi-directional ng-path based labeling algorithm to solve the pricing subproblems, generation of limited arc memory rank-1 cuts with up to 5 rows, reduced cost fixing of arc variables, enumeration of elementary routes, automatic dual price smoothing stabilization, and multi-phase strong branching with pseudo-costs.

To improve the master problem relaxation, we additionally generate homogeneous extended capacity cuts. We computationally show that these cuts, even in the presence of rank-1 cuts, are important for solving difficult instances of the problem. Other contributions include pricing subproblem dependent memory for rank-1 cuts, and the concept of « enumerated mode » for pricing subproblems.

The proposed algorithm was tested on a set of standard instances of the problem, including multi-depot and site-dependent variants. The dimension of instances that can solved to optimality was doubled in comparison with the state-of-the-art algorithm by Baldacci and Mingozzi (2009). Several best-known solutions were improved.


Online user: 1 RSS Feed