TSPTW TSPTWTSPTW

Time windows are considered side constraints over the classic TSP.

Overview

The tsptw-kcxbievqo879 schema defines a TSP with Time windows. If you’ve just worked through the TSP schema you’ll notice that almost all the elements in this particular problem are the same as the tsp-mcvfz472gty6 schema. The big difference is on the model input: the Geocode now gets two additional optional fields. The SolutionResponse also now defines a set of arrival times which corresponds to the length of the tour.

Applicable models

• tsptw-kcxbievqo879

Endpoints

• POST: https://api.icepack.ai/vehicle-router/solve/ (input)
• GET: https://api.icepack.ai/vehicle-router/solve/{requestid} (output)

Input

So lets start with the modification to the input payload. We can now add our time windows to the Geocodes (for those that have time windows). The schema defines the time windows on the Geocode:

message Geocode {
    required string id = 1;
    required float x = 2;               // longitude for earth-routing
    required float y = 3;               // latitude for earth-routing
    optional float windowStart = 4;     // the earliest the task can start
    optional float windowEnd = 5;       // the latest arrival at the geocode
}

You’ll see the usefulness of having optional fields in protobuf here. We don’t necessarily always want to apply a window to a location so having the ability to leave it out is useful. Here’s some sample data from the github repo.

points {
  id: "The Dropping Well"
  x: -6.2550621
  y: 53.307991
}
points {
  id: "Nearys"
  x: -6.26119
  y: 53.3407516
  windowStart: 748.266
  windowEnd: 3248.302
}
... 

In this example, “The Dropping Well” doesn’t have a particular time window, but “Nearys” does. Remember that with TSPs the tour needs to end where it starts, so if you place a time window on the first node in this context, it means that it will apply to both the beginning and end of the tour. You’ll notice that we didn’t specify any units for the time windows here either. The reason for this is we’re automatically measuring the minutes since midnight when working with the road network. We’ve chosen to make this a standard interpretation across the academic-style problems. For control over the units and scaling employed, see the IVR series of routing models. It’s worth mentioning that the IVR models can do everything the academic models can do (and more), it’s just sometimes simpler to see all the concepts one at a time without diving into the deep end.

Output

We have several common components here with the TSP. The edges and tour have exactly the same interpretation as before. The edge now also has a time field which corresponds to the travel duration (in minutes) to move between nodes.

message Edge {
    message Geometry{
        required float x = 1;
        required float y = 2;
    }
    required string from = 1;
    required string to = 2;
    optional float distance = 3;
    optional float time = 4;          // this is the additional field over the TSP model
    repeated Geometry geometry = 5;  
}

The solution response also has an extra field to provide the arrival times at each location.

message SolutionResponse {
    repeated string tour = 1;           // this is the tour produced by the solver.
    repeated Edge edges = 2;            // the interstops descriptions
    repeated float arrivalTimes = 3;    // the arrival time at each node (corresponding to the tour)
}