By Dr. Yasel Costa, ZLC Professor.
The Travelling Salesman Problem, ‘given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?’ is a mathematical classic, first mentioned in 1832 and studied seriously for nearly a hundred years. Research on its variant the Vehicle Routing Problem (VRP) which aims to minimise total route cost goes back to 1959.
Many solutions, exact or heuristic, are available. Why then have I and other researchers from the UK, Netherlands, and the US revisited this topic? The short answer is that the classic VRP doesn’t fully address the needs and concerns of present-day route planners. In particular, the costs to be minimised are not just in cash but also in greenhouse gas emissions, and these are not a simple function of mileage. This is why the problem is often now renamed the Pollution-Routing Problem (PRP). Further, to be of practical use, solutions to the VRP/PRP have to recognise a series of constraints which are often ignored in the classical formulation.
These include time – the route has to be completable within a driver’s shift, there may be requirements for particular drops to be made in specified time slots, and vehicle speeds must be legal and attainable (given congestion). Speed is also a factor in fuel consumption, and therefore in emission production (witness the ‘downspeeding’ strategies now widely employed in logistics to reduce fuel consumption).
Further, a useful solution to PRP needs to take into account the fact that as the delivery round continues, the load being hauled gets lighter so, other things being equal, fuel consumption falls.
There is also the question of geography. Mathematicians love to model events occurring on an infinite and featureless peneplain, but the real world has topography – uphill and downhill – which has significant effects on both speed and fuel consumption. While many PRP models include a factor for road gradient in the initial parameters, this tends not to be carried through in detail to the solution methodology.
There are other constraints which may seem obvious but are easily forgotten. For example, the vehicle can’t be loaded beyond its capacity; every route starts and ends at the home depot; each customer is visited once but only once, and by exactly one vehicle (we can’t have fractions of trucks in the model!).
So we have re-addressed ‘the pollution-routing problem with speed optimisation and uneven topography’, which is the title of our paper in issue 164 of the journal ‘Computers & Operations Research’ (visit this page to view the full paper).
We have taken two approaches. In both, we aim to build routes that minimise the sum of (variable) routing costs (fuel, pollution) and (fixed) driving costs (vehicle costs, driver wages and others) while optimising vehicle speeds to reduce emissions/fuel consumption without violating customer time windows. At the same time we are computing fuel consumption by considering real terrain information (ie, not assuming a constant or average road gradient throughout the route).
The two approaches we explore are, firstly, a ‘branch-and-price’ algorithm which will give exact solutions, and secondly a ‘Tabu Search’ metaheuristic approach for medium to large scale instances (25, 50, even 100 destinations). Key to the efficiency of both approaches is our novel speed optimisation algorithm.
We tested our proposed solutions against two types of dataset. Firstly, we adapted (by adding randomly generated information on route gradients) datasets taken from the research of previous authors on VRP. Second, we created a real-world dataset based on the distribution network of a large health and beauty retailer (serving 248 customers, in Hong Kong. This gives a nice clustering of destinations in central districts plus other more remote locations, and plenty of topography, from the moderately hilly to the mountainously steep).
We were also able to use the real-world dataset to model the effects of reducing the payloads on hillier arcs (sections of route), in other words by making as many as practicable of the deliveries in less hilly areas first. (There are of course some non-cost reasons why heavily loaded trucks may not be desirable on the steepest parts of the route and that is an aspect that further research could integrate with our model).
In tests, our branch-and-price approach found the exactly optimal solution in 61 out of 116 instances, including all instances of up to 25 customers, most instances up to 50 customers, and many with up to 100 customers, in reasonable time. The metaheuristic approach found near-optimal solutions for all instances, each taking less than a minute of computational time. That suggests that the approach may be of real managerial utility.
More generally, applying our solutions to the real-world yields a number of managerial insights. Consideration of payloads and arc gradients offers fuel/emission savings of up to 53%. Savings can be achieved by scheduling ‘uphill’ customers later along the route, when the payload has been reduced. (Note that these savings are present even if the planned route is not the shortest possible). Meanwhile we have also shown that if elevation/gradient is ignored when planning routes, estimates of fuel consumption and therefore economic and emissions costs are likely to be highly inaccurate.
For more information, please see our paper (reference above) or contact Yasel Costa, [email protected].
