Exploring time windows, timeliness penalties, and unassigned penalties for routing on Nextmv Cloud

Learn how to route a fleet of vehicles while working with time windows, time penalties, and unassigned penalties using the Dispatch app on Nextmv Cloud.

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 measured in seconds and represented as the `value` in Nextmv Cloud. 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 Data, 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.

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:

  1. Change our default speed from 20 m/s to 25 m/s (for a bit more oomph!)
  2. Pare down the input to 2 vehicles and 13 stops (representing a total of 5 orders). Do this by deleting lines 222 through 714 and then 31 through 82 from the input file.

Now, click the teal “Run” 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, scroll down to our Output Data located below the map. Click into `state` and expand each of the sections. Within `vehicles` we learn the following about the routes:

  • 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 under the `unassigned` section of the output. And based on what we covered in the defaults, this means we’ve incurred an unassigned penalty.

To see the impact, click into `value_summary`. You’ll see a list of several fields and values. For now, let’s focus on a few. We can see that `total_unassigned_penalty: 600000`, which accounts for 3 unassigned stops multiplied by the unassigned penalty of 200,000 seconds we set in the default. This means if our fleet had visited those 3 stops, our `value: 620284` would be 600,000 seconds smaller. 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”. 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 it’s decreased to 27,574 seconds and our unassigned penalty dropped to 0. This is a lot better compared to our previous value of 620,284 seconds!

But why didn’t the value drop by a clean 600,000 seconds? 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`. Let’s have a look at the earliness penalties we have for our current scenario. In the Output Data, we can see that we incur a `total_earliness_penalty` of about 7,091 seconds. If you really dig into the details of the output for each `vehicle`, you’ll learn that this is derived from the dropoff stops for orders 1, 2, and 3.

Our current value in this state is 27,574 seconds. What if we zeroed out our earliness penalties? Let’s try. Set the `earliness_penalty: 0” in your input in the default section. Now click “Run”. Once the job is complete, view the output, and you should see our new value is 20,484 seconds — essentially 7,091 seconds less than our value before.

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.

Get the latest updates
Copy to clipboard
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Register to watch
Copy to clipboard
Thank you! Your submission has been received!
Oops! Something went wrong while submitting the form.
Video by:
No items found.