When it comes to optimizing decisions, the ability to express important details can often mean the difference between a solution that just manages to get the job done versus one that ends up saving a significant amount of time and effort. With vehicle route optimization, if drivers can satisfy route constraints by visiting one of several similar stops — for example, a driver acquiring a bag of ice from one of a dozen potential pickup locations instead of a single one — this grants greater flexibility for potential routes that maximize the chance for better solutions.
We refer to this flexibility in choosing one stop among a set of many candidates as alternate stops in the Nextmv API. While this capability is sometimes generally referred to solely as "breaks" in the routing space, alternate stops with Nextmv are sufficiently powerful that you're not constrained to just modeling driver breaks: any set of stops can be grouped under alternate stops for a variety of potential use cases to help provide effective solutions.
Today we'll explore the Nextmv alternate_stops feature, why it's useful, and how to put it into practice.
Leaving the nest: A VRP with one driver
We'll begin with an example scenario to illustrate the utility of alternate_stops and dig in deeper once we're comfortable with the basics.
We've highlighted some traditional use cases for this feature – like breaks stops for delivery drivers – but we're going to leverage the power of alternate_stops in order to highlight it for an entirely different space: birdwatching.
I've been a birdwatcher for most of my life, and there's more strategy to it than you might think. While some of the more everyday species are easier to find, spotting uncommon birds on your own or with a group of birders to help can be a challenge. If you're after a rare warbler or songbird during the migratory season, you'll need to strategically choose when to look, where to look, and maybe even leverage some of the modern tools that birders use to share rare sightings in a given area.
Let's frame a birdwatching trip as a routing problem that we can translate into Nextmv input JSON. I'll also set the stage at a place I’ve birdwatched before: University of North Carolina at Chapel Hill.
We'll begin our excursion on UNC campus at the old well at 7:00 AM to capitalize on the flurry of bird activity near dawn. Imagine that we're using crowdsourced data to pinpoint where certain species of birds have been cited in the area. Instead of working within a constraint like precedes or succeeds, which for example, would require that we visit a pick-up location before a drop-off location, we'll express in JSON that there are ideal times early in the morning that some rare birds we'd like to catch sight of may appear. We can satisfy that requirement using target_time for a given stop and encourage any potential solutions to visit these stops in a timely manner by attaching a lateness_penalty to the location. (Configuring earliness and unassigned penalties are also options for these types of problems, but we’ll keep our setup simple for now.) Because we’re using Nextmv Cloud, our value function will look to minimize time on road for each route.
For this initial problem input, we'll skip any alternate_stops for now to keep it simple. Given a driver named audubon who starts their shift at 7:00 AM, we’ll forego any quantity settings (because we're neither picking up nor dropping off items) but we will indicate five-minute stop durations which permits enough time to sight and record any birds. Additionally, we define a few birdwatching stops with penalties to express that there's an ideal time that the bird will be visible. After each indicated target time, the likelihood to spot the indicated bird drops off significantly. To make our stops descriptive, we'll format each stop as <bird species name>@<location> – we'll make use of different locations a little later.
Here's what our complete input JSON looks like:
The following solution offers the optimized route:
This solution has some interesting properties. The input JSON expresses that there are a few locations with early times where birds are present and able to be seen. For example, the summer-tanager@pine-tree is best seen before 7:05 AM while the pine-warbler@bush is most visible before 7:10 AM, both of which are shortly after the audubon driver begins their shift. However, because these stops are at either ends of the route area, our driver suffers a hard-to-avoid penalty: sending them to one stop forces them to arrive late at the other.
Consider the Solution Value Composition graph which concisely summarizes that our best route (Solution 5) suffers a lateness penalty, regardless of the fact that it represents the best option given all constraints:
This graph visualizes a lateness penalty of 7,745 and a total vehicle travel time of 3,741 seconds. The input JSON presents a challenging problem that can't avoid a lateness penalty entirely due to the target_time and lateness_penalty values attached to certain stops.
With ten stops to visit and some stops critical to visit in a timely manner, what options do we have to find even better solutions?
Early birds: A VRP with two drivers and break locations
Recall that the canonical example for using alternate_stops is for driver breaks – that given a set of stop locations, alternate_stops lets us express that one stop out of many can satisfy a driver's requirement for one break during a route. Another driver – whose name is darwin – is available to help us in the morning, but isn't an early riser and needs a morning coffee break. Our driver isn't picky, though – any coffee shop along their route will do (we'll withhold judgment for taste in coffee… for now). If we can add a second driver to the route, we may be able to split the required stops between them and reach the desired stops in time and avoid any lateness penalties.
This is an excellent opportunity to use alternate_stops. Given a choice of three potential break locations for the new driver, we can indicate that stopping at any one of them satisfies the driver's requirement for a coffee break. We implement this strategy by making the following changes to the input JSON:
- Add a new vehicle with an id of darwin and set the vehicle's alternate_stops to three named stops. The solver will consider a solution complete as long as the route for this vehicle visits one of these stops.
- Populate the alternate_stops field with the associated stop location information for the stops we just added to the darwin vehicle.
The input JSON becomes:
Our new solution with an additional driver that takes one coffee break yields the following route:
As you can see, both drivers take a portion of the stops – audubon along the route outlined in blue and darwin along the orange route. Let's inspect the Solution Value Composition:
There's no longer a lateness penalty for our best solution (Solution 12)! This indicates that our new solution with an additional driver satisfies the desired target_time constraints and all of the birdwatching spots are visited at their ideal times.
Although this is a longer total travel time (4,004 seconds) than our original, single-driver scenario, the solution honored the lateness_penalty values that we set on particular stops, so Nextmv has correctly prioritized for the desired outcome (arriving at each stop on time). After finding a solution that negates that penalty weighted at 5 given our input JSON, later solutions seek to minimize total travel time.
This example demonstrates the driver break use case for alternate stops, but we can explore this feature further for even better results.
A wild tanager appears: A VRP with one driver and alternate sighting locations
Let's return to the original input: one driver visiting ten stops. Can we find a solution that both avoids a lateness penalty and reduces travel time even further?
While we can find a summer-tanager at the pine-tree stop, imagine that we've been told that the bird has been sighted at another spot in the surrounding area. This bird appears at a bird feeder and can be reliably seen as long as we arrive before 7:30 AM. We now have two alternate stops that satisfy the need to spot a Summer Tanager!
Let's modify the input data accordingly. To codify this changed situation, we will:
- Remove the summer-tanager entry from stops.
- Enter the stop we just removed as well as the brand new feeder location to the top-level alternate_stops field.
- Attach the alternate_stops field to our vehicle with each of the two alternate stops.
The two new stops in our data are summer-tanager@pine-tree and summer-tanager@feeder. The revised input data looks like this:
Here's what the updated solution looks like for a single vehicle using alternate stops.
This already looks quite a bit different from either the original route or two-driver route! The Solution Value Composition is even more interesting:
This solution that takes advantage of an alternative stop for one vehicle achieves zero lateness penalty and a shortened trip time of 3,607 seconds! The benefits of an additional stop here are evident and have helped us find a much more efficient route. You can imagine how you might extend this example further given new information. For example, if Summer Tanagers appear at additional locations, adding stops to the alternate_stops field can introduce more options to satisfy the stop requirement.
Even More Alternatives
This post has introduced alternate stops with two use cases that are equally well-served by Nextmv's alternate_stops feature. Take a look at the alternate stops page in the Nextmv documentation to learn more about the different settings that are available beyond just target_time like hard_windows. Happy routing!
Banner image credit: National Gallery of Art
.jpg)
