Advanced Route Optimization

Overview

Advanced Route Optimization provides the ability to accurately schedule a mobile worker to arrive at a location within a precise time window.

Combining CoPilot’s routing algorithms with the preferences and predefined Service Level Agreements (SLAs) stored in back office planning systems provides an output of highly accurate ETAs. These ETAs can then be shared with customers in advance, providing the option to schedule a visit by time, day or location.

Advanced Route Optimization requires an additional license attribute. Please speak to your Trimble Maps account manager if you are interested in using this functionality.

All CoPilot releases include a basic Optimization option. Taking each location and using a straight-line method, it simply puts the stops in a logical and efficient order.

CoPilot Advanced Optimization offers a few major enhancements to the basic optimization:

1. Road Distances are used to calculate the optimized route.
2. Time restricted windows are taken into account, for example pre-10am or 10am-12pm.
3. Break times can be scheduled.
4. Non driving time—for instance the time taken to make the delivery—can be included to enhance the ETA accuracy.

Step-By-Step Advanced Optimization Process

1. Geocoding. Prior to any route sequencing CoPilot needs to determine all lat/lon locations for every stop. Any non-geocoded destinations will be removed from the trip list.

2. Grouping of stops. The grouping is determined by a number of factors including nearby location and time windows.

3. Optimize groups, using by road distance for ETA calculation. Optimize the groups.

4. Optimize stops inside each group. Following the optimization of the groups, it is now time to optimize the stops within the groups to find the most efficient way to reach each destination.

5. Generate an ETA for each stop. Once all stops are in order the ETA can be generated taking into account any wait time or break times included. These are then returned to the integrated application.

Rules for Advanced Optimization

• Time windows need to be feasible. If the driver leaves the depot at 8:30am for a 40-minute drive to reach a pre-9am, this would not be feasible.
  • Infeasible routes will increase the time to optimize as CoPilot will rerun the optimization many times trying to find a feasible route.
  • The infeasible destination will be delivered at the time closest to the window.
• Destination open and close window time should be greater than 30 minutes.
  • Preferably at least 1 hour to make an achievable route.
• Max 200 stops.
• Optimization can take between one and 10 minutes based upon the complexity of the route, the device processing power and other applications also running at the same time.
• Optimization should not be requested when CoPilot is navigating. If the driver is out of the depot and requires re-optimization it is recommended this happens during the device downtime such as a break time.
• CoPilot Advanced Optimization has been created as a one driver, one day route optimization. It does not replace any system used for job allocation to an individual driver
• Optimizing when out on the road
  • Any requests to re-optimize after the driver has left the depot should be planned for break times due to resource constraints.
  • Amending the stop list and stop order in any way after communicating to customers any planned arrival time will impact on the time.
• Driver must follow the planned route. Deviation will impact the ETAs.
• Break times should be allocated with sufficient time to ensure the break does not cause time windows to fail.
• The greater the number of time windows that need to be met, the longer the time to optimize as this increases the route complexity.

Note: Slack time is added at the start of a stop if the ETA is before the opening time window. For example, if scheduled to arrive at a stop at 13:00 but the ETA is 12:45 there will be 15 minutes of slack time at that stop. This time is taken into consideration to calculate all subsequent stops.

Optimization Calculation Times

Optimization times are dependent upon a variety of factors. The number of stops is not representative of the time it will take to optimize. For example, a 50 stop, complex route will take longer than a 100 stop simple route.

The complexity is introduced with time windows, especially infeasible or tight time constraints.

Device Comparison Statistics

Running the Advanced Optimization module on a handheld can take a significant amount of processor/RAM in order to complete the task in the most efficient time.

During our internal testing we have seen significant differences in times to optimize based upon the processor and RAM available on the device. Taking an 87-stop route with two time-restricted destinations, the optimization calculated a 36-mile route which we have seen take between 1 minute and 4 minutes based upon the processor/RAM available.

It is advisable that when running the optimization to ensure that other processes are limited to as few as possible and any essential processes are lightweight as these will have a significant detrimental impact on the time to optimize.

Multiple Time Windows

One of the barriers to driver acceptance is related to their knowledge of regular customer patterns. For instance, if a business closes between 12-1pm for lunch every day, the driver would know not to attempt to reach this destination between these times. If, however, this information exists in a database to include open and close times, as well as lunch break times, then these could be used to provide CoPilot with greater constraints around the delivery options.

The CoPilot optimization module has been enhanced to take into account any known time when the destination should not be reached.

This has been implemented in a flexible way to work with the format of the stored data, so you can either provide a block time or two positive time windows.

Block time: The business is open between 9am to 5pm but is closed for lunch between 12-1pm

Two positive times: The business is open between 9am to 12pm and from 1pm to 5pm. Passing in multiple time windows will increase the overall time to optimize stops as CoPilot tries to find a route which is feasible to take into account the additional parameters.

Note: If you currently have a limited data for destinations which include block / second time windows, all other stops can be passed with null values for the extra fields, making them a single time window stop. If you intend to improve your database to include this additional information it would be advisable to implement one of the enhanced APIs from the outset as the additional information can be used for any destinations, without risk to the stops which only have a single time window.

Break Times

In order to accurately schedule the entire day, it is also necessary to plan the driver’s break times. This can be done by providing an exact location or allowing CoPilot to plan the stop at a convenient location based upon the time restrictions. If a location is not provided, the break time is allocated to a convenient completed stop, and no drive time is calculated. Once the break is completed, the drive time will be calculated to the next stop from the previous stop.

In order to add a break time, please ensure the stop number is registered at 1001 or above. This will indicate to CoPilot this is a break and not a regular destination stop. The usual rules apply to add wait time equal to a break length required. CoPilot can support multiple break times, in this instance the stops should be labelled 1001, 1002, 1003 etc.

Please ensure that a sufficient time window is allowed for the break to ensure this can be appropriately scheduled. We would suggest at least a one hour window for a half hour break to be scheduled. Providing an exact time for the break to be taken is possible, but please note this risks inefficiencies being introduced, as it will be unlikely that the driver will be finished on a the previous job exactly at the required start break time. Therefore CoPilot will introduce slack time prior to the start of the break, increasing the total length of the break planned.

Please note break times will be ignored if:

• The driver does not start before the break time end. This enables standard break time windows to be passed in for every driver, without knowing their specific start time.

• The driver can return to the end depot before the end of a break time. CoPilot believes that a driver will not take a break if they are able to return to the depot before the break is required.

An example of a break stop from an input file:

1002||||||||||1700|1730|1200

Only the following fields are defined for breaks:

• The ID of the stop—1001, 1002, etc.
• The time window during which the break should be taken.
• The duration of the break as dwell time in seconds.

Static Stops

Within a daily stop list, a driver may wish to start or finish their day with a specific stop or set of stops. To achieve this, a stop would need to be excluded from the optimization module. Within the CoPilot V10 advanced optimization module, stops can be defined as a static stop by making the stop numbers start from 2001.

Static stops can only appear at the beginning or the end of a stop list. If the static stop is inserted in the middle of the sequence they are not guaranteed to remain in the same position once they optimization calculation has completed.

The other rules surrounding the removal of a stop from the input optimization list also applies to static stops. For example if the stop cannot be geocoded, it will not be included within the optimized output stop list.

An example of the content from an input file which includes static stops can be found below:

0847|52558629|-259679|52558629|-259679
2001|||||||PE12 6HW|52806278|-107469|0700|1000|150
1|||||||PE12 6NX|52805213|-56727|0700|2000|150
2|||||||PE12 6SF|52759118|-34316|0700|1200|150
3|||||||PE12 6SF|52759118|-34316|0700|2000|150
4|||||||PE12 8SG|52750445|17908|0700|1000|150
5|||||||PE12 8RR|52731962|-18979|0700|2000|150
2003|||||||PE12 0QQ|52678994|-15104|0700|2000|150
2004|||||||PE12 0NP|52679165|-24786|0700|2000|150

Within this file, the first two and last two stops would remain the same. The middle stops with the stop number running from 1 to 5 would pass through the optimization process and the optimal stop order will be provided.

When using static stops, the first static stop should start at 2001 and increment by 1 for all further stops. A static stop can be entered at the beginning, the end or both the beginning and the end of a stop input list.

Traffic

Traffic is not included in the daily planning and optimization of the route. In general, a road that is blocked at 7 a.m. during optimization may well be clear when the driver reaches the location until 5 p.m.

However, historical road speed data, based on your start day and time, will be used for routing.

The Input file

Header information

Driver Start Time | Start Latitude | Start Longitude | Finish Latitude |Finish Longitude

• Driver Start time – This is the time the driver is expected to leave the depot. This will be used as the start time for the optimization planning. The third-party application may choose to fix this time as the driver is required to leave at x time every day, or this can be an estimated time that 20 minutes after the job list has been input to the device the driver should be leaving the depot.
• Start and finish locations have to be provided in latitude/longitude. The locations can be different to allow a depot start and home finish, if required.

Body information

Original Stop Number | Destination Name | Destination Address 1| Destination Address 2 | Destination Address 3 | City | Country Code | Postcode| Lat | Long |Time Window Open | Time Window Close | Stop Time

• Original Stop Number – This is the unique stop number that will be used to identify the pre-optimized and optimized stop order. Stop number 1 should be passed as the first stop and an increment of 1 for each subsequent stop should be passed to ensure consistent output results are received.
• Destination Name – This is usually the named contact at the destination location
• Destination Address 1/2/3 – The destination address
• City – The destination address city
• Country Code – This is the country the destination is located
• Postcode – The destination postcode
• Time Window Open – This is the earliest available time the driver should reach this destination
• Time Window Close – This is the last available time the driver should reach this destination
• Stop Time – This is the length of time in seconds it is estimated the driver will be at the destination before starting to the next location

Example

0820|53987753|-1092771|53787253|-1072791
1|MISS LISA MARSHALL|15 HORNBEAM ROAD|||YORK|GB|HG3 8RA|53989650|-1528553|0700|2000|180
2|FAO CATHY SIMPSON|SIMPSON HOUSE|25 SIMPSON ROAD||HARROGATE|GB|HG3 8RA|53879500|-1524145|0700|1000|180
3|MR T UNDERWOOD|BEAM SQUARE LTD |150 BEAM STREET||HARROGATE|GB|HG4 8PB|||0700|2000|180

Block Time Window

As above description for a Single Time Window Header and Body, but with the addition to end of the Body:

• Block Window Start Time: Blocking window start time, this is the earliest time that you do not want the driver to reach this destination.
• Block Window End Time: Blocking window end time, this is the latest time that you do not want the driver to reach this destination

Example

0820|53987753|-1092771|53787253|-1072791
1|MISS LISA MARSHALL|15 HORNBEAM ROAD|||YORK|GB|HG3 8RA|53989650|-1528553|0700|2000|180|1200|1300

Two Time Windows

As above description for a Single Time Window Header and Body, but with the addition to end of the Body:

• Time Window Open – the earliest available time the driver should reach this destination
• Time Window Close – the last available time the driver should reach this destination before the customers break
• Stop Time – the length of time it is estimated the driver will be at the destination before starting to the next location
• Second Window Start Time: Second window start time – the earliest time that you want the driver to reach this destination after the customers break in the day
• Second Window End Time: Second window end time – the latest time that you want the driver to reach this destination

Example

0820|53987753|-1092771|53787253|-1072791
1|MISS LISA MARSHALL|15 HORNBEAM ROAD|||YORK|GB|HG3 8RA|53989650|-1528553|0700|1200|180|1300|2000

The Output file

Header Output Information

Total ETA | Total Distance in Miles | Execution Time

1. Total ETA – the time the driver is expected to return to the finish latitude/longitude

2. Total Distance in Miles – the complete distance the driver is expected to complete from start to finish

3. Execution Time – the time it took for CoPilot to optimize the stop order on the handheld

Body Output Information

Optimized Stop Number | ETA | Original Stop Number | Time Window Met

1. Optimized Stop Number – the new proposed optimized stop order. If the request was for an ETA only calculation this will match the Original Stop Number.

2. ETA – the estimated time the driver will reach this destination

3. Original Stop Number – the original input stop number

4. Time Window – indicates if the destination was reached successfully within the allocated time window provided

Example Output file

| Total ETA               |       | 08:55      |            |
| :---------------------- | :---- | :--------- | :--------- |
| Total Distance in Miles | 20    |            |            |
| Execution time          | 00:30 |            |            |
| OptStopNo               | ETA   | OrigStopNo | TimeWindow |
| 1                       | 08:35 | 2          | Y          |
| 2                       | 08:40 | 3          | Y          |
| 3                       | 08:45 | 1          | Y          |

Optimization Logging

During the advanced optimization, log files are generated that can be used to investigate further the process CoPilot followed in order to generate the output provided. These outputs are mainly for our understanding and investigation if the output generated does not provide the expected results.

The logging is recommended only for internal analysis and investigation, it would be advisable to enable logging during the implementation and testing phase, it is not recommended to leave this enabled once deployed into the end user base.

Enabling Optimization Logging

In CoPilot edit the user.cfg to include

[User Settings]
“EnableCustOptLogs”=1

When running optimization a new folder within the CoPilot folder will be created CustomizeOptimizationLog and inside the file “custopt.log” will be generated. On iOS devices, the CustomizeOptimizationLog folder can be found inside of Caches\logs in versions of CoPilot above 10.19.3.48.

Optimization Configuration options

It is advisable to speak with Trimble Maps’s Sales Engineering or Support teams prior to making changes to the Optimization configuration options, but the following settings are available for configuration to help improve the optimized output to meet your needs.

If you are receiving the following error callbacks

ERROR_MAXDISTANCE - the stops are deemed too far from the depot for optimization. (Note: This error message only returns for optimization, not for ETA requests.) Please increase the following value. This value is in miles.

[Optimization]
"MaxAirTravelMile"=100

ERROR_WAIT_TIME - the wait time provided exceeds the preset max threshold. The values below are in minutes. The max time allowed for break is 2 hours. The max time allowed for a regular stop is 30 minutes

[Optimization]
WaitTime_Break_Max=120

[Optimization]
WaitTime_Regular_Max=30

Ordering Stops by Side of Street

Available in CoPilot 10.14 and Later

CoPilot’s advanced optimization logic has been enhanced so it can take into account the side of the street a stop is on when optimizing a route. This can help avoid situations where a driver is routed back and forth to delivery stops on both sides of a busy road. Instead, CoPilot will attempt to generate a route where the driver is provided with stops on the same side of the street.

How It Works

Our advanced optimization puts stops in a logical and efficient order, regardless of the stop’s side of the street. A new, configurable setting allows CoPilot to consider the side of street before reordering stops. This side-of-street setting is applied to all road types except for local roads—where going back and forth across a street is generally safe and preferable.

Changing the Side of Street Setting

Side-of-street optimization is disabled by default as it is not used by all customers. To enable it, you need to add the following configuration to the CoPilot user.cfg file:

[Optimization]
"UseSideOfStreet"=1
//Default is 0, which is off

Side of Street Considerations

When changing the default side-of-street setting, here are some things to keep in mind:

• Optimizing stops on the same side of the street may negatively impact the overall ETA and drive time.

• The side of street for a stop is determined using a street address or latitude/longitude point. For best results, use an exact address or a lat/long point that is more than 10 feet away from the road, on the side of the road where the stop is located.

• If the side of the street cannot be determined for a stop, the route may approach the stop from either side.

Side of Street Example

Below is a route with six stops on a primary road. With side-of-street optimization turned off (the default), the route is optimized to group together stops that are close together. As a result, it goes back and forth across the street.

With side-of-street optimization turned on, the route hits the stops on the northbound side of the road and then returns to the stops on the southbound side.

Optimization APIs

CPIK - Please see the Optimization section

SDK - Please see the Optimization section