The pickup and delivery problem with time windows and transshipment

Pickup and delivery problems with time windows are frequently encountered by courier companies. These companies serve customers that require transportation of a package from a pickup location to a delivery location. This paper presents an empirical study on usefulness of transshipment points in such a context. Transshipment allows for a request to be served by two vehicles: one vehicle collects the load at the pickup location, drops it at a transshipment point, and another vehicle carries the load to the delivery location. The motivation for this work came from the practice observed in a large San Francisco based courier company that allows transshipment of loads between vehicles. The company serves large geographic area covering several neighboring cities. The main reasoning behind allowing transshipment lies in the idea of keeping drivers in their home area. We have investigated a generalization of this transshipment practice, allowing vehicles to move through entire service area in order to evaluate the usefulness of transshipment. We identify circumstances under which transshipment may be beneficial.