INTEC   05402
INSTITUTO DE DESARROLLO TECNOLOGICO PARA LA INDUSTRIA QUIMICA
Unidad Ejecutora - UE
artículos
Título:
"A reactive MILP approach to the Vehicle Routing Problem with Time Windows"
Autor/es:
DONDO, RODOLFO G.; CERDA, JAIME
Revista:
INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH
Editorial:
Blackwell
Referencias:
Año: 2006 vol. 13 p. 441 - 459
ISSN:
0969-6016
Resumen:
Abstract
The time-window-constrained vehicle routing problem (VRPTW) is a well-known combinatorial problem.
Its goal is to discover the best set of routes for a vehicle fleet in order to service a given number of customers
at minimum cost. Vehicle capacity, maximum service time and time-window constraints must be satisfied.
Most proposed VRPTW optimizing approaches intend to discover the best or a near-optimal solution at
once. Improvement methods are old strategies that apply heuristics to insert customers into tours and/or
rearrange nodes to obtain better routes. They are performed until no further improvement is achieved.
Little research has been focused on model-based reactive approaches seeking a better solution by exploring
a small solution space around the current solution. This work presents a new model-based improvement
methodology for the multi-depot heterogeneous-fleet VRPTW problem to enhance an initial solution
through solving a series of MILP mathematical problems that allow exchanges of nodes among tours and
node reordering on every route. By restricting the range of improvement options, the problem size can be
bounded and a limited number of binary variables is required for real-world problems. The improvement
formulation is based on a continuous time-domain representation that handles assignment and sequencing
decisions through different sets of binary variables and uses the notion of a generalized predecessor instead
of a direct predecessor. Several types of VRPTW problems have been efficiently solved.