{"body":"

What is the vehicle routing problem in operational research?

You might have heard of the travelling salesman problem. At first, it sounds simple. Given a list of locations, find the shortest route to visit them and return. But as you add more locations, the number of possible routes, i.e. the number of ways to order the locations, grows exponentially and soon becomes mind-boggling.

The underlying problem is even more challenging when delivering groceries – it’s known as the ‘vehicle routing problem’. Every vehicle route is an instance of the travelling salesman problem. Yet we also need to decide which customer locations will be visited by each route, taking into account constraints such as:

vehicle capacities: each vehicle has a limit on total weight and a number of chilled, frozen, and ambient storage containers it can deliver at a time, so orders assigned to each route should not in total exceed those limits
timings: customers are promised delivery time slots of small length, e.g. 1 hour; each route must start and end within a driver’s shift time and allow time for the driver’s break.

Then there are multiple optimisation considerations:

business goals: factors such as the number of vans used, total travel time and time window violations all impact the bottom line and customer satisfaction
environmental goals: minimising the number of vans and reducing total travel time can reduce fuel consumption and environmental impact.

Enter dynamic route optimisation

In the classical vehicle routing problem, we know all the customer orders in advance.
However, we need to maintain an optimised routing solution even as customers continue to place and edit their orders.

We can accept a customer order for a particular time slot only if we are sure we can fulfil it. So there must be enough capacity left in a vehicle, and it must be able to reach the customer within the requested time window - without causing delay to other customers’ orders.

So we need to make sure that our new order can fit into the existing delivery schedule.

For the above reasons, the vehicle routing problem we solve is dynamic and non-linear, meaning that it changes over time, with orders being added, removed or modified. Our proposed solutions must be able to cope with these on-the-fly changes.

A note on travel times

In the vehicle routing problem, we assume we know travel times between any pair of locations. However, in practice predicting travel times is a complicated problem in its own right, as these times depend not just on the travel distance but also the day of the week, time of the day, road conditions and other factors.

We solve the problem of travel time prediction separately from the vehicle routing problem using Machine Learning methods based on large amounts of historical data. The predicted travel times are then used by our vehicle routing algorithms.

Why is the vehicle routing problem important?

The last-mile is one of the most significant costs for retailers. What’s more, optimised routes mean less time and vehicles on the road, fewer fuel emissions and reduced costs. So how do we go about tackling this challenge?

Optimising delivery routing isn’t just hard, it’s NP-hard&

Ocado Technology delivers its end-to-end online grocery solutions, including routing optimisation algorithms, to some of the world’s largest grocery retailers. The volume of online sales for these retailers may reach hundreds of thousands of orders per week. To fulfil this demand, a single facility on a single day might dispatch hundreds of routes carrying thousands of orders.

_{A visualisation of routes for Ocado Retail Ltd}

There are a vast number of possible solutions. For example, for 2,000 orders and 100 vans - that’s 10³⁸⁹⁷ possible route permutations (compared to 10⁸² atoms in the universe!).

The challenge we face is that vehicle routing is an NP-hard problem. Put simply, it means you can’t guarantee to find an optimal solution within a reasonable time limit. So we need smart algorithms that would allow us to find good quality routing solutions efficiently.

Routing algorithms

Vehicle routing being such an important and complicated problem, it has also been one of the most extensively studied problems in operations research.

One group of methods used to tackle this problem is mathematical optimisation. We systematically explore possible solutions, and search directions proved not to lead to an optimal solution are abandoned early to save computation time.

Examples of mathematical optimisation include Mixed-Integer and Linear Programming, as well as Constraint Programming.

Another approach is Machine Learning, where an algorithm tries to learn a good solution from a huge amount of data.

Dealing with the issue at scale

While the methods mentioned above can work well on smaller problems, until we see a step-change in compute (such as with quantum computing in the future), the methods mentioned above would not be practical to deal with the real-life scale and complexity of a typical dynamic vehicle routing problem.

So we’ve taken approaches that scale better with the problem size:

1) Simulated Annealing

A well-known method we use is Simulated Annealing. In this algorithm, an initial solution is gradually improved by means of small changes called moves.

If such a change improves the solution quality, it is accepted, and the solution is replaced by the resulting better one.

If a move makes a solution worse, it can still be accepted with some small probability to explore the existing possibilities better.

2) Metaheuristics and genetic algorithms

A more sophisticated method we apply involves a combination of metaheuristics and a genetic algorithm. In genetic algorithms, one maintains a collection of several solutions at the same time. This collection is called a population, in analogy with biological evolution.

At every iteration of the algorithm, two solutions from a population (parents) combine to form a new solution (offspring). If the offspring is a better solution it replaces one of the parents.

The process results in the gradual quality improvement of solutions in the population. We further enhance solution quality through metaheuristics like, for example, route tightening.

Using simulations to compare approaches

To compare different dynamic routing algorithms, we developed a simulation framework.

Our simulation generates events like order placement, cancellation or modification and feeds them into the algorithm.

It simulates the actual dynamic environment where the algorithms operate and allows us to compare their performance and solution quality under similar conditions.

Looking to the future

Our routing algorithms make 14 million calculations per second to optimise delivery journeys for Ocado.com alone. It allows our partners to keep their deliveries on time and manage driver and vehicle operations at scale. These advanced data science and machine-learning solutions enable our partners to achieve a highly efficient, optimised, last-mile.

We develop our operational research solutions in-house and we uniquely tailor them to the problems we face. Our team has the opportunity to work on projects that have a real impact on business efficiency and the environment.

Our culture is one of continuous improvement. We’re already collaborating with academic institutions through the Knowledge Transfer Partnership (an InnovateUK scheme) to help us reduce our fuel emissions and business costs further.

Looking forward, we continue our work on improving routing optimisation, using data and smart algorithms to make a positive impact on our partners’ businesses and the environment.

More widely, we’re exploring the impact of trends such as immediacy, same-day deliveries and the impact of different vehicle types on how we optimise deliveries for online grocery shoppers.

","presentation":{"classes":"","theme":"theme-default","columns":""}}

Beating the vehicle routing problem with operational research