Missing from the Model: Orders, Drivers, Tractors and Trailers and Non-Linear Loading

The vehicle routing problem was set down in 1959, and the hundreds of papers since have mostly kept its original shape: customers with a demand, vehicles with a capacity, a capacity constraint that adds up. That shape was right for the computers of the time. It is not the shape of a transport operation, and it is not the shape of the transport management systems that operations actually run on.

This paper, written at Optrak and presented at GECCO in 2013, looks at three places where the gap matters, with examples taken from Optrak customers (referred to by letter, as we did not have permission to name them).

Orders, not demand. People do not place demand; they place orders, and the paperwork, the service levels and the delivery constraints attach to the order. Two orders for the same shop may arrive at the depot at different times, may be deliverable together or apart, may need different vehicles. A weekend newspaper operation illustrates it: supplements printed days ahead and live news arriving at 4am are two orders to every shop, and the best plan delivers them together to rural stores and separately, in a pre-run, to urban ones. Aggregate them into one demand and the pre-run is impossible; treat them as two customers and the unload time, which is a fixed part plus a variable part per unit, is counted twice. Neither gives a usable answer.

Drivers, tractors and trailers, not vehicles. The standard model has a vehicle that leaves the depot and comes back. Real fleets have drivers with shift and break rules, tractor units, and trailers of different types, which are separate resources and are combined and recombined through the day. Collapsing them into one thing makes the common cases, a driver changing trailer at the depot or two drivers sharing a vehicle across shifts, impossible to express.

Loading that does not add up. Goods go on vehicles in pallets, roll cages and stillages, and the rules for how they are packed are about handling speed rather than space. One food-service company’s rule is that a customer’s goods must use the minimum number of roll cages, so the volume of two orders is not the sum of their volumes. Multi-compartment tankers and temperature-controlled trailers with moveable bulkheads make the capacity constraint still further from a single number.

The paper’s argument is that bolting these onto the standard formulation as extra constraints, the “VRP plus” approach, does not work, because the base model has the wrong objects in it. The data model has to start from orders, resources and loads, and the optimiser has to search over that model directly.

That is the design Optrak is built on. The three sections map onto three parts of the product: orders, products and shipments, fleet and resources and loading models. The data model page sets out how they fit together.

Read the paper: doi.org/10.1145/2464576.2482686

Published in the Proceedings of the 15th Annual Conference Companion on Genetic and Evolutionary Computation (GECCO ‘13 Companion), pages 1079 to 1084, ACM, 2013. This is Optrak’s own work; the examples are from customers of the time and some of the detail has moved on, but the argument has not.