The problem of en route pickup and delivery is known as the Pickup and Delivery Problem (PDP). It is an extension of the Vehicle Routing Problem (VRP). The important new features of this problem are that pickups can occur en route at customer sites (away from the central depot), and that deliveries are allowed in the same route. This occurs, for example, with transportation systems for handicapped people, where a person can be picked up at one place and dropped at another without going through the central depot. A PDP can be either a single-depot or multiple-depot problem.

PDP problems involve the same kinds of constraints as standard VRPs, with several differences. One is that the vehicle may reach its capacity limit en route (after multiple pickup visits) rather than while loading at the depot. Another difference is that because pickups are occurring en route, the pickups become subject to delays and time windows, just as with the drop off visits. In addition, the pickup and delivery visits are often constrained to be performed by the same vehicle, in order to avoid a return trip to the central depot.

The following figure shows a sample solution for a PDP:

The first step is to write a natural language description of the problem. A good way to start this process is to analyze the constraints and objectives.

What are the constraints in this problem?

The objective is to minimize the cost of the delivery of all the parcels.