CVRP

The capacitated vehicle routing problem, or CVRP, is the standard textbook version of the vehicle routing problem. Each vehicle gets one number for how much it can carry — usually a weight or a volume — and the deliveries on a route have to add up to less than that number.

Most routing software is built around this version, because a single number is straightforward to work with. The difficulty is that very few vehicles behave like one. A tanker has separate compartments, and what was last in each one decides what can go in next. A temperature-controlled trailer is divided by a movable wall, so how much frozen space it has depends on where that wall is set. A load of roll-cages has to come off in the order the drops happen, or the driver is unloading half the vehicle at every stop.

Rather than reduce a vehicle to one number, Optrak checks whether a load genuinely fits and can be unloaded in order while it builds the route. The case for doing it that way is set out in Pigden (2013).