A Branch-and-Cut-and-Price algorithm for the Two-Echelon Capacitated Vehicle Routing Problem
Guillaume Marques  1, 2, 3@  , Ruslan Sadykov  2, 3@  , François Vanderbeck  2, 3@  , Jean-Christophe Deschamps  1@  , Rémy Dupas  1@  
1 : Laboratoire de líntégration, du matériau au système  (IMS)  -  Website
Université Sciences et Technologies - Bordeaux 1, Institut polytechnique de Bordeaux, Centre National de la Recherche Scientifique : UMR5218
33405 TALENCE CEDEX -  France
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

The two-echelon capacitated vehicle routing problem aims to deliver goods to customers by processing and consolidating goods through intermediate depots. The problem involves two different fleets of homogeneous vehicles. The first fleet ships goods from the distribution center to the intermediate depots. The second fleet picks the goods at intermediate depots and delivers them to the customers. To solve exactly the problem we base our work on an efficient Branch-Cut-and-Price algorithm which combines the best techniques proposed recently for vehicle routing problems. Our contributions include a new path-based formulation of the problem without the need to use additional flow variables, a new family of valid inequalities, and a new branching strategy. Using the improved Branch-Cut-and-Price algorithm we were able to solve all classic instances of the problem with up to 10 intermediate depots and 200 customers. Thus we double the size of instances solved to optimality. Computational results for new instances with up to 15 intermediate depots will also be presented.

Online user: 1 RSS Feed