9. VRP with Pickup and Delivery

Abstract
9.1 Introduction In the VRP with Pickup and Delivery (VRPPD), a heterogeneous vehicle fleet based at multiple terminals must satisfy a set of transportation requests. Each request is defined by a pickup point, a corresponding delivery point, and a demand to be transported between these locations. The requested transport could involve goods or persons. This latter environment is called dial-a-ride. The objective function(s) generally minimizes system costs. The VRPPD with Time Windows (VRPPDTW) is a generalization of the VRPTW examined in Chapter 7. In the pickup (resp., delivery) version, the VRPTW is the particular case of the VRPPDTW where the destinations (resp., origins) are all at a common depot. Problems in this class involve time constraints that establish time intervals during which service must take place at each stop, or that express user inconvenience and maximum ride time restrictions for passengers. For example, time windows for dial-a-ride problems model preferred pickup and delivery times specified by the customers. In addition to time windows to be satisfied at each stop, the VRPPD involves several other sets of constraints. These impose visiting each pickup and delivery stop exactly once, not exceeding the capacity of vehicles, and coupling the pickup and corresponding delivery stops on the same vehicle routes and impose visit precedence among each pickup stop and its associated drop-off stop. There are also depot constraints that ensure vehicles return to the appropriate terminals and resource restrictions on the number of drivers and vehicle types.