Premium
A robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem
Author(s) -
Pessoa Artur,
Uchoa Eduardo,
Poggi de Aragão Marcus
Publication year - 2009
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20330
Subject(s) - vehicle routing problem , branch and cut , column generation , computer science , set (abstract data type) , mathematical optimization , routing (electronic design automation) , relaxation (psychology) , algorithm , mathematics , integer programming , psychology , computer network , social psychology , programming language
Abstract This article presents a robust branch‐cut‐and‐price algorithm for the heterogeneous fleet vehicle routing problem (HFVRP), vehicles may have distinct capacities and costs. The columns in the formulation are associated to q ‐routes, a relaxation of capacitated elementary routes that makes the pricing problem solvable in pseudopolynomial 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 with up to 75 vertices were solved to optimality, a major improvement with respect to previous algorithms. © 2009 Wiley Periodicals, Inc. NETWORKS, 2009