Vehicle Routing Problems
(LANCS project - Transport)
with Richard Eglese and Adam Letchford
Vehicle Routing Problems (VRPs) are concerned with the determination of a minimum cost set of routes for a fleet of vehicles, under the condition that deliveries or pick-ups are made at certain points of a network. Often, side-constraints exist such as limited vehicle capacities, multiple commodities, time windows, backhauls, mixed fleets, multiple depots, adjustments in real-time, etc.
The simplest versions of the problem, such as the Traveling Salesman Problem, the Capacitated VRP, and the VRP with Time Windows, are amenable to exact solution methods. The main techniques are branch-and-cut, in which constraints (rows) are generated dynamically via so-called separation algorithms, and branch-and-price, in which variables (columns) are generated dynamically via dynamic programming. A recent exciting development is branch-and-cut-and-price, which by combining row and column generation gives bounds of extremely good quality, though with the complication of handing a huge number of both variables and constraints.
More realistic VRPs involve so many side-constraints that exact solution methods are not viable. In this case, heuristic methods such as insertion, simulated annealing, tabu search and genetic algorithms are more suitable. There is a need to extend current state-of-the-art heuristics to cope with such real-life complications.
See also the page on Arc Routing Problems.
Return to the Optimisation Research Centre page.
Return to the Supply Chain Management and Modelling Research Centre page.
