- Products ProductsLocation Services
Solve complex location problems from geofencing to custom routing
PlatformCloud environments for location-centric solution development, data exchange and visualization
Tracking & PositioningFast and accurate tracking and positioning of people and devices, indoors or outdoors
APIs & SDKsEasy to use, scaleable and flexible tools to get going quickly
Developer EcosystemsAccess Location Services on your favorite developer platform ecosystem
- Documentation DocumentationOverview OverviewServices ServicesApplications ApplicationsDevelopment Enablers Development EnablersContent ContentHERE Studio HERE StudioHERE Workspace HERE WorkspaceHERE Marketplace HERE MarketplacePlatform Foundation and Policy Documents Platform Foundation and Policy Documents
- Pricing
- Resources ResourcesTutorials TutorialsExamples ExamplesBlog & Release Announcements Blog & Release AnnouncementsChangelog ChangelogDeveloper Newsletter Developer NewsletterKnowledge Base Knowledge BaseFeature List Feature ListSupport Plans Support PlansSystem Status System StatusLocation Services Coverage Information Location Services Coverage InformationSample Map Data for Students Sample Map Data for Students
- Help
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
- information about our vehicle
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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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
]
}
]
}
}
]
}
Information about the vehicle
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
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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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",
"tasks": {
"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
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"
},
"load": [
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"
},
"load": [
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"
},
"load": [
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"
},
"load": [
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"
},
"load": [
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"
},
"load": [
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"
},
"load": [
0
],
"activities": [
{
"jobId": "arrival",
"type": "arrival"
}
]
}
],
"statistic": {
"cost": 0.21860000000000002,
"distance": 2186,
"duration": 504,
"times": {
"driving": 504,
"serving": 0,
"waiting": 0,
"break": 0
}
}
}
]
}
