Groupe d’études et de recherche en analyse des décisions

G-2010-22

The Vehicle Routing Problem with Time Windows: State-of-the-Art Exact Solution Methods

, et

The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to service given customers exactly once each while satisfying the vehicle capacity and customer time windows. The VRPTW has been widely studied. We present here a short survey on the successful exact methods for solving it. These are branch-cut-and-price algorithms, except the most efficient one which solves, by a mixed-integer programming solver, a reduced set partitioning model obtained by performing variable elimination based on reduced cost. This method was able to solve all well-known Solomon's benchmark instances except one, outperforming all the other algorithms previously published.

, 13 pages