# Traveling Salesman Problem

Let's explore solving the traveling salesman problem: given a set of locations, find the shortest route to visit each location and return to the original starting point.

## Gather data to create a request

For the request URL we have:

POST https://tourplanning.hereapi.com/v3/problems


To calculate the results, we need to provide:

• the starting point
• the coordinates of the locations we want to visit

### Authentication

Tour Planning API supports authentication using both API Key and Bearer Token. To get started for free, you can create an account and get your API Key. For other authentication methods, see the Identity & Access Management Developer Guide.

### Coordinates of locations to visit

The the locations we want to visit (jobs) are listed below in no particular order. Our goal is to find the optimal order to visit all of the following locations:

A: 47.620835, -122.333295
B: 47.623879, -122.335212
C: 47.620571, -122.339785
D: 47.623690, -122.333005
E: 47.622017, -122.336911


Our starting point (depot) is labeled S is located at 47.623231,-122.340168 or 872 Republican Street, Seattle, WA. We will specify the coordinates of our depot later along with our fleet.

Sometimes we want to arrive during specific time windows that certain locations are open, in this example, we are not specifying time constraints that would impact our route. But if we wanted to set availability for depots, we could do that using the times parameter.

Another parameter that we're not going to explore in this example is demand. With this parameter, you can specify an array of flexible units that maps to a vehicle's capacity. For example, a demand array of [2,1] for a delivery job can mean that two passengers and one suitcase will be dropped off. Another example would be setting [3] for a pick-up job, and that can mean 3 packages will be picked up. Demand in a job corresponds to capacity in the fleet. In this example, we've set demand and capacity to [0] because we are not concerned about tracking shipments and capacity.

{
"jobs": [
{
"id": "A",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "B",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "C",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "D",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "E",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
}
]
}


The Tour Planning API can calculate routes for both trucks and normal passenger cars. It also provides information about the cost of the trip based on the details about the vehicle. Because of this, you have to provide some information about your fleet of vehicles upfront when you create a request.

### Set up fleet profile

Each profile has to have a name. In general, all vehicles with more than 2 wheels and less than 3500 kg can typically share the same routing profile with type car, unless some of your cars or vans shall avoid toll roads and others not. In that case, you would need more than one profile. The vehicle type can be either set to car, truck, scooter, bicycle or pedestrian. Trucks have driving restrictions and the route can be a little bit different to accommodate for things like height, weight, and turn limitations for trucks.

{
"profiles": [
{
"name": "car_1",
"type": "car"
}
]
}


### Set up vehicle details

Next, we need to set up vehicle details such as cost, profile information, and shift availability. The profile is tied to the name of the profile that we defined earlier. It should not represent anything too specific about your vehicle due to privacy reasons.

With shifts you can set the availability and the start and end location of your vehicles. For this example, we want to come back to our original starting point so we'll set the start and end location to the same coordinate.

The capacity allows you to define an array of unspecified units so for example, you can say use capacity [4,2] to show that your vehicle has capacity for 4 passengers and 2 suitcases. Capacity maps to demand that we will set at the next step. For example, we won't worry about capacity because are not planning to accommodate any passengers or packages so we'll set capacity to [0].

When describing fleet, amount represents the number of vehicles that you have that follow the same availability shift and same cost profile. For this example, we assume that we have only one vehicle so we set amount to 1.

{
"types": [
{
"id": "car_profile",
"profile": "car_1",
"costs": {
"distance": 0.0001,
"time": 0
},
"shifts": [
{
"start": {
"time": "2021-07-04T09:00:00Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
},
"end": {
"time": "2021-07-04T18:00:00Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
}
}
],
"capacity": [
0
],
"amount": 1
}
]
}


## Create the request (Problem)

Let's make the call to our API:

POST https://tourplanning.hereapi.com/v3/problems?apiKey=YOUR_API_KEY


And for the body, we have information about our jobs and fleet:

{
"plan": {
"jobs": [
{
"id": "A",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "B",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "C",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "D",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
},
{
"id": "E",
"deliveries": [
{
"places": [
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"times": [
[
"2021-07-04T10:00:00.000Z",
"2021-07-04T12:00:00.000Z"
]
],
"duration": 0
}
],
"demand": [
0
]
}
]
}
}
]
},
"fleet": {
"types": [
{
"id": "car_profile",
"profile": "car_1",
"costs": {
"distance": 0.0001,
"time": 0
},
"shifts": [
{
"start": {
"time": "2021-07-04T10:00:00.000Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
},
"end": {
"time": "2021-07-04T12:00:00.000Z",
"location": {
"lat": 47.623231,
"lng": -122.340168
}
}
}
],
"capacity": [
0
],
"amount": 1
}
],
"profiles": [
{
"name": "car_1",
"type": "car"
}
]
}
}


## Evaluate the response (Solution)

Below is the response showing the optimal order to visit each stop (C->E->A->D->B), the duration of the trip (504 seconds), the travel distance (2186 meters), and more:

{
"statistic": {
"cost": 0.21860000000000002,
"distance": 2186,
"duration": 504,
"times": {
"driving": 504,
"serving": 0,
"waiting": 0,
"break": 0
}
},
"tours": [
{
"vehicleId": "car_profile",
"typeId": "car_profile",
"stops": [
{
"location": {
"lat": 47.623231,
"lng": -122.340168
},
"time": {
"arrival": "2021-07-04T10:00:00Z",
"departure": "2021-07-04T10:00:00Z"
},
0
],
"activities": [
{
"jobId": "departure",
"type": "departure"
}
]
},
{
"location": {
"lat": 47.620571,
"lng": -122.339785
},
"time": {
"arrival": "2021-07-04T10:00:49Z",
"departure": "2021-07-04T10:00:49Z"
},
0
],
"activities": [
{
"jobId": "C",
"type": "delivery"
}
]
},
{
"location": {
"lat": 47.622017,
"lng": -122.336911
},
"time": {
"arrival": "2021-07-04T10:02:18Z",
"departure": "2021-07-04T10:02:18Z"
},
0
],
"activities": [
{
"jobId": "E",
"type": "delivery"
}
]
},
{
"location": {
"lat": 47.620835,
"lng": -122.333295
},
"time": {
"arrival": "2021-07-04T10:03:44Z",
"departure": "2021-07-04T10:03:44Z"
},
0
],
"activities": [
{
"jobId": "A",
"type": "delivery"
}
]
},
{
"location": {
"lat": 47.62369,
"lng": -122.333005
},
"time": {
"arrival": "2021-07-04T10:05:01Z",
"departure": "2021-07-04T10:05:01Z"
},
0
],
"activities": [
{
"jobId": "D",
"type": "delivery"
}
]
},
{
"location": {
"lat": 47.623879,
"lng": -122.335212
},
"time": {
"arrival": "2021-07-04T10:06:33Z",
"departure": "2021-07-04T10:06:33Z"
},
0
],
"activities": [
{
"jobId": "B",
"type": "delivery"
}
]
},
{
"location": {
"lat": 47.623231,
"lng": -122.340168
},
"time": {
"arrival": "2021-07-04T10:08:24Z",
"departure": "2021-07-04T10:08:24Z"
},
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 0.21860000000000002,
"distance": 2186,
"duration": 504,
"times": {
"driving": 504,
"serving": 0,
"waiting": 0,
"break": 0
}
}
}
]
}