Nextmv Cloud is the fastest way to get hands on with the Nextmv decision stack. Our Dispatch app on Nextmv Cloud offers an out-of-the-box experience for route planning and optimization and supports a growing list of common constraints for representing the reality of your business.
In a previous blog post, we explored a few common routing problem constraints, such as capacity and speed. In this post, we’ll explore target times, hard time windows, timeliness penalties, and unassigned penalties.
If you haven't already, sign up for a free Nextmv Cloud account and follow along!
Hello, input file and blank map, my old friends
When you log into Nextmv Cloud, you’ll land on the page with an input data selector and an empty map. This is the place where many routing problems — great and small — begin.
Within our Dispatch app, we’re optimizing for a KPI or business objective that minimizes our fleet’s combined travel time. This is called the value function and is measured in seconds. Several factors contribute to total travel time, including vehicle speeds, how long a vehicle spends at each stop, how punctual a vehicle is at each stop, and/or if a stop doesn’t get assigned to a vehicle. We’ll be keeping an eye on each of these as we walk through this example.
OK, let’s dive in. Under Input Dataset, choose the file called “Fleet with Pickup/Delivery & Time Windows.” You’ll see a new input file appears and includes several default settings that apply default properties to all vehicles and stops.
.png)
For our vehicles, there’s a defined start and end location (they’re the same in this case, so it’s a depot scenario), a shift start and end (amounting to a two-hour window), and average vehicle speed (in meters per second).
For our stops, there’s a defined stop duration of 120 seconds and several penalty fields that follow, including:
- `unassigned penalty`: The cost applied to the value function in seconds for not visiting a stop. While the units here don't measure an actual span of time for not visiting a stop, it provides a way to represent the severity of missing a stop in the final value function.
- `earliness penalty`: The cost applied to the value function for arriving at a stop too early and having to wait. This is a scalar value that's applied to every second before a target time.
- `lateness penalty`: The cost applied to the value function for arriving at a stop too late. This is a scalar value that's applied to every second beyond a target time.
We’ll come back to the specifics of these penalties shortly.
We now have an understanding for our default settings. Let’s do two more things:
- Change our default speed from 20 m/s to 25 m/s (for a bit more oomph!)
- Pare down the input to 2 vehicles and 13 stops (representing a total of 5 orders). Do this by deleting lines 222 through 715 and then 31 through 82 from the input file.
Now, click the teal “Run App” button. You should see routes (generated using a Haversine measure) appear on the map. But it’s also clear that our order fulfillment didn’t exactly go according to plan. Curious... Let's see what happened.
A case of unassigned stops
In our input file, we are looking to route 2 vehicles to visit 13 stops, which represents 5 orders. The resulting routes on the map show us that the 3 stops for order 3 do not get visited. What happened?
To investigate, you can mouse over the stops on the map and see that order 3 is not serviced. You can confirm this by expanding the routes for each vehicle to see that:
- Vehicle 1 started at the depot, picked up order 2, picked up order 1, dropped off order 2, dropped off order 1, and then returned to the depot.
- Vehicle 2 started at the depot, handled order 4, then order 5 (with three pickups), and then returned to the depot.
So we’ve confirmed that no vehicles handled order 3, which consisted of three stops (2 pickups and 1 dropoff). This means order 3 was unassigned. This is also reflected in the Solution Value Composition Chart. You can see that a total unassigned penalty of 600,000 is applied to each solution, including the best one found. If those 3 stops were assigned, our overall solution value would decrease by 600,000 seconds. Let’s put this to the test by assigning order 3.
First, we need to understand why the order 3 stops weren’t assigned. If you have a detailed look at the vehicle and stop details in the input file (which we’ve not thus far), you’ll see we have a capacity issue. Our vehicle capacities are set to 85 units. Order 3’s pickups total 156 units. Our vehicles couldn’t accommodate those quantities, so those stops went unassigned.
While this may not be exactly what you’d do in the real world, let’s change both vehicle capacities to be 160. Click “Run App”. You should see the following:
- Vehicle 1 started at the depot, handled order 3, then order 4, and then returned to the depot.
- Vehicle 2 started at the depot, handled order 1, then order 2, then order 5 (with three pickups), and then returned to the depot.
And if you look at the value function, you’ll see that it has decreased and our unassigned penalty dropped to 0.
But what are those other penalties that are being applied to the value function? To understand this, let’s have a proper look at the earliness and lateness penalties.
Earliness and lateness penalties
At the start of this post, we reviewed the information in the defaults section of the input file and deleted a bunch of vehicle and stop information. But we didn’t look too closely at the details of what remained. That time has come.
The `vehicles` section of the input is familiar to us since we just modified the vehicle capacity. Let’s look at the `stops` section. The stops for each order contains the following information:
- id` to uniquely identify the stop using free-form text (useful for denoting pickups and dropoffs)
- `position` of the stop using geo coordinates
- precedes` to specify if a stop must precede another (when multiple stops share the same value for precedes, it indicates multiple pickups before a dropoff)
- `quantity` indicating how many units will be picked up (a negative value to indicate consuming capacity from a vehicle) or dropped off (a positive value to indicate returning capacity to a vehicle)
- `target_time` to specify the date and time when the vehicle ideally visits the stop
- `hard_window` to specify a date and time range for when the vehicle must visit the stop
We know that earliness and lateness penalties are calculated using a scalar that’s applied to every second a vehicle arrives at a stop before or after a defined `target_time`. Try modifying or zeroing out these penalties to see how it impacts your routes and overall value function.
What’s next?
This post explored timeliness penalties that account for earliness, lateness, and unassigned stops that you can configure with the Dispatch app on Nextmv Cloud. In future posts, we’ll explore other constraints such as compatibility attributes for defining delivery zones or ensuring ice cream gets picked up by a vehicle with a freezer), in addition to ways to evaluate the outputs that make up the overall value function. This includes the makeup of penalties in your final solution and how long you let your app run impacts the quality of solutions over time.
We’re incorporating new functionality all the time to help you reflect the reality of your business and streamline the decision-making workflows that power it. Let us know what you’d like to see us add to Nextmv in the future by contacting us.
