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?

Mathematical Optimization
for Better Decisions

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

Mise en place is a term used to describe food preparation by professional chefs. We show you how to prepare the implementation of new software for production planning to ensure that nothing can go wrong.

Read more »

Planning can be complex enough and make you feel as if you are stuck in a maze. High usability in planning software is crucial to ensure an effective workflow.

Read more »

Those who believe that Operations Research is just for mathematicians is mistaken. We encounter applied mathematics in the form of OR every day…

Read more »

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

Number of tours

14

9

5

Length of tours

525,50 km

413,47 km

112,04 km

Costs per
day

€17,34

€13,64

€3,70

Costs per
year

€6329,70

€4980,20

€1349,50

Number of tours

Manual planning

 14

Basic planning

9

Difference

5

Length of tours

Manual planning

525,50 km

Basic planning

413,47 km

Difference

112,04 km

Costs per day

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.

Have you already got your factsheet Factsheet on this topic?

Mathematical optimization for route planning can be implemented with simple means and achieves amazing savings! Our factsheet provides an overview of possible applications, including the mathematical formulas and possible extensions.

To obtain our factsheet, all you need to do is enter your contact details in the space below. A pop-up window will then open to download the whitepaper. Please note that by providing us with your email address, you agree that we may contact you on this topic. You may revoke this agreement at any time by contacting privacy@optano.com.

Sabrina Geismann
Sabrina Geismann

Do you have any questions?

Dr. Sven Flake
Analytics Senior Consultant