Using column generation to solve the vehicle routing problem with time windows

The vehicle routing problem with time windows (VRPTW) involves the design of a set of minimum cost routes, originating and terminating at a central depot, for a fleet of vehicles which services a set of customers with known demands. Each customer is serviced exactly once within its time window and, furthermore, all the customers must be assigned to vehicles such that the vehicle capacities are not exceeded. In this paper the authors present a new optimization algorithm for a set covering type formulation of the VRPTW solved by column generation.