The pickup and delivery problem with time windows (PDPTW) involves the construction of optimal routes which satisfy a set of transportation requests under capacity, time window, pairing, and precedence constraints. A transportation request is characterized by a pickup location and a delivery location. A transportation request must be served by the same vehicle. A vehicle may serve multiple transportation requests as long as other constraints are satisfied. We consider a generalized pickup and delivery problem with time windows (GPDPTW), in which a transportation request consists of a pickup location and many delivery locations. Here, a transportation request must be served by the same vehicle, too.
In this paper, we propose a branch and price algorithm for the problem. An enumeration technique with preprocessing and elimination rules is used for the column generation problem. We tested the algorithm on a hundred instances which are randomly generated and the computational results are reported.
