The pickup and delivery problem with time windows

The vehicle routing problem (vrp) involves the design of a set of minimum cost routes for a fleet of vehicles which services exactly once a set of customers with known demands. The pickup and delivery problem with time windows (pdptw) is a generalization of the vrp which is concerned with the construction of optimal routes to satisfy transportation requests, each requiring both pickup and delivery under capacity, time window and precedence constraints. This paper presents an exact algorithm which solves the pickup and delivery problem when transporting goods. This algorithm uses a column generation scheme with a constrained shortest path as a subproblem. The algorithm can handle multiple depots and different types of vehicles.