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

May 26, 2021

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.

blog-vehicle-routing-problem-dispatch-app-input-json-constraints-nextmv-cloud-v1

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?

blog-nextmv-dispatch-order-three-unassigned-routing-problem

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.

blog-nextmv-dispatch-order-three-assigned-routing-problem

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.

Featured posts