"A reactive MILP approach to the Vehicle Routing Problem with Time Windows"

DONDO, RODOLFO G.; CERDA, JAIME

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Blackwell

Año: 2006 vol. 13 p. 441 - 459

0969-6016

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.