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.

Traveling Salesman Problem
Figure 1. Traveling Salesman Problem

Gather data to create a request

For the request URL we have:

POST https://tourplanning.hereapi.com/v2/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",
      "places": {
        "deliveries": [
          {
            "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",
      "places": {
        "deliveries": [
          {
            "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",
      "places": {
        "deliveries": [
          {
            "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",
      "places": {
        "deliveries": [
          {
            "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",
      "places": {
        "deliveries": [
          {
            "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 our 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. A profile mainly states what type of vehicle you have, so a reasonable name of a profile can be the model of the vehicle (like "bmw_m3") or it could be the type of vehicle (like "mini_van"). The type can be either set to car or truck. 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": "bmw_m3",
      "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 and the id of your vehicle can represent something more specific about your vehicle such as washington to specify the relative geographical location of your fleet.

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": "bmw_m3_washington",
      "profile": "bmw_m3",
      "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/v2/problems?apiKey=YOUR_API_KEY

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

{
  "plan": {
    "jobs": [
      {
        "id": "A",
        "places": {
          "deliveries": [
            {
              "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",
        "places": {
          "deliveries": [
            {
              "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",
        "places": {
          "deliveries": [
            {
              "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",
        "places": {
          "deliveries": [
            {
              "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",
        "places": {
          "deliveries": [
            {
              "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": "bmw_m3_washington",
        "profile": "bmw_m3",
        "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": "bmw_m3",
        "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": "bmw_m3_washington_1",
      "typeId": "bmw_m3_washington",
      "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
        }
      }
    }
  ]
}
Solution to traveling salesman problem
Figure 2. Solution to traveling salesman problem

results matching ""

    No results matching ""