Breaks and Time Window Optimization

During a route it may be desirable to schedule a break; for example for lunch, an appointment or to meet statutory requirements for driver rest periods.

GeoBase provides the Break class to generate these routing objects. Break objects can be at a defined (LatLon) location if the break location is known (for example at a particular depot) or without a set location if the break location is unknown (if, for example, a driver wants the destination to be private or the location of the break constantly varies).

In this section of the routing tutorial we will use the Break class to create a routestop Break.

The following code segment creates a Break object at a known LatLon location.

Caution
All times should be specified in UTC. A TimeZone object can be used to easily convert from UTC back to the local time zone.

// Create route stops 
RouteStop Depot = new RouteStop(new LatLon(34.1018, -118.2973));
RouteStop Cinema = new RouteStop(new LatLon(33.677948, -117.875051));
RouteStop Mall = new RouteStop(new LatLon(33.845914, -118.232105));
RouteStop Arena = new RouteStop(new LatLon(34.0720, -117.4962));

// Create a Break object
Break LunchBreak = new Break(33.63937, -117.94166);

// Add Break properties
LunchBreak.Description = "Lunch at Jim's Burgers";
LunchBreak.MinimumTime = new TimeSpan(0,10,0);
LunchBreak.AverageTime = new TimeSpan(0,30,0);
LunchBreak.RenderBrush = new System.Drawing.SolidBrush(Color.FromArgb(80, Color.Green));
LunchBreak.WindowStart = DateTime.Parse("11:00:00").ToUniversalTime();
LunchBreak.WindowEnd = DateTime.Parse("13:00:00").ToUniversalTime();
LunchBreak.Penalty = 10;

// Create a route
Route myRoute = new Route();

// Set the start location of the route
myRoute.Start = Depot;

// Add other route stops
myRoute.AddStops(new RouteStop[] { Cinema, Mall, Arena, LunchBreak });

// Optimize the route for a start time of 9am today
OptimizeResult myOptimizeResult = myRoute.OptimizeStops(DateTime.Parse("09:00:00").ToUniversalTime());

// Show the route on the map
Directions fastdirs = myRoute.GetDirections();
fastdirs.RenderColor = Color.Blue;
renderList.Add(fastdirs);

This example creates a break at a known location (33.63937, -117.94166). The break window is between 11am and 1pm with a minimum duration of 10 minutes and a typical duration of 30 minutes.

The route generated will appear as follows:

Tip
The numbers shown on the map relate to the order in which the stops are visited. The first stop in a route is green by default. Breaks are gray by default, but in the example above we have changed the break color to pale green.

With a 9am start, the calculated arrival times for the example route above are:

The total length of this route is approximately 2 hours and 11 minutes.

The routing engine has ensured that the break occurs within the available time window of 11am to 1pm. However, in the event of conflicting time windows the engine will give priority to stops or breaks with larger penalty values.

In this example only the break has an arbitrary penalty specified, giving it priority. Notice that it is also the only stop with a set AverageTime property (30 minutes). For all other stops, no time is spent onsite; they are simple drive-by deliveries. This means that the arrival time for each stop will be the same as the departure time.

We will now change the start time of the example route to 11am:

OptimizeResult myOptimizeResult = myRoute.OptimizeStops(DateTime.Parse("11:00:00").ToUniversalTime());

With this new start time the optimized route will be recalculated and shown as follows:

The route stops have been re-ordered to ensure the lunch break still occurs within its time window. Note that the total length of the route is now approximately 2 hours and 22 minutes, over ten minutes longer than the route with a 9am start.

If the break location is unknown, a Break object can be created using LatLon.Empty, as in the following example:

Break NoLoc = new Break(LatLon.Empty);

Note
Note that empty Break locations are not rendered on the map. They are not usable with a RouteMatrix, Route highlighting or Direction. If an empty Break occurs within a route that has been rendered on a map by calling the Route object's GetDirections it will be indicated by a missing routestop (eg. 1, 2, 3, 5, 6).

If the LatLon property is Empty, the break both begins and ends at either the last location visited before the break commenced or at the first stop following it unless its time window is completely within the driving time between the previous and next stops, in which case it begins at the WindowStart time. The break leg will be extended if necessary, pushing out the start time of the following stop.

If the StartTimeIsFixed property is true the break will start at the WindowStart time and the WindowEnd property will be ignored. If the AverageTime is less than the MinimumTime then the optimization algorithm will use the larger MinimumTime value to determine the stop's duration. Typically only the AverageTime property should be used to set the break duration.

Note

Breaks for which the StartTimeIsFixed property is true are still subject to prioritization based on penalty values. Their fixed start times may not be honored by the routing engine if doing so will reduce total route penalties. If two empty breaks with StartTimeIsFixed properties set to true conflict with one another (for example two empty breaks with AverageTime values of 30 minutes and WindowStart times of 9am and 9:20am), the first break (starting at 9am in this example) will be given priority.

If the break location is known and the TimeIncludesExtraTravel property is true, any additional travel time required exceeding that needed to travel directly between the routestops immediately preceding and following the break is taken out of the break time. That is, any extra travel time is taken out of the driver’s allocated break period up to the MinimumTime value.

MinimumTime is always honored, even if the combination of travel time and minimum time are greater than the allocated break time. The route leg is simply extended.

Leg without break

[Location 1] --[30 Minutes of Travel]--> [Location 2]

Leg with break

[Location 1] --[20 Minutes of Travel]--> [Break Location (30 min av.)] --[20 Minutes of Travel]--> [Location 2]

In the example above, if the AverageTime break period is 30 minutes, only 20 minutes will be available at the break destination (assuming the MinimumTime is 20 minutes or less). With the break present, the total travel time from location 1 to 2 is 40 minutes rather than the 30 needed without it. The extra 10 minutes of travel will be taken out of the driver's allocated break time.

Note

The Penalty property determines the priority of the break event. This penalty is incurred if the time window is missed. If the break is a high priority, such as a medical appointment or regulated rest period, a high penalty should typically be set. For lower priority breaks, other stops may have higher penalty values. Penalty's default value is -1, indicating that it has not been set and will not be used. IdlePenalty may also be used to specify a penalty value for a vehicle that arrives too early at its destination (that is, a vehicle that must sit and wait before its delivery window). This value should be greater than or equal to zero. A value of -1 indicates that the idle penalty is not set and will not be used. The IdlePenalty value is taken into account by the optimization algorithm during route optimization, together with the Penalty value.

The route engine calculates a suitable route that optimizes stop and break ordering based on time windows and penalties.

Note
If calculating the total distance or time of a route containing breaks using GetTotalTime() or GetTotalDistance it is important to note that GetTotalDistance includes only known route leg lengths. It does not include legs that contain breaks at unknown locations. GetTotalTime() does not include time spent at stops (MinimumTime or AverageTime) and treats all stops as drive-by deliveries.

// Total route travel time excluding duration of stops
TimeSpan time = fastdirs.GetTotalTime();
// Total route travel distance excluding empty break legs
double totalDistance = fastdirs.GetTotalDistance(DistanceUnit.KILOMETERS);