# Optimal route planning at the touch of a button

## Optimal route planning at the touch of a button

– using just mathematical basics.

There is currently a lot of talk about the fact that we all have to save much more energy, especially fossil energy. And even if it is of course the large companies whose efforts make the biggest difference, measures on a small scale can also make their contribution with their savings. Using an (admittedly highly simplified) example, we will show how, for example in the area of route planning, savings can also be made in small companies with mathematical optimization.

Routes are still planned based on empirical value; as the saying goes, based on our gut instinct. We have decided to use the example of an inner-city delivery service in order to demonstrate how you can optimize routes, lower your fuel costs and CO2 emissions as well as simulate strategic decisions (scenarios) using just a simple mathematical model. But let’s begin with route optimization first of all.

#### Our Example

Our delivery service supplies its customers on a daily basis and deploys a fleet of motor scooters in order to get around quickly in inner-city traffic. All of the drivers have been working for the company for several years now and know their way around quite well. This is why they mostly plan their tours themselves. However, the monthly accounting of the fuel receipts and log books shows that the fuel costs of the delivery service are extremely high. This means the routes will have to be planned by the manager in the future. However, manual planning is not only time-consuming; you also can’t be sure if it will yield an optimal result.

You can get the best result within a short time using mathematical optimization. Our delivery service decided to take part in the experiment and test automated route planning.

### Considerable savings with little effort

You can achieve rapid success with just a basic optimization model which is entirely in line with the proverbial Pareto Principle, according to which you can achieve an 80% success rate with 20% effort. This applies in particular to our route planning example since the problem is fairly straightforward and can therefore be demonstrated with a very basic model.

The diagram shows the tours over the course of one day as driven by the delivery service so far.

The route planning problem meets the two core requirements which enable it to be solved using mathematical optimization:
1. Point: We can work out how expensive a specific route plan is;
2. Point: We can note down all the important connections which constitute a route plan.

In general, mathematical optimization always works as follows:
• it develops any valid solution; in this case a route plan;
• it calculates how expensive the solution is;
• it looks for another solution which is less expensive.

Unfortunately there are so many possible solutions of this type that it would be impossible to count them all. Fortunately, this task can be assumed by special software – a so-called solver – which works with all sorts of scientific and practical tricks in order to find the best solutions in as clever and targeted a manner as possible.

Are you interested in our factsheet?

### The solver does the searching

The route planning objective is clear: the length of all the routes per day should be as short as possible. The optimization target is therefore:

This includes, in particular, the decision as to what constitutes a route in the first place. A real optimization model describes this connection mathematically. Of course, some data is required as a parameter. First of all, it is important to find out whether every possible connection between the locations on the map is part of a tour or not. Mathematically, this corresponds to a binary variable which can either have the value “yes, it is” (numerically 1) or “no, it isn’t” (numerically 0).
We can also formulate the target function mathematically using the distance between two locations:
The „costs“ of a sound decision thus correspond to the entire length of all routes. If a connection between two locations isn’t part of a route, the decision variable for this part is “0” and so the distance between these locations is irrelevant in the target function. Now we could calculate the shortest and therefore the least expensive tour. But so far we have only focused on point 1: We can evaluate tours by allocating costs to them. However, point 2 is just as important: We have to formulate all the relevant connections. And the question here is: what actually constitutes a route? Some would argue that it is perfectly obvious as to what constitutes a route. Basically, this is correct but a mathematical system only does what it is told to do – therefore we have to record all the self-evident facts precisely. We therefore have to observe some constraints:

Point C5 – one of the self-evident facts – can be extended to include a further target: do all the scooters really need to be in use?

More interesting articles

How can industry make optimal use of energy to achieve a climate-neutral production infrastructure? Mathematical optimization may have the answers…

When volatile demand meets production planning and how mathematical optimization can help

Production planning can be performed far more efficiently with mathematical optimization instead of a spreadsheet. We demonstrate the advantages!

From a mathematical viewpoint, there may be better formulations. However, for a trial run of this problem at hand, this should be sufficient for now.

### The model means you’re more than half-way

And after a few months the results are evident, not just in theory but in practice: fuel costs have definitely been reduced since planning the tours by automation every morning.

And after a few months the results are evident, not just in theory but in practice: fuel costs have definitely been reduced since planning the tours by automation every morning.

Manual planning

Basic planning

Difference

14

9

5

525,50 km

413,47 km

112,04 km

€17,34

€13,64

€3,70

€6329,70

€4980,20

€1349,50

Manual planning

14

Basic planning

9

Difference

5

Manual planning

525,50 km

Basic planning

413,47 km

Difference

112,04 km

Manual planning

€17,34

Basic planning

€13,64

Difference

€3,70

#### Costs per year

Manual planning

€6329,70

Basic planning

€4980,20

Difference

€1349,50

Of course, this is only a very abstract and theoretical example. However, we have made the experience over the years that considerable savings can almost always be achieved by optimizing such problems. In addition, if necessary, we can also add the minimization of CO2 emissions as an objective and optimize it further. There are many ways to save energy, let’s use them!

OPTANO can also be used to optimize much more complex scenarios and problems. We will be happy to advise you on whether the use of mathematical optimization is worthwhile for your company. Just contact us.