Delivery Time Windows

GeoBase provides advanced routing services which enables routes to be optimized using many different criteria. These criteria include:

• Vehicle attributes (such as the height and size of the vehicle)
• Physical attributes of the road (such as the number of lanes and speed limit)
• Traffic conditions (either real-time, historical or predicted)
• Delivery time windows (specifying a time window in which each stop must be visited)

This topic describes how to optimize a route using time windows, with relevant code examples. A time window is a specified time period in which the stop must be visited (such as between 9am and 5pm, or between 2pm and 4pm). GeoBase can then plan the route to ensure that each stop is visited only within its time window.

Time windows are especially useful in situations where deadlines are important (such as utilities, repair companies and delivery services).

Each RouteStop object has a WindowStart and WindowEnd property. These properties should be set to DateTime objects representing the time and date of the start or end of the stop's time window. A penalty can also be assigned to each stop using the RouteStop object's Penalty property. A more important time window should be given a higher penalty value.

The RouteStop object's IdlePenalty property 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 following code snippet creates a RouteStop object that represents a customer that is available only between 10am and 1pm.

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.

// The RouteStop object is found in the Telogis.GeoBase namespace.
// The LatLon location used to create the route stop is the customer's 
// address. We could use the geocoder to obtain these
// LatLon coordinates from a textual address (in this case,
// "20 enterprise, aliso viejo, ca 92656")
RouteStop rs = new RouteStop(new LatLon(33.5846,-117.7325));

// The Tag property can be set to any object you want, in this case
// we'll use the customer's phone number. When the stops are rearranged
// by GeoBase the Tag property can be used to identify each stop
rs.Tag = "1-234-567890";

// An average of 12 minutes is spent unloading and loading materials
// at this stop. This is important for time window calculations.
rs.AverageTime = new TimeSpan(0, 12, 0);

// The customer is available only after 10am. Note that this time
// is specified in UTC. We use the DateTime.ToUniversalTime() method
// to convert from local time to UTC.
rs.WindowStart = DateTime.Parse("10:00:00").ToUniversalTime();

// And the customer is able to accept deliveries that begin as
// late as 1pm; again this time is specified in UTC.
rs.WindowEnd = DateTime.Parse("13:00:00").ToUniversalTime();

// The penalty, if we can't visit the customer in the given time window.
rs.Penalty = 10;

If this customer is part of a route (named myRoute, in the code snippet below) GeoBase can rearrange the stops on the route to ensure that this customer is visited between 10am and 1pm. The code snippet below demonstrates this:

// We'll assume that our route starts at 9am
DateTime routeStartTime = DateTime.Parse("09:00:00").ToUniversalTime();

// Rearrange the stops to ensure that all time windows (if 
// specified) are honored.
OptimizeResult myOptimizeResult = myRoute.OptimizeStops(routeStartTime); 

// The OptimizeResult object contains information about the optimization
// process, such as stop arrival and departure times. In some situations
// it may be impossible to honor all the time windows, in which case the
// OptimizeResult object can be used to determine which time windows
// could not be honored.

The remainder of this topic provides detailed examples of how to specify time windows and analyze the OptimizeResult object.

First create a Route object containing the stops. The following code snippet creates a route with six stops. Note how the Tag property of each RouteStop object is used to identify the stop.

Tip
The Creating a Route topic describes how to create a Route object from a series of RouteStop objects.

Caution
In this example we assume that no time is spent at each stop: it is a simple drive-by delivery. This means that the arrival time for each stop will be the same as the departure time. If your scenario has a time delay at each stop for unloading or loading of goods, be sure to set the AverageTime property for each stop to the number of minutes spent unloading/loading at that stop.

// Create the stops
RouteStop stopDepot = new RouteStop(new LatLon(33.581650, -117.727285));
stopDepot.Tag = "Depot";
RouteStop stopA = new RouteStop(new LatLon(33.677948, -117.875051));
stopA.Tag = "Stop A";
RouteStop stopB = new RouteStop(new LatLon(33.857584, -117.771324));
stopB.Tag = "Stop B";
RouteStop stopC = new RouteStop(new LatLon(33.966639, -118.078888));
stopC.Tag = "Stop C";
RouteStop stopD = new RouteStop(new LatLon(33.845914, -118.232105));
stopD.Tag = "Stop D";
RouteStop stopE = new RouteStop(new LatLon(33.833026, -118.190407));
stopE.Tag = "Stop E";

// Don't forget to set the average time spent at each
// stop (through the RouteStop.AverageTime property) if 
// you need time to load/unload goods...

// Create the route containing the six stops defined above
Route myRoute = new Route();
myRoute.Start = stopDepot; // always start at the driver's depot
myRoute.AddStops(new RouteStop[] { stopA, stopB, stopC, stopD, stopE });

Calling the Route object's GetDirections method will return the route shown below.

The numbers shown on the map relate to the order in which the stops are visited.

The arrival times for each stop are shown in the table below.

Note the total length of the route is approximately 1 hour and 17 minutes.

The following code snippet modifies Stop E to have a time window of 9.30am - 10am. There is an arbitrary Penalty if this stop is not visited within the specified time window.

Tip
It is not necessary to set a time window for every stop.

stopE.WindowStart = DateTime.Parse("09:30:00").ToUniversalTime();
stopE.WindowEnd = DateTime.Parse("10:00:00").ToUniversalTime();
stopE.Penalty = 10;

Optimize the route for the given time window using the code snippet below.

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

Note how GeoBase has reordered the route to ensure that Stop E is visited between 9.30am and 10am.

The arrival times for each stop are shown in the table below. This route is 7 minutes longer than the previous route and the last four stops on this route are in a different order.

The code used to generate the arrival information was:

foreach (OptimizedStop os in myOptimizeResult.GetStops()) {
    String tag = (string)os.RouteStop.Tag;
    String arrival = os.ArrivalTime.ToString();
    Console.WriteLine(tag + ", " + arrival);
}

The OptimizeResult object returned by OptimizeStops contains an array of the original RouteStop objects as OptimizedStop objects. Each OptimizedStop object contains a number of properties that provide useful information, such as:

• Arrival and departure time for each stop
• Whether the time window constraint was honored or not
• How long the driver needs to wait at the stop before the time window starts
• How late the driver will arrive at the stop after the time window ends

The OptimizeResult object allows you to determine if it is possible to honor all the time windows on the route. In some situations it may be impossible to visit every stop within its time window.

The following scenario will be used to demonstrate the OptimizeResult object:

• All stops must be visited between 9.45am - 10.15am
• Stops A, B and D represent standard deliveries. These stops have a small penalty.
• Stops C and E represent time-critical deliveries. These stops have a large penalty.

Note
Clearly not all time windows can be honored because the fastest route between all the stops is 1 hour and 17 minutes long. The time window is only 30 minutes wide. GeoBase will optimize the order of the stops to meet as many time windows as possible, while minimizing the total penalty.

The following code snippet modifies the stops to match the scenario described above.

// can't deliver before 9.45am...
stopA.WindowStart = stopB.WindowStart = stopC.WindowStart = stopD.WindowStart
    = stopE.WindowStart = DateTime.Parse("09:45:00").ToUniversalTime();

// can't deliver after 10.15am...
stopA.WindowEnd = stopB.WindowEnd = stopC.WindowEnd = stopD.WindowEnd
    = stopE.WindowEnd = DateTime.Parse("10:15:00").ToUniversalTime();

// stops A, B and D have a small penalty
stopA.Penalty = stopB.Penalty = stopD.Penalty = 10;

// stops C and E are time-critical. their per-minute waiting cost 
// is 50x higher than stops A, B and D
stopC.Penalty = stopE.Penalty = 500;

The following code snippet will use the optimization results to display the tag for the stop, the arrival time at the stop, the departure time, time window violation and any waiting or delay time in the optimized schedule. We can use this output to determine if the schedule is possible and the estimated arrival times for each stop.

Tip
This code snippet uses the GetStops method to retrieve all the stops, in the order that they are scheduled. You can use the GetViolatedStops method to retrieve only the stops with violations.

// We'll use this TimeZone object to convert from UTC back
// to our local timezone
Telogis.GeoBase.TimeZone tz = new Telogis.GeoBase.TimeZone();

foreach (OptimizedStop os in myOptimizeResult.GetStops()) {

    // The tag we set earlier ("Stop X").
    // This allows us to compare the ordering of the stops
    // in different routes.
    String tag = (string)os.RouteStop.Tag;

    // Any problems when honoring the time window?
    // One of: 'None', 'TooEarly' (driver arrives before the
    // time window starts), 'TooLate' (driver arrives after
    // the time window ends)
    String violation = os.Violation.ToString();

    // arrival and departure times
    DateTime arrivalTime = tz.ConvertTime(os.ArrivalTime);
    String arrival = arrivalTime.ToString();
    String departure = arrivalTime.Add(os.RouteStop.AverageTime).ToString();

    Console.WriteLine(String.Format("{0} - {1}. Arrive at {2}, depart at {3}", 
        tag, violation, arrival, departure));

    // os.TimeWaiting will be greater than 0 only if the driver
    // is scheduled to arrive before the time window starts
    // (this is a "TooEarly" violation)
    if (os.TimeWaiting.TotalSeconds > 0) {
        Console.WriteLine(String.Format("Driver will have to wait for {0}", os.TimeWaiting.ToString()));
    }

    // os.TimeDelay will be greater than 0 only if the driver's 
    // arrival at the stop is delayed due to scheduling constraints
    // (this is a "TooLate" violation)
    if (os.TimeDelay.TotalSeconds > 0) {
        Console.WriteLine(String.Format("Driver will be {0} late", os.TimeDelay.ToString()));
    }
}

The output of this scenario is shown below.

Only Stop C, Stop D and Stop E are visited within the specified time window. These three stops include the two stops with the highest penalty (Stop C and Stop E, which are time-critical deliveries).

When a driver arrives at a stop early GeoBase will schedule the driver to wait until the start of the stop's time window. Stop C requires a wait of approximately 7 minutes before the start of the time window.

Note
Wait time is unproductive. Because of this, GeoBase considers wait time to be a TooEarly violation.

Stop A and Stop B are scheduled too late. However, Stop C and Stop E (the two time-critical deliveries) are both scheduled by GeoBase (with appropriate wait times) to fall within the time window.

GeoBase intelligently places Stop D between Stop C and Stop E to avoid backtracking.

Tip
The delay times and arrival estimates can be used to provide the customer with an ETA. This is especially useful when a delay is expected.

This topic has demonstrated how to:

• Create a RouteStop object with a time window.
• Optimize the arrangement of stops in a Route object to honor time windows.
• Get and inspect the results of the optimization process to find time window violations, arrival/departure times and delay/wait times.

The Map Explorer sample application, included with your GeoBase installation, provides a complete and functional demonstration of time windows. Create a RouteStop by right-clicking on the map and selecting Route | Add as Stop. Then right-click the RouteStop and select Set Time Window to modify the start and end times of the window, the penalty and the average time spent at the stop.