AN OPTIMIZATION ALGORITHM FOR THE VEHICLE-ROUTING PROBLEM WITH TIME WINDOWS-BASED ON LAGRANGIAN-RELAXATION

Our paper presents a new optimization method for the Vehicle Routing P roblem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start w ithin a given time interval-a so-called time window. Our method is bas ed on a Lagrangian relaxation of the constraint set requiring that eac h customer must be serviced. The master problem consists of finding th e optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem with Time Windows and Capacity Constraints. The optimal multi pliers are found using a method exploiting the benefits of subgradient methods as well as a bundle method. The method has been implemented a nd tested on a series of well-known benchmark problems of size up to 1 00 customers. Our algorithm turns out to be very competitive compared to algorithms considered in the literature, and we have succeeded in s olving several previously unsolved problems.