(Not Signed In)

Sign In

Resources

Delivery time windows

Overview

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

This topic does not describe how to create a complete time window-based routing application. However, all necessary code examples are provided, allowing you to quickly add time window functionality to your own routing application.

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).

Creating a RouteStop object with a time window

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

All times should be specified in UTC. The DateTime.ToUniversalTime() method will convert from local time to UTC. To convert from UTC back to the local time zone use the Telogis.GeoBase.TimeZone object's ConvertTime() method.

// the RouteStop object is found in the Telogis.GeoBase namespace
RouteStop rs = new RouteStop();

// customer's address - we could use the geocoder to obtain these 
// LatLon coordinates from a textual address (in this case,
// "85 enterprise, aliso viejo, ca 92656")
rs.Location = new LatLon(33.5817,-117.7272);

// the Tag property can be set to any object you wish, 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-866-TELOGIS";

// an average of 12 minutes is spent unloading and loading materials
// at this stop. this is important for time window calculations.
rs.AverageTime = 12;

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

// ...and the customer is available only before 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 local time -- but the
// parameter given to OptimizeStops() must be specified in UTC
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.

Optimizing a Route object with time windows

Create the Route 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.

// 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";

// 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.

 
Stop Arrival time
Depot 9:00:00 AM
Stop A 9:13:49 AM
Stop B 9:30:32 AM
Stop C 9:54:44 AM
Stop D 10:11:12 AM
Stop E 10:16:54 AM

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

Optimizing the Route object for time windows

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.

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

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.

Stop Arrival time
Depot 9:00:00 AM
Stop A 9:13:49 AM
Stop B 9:37:47 AM
Stop C 9:43:51 AM
Stop D 9:59:52 AM
Stop E 10:23:45 AM

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);
}

Analyzing the OptimizeResults objects

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:

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:

Clearly not all time windows can be honored because the fastest route between all the stops is 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 = stopF.WindowStart = DateTime.Parse("09:45:00");

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

// 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.

This code snippet uses the GetStops method to retrieve all the stops. 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.

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.

Stop Violation Arrival Delay/Wait
Depot None 9:00:00 AM  
Stop A TooEarly 9:38:15 AM Wait for 00:06:44
Stop B None 10:01:28 AM  
Stop C None 10:07:10 AM  
Stop D TooLate 10:31:09 AM 00:16:09 late
Stop E TooLate 10:47:53 AM 00:32:53 late

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.

Conclusion

This topic has demonstrated how to:

The Map Explorer sample application (included with your Telogis 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.

 

Published, Aug 3rd, 13:55

Tagged under: routing route optimization maps