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

RODOLFO DONDO,; JAIME CERDÁ,

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Blackwell Publishing

Año: 2006 p. 441 - 459

0969-6016

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. Vehicles 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 get 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 generalized predecessor instead of direct predecessor. A two-stage optimizing strategy that first reassigns nodes to tours and then reorders nodes on the same tour was developed. Several types of VRPTW problems have been efficiently solved.