The magic (and math) behind route optimization software

Imagine dispatching a driver to pick up a passenger in the city. One driver picking up one passenger is simple - just find the best route and go. However, when you have multiple pre-booked pickups, with specific pickup and drop-off windows as well as driver and vehicle constraints,  route planning becomes much more complicated. 

This question affects every transportation service - from ride hailing and taxi companies to Non Emergency Medical Transport (NEMT) and student transport providers; from delivery and logistics operators to field agent and utility companies, rental and car sharing. Anyone who needs to dispatch complex multiple stop-points and routes and meet SLAs in the most cost effective way to the business.   

The team at Autofleet understands both the math, and the reality of dispatch and route planning. Thanks to our optimized route planning software we were able to build an adaptive solution that optimizes customer experience KPIs such as improving On Time Performance (OTP) and trip completion rate as well as fleet efficiency KPIs including reduction in deadhead distances and increase in fleet utilization.

Why is route optimization a hard problem?

Optimized route planning is critical for a viable, sustainable business. It allows companies to reduce costs, increase efficiency, do more with less resources, and meet SLAs and customer expectations. However, the problem of route planning is hard because its complexity grows exponentially: The more stop points you add, the more possibilities there are. By a lot.

Take for example a plan with 5 stop points. There are 120 different route combinations between these points (A to B to C to D to E, A to C to D to E to B etc.). With 10 stop points, there are already 3,628,800 optional routes, and with 20 there are more possible routes than there are grains of sand on a beach. And that is without factoring in multiple driver and vehicle related constraints that add to the complexity of the problem.

Even with the aid of software, route optimization is a difficult challenge. In fact, it is considered a classical NP-hard problem in computer science. That is - a problem computers find difficult to solve because it quickly grows too complex to solve within a reasonable time frame. 

There is no algorithm that guarantees a quick solution for all scenarios. In theory, you can “brute force” the problem - try out every possible route to find the best one. But with so many possibilities, it quickly becomes impossible to solve in any reasonable amount of time.  

Planning - Creating efficient routes in real life 

As a leader in optimization solutions for fleets, Autofleet employs advanced algorithms that provide real-world solutions to optimize dispatching and scheduling. 

First, in real world situations, a near-optimal solution that can be calculated in a fraction of the time it takes to find the most optimal solution is a viable and better option than waiting for days for the ultimate answer.  

So we begin by calculating a viable and good enough plan and adapt it by implementing incremental changes. It is easier to solve the problem once you have an initial solution, and it can be done efficiently and with great results.   

This is further supported by setting constraints on acceptable solutions (e.g. you cannot pick up a kid to school at 3AM, or ask a driver to do a 20 hour shift). And then eliminating any solution that breaches any of those constraints quickly, without letting them run their full course.

Solutions that already failed, and those solutions that are similar to them are avoided. And solutions that are so similar to the current plan as to not make much difference are ignored as well. 

Combining these techniques creates a plan that is both near-optimal and efficient, and can be used to dispatch drivers.

The Autofleet way: Route planning re-optimization on the go

In real-world situations, even once you have a good plan, new variables come into play - traffic, driver availability, last-minute cancellations, new orders, will-call rides and more. Even if you did all the calculations and created a solid schedule, in the less than ideal conditions of the real world, it can never play out as planned. 

Therefore, a new plan may be needed. But if optimized route planning is a difficult problem to solve once, before the beginning of a shift, imagine how hard and time consuming it is to come up with a new solution each time the situation changes.

Running the entire planning process again makes no sense - it takes a lot of time, and does not scale. In fact, by the time you finish running the whole plan again, new circumstances will arise. 

The dynamic nature of mobility services, with real-time changes in traffic, drivers, passengers, and the need for both ASAP and planned requests, can render plans obsolete without a solution for updating and adapting them.

The naïve solution is to simply add any change to the existing plan. And while adding a single stop point may not make much difference, these changes pile up and accumulate. It can quickly degrade any plan to the point it is unusable. Moreover, changes like a driver calling in sick, or a major roadblock, have a ripple effect that can make any planned schedule completely irrelevant.   

The problem is how to meet the need to re-optimize plans on the fly, and adapt them to changing circumstances. And how to tell which of the plans is better? The current one, or the new re-optimized solution? Figuring that out is not a simple task (remember the number of possible options is huge!).

The evaluation process takes several steps. First of all, the re-optimized plan needs to meet a certain set of constraints, such as meeting all arrival windows on time.

Only plans that are within the parameters set by the constraints are moved on to the next step, where they are scored according to specific KPIs. And only the highest scoring plan is dispatched. Makig sure the best plan is always in play.  

A deeper dive into the algorithm 

Without getting too technical, let's dive a little deeper into the logic behind the algorithm, and get a better understanding of how re-optimization works to adapt and improve dispatching in real time. 

One of the best shortcuts when re-optimizing a plan is to eliminate solutions that failed before. This is called “backtracking” and it allows us to start with fewer options, avoiding those that we already know do not work. 

We can also implement “domain reduction” that takes into account the current state of the fleet as a starting point, and places constraints on the search for the optimal route based on the reality of the situation. For example  if a driver is about to end his or her shift, we don’t give them another long ride. If they are heading north, we should avoid turning them around etc.  

Another optimization is “localizing” the search, by swapping just a couple of routes at a time and seeing if the change generates a better result. If we see an improvement we can propagate the change, and test again. 

Lastly there are “heuristics”, which are the closest thing to common sense math has to offer. Ensuring, for example, we do not change routes to drivers that are already close to the pick-up point, clustering rides going in the same direction, disregarding routes that are already very similar, taking into account the geography of the area and more.

The bottom line - route planning is great in theory, route re-optimization makes it great in reality 

There is no way to scale a modern ride service without using a route planning or dispatch software solution. Especially for those who provide contact rides such as student rides or NEMT services, or delivery and logistics services that rely on forward planning.. 

The dynamic nature of mobility services, including dealing with real-time traffic, drivers' and passengers' last-minute changes, and the need to accommodate ASAP requests as well as planned ones, means that plans can become obsolete almost as soon as they are ready without a solution to update and adapt them.

Experience shows that companies that understand that, and move beyond basic planning to adaptable re-optimized dispatch schedules, perform better in terms of efficiency - providing better service with a smaller head count and more consistency.

Some of it may sound like math mambo-jambo - but the bottom line is that for a real time, optimized route planning software to deliver the operational excellence your business requires, there is no getting around automated and optimized techniques to adapt your routes to the changing reality.