Help

Getting Started with the Route Optimization API – Traveling Salesman Problem

Previous Article

The Route Optimization API works via an HTTP endpoint and you POST a JSON document to https://graphhopper.com/api/1/vrp?key=[YOUR_KEY]

This requires an API key that you can get here: login and go to API keys and generate an API key by clicking the Add API key button. Copy it and paste it to [YOUR_KEY].

Let us start solving the traveling salesman problem. Assume you want to find the fastest round trip through Germany’s 5 biggest cities (lon,lat) starting in Berlin:

  • Berlin (13.406, 52.537),
  • Hamburg (9.999, 53.552),
  • Munich (11.570, 48.145),
  • Cologne (6.957, 50.936),
  • Frankfurt (8.670, 50.109)

First, specify your vehicle at the start location Berlin. By default, it uses a car with zero capacity that uses the network of OpenStreetMap.

"vehicles" : [
   {
     "vehicle_id": "my_vehicle",
     "start_address": {
         "location_id": "berlin",
         "lon": 13.406,
         "lat": 52.537
     }
   }
]

The "vehicles" array holds only a single vehicle, however, you can specify an arbitrary number of vehicles. You only need to make sure that this in line with your plan.

Second, you need to specify 4 services that represent the remaining cities.

"services" : [
   {
     "id": "hamburg",
     "name": "visit_hamburg",
     "address": {
       "location_id": "hamburg",
       "lon": 9.999,
       "lat": 53.552
     }
   },
   {
     "id": "munich",
     "name": "visit_munich",
     "address": {
       "location_id": "munich",
       "lon": 11.570,
       "lat": 48.145
     }
   },
   {
     "id": "cologne",
     "name": "visit_cologne",
     "address": {
       "location_id": "cologne",
       "lon": 6.957,
       "lat": 50.936
     }
   },
   {
     "id": "frankfurt",
     "name": "visit_frankfurt",
     "address": {
       "location_id": "frankfurt",
       "lon": 8.670,
       "lat": 50.109
     }
   }
]

Please find the complete JSON request here.

To solve the simple traveling salesman problem, you need to POST the problem to our Route Optimization API. When exploring our API, we can recommend you to use our API Explorer or cURL. Either way, as described above you need to post this request to

https://graphhopper.com/api/1/vrp?key=[YOUR_KEY]

Let us assume you do not want your vehicle to come back to Berlin, but to stay in one of the other cities. Then add "return_to_depot": false

"vehicles" : [
   {
     "vehicle_id": "my_vehicle",
     "start_address": {
         "location_id": "berlin",
         "lon": 13.406,
         "lat": 52.537
     },
     "return_to_depot": false
   }
]

This way the algorithm determines where to end the route according the overall optimization objective. The default here is "min": "transport_time" (see “objectives” in our documentation). In this example, the algorithm finishes the route in Munich.

Let us assume you have good reasons to end your trip in Cologne, then add an end_address to your vehicle specification and remove the return_to_depot entry like this:

"vehicles" : [
   {
     "vehicle_id": "my_vehicle",
     "start_address": {
         "location_id": "berlin",
         "lon": 13.406,
         "lat": 52.537
     },
     "end_address": {
         "location_id" : "cologne",
         "lon": 6.957,
         "lat": 50.936
     }
   }
]

This enforces the vehicle to end its route in Cologne.

Now assume that you want to combine your round trip with an important date in Frankfurt where you need to be at latest 6 hours after you have left Berlin. To ensure this, you need to assign an appropriate time window. This is as easy as adding the time_windows property to your service specification like it is illustrated here:

{
    "id": "frankfurt",
    "name": "visit_frankfurt",
    "address": {
        "location_id": "frankfurt",
        "lon": 8.670,
        "lat": 50.109
    },
    "time_windows" : [ 
        {
            "earliest": 0,
            "latest": 21000
        }
    ]
}

This will force your vehicle to visit Frankfurt first.

Note that when you work with time windows, infeasible problems result in unassigned services. For example, it is impossible to get from Berlin
to Frankfurt in 4 hours by car. Thus, if the latest arrival time in Frankfurt is

"time_windows" : [ 
    {
        "earliest": 0,
        "latest": 14400
    }
]

Frankfurt definitely ends up in the unassigned service list:

"unassigned": {
      "services": [
        "frankfurt"
      ],
      "shipments": [
      ],
      "breaks": [
      ],
      "details": [
        {
          "id": "frankfurt",
          "code": 2,
          "reason": "cannot be visited within time window"
        }
      ]
}

As you can see, it does not only tell you that Frankfurt cannot be visited, but it also tells you the reason for it: "cannot be visited within time window".

It is quite unrealistic that if you travel all the way from Berlin to Munich that your stay in Munich only takes 0 seconds. Therefore, if your visit takes
for example 2 hours, just add a duration property to your Munich service:

{
     "id": "munich",
     "name": "visit_munich",
     "address": {
       "location_id": "munich",
       "lon": 11.570,
       "lat": 48.145
     },
     "duration": 7200
}

Let us now assume that you want to make this round trip a bit more exciting and challenging, thus you decide to switch from boring car to bike (you will definitely be a hero if you manage the round trip by bike). Here, you cannot use the default vehicle type anymore, but you need to define your bike yourself. This requires two changes, first, define a vehicle type in vehicle_types and, second, make a reference to the specified type in your vehicle with type_id:

"vehicles" : [
    {
        "vehicle_id": "my_vehicle",
        "start_address": {
            "location_id": "berlin",
            "lon": 13.406,
            "lat": 52.537
        },
        "type_id": "my_bike"
    }
],
"vehicle_types" : [
    {
        "type_id" : "my_bike",
        "profile" : "bike"
    }
]

The solution of your bike round trip indicates that it takes you more than 5 days, but only if you are strong enough to bike without rest.

Please find the complete JSON request here.

You might have numerous other requirements to the sequence of your visits. For example, you might want to visit Cologne first and Munich right after you have visited Cologne. This might be enforced either with time windows or with our relation feature. Please visit docs.graphhopper.com to explore the full power of our Optimization API.