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 Problem with Time Windows (VRPTW). The VRPTW is a generalization of the Vehicle Routing Problem, where the service of a customer must start within a given time interval – a so-called time window. Our method is based on a Lagrangian relaxation of the constraint set requiring that each customer must be serviced. The master problem consists of finding the optimal Lagrangian multipliers and the subproblem is a Shortest Path Problem with Time Windows and Capacity Constraints. The optimal multipliers are found using a method exploiting the benefits of subgradient methods as well as a bundle method. The method has been implemented and tested on a series of well-known benchmark problems of size up to 100 customers. Our algorithm turns out to be very competitive compared to algorithms considered in the literature, and we have succeeded in solving several previously unsolved problems.