PDP-VRP
Overview
The pickup and dropoff problem is a further generalisation of the vehicle routing problem. Unlike the CVRP where all demands are required to be positive, the pickup and dropoff problem specifies a pickup quantity and dropoff quantity at each node (a positive and negative amount). The rules of the game are that the vehicle needs to pick up before it can drop off, but that all demands are interchangable. This means that it’s not a specific order from point A that must be delivered to point B - if there’s a quantity from location C which matches the demand of location B, then it’s not a prohibited move.
Usefulness
In the real world, these kinds of use cases are quite unlikely. The main reason for this is the other assumption that is being made in academic pdp’s is that the quanitites are arbitrarily splittable into the chunks that are required to be delivered. In instances like the delivery of fluids, this may well be possible. But even then, there are often specifics related to the type of product which are not directly being modelled which require items from a particular source to be delivered to a specific destination.
We don’t really focus on these kinds of problems because they’re few and far between, but it should be important to note that having a concept of a pickup and a dropoff is really powerful. The problem is we often want to enforce additional relationships between these concepts so that we know that the product which was picked up is moved to some destination in an immutable manner. In order to enforce this type of behaviour we need to add two additional constraints, the first is that the pickup and the delivery should be done on the same vehicle, and secondly, that the pickup should be performed before the dropoff. The IVR7/8 Job schema component allows for modelling these kinds of situations easily.
Once you start playing with these more complex concepts (such as pickup and dropoff) it’s probably time to use the complete IVR schema which is capable of modelling all simpler formulations and more.