HMoe-esristaff

Fleet Routing with the VRP Solver: Time Windows

Blog Post created by HMoe-esristaff Employee on Sep 25, 2018

More and more companies need to incorporate appointment times or time windows into their routing solutions.  The 30-minute guarantee isn’t just for pizza delivery anymore.  We will discuss the basics of time windows in the VRP solver and how to prioritize their importance.

 

The Basics

Time windows are a way to indicate when the route/driver should arrive at that order location.  The VRP Solver supports two time windows per order.  If the beginning time for a time window is left null, then it will correspond with starting at the earliest start time of the earliest route.  Similarly, if the ending time for a time window is left blank, then it will correspond with the latest ending of the last route.

 

Unless using the Rest Request system, the time window fields are set up to accept either just time or time and date.  If it is just the time then it is assumed to be on the default date.  If using both date and time be sure to use both date and time in all time fields in Orders, Depots, Routes, and Breaks.  The Rest Request system requires that all times are in milliseconds since epoch (which is January 1st 1970).  It, therefore, will inherently have both date and time.

.

Note: Time windows do not include when the drivers should be done at that location, ready to go to the next location.  It is only when they should arrive at the location.  If you need to model it so that the driver leaves within a certain time, then for your time windows subtract the service time from the TimeWindowEnd value. This allows for if the driver was to show up right at the end of this modified time window they would be completed with the service time and leaving right at the end of the original time window.

 

Hard vs. Soft Time Windows

Hard time windows mean that the route/driver must show up during the designated time frame of the time windows.  A soft time window, on the other hand, allows the route/driver to show up late but the violation is penalized in the solver so that violation times are minimized.  To indicate that the time window is hard set the corresponding MaxViolationTime to zero.  Leaving this value as null makes it a soft time window.  Giving a positive value for MaxViolationTime makes it a soft time window within a hard time window.  This means the route/driver can be late to that location, incurring the violation penalty, but only up to the MaxViolationTime.  At that point it is a hard time constraint.

Time window fields in the orders attribute table.

 

Prioritizing Time Window Violations or Total Cost

When setting up a problem with soft time windows you have the option to identify how much priority you want to place on minimizing the time window violation time vs minimizing the total cost of the routes (which includes the total time and total distance for all of the routes).  These two priorities are usually working against each other.  Minimizing or eliminating time window violations usually requires higher costs because.  This is because the shortest tour amongst all of the stops will likely not satisfy the time windows.  To indicate the preference for the VRP problem use the parameter Time Window Violation Importance.  There are three options for this parameter: Low, Medium, and High.

  • Low - Prioritizes minimizing the total cost over the time window violations
  • Medium - Tries to find a balance between the time window violations and added cost
  • High - Minimizes the time window violations at the expense of added cost

 

Time Window Violation Importance field in the Solve VRP GP Tool

 

Time Window Violations Importance Field in the Advanced Settings of the VRP layer properties.

 

Geo-Local or UTC Time

When using the UI in ArcMap for VRP layers or the GP tools in either ArcMap or ArcGIS Pro it is natural to type in the time fields using the local time for that location (Geo-Local).  However, when switching to the rest request method those times need to be converted to milliseconds since epoch.  This UNIX way of representing time has a strong convention of referencing time based on UTC. Therefore, most conversion methods convert those times using UTC instead of Geo-Local.

 

The VRP Solver allows for some flexibility in specifying time.  It allows the option of having that input as a Geo-Local time as well as UTC. You, therefore, need to specify which format is being used.  This is done with the parameter time_zone_usage_for_time_fields with the two parameter options of GEO_LOCAL or UTC.  Setting this parameter is only available in the GP tools or the rest request and it defaults to Geo-Local.  When using the VRP layers in ArcMap there is no way to switch it to using UTC.

 

Time Zone Usage for Time Fields field in the Solve VRP GP Tool.

 

Get Involved

When using soft time windows and a violation is needed, would you prefer to see one order with a larger violation or several orders with smaller violations?  Click here to answer.

 

How many time windows do you want to model?  Click here to answer.

Outcomes