TSP TSPTSP

Overview

When we run a TSP against real-world networks, we’re actually running an ATSP - where the A stands for Asymmetric. The reason for this is that the distance from A to B is typically different to the distance from B to A once we consider turn restrictions, one way roads, etc.

Seems like an obvious thing to take account of which is why we don’t natively support the symmetric version of the problem (we find it’s more the exception than the rule in real-world problems). So wherever you see an Icepack API handling a routing problem, know that it’s handling the asymmetric version of this problem - we omit the A to keep the acronyms shorter!

Applicable models

  • tsp-mcvfz472gty6

Endpoints

Input

In order to construct a valid TSP request, we’ll require some locations which we would like sequenced. Each location requires three pieces of information, namely; an ID, a Longitude and a Latitude.

The IDs are required on each location in order to avoid any ambiguity in the response from the API. This is true for almost all the objects in all schemas where the field “id” is used. If a duplicate ID is provided, the API will throw an error.

If you’re comfortable in C#, R or Python, all examples in these languages are available in the github repository. Use whichever language you prefer - as long as you’ve generated the schema for your target language correctly. See the section on Compiling the model schemas for more information.

The TSP schema (tsp-mcvfz472gty6) has the following input sections:

message Geocode {
    required string id = 1;
    required float x = 2; //longitude for earth-routing
    required float y = 3; //latitude for earth-routing
}
message TSP {
    enum eDistanceType {
        RoadNetwork = 1;
        Euclidean = 2;
        Haversine = 3;
    };
    repeated Geocode points = 1;
    optional eDistanceType distancetype = 2 [default = RoadNetwork];
}

This portion of the schema allows you to provide a list/vector/array of geocodes which you would like sequenced. You’ll see that we natively support three distance types which can be specified on the distancetype field. This TSP message fully encapsulates all the model data we now want solved. The last step is to tell the API what we would like it to do with the input data. We call this a SolveRequest and it follows a common pattern across most end-points which looks like this:

message SolveRequest {
  enum SolveType {
    // Ignores provided routes. Solves using internal seed mechanisms.
    Optimise = 0;  
     // Evaluates the provided route sequence. Single solution response.
    Evaluate = 1; 
    // Uses routes as starting solution and continues to optimise.
    ReOptimise = 2;  
  }
  optional TSP model = 1;       // either model(1) or modelID(2) should be specified
  optional string modelID = 2;  // the model ID from a previously optimised
                                // request (for use with evaluate solve type)
  repeated string visitSequence = 3;  // for solveType = [Evaluate, ReOptimise].
  optional SolveType solveType = 4 [default = Optimise];
}

The model we constructed above is provided on the first field called model. This field is optional because a modelID may also be provided which refers to a model from a previous request. This is useful when you have particularly large models that you don’t want to send repeatedly to the API but may want to experiment with different visit sequences. The usage for this is rather advanced so if you’re just starting out we recommend simply using the model field in the solve request.

A visit sequence can be omitted when we’re using the Optimise solve type. If you’re interested to see how your own tour stacks up against a solution from the solver, you can populate the visit sequence with the location IDs in the order you would like the tour to evaluate. The solver will then return the road network distance and edges associated with that solution. This is particularly useful for exploring alternative sequences which may be preferred by users. The ReOptimise mode uses the provided visit sequence as a starting point and tries to find an improved solution. This is often useful in more complex models where constraints may be added incrementally to a solution and by providing the solver with a (feasible) starting solution, it will typically converge a bit quicker.

Both the Optimise and ReOptimise solve requests will only ever return a feasible solution (if a solution is found). The Evaluate is used to evaluate a solution, with all of its broken constraints. This is not very useful in a TSP model because it’s trivial to construct a feasible solution (it might not be very good) but there aren’t actually any constraints for the solver to break. You’ll see that the Evaluate mode is very useful in the IVR series of models which start to play with ideas like time windows, capacity constraints, slack and tardiness.

Looking at the sample from the repo, we’ll be submitting a piece of protobuf which looks like this

model {
  points {
    id: "1"
    x: -6.23078
    y: 53.391697
  }
  points {
    id: "2"
    x: -6.3513303
    y: 53.427757
  }
  ...
  points {
    id: "9"
    x: -6.1607089
    y: 53.265144
  }
  points {
    id: "10"
    x: -6.1774259
    y: 53.394672
  }
}
solveType: Optimise

We can then serialise this into the problem envelope which tells the API what kind of problem this is we’d like to have solved.

type: "tsp-mcvfz472gty6"
subType: INPUT
content: <Serialised TSP model (binary)>

We simply serialise this problem envelope into the body of the http request and the API will know to unpack the content in this message as a tsp model (specifically, a tsp-mcvfz472gty6) and will solve it accordingly. The submission of models is handled through a POST http request. The retrieval of model solutions is handled by a GET request. You’ll find more information on this in the Calling the API section as well as the Model submission section.

Output

The response message from the solver is defined as follows:

message SolutionResponse {
    repeated string tour = 1;
    repeated Edge edges = 2;
}

The tour is the core of the solution provided by the API. This sequence of strings corresponds to the optimal sequence that should be taken to minimise the travel distance taken through the nodes. The strings correspond to the id’s of the points that we submitted. For this reason, it’s important that you don’t submit duplicate id’s for the points (the payload will be rejected) and this is the reason why - you won’t be able to accurately interpret the solution if there are duplicates!

The list of edges that are returned with the tour are very useful if the request was configured to run against the road network. Looking at the Edge definition in this context:

message Edge {
    message Geometry{               // a light-weight geocode definition to mark the parts of the path
        required float x = 1;       // between the "from" and "to"
        required float y = 2;
    }
    required string from = 1;        // the source point
    required string to = 2;          // the destination point
    optional float distance = 3;     // the distance of this edge (i.e. between "from" and "to")
    repeated Geometry geometry = 4;  // geometry is populated for road network pathing.
}
We can see that we have everything we need here if we wanted to plot these details on a map. The list of Geometry is the order of travel through the road network (at the highest level of granularity we support) so the order of these Geometries is important because they actually form a linestring (a sequence of points defining a line) between the origin and destination points. Isolating just the first edge in a sample response looks like this:

from: "The Oval Bar Dublin"
to: "The Palace Bar"
distance: 1.797
geometry {
  x: -6.26024
  y: 53.3482742
}
geometry {
  x: -6.26027679
  y: 53.3482704
}
geometry {
  x: -6.26025677
  y: 53.3482094
}
.... (lots of stuff)

The R-package (iceR), and python scripts have neat ways of quickly tabling all the response data for our schemas so that you can plot with a one-linear on leaflet or your own canvas. The other advantage of working with the package is that a tabular output is provided, which is a preferred data-format for languages like R. Our routing data is typically tabulated into two objects, a nodes table (which describes the stops) and an edges table (which describes the interstop movements).

“TSP” was last updated: November 20, 2023