Scientific Program > Talks by Speaker > Marques Guillaume

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.