Real-time scheduling: Is it possible to combine real-time scheduling and a real optimisation?

Real-time scheduling More IQ blog feature Image BW

Route optimisation, also known as the “Travelling salesman problem”, is a complex mathematical problem due to the number of solutions. As an example, if you have:

2 jobs to optimise, you have 2 solutions
3 jobs to optimise, you have 6 solutions
10 jobs to optimise, you have 3 628 800 solutions
15 jobs to optimise, you have 1 307 674 368 000 solutions
100 jobs to optimise, you have 93 326 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 000 solutions

100 jobs is only about 4 days of work for 5 technicians, so a very small diary set for most companies.

Of course, no optimisation software explores the full range of solutions as the time to optimise 100 jobs would take millions of millions of years using all the computing power on the planet. Most science fiction fans would recognise the research of 42 in “The Hitchhiker’s Guide to the Galaxy”.

To add to the complexity, a pure route optimisation is not very useful in the real world as many constraints must be added to the mix: multiple technicians with different skills, equipment’s, timetable, availability, starting location, job’s skill or equipment requirement, bookings, time window etc etc. In some cases, manually finding a single solution matching all these constraints could already be a challenge before even speaking of optimisation.

The field service offering

The field service software sector propose of a multitude of “fleet solution” or “fleet management” offering and many are the ones to offer a “tour optimisation” solution under the name of “route planning software” or “route mapping”.

So how is it possible to optimise diaries when we speak about hundreds or thousands of mobile technicians with weeks ahead of work in real-time?

The most common approach to optimise mobile workforce diaries is to use classical stochastic algorithms like simulating annealing or genetical algorithms. These algorithms have the fantastic capacity to be able to optimise many problems with only a description of what is required at the end. All the complexity of the computation to get to the result is hidden by these simple algorithms.

This sounds promising but all suffer from the same issues.

There is no end to the optimisation and the only way to get an optimised diary is to let the algorithm run “enough”. In general, it is assumed the optimum solution is reached if no improvement has been found after a period of time or a number of tries which in general represents a significant part of the total optimisation time.

The problem is the general time to find a solution grows exponentially with the volume.

As you have probably guessed reading this description, these algorithms are far from being real time. In addition, these algorithms:

require a lot of computing power
very hardly scale
are running for a very long time (and sometimes too long) to respond for a global optimisation
can’t manage interactive scheduling needs

So if you need interactivity, this doesn’t work well.

Fleet management software implements multiple solutions to mitigate these issues:

Optimise only each individual tour – seems optimised but it is not!

This is the most common unfortunately. Jobs get assigned to a technician (by proximity, skill set) and only the technician tour is optimised. This is very interesting for software vendors as this solution is very easy to implement and even simple if using the Google API to do so. Unfortunately, if it looks optimised on a map, this is very very far from an optimum solution. I have run many proofs of concept and many simulations and I end up with an average of 40% extra saving when using a proper algorithm! It is a bit frustrating as a speciality of optimisation to see a fleet solution using these methods and promoting their optimisation at a much high price than More-IQ… Some do not even hide as being open-source…

If you want to understand why, check this page

Not managing all constraints – do less but get less

This is another way to limit performance requirement. Limiting the number of technicians being optimised, optimising only one day ahead, reduce the scopes of the optimisation, reduce hardware requirement and reduce scheduling time… but also significantly degrade the optimisation result.

Propose real-time non optimised solution – the worst choice in booking context

This is another very common way when booking is required with the customer. The booking is taken based on capacity stats hopping the background or nightly optimisation will find an optimised solution later. Unfortunately, this is a counter efficient way of making a booking. Once a booking is made, the latitudes for the optimisation to improve the results are much lower if any. This way of booking makes the inefficiency build up all along the day. It is quite easy to understand why. If you are given a list of jobs to optimise over a few technicians. You will try to swap them around up to get a good result. But if you are now told each job is blocked on a specific day on a two hours slot, you will very quickly give-up as nothing can really more.

This is exactly what append when an optimisation is expected to optimise the booking once all have been made.

As an illustration, this is the result of 3 simulations, one with 4h booking slot, then 2h booking slots then 1h. There graphs show the total cost of the workforce team (salary cost + travel cost).

The first bar (pink) represents the cost for blind booking (no optimisation at all), the second bar (blue) when making booking with a simple indication of the slots with a near job, the third bar (green) is the result of the previous method then a nightly optimisation, the last bar (yellow) is the result of using an optimised booking algorithm.

As you can see, the difference is very significant and the smaller the slot gets, the worst any other form of booking and optimisation get except the optimised booking one.

As you have understood, all the solutions above are only a workaround and try to offer faster response time to the detriment of optimisation results, the “faster” being generally quite far from a real-time response.

So is it possible to have a good optimisation with real time response time?

The response is yes. Very few companies have built their own algorithm, commonly based on heuristics, drastically more complex to build but far more efficient. They clearly identify themselves as scheduling specialists. Now if these companies have a real time algorithm, they are not identical at all in terms of scalability and scheduling capacity.
And here come More-IQ. If I can name a few real time scheduling software, when the point is to scale seamlessly with thousands of technicians or to offer a real true cloud solution with all its scalability and resilience benefits then there is not much choice.

So what must you expect from a real-time schedule optimisation software?

Scheduling a few jobs in must be immediate and immediately optimised whatever the diary load (volume of jobs but also volume of transactions)
Scheduling a single job must be able to reorganise multiple diaries at once. If it can’t do that, this is not a real optimisation.
Scheduling must be able to reallocate in real time the jobs of a worker made unavailable.
Booking processes must be able to propose all possible optimised solutions for a planner before confirming the booking in order to negotiate the best solution with this customer. This is quite key to improve fleet efficiency. Just taking a blind “slot” request from a customer and scheduling it is the best way to lose other very acceptable solutions with a great saving.
The solution must be able to reoptimise on the fly the emerging day when applicable. If a job takes longer or if a job can’t be made because the customer is absent, being able to reoptimise immediately the load on multiple technicians is a great way to improve efficiency but also customer satisfaction.

Summary

As a summary, I would just recommend you to be careful when choosing a scheduling solution and even more a real time scheduling solution:

Expect a demo with a real dataset. If it doesn’t tell you what the response time will be when multiple users are interacting with the system, it at least must give you an indication of the fastest response time you can get.
Poor response time on a demo is never promising.
Get information about their scheduling method. If they use the google API or only do a tour optimisation, then you may have real time scheduling but with poor optimisation.
If you have to press a button to run the optimisation or if there is a nightly or scheduled optimisation (and this is what the most well-known brand does) then flee. Don’t assume optimisation will be good because the vendor is such a big company that they must have the right solution.