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
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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom