A Robust Branch-Cut-and-Price Algorithm for the Heterogeneous Fleet Vehicle Routing Problem

Artur Pessoa (arturproducao.uff.br)
Marcus Poggi de Aragão (poggiinf.puc-rio.br)
Eduardo Uchoa (uchoaproducao.uff.br)

Abstract: This paper presents a robust branch-cut-and-price algorithm for the Heterogeneous Fleet Vehicle Routing Problem (HFVRP), vehicles may have various capacities and fixed costs. The columns in the formulation are associated to $q$-routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudo-polynomial time. Powerful new families of cuts are also proposed, which are expressed over a very large set of variables. Those cuts do not increase the complexity of the pricing subproblem. Experiments are reported where instances up to 75 vertices were solved to optimality, a major improvement with respect to previous algorithms.

Keywords: vehicle routing, extended formulations, cutting planes

Category 1: Combinatorial Optimization

Category 2: Applications -- OR and Management Sciences (Transportation )

Category 3: Linear, Cone and Semidefinite Programming

Citation: To appear in WEA07 - LNCS, 2007

Download:

Entry Submitted: 04/21/2007
Entry Accepted: 04/22/2007
Entry Last Modified: 06/13/2008

Modify/Update this entry