Excel Routing - TSPRouting - TSP
The Excel Add-in currently supports 2 variants of the TSP:
TSP
The TSP solver can be used to find the shortest route which visits each of the locations provided including returning back to the starting location. See the TSP Overview section for more details. The TSP model reads and writes data to a worksheet named TSP Data
TSP Data Requirements
First, select a Template option from the dropdown and then click on Create TSP Template. This will create a new TSP Data worksheet or replace an existing one.
For example, the ‘Library example - UK’ template will populate the spreadsheet with 9 sample locations as an example of how information should be entered. A blank template will only populate the headings of each column.
For each location, including the starting location, provide the following:
- ID: A unique location ID as a string or number. Spaces are allowed and IDs are case-sensitive. E.g. Customer1, Customer 1, customer_1, c1, 1 are all valid IDs. Space is trimmed from the start and end of an ID.
- Longitude: The location’s longitude in decimal degree format, in the range [-180,180]. E.g. -6.29987
- Latitude: The location’s latitude in decimal degree format, in the range [-90,90]. E.g. 53.37307
Next you can specify how the distances are calculated between each location via the Distance Options:
- Road Network: This is the default and calculates the road network distance between points.
- Haversine: The great circle distance is the shortest distance a plane would fly between two points and is called the Haversine distance.
- Straight: This is the straight line (Euclidian) distance as if the points were on a flat surface.
TSP Solution
Once the problem has been solved, the results will be written to the TSP Data spreadsheet. The Visit Seq provides the order in which each location should be visited. Note that since this is a cycle is doesn’t matter where you start from, but in terms of the solution the first location ID will be used as the start and end location.
In addition to the order in which the locations are visited, a second table provides the distance between each leg of the trip ([From] From location, [To] To location) and the total distance travelled [Accum.(km)] at the end of that leg. Distances are provided in kilometres and the total trip distance is the last value in the Accum. column.
Information regarding the solve status, including the solve request ID and solve time, can be found on the Solve Status page. Note that this worksheet is overwritten when a new problem is solved.
TSP Input Errors
- Duplicate IDs. Location IDs must be unique. If a duplicate is detected in the input, the following error message will be displayed:
- Be careful you do not inadvertently swap the longitude and latitude values when entering them into the worksheet.
- The long/lat location 0,0 is considered an error as it is often an indicator of missing data rather than as a valid scheduling point at the null island.
TSPTW
The TSPTW solver is similar to the TSP but includes time window constraints on each of the locations to be visited. The model reads and writes data to a worksheet named TSP-TW Data
TSPTW Data Requirements
In addition to the TSP data requirements described above, a time interval must be provided for each location, which specifies the earliest and latest time that a visit can occur. The solution to a TSPTW is the same as a TSP when the window constraints do not affect the solution. TSP distances will always be equal to or lower than TSPTW solutions.
For each location, including the starting location, provide the following:
- ID: A unique location ID as a string or number. Spaces are allowed and IDs are case-sensitive. E.g. Customer1, Customer 1, customer_1, c1, 1 are all valid IDs. Space is trimmed from the start and end of an ID.
- Longitude: The location’s longitude in decimal degree format, in the range [-180,180]. E.g. -6.29987
- Latitude: The location’s latitude in decimal degree format, in the range [-90,90]. E.g. 53.37307
- Start(min): The earliest time a visit is allowed in minutes.
- End(min): The latest time a visit is allowed in minutes.
The Icepack model only works with minutes from a given reference time. This means that time zones and day boundaries do not have to be interpreted by the solver.
- First pick a reference time which is the same or earlier than any of the start times.
- Now find the time in minutes from the reference time to the time you are interested in. This minute value is what needs to be entered in the Start and End fields for the TSPTW model. Note that, since we pick a reference time as early as any start times, this value should always be greater than or equal to 0.
So for our first example, we select 8:00 as our reference time. The end time is now the length in minutes to 17:00, which is (17-8)hours * 60min/hour = 540 min. Since all the locations in this example have the same time windows we set the Start = 0 (our reference time of 8:00) and the End = 540 (which is 540 minutes after 8:00, i.e 17:00) for each location.
But what if we could only visit location B between 12:00 and 12:30. We first calculate the Start as the number of minutes from our reference time of 8:00, i.e (12-8)hours * 60min/hour = 240. Our End is 30 minutes after this, i.e. 240min + 30min = 270.
The same distance calculations are available for the TSPTW as shown for the TSP, namely, Road Network, Haversine (Greate circle) and Straight.
TSPTW Solution
Once the problem has been solved, the results will be written to the TSP-TW Data spreadsheet. The Visit Seq provides the order in which each location should be visited along with the Arrival time in minutes at which the location is reached. Unlike the TSP, the starting location is important as the start and end time windows on the starting location must be valid at both the start of the sequence and again at the end.
In addition to the order in which the locations are visited, a second table provides the distance between each visit within the trip and the total distance travelled [Accum.(km)] up to that point. Distances are provided in kilometres and the total trip distance is the last value in the Accum. column.
The Arrival time at each To location is provided in minutes, and the time taken to traverse the From-To leg is given as the Duration in minutes.
Information regarding the solve status, including the solve request ID and solve time, can be found on the Solve Status page. Note that this worksheet is overwritten when a new problem is solved.
TSPTW Input Errors
- Duplicate IDs. Location IDs must be unique. If a duplicate is detected in the input, the following error message will be displayed:
- Be careful you do not inadvertently swap the longitude and latitude values when entering them into the worksheet.
- The long/lat location 0,0 is considered an error as it is often an indicator of missing data rather than as a valid scheduling point at the null island.
- Time window durations must be greater than 0.
Hint and Tips
An important use of the time window constraint is to prioritise when a location is visited. For instance, in the example using famous landmarks in England shown above, we could move the visit order for the Tate Modern up by providing it with an End time lower than what the unconstrained sequence gives us as 211 minutes. Giving the Tate Modern a Start of 0 and End of 200 minutes, results in the solution below.
Notice that the Tate visit is moved up to 4th in the sequence and that the arrival time is less than 200 minutes at 119 minutes. However, the cost of moving this visit up is an additional 10km of travel. A common mistake is for users to try and constrain the problem too tightly with time windows leading to infeasible problems.
Sample Templates
Below is a brief description of the sample template data that is provided to help you start.
Library Example - ZA
14 Library locations are provided within Johannesburg, South Africa. The TSPTW variant sets a default time window of 0 to 90 minutes, which provides a 1H30min window in which to visit all the locations.
POI - Gauteng - ZA
This example uses 12 locations spread across Gauteng, South Africa which are either important historical landmarks or popular tourist destinations. The TSPTW variant sets a default time window of 8 hours for each location, for example this could represent 9:00am to 5:00pm.