Before we get to the all-important burgers, imagine for a moment that you're a dispatcher supervising a fleet of drivers. Each driver’s vehicle will be distributing orders that were neatly packed into their rides the night before. All the drivers show up for their shifts and are ready to go about their routes, but a batch of new deliveries came in at the last minute that have to get assigned. What now? How do the new deliveries get incorporated into the pre-existing routes that are about to unfold?
For most fleet and dispatch management operations, circumstances can change rapidly and require quick decision-making in order to ensure that service remains nimble and responsive. As inputs for a given set of stops change over time — such as adding a delivery destination for a driver during their route — there are a few potential strategies that you might use to incorporate those changes into routing solutions.
In this post, we’ll explore one strategy that uses Nextmv’s vehicle backlog feature.
What is a vehicle backlog?
A vehicle backlog is a list of stops assigned to a vehicle that have yet to be serviced. Any stop in a vehicle’s backlog is guaranteed to get assigned to the vehicle’s route. There are generally two ways to think about vehicle backlogs: fixed and flexible.
In a fixed backlog scenario, once you assign routes to vehicles, any additional stops can only be appended to the end of an established route. There are a few reasons to choose this approach: it tends to be simpler and, in some cases, the use case in question may dictate this choice (e.g., if deviations for a route shouldn't happen).
However, fixed backlogs have disadvantages. You might imagine a vehicle visiting a long list of stops traveling in one direction that receives a pickup order halfway through its trip that is located near one of its upcoming stops. You could save a tremendous amount of time with a quick detour during the trip rather than appending the stop to the end of a fixed backlog and subsequently backtracking later.
If a driver along a route is able to adapt this way on the fly and rearrange their set of stops mid-route, this is referred to as a flexible backlog. Learning how to leverage flexible backlogs with Nextmv is the focus of this post. (You can follow along by signing into Nextmv Cloud or creating a new account for free.)
Part 1: A gauntlet of burgers - Solving a basic VRP
To begin, we'll establish an illustrative use case and demonstrate how to use the backlog property to react to new, incoming orders. They say to write what you know, so today I'm optimizing for what I’d argue is the most crucial delivery asset of all: fast food burgers.
Let’s explore a sourcing scenario, where I (your author) await (hungrily) to be served the best burgers in the Boise, Idaho area. Given an example list of vehicles and burger joint locations, we can quickly solve this vehicle routing problem (VRP) for an optimized burger sourcing route using the Nextmv console.
Our Nextmv Cloud input needs to capture the following:
- Two vehicles (identified by driver name) and twelve stops (identified by burger type)
- Each vehicle has a capacity of seven burgers
- Each stop has a pickup quantity of one burger
- Both vehicles end at the same location where I’m waiting
We’ve not defined where each vehicle must start. Instead, we'll let vehicles start at the first stop on their route and we'll rely on Nextmv to determine this.
Our default value function is looking to minimize total vehicle travel time. Given three seconds to solve for this input, we're given the following optimized route:
Let's look at a representation of each vehicle's plotted route:
tina:
- havarti-burgers →
- irish-burgers →
- latke-burgers →
- gruyere-burgers →
- jalapeno-burgers →
- kale-burgers
bob:
- bacon-burgers →
- arugula-burgers →
- double-burgers →
- edamame-burgers →
- cheddar-burgers →
- fried-burgers
If there were no additions to my order, this is how each vehicle route would unfold. But shortly after I had finalized my order (and each vehicle’s route had been determined), I realized I must add another burger to my list…
Part 2: A sudden craving - Inserting a new stop early on
The Monterey Jack burger! How could I have forgotten it? By the time I remembered, both vehicles just got started and are still servicing their first stops. But I also know that the drivers really look forward to visiting the stops they're initially given and don't want them to change after they're assigned. (The burger community is tight-knit in that way.) So we want to keep the same stops assigned to each vehicle while inserting a new stop along the way, but how do we go about it?
We’ll use the backlog property. As described in the Nextmv backlog documentation, the backlog property is set per vehicle as an array of stops that vehicle must service. In other words, each listed stop in a vehicle’s backlog array must appear in the calculated route for that vehicle. This feature allows the Nextmv solver to decide the best way to reorder each vehicle’s backlog stops in addition to new stops so the entire route is more efficient.
In our example scenario, each vehicle is in the process of servicing the first stops:
- tina: havarti-burgers
- bob: bacon-burgers
In order for Nextmv to determine how to insert monterey-burgers into the route, we need to modify our initial input JSON slightly by:
- Adding in a backlog array containing the ids of the backlog stops for each vehicle
- Setting a unique start location for each vehicle at their respective first pickups (havarti-burgers and bacon-burgers)
- Add in monterey-burgers to our list of stops
Doing this accomplishes two things. First, it keeps the same stops determined in Part 1 assigned to each vehicle (because our drivers are particular about their assignments). Second, it creates the opportunity to integrate a stop for monterey-burgers into our overall solution that’s conveniently on the way for one of our vehicles.
Here is our new input file:
Here's the added stop with a newly calculated route:
As you can see, slipping monterey-burgers into bob's backlog is the best solution. It’s on his way! You may also note that, despite the fact that the added stop is only a very minor detour for tina's route in blue, bob was still assigned this stop. Recall that our default value function is focused on reducing total vehicle travel time, so this sequence of stops should provide the best solution to achieve that goal. Instead of making our best manual guess between two options that look fairly close, we can rest assured that a more efficient solution has been chosen by Nextmv.
Here's the updated route for vehicle bob (the added stop is starred):
bob:
- bacon-burgers →
- arugula-burgers →
- double-burgers →
- edamame-burgers →
- * monterey-burgers →
- cheddar-burgers →
- fried-burgers
Now, if a vehicle has been instructed to drive from point to point, one stop at the time, there's no discernible difference (aside from a little more travel time) between this route and the one we produced in Part 1. The monterey-burgers will appear as the stop following edamame-burgers without making drastic changes to the vehicle’s route.
We've now seen the backlog feature in action and used it to insert a stop when vehicles are just starting out on their routes. But my burger machinations aren’t complete yet…
Part 3: A fickle pickle - Inserting a new stop mid-route
This time I deliberated for a while before deciding on my latest culinary demand: pickle burgers. They are too good to pass up! But our vehicles are mid-route rather than at the start of their respective routes this time. How should they adapt?
Let’s say my latest order comes in as tina is picking up the latke burger and bob is picking up the edamame burger. That means the remaining backlog stops from the originally optimized route are:
tina:
- gruyere-burgers →
- jalapeno-burgers →
- kale-burgers
bob:
- monterey-burgers →
- cheddar-burgers →
- fried-burgers
To insert the new pickle-burgers stop into one of our vehicles’ flexible backlogs, we need to make a few changes to our input file:
- Update the backlog array for each vehicle with the remaining backlog stops (in keeping with driver preferences)
- Update the unique start location for each vehicle to that of their current stops (latke-burgers for tina and edamame-burgers for bob)
- Add in a unique shift start for each vehicle that corresponds to the estimated time of delivery (ETD) for their current stops (this can be found in the output JSON)
- Update capacity to accurately reflect the pickups they’ve already performed (e.g., tina has picked up 3 burgers, so her new capacity is 4)
- Add pickle-burgers to the list of stops
We end up with the following input:
This yields the following solution:
This change in course takes tina along a different route to the end position in order to swing by pickle-burgers but still ensures that each vehicle's original set of stops are included in their optimized route.
Well done! We've successfully (and efficiently) adapted mid-route to changes in pickup locations and with minimal disruptions to our vehicles using flexible backlogs.
Fixed vs. flexible backlogs: A comparison
At the beginning of this post, we touched on two approaches to backlogs: fixed and flexible. In this post, we walked through how to use flexible backlogs with Nextmv. But what if we had tried Part 3 using only fixed backlogs?
Let’s have a look! We’ll use the Haversine distance (“as the crow flies”) view in the map for dramatic effect. Using flexible backlogs, this is what our final solution looks like:
Stop 2 here represents pickle-burgers getting flexibly inserted into tina's route.
Using fixed backlogs, this is what our final solution looks like:
In the case of using a fixed backlog, tina would have had to backtrack from kale-burgers to pickle-burgers because our new stop would have been appended to the end of the route, rather than flexibly inserted into it.
Further reading
This concludes our exploration of flexible backlogs, but your journey doesn't need to end here. Other Nextmv features like precedence and penalties work alongside backlogs in order to permit you to find optimized routing solutions to a wide range of scenarios, so dive into the Nextmv documentation, videos, and other posts like this to find more ways that Nextmv can help you.
