A traveling salesperson (TSP) route request must have at least three locations. Unlike simple multi-address route requests, the <start_location> element is optional.
TSP route requests are multi-address requests that have the optimize_route attribute present and set to TRUE. TSP route requests attempt to reorder the unfixed locations in the request to optimize the overall route.
All the locations in a TSP request are classified as unfixed or fixed:
Unfixed location: If a location is specified with the <location> element, it is considered an unfixed location and is subject to reordering during route computation.
Fixed location: If the location is specified with a <start_location> or <end_location> element, it is considered a fixed location and is not subject to reordering during route computation.
If intermediate locations need to be fixed, a simple multi-address route request should be used instead of a TSP route request.
TSP route requests use the route_type attribute to classify the route as an open or closed tour.:
Open tour: The route does not return to the start location.
Closed tour: The route returns to the start location.
If a TSP closed tour route is requested, the <start_location> element must be specified. This start location is also used as the end location during route computation. If an <end_location> element is specified in a TSP closed tour route request, an error is returned. By definition, TSP closed tour routes use a single fixed start and end location but the intermediate locations are still subject to reordering.
Example: TSP Open Tour Route Request
To drive from your workplace, visiting customers A, B, and C:
The route has the workplace as a fixed start location.
The route has customers A, B, and C as unfixed intermediate locations. These locations are reordered to optimize the overall route.
The returned route is an optimized open tour route from the workplace to the first reordered location, through the second reordered location, to the final location.
Example: TSP Closed Tour Route Request
To drive from your workplace, visiting customers A, B, and C, and then returning to your workplace:
The route has the workplace as a fixed start location. The workplace is also used as a fixed end location. An <end_location> element should not be specified in the route request. The routing engine adds the subroute from last unfixed location to the workplace automatically when it sees a request for a closed tour.
The route has customers A, B, and C as unfixed intermediate locations. These locations are reordered to optimize the overall route.
The returned route is an optimized closed tour route from the workplace to the first reordered location, through the second and third reordered locations, and finally back to the start location.
TSP route requests can contain several attributes specific to each subroute. These attributes include return_subroutes, return_subroute_edge_ids, and return_subroute_geometry. These attributes are explained in Route Request XML Schema Definition.