# Real-time schedulingIs it possible to combine real-time scheduling and a real optimisation?

## Route optimisation is a complex mathematical problem

Route optimisation also known as the “Traveling salesman problem” is a complex mathematical problem due to the number of solutions. As an example, il 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 or million … of years using all the computing power of 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 skll or equipment requirement, bookings, time window etc etc. In somme cases, manualy finding a single solution matching all these constraints could be already 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 technician 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 sound 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.
I remember a long time ago a chat with a PhD in optimisation arguing the optimisation for the next day delivery plan had run at least 3 days to provide a good result.
This can sound funny, but this is the exact description of a very common issue when as route planning software using these algorithms would require to run much longer than the maximum possible time to render an optimised solution. The algorithm are stopped much before a proper result and the output is a poor optimisation. The bad part of the story is it is quite difficult for a user to find out the result is not optimum and often the status is “our software has an optimisation feature so we have optimised diaries, box ticked”.
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 sometime too long) to respond for a global optimisation
• can’t manage interactive scheduling needs
So if your 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 et) and only the technician tour is optimised. This is very interesting for software vendors has 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 endup 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...
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 etc 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 base don capacity stats hopping the background or nightly optimisation will find an optimised solution later. Unfortunately, this is a counter efficient way of making booking. Once a booking is made, the latitudes for the optimisation to improve the results are much lower if any. This way of booking make the inefficiency build up all along the day. It is quit easy to understand why. If you are given a list of jobs to optimise over a few technicians. You will try to swap them aroung up to get a good result. But if you are now told each job is blocked on a speciifc day on a two hours slot, you will very quickly giveup as nothing can really more.
This is exactly what append when an optimisation is expected to optimse 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 algorythm.
As you can see, the difference is very significat and the smaller the slot get, the worst any other form of booking and optimisation get except the optimised booking one.
As you have undestood, 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-tile response.

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

The response is yes. A 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 specialist. Now if these companies have a real time algorithm, they are not identical at all in term 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 immedialty optimised whatever the diary load (volume of jobs but also volume of transactions)
• Scheduling a single job must be able to reorganise multiple diary at once. If it can't to that, this is not a real optimisation.
• Scheduling must be able to reallocate in real time the jobs of a worker made unavailable.
• Booking process must be able to propose all possible optimised solutions for a planner before bamking the booking in order to negotiate the best solution with his customer. This is quite key to improve a 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 reoptimize 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 will be the response time 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 a real time scheduling but with a poor optimisation.
• If a single job scheduling is not able to reorganise multiple technicians at once then you may have a real time scheduling but a 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.