Research

Multi-Objective Vehicle Routing and Loading with Time Window Constraints: A Real-Life Application

Xiang Song, Dylan Jones, Nasrin Asgari, Tim Pigden (2020) — Annals of Operations Research 291, 799–825

Last updated: 2026-11-08

Most vehicle routing research describes what a vehicle can carry as a weight, and perhaps a volume. This paper, written with the Centre for Operational Research and Logistics at the University of Portsmouth and with Optrak as the industrial partner, starts from a vehicle that is not like that.

The operation is food service: ambient, chilled, frozen and produce lines, plus cleaning chemicals, delivered to catering customers from one depot. The goods travel on three kinds of container, pallets and small and large roll-cages, with different footprints, and all of them stand on the floor of a multi-temperature rigid. Frozen goods go on pallets at the front, behind a bulkhead that moves to suit how much frozen is on board, and come off through a side door; the rest comes off the back. So how much goes on depends on what else is on the vehicle, and whether it can come off without repacking depends on the order the drops are made in.

The paper sets that out as one problem rather than two. Customers are placed on routes and orders are placed on pallets and pallets on the floor in the same model, with an unloading rule, adapted from the last-in-first-out constraint in the 2L-CVRP literature, that lets a pallet come out sideways as well as straight back. Three things are minimised: distance, the number of vehicles, and the number of pallets that carry more than one customer’s goods, because a driver unloads a dedicated pallet faster than a mixed one. The three pull against each other, so they are combined into one cost and the paper shows how the answer changes as the price of a mixed pallet is varied.

A mixed-integer model solves small cases to optimality. For a 489-customer instance, built on real geography with simulated orders, the paper proposes a generalised variable neighbourhood search and compares it with the Optrak software of the time, given the same instance and five minutes. The search found better values of the paper’s combined objective. The paper notes why the comparison is not quite like for like: the production software was also handling driver breaks and time-of-day speeds, which the model leaves out, and it was allowed to send a vehicle out twice in a day, which the model does not. But the result stands as the paper reports it.

What Optrak took from the work is the problem, not the solver. The paper’s vehicle is the one the 2D loader is built for: containers of different footprints on one floor, a bulkhead that moves, product types restricted to parts of the vehicle, and an unloading order fixed by the route. In the product the loading check runs inside the optimiser, on every change it tries, rather than as a research solver run once on a fixed instance; that is the part of the problem the paper’s five-minute budget could not address. The paper’s third objective, keeping one customer’s goods together, is the order structure in the data model.

The paper gives a University of Portsmouth site for the 489-customer instance. That address no longer exists, and the instance cannot be published here: it holds real customer information. Instances modelled on one real operation, rather than one constraint at a time, are rare. Building them is not the difficulty: we can generate them in new places, with the characteristics of a real operation, such as how closely the drops are spaced, the kinds of site delivered to and the pattern of orders, and with none of any customer’s own data in them. What is missing is someone to curate them and help us publish them for academic use. If that interests you, we would like to hear from you.

Read the paper: doi.org/10.1007/s10479-019-03205-2

Published in Annals of Operations Research, volume 291, pages 799 to 825 (Springer, 2020), in the special issue on real-case applications of operational research. It is open access under the Creative Commons Attribution 4.0 licence, and a copy is hosted here. This is Optrak’s own work with the University of Portsmouth and the University of Roehampton; the software compared against is the version of the time.

Citation

Song, X., Jones, D., Asgari, N. and Pigden, T. (2020). Multi-objective vehicle routing and loading with time window constraints: a real-life application. Annals of Operations Research 291, 799–825. https://doi.org/10.1007/s10479-019-03205-2

Download PDF

See Optrak on Your Own Routes

Book a demo and we'll model your fleet, depots and constraints — and show the savings on real data.