How to Solve the Traveling Salesman Problem for Logistics

The traveling salesman problem (TSP) requires us to determine the fastest route between different waypoints. In this hands-on tutorial, we’ll see how TomTom’s Waypoint Optimization API solves this problem.

Global logistics and shipping are some of the fastest emerging markets in the world. According to Business Wire, the global logistics market reached a value of $4.92 Trillion in 2021.

Due to the increase in online shopping, the e-commerce and delivery business has grown tremendously. However, the large scale of shipments brings about the traveling salesman problem (TSP), which requires determining the most efficient route to cover each waypoint. At the core, the challenge is determining the fastest route that covers each delivery destination with minimal backtracking and time-wasting.

The importance of solving TSP for organizations related to the supply chain is enormous because the amount of time and money delivery costs will directly impact the business’s profit. Furthermore, many other problems, such as path optimization in printed circuit board assembly, efficient vehicle routing, and path optimization, are directly related to TSP.

With so many factors contributing to TSP, it’s classified as an NP-hard problem. This means that there’s no clear, consistent solution. And as you add more waypoints in TSP, the complexities and time it takes to get an optimized solution will increase.

However, TomTom’s Waypoint Optimization API is designed to help us find optimized routes between multiple waypoints. In this article, we’ll look into how TomTom’s Matrix Routing API can help us calculate route summaries between each leg of the trip.

The Project

Prerequisites

Before you get started, here are the prerequisites you’ll need:

• Basic knowledge of JavaScript — mostly Node.js and Express.js

• A Postman account

• A TomTom Developer account and (free) API key

Starter Application

In this section, we’ll create a basic Node.js application using this repository as a starting point. You can skip this section if you already have a Node.js application running. The starting code is a cleaned-up version of Node.js and Express.js server with the required packages.

After cloning the repository, we need to install all the dependencies using the code below:

npm i  

The next step is to get a TomTom API key to utilize the waypoint optimization API to solve the TSP problem.

Once you’ve created, verified, and signed in to your account, go to the dashboard and select Keys on the left navigation bar to copy your API key.

Next, create an .env file inside the root directory of our project. If you used the starter repository, the .env file with the required variables is already created.

After completing this step, our server with all basic requirements is ready, and now we can start working on solving the TSP problem with the help of TomTom’s waypoint API.

Waypoint Optimization with TomTom

This section aims to demonstrate TomTom’s ability to solve the TSP problem using waypoint optimization. To understand this, we’ll create an API endpoint that accepts sequences of locations and the type of vehicle as arguments. Then, we’ll use TomTom’s Waypoint Optimization API to find the best-optimized path.

For this tutorial, initially, we’ll use 12 different locations for the first set. Then, we’ll demonstrate the same call using some truck-specific options. Lastly, we’ll check both of these options for 30 waypoints.

According to TomTom’s API documentation, the endpoint we are targeting is https://{baseURL}/routing/waypointoptimization/{versionNumber}?key={Your_API_Key}. And in our application, we’ve stored three variables — baseURL, versionNumber, and API_KEY — inside the .env file in root directory of the project. Furthermore, the endpoint accepts two arguments:

1. Waypoints: An array of points containing latitude and longitude.

2. Options: We can use the options argument to customize the API response according to the vehicle and other constraints.

If you followed the starter repository, the route for this API call would already be added inside the routes/waypoints.js file with all necessary imports.

But, if you’re starting from scratch, create a file under the routes folder named waypoints.js and add the following code:

const express = require("express");
const router = express.Router();
const { findOptimizedRoute } = require("../controller/waypoints");
router.post("/optimizedRoute", findOptimizedRoute);
module.exports = router;

The next step is to define a controller method inside using the code below:

controllers/waypoints.js file.
const request = require("request");
exports.findOptimizedRoute = async (req, res) => {
  const { waypoints, options } = req.body;
  request.post(
    {
      url: `${process.env.BASE_URL}routing/waypointoptimization/${process.env.VERSION}?key=${process.env.TOMTOM_API_KEY}`,
      body: JSON.stringify({ waypoints, options }),
      headers: {
        "content-type": "application/json",
      },
    },
    function (err, resp) {
      if (err) {
        res.status(400).json({ message: "There was a problem with this request."})
      } else {
        res.json(JSON.parse(resp.body));
      }
    }
  );
};

The above code accepts arguments from the request body — namely waypoints and options — and then sends a response back to the user. After adding this code, open a terminal and execute npm start to start the server.

For this tutorial, we’ll use Postman to test the newly created API. It’s a widely used API testing platform. Furthermore, we are using 12 random waypoints as test data, the maximum support waypoints for regular tier users.

With that in mind, let’s open Postman and enter the endpoint in the URL tab. Don’t forget to set Content-Type as application/json.

For this demonstration, we’ll use the attached demo JSON body, which we can use to test the API. As an example, we’ve selected “car” for our travel mode and added a couple of output extensions to give us the route and leg summary of the trips.

A successful response will give an optimized order for you to follow to plan your trip efficiently. And in the summary section, you’ll find the total distance in meters and the total time the trip could take. Moreover, the leg summary section is perfectly set to determine the time and distance between each waypoint.

It’s also worth mentioning that route summary and legs summary use Matrix Routing API under the hood.

Now, let’s try the same JSON with some truck-specific options. TomTom’s Waypoint Optimization API provides many truck options, such as length, width, height, axle weight, and so on. Check out the API documentation to see all the possibilities.

As you can see in the image below, the optimized order changed according to the vehicle requirements. We can also see that the total distance and time with the truck would be more than the car.

This API can be a game changer for organizations that operate fleets of trucks and delivery services. The profit of these organizations is mainly dependent on efficiency. These extra options can significantly increase efficiency. Furthermore, TomTom accounts for dimensional information such as width, height, weight, the type of vehicle road, traffic data, and so on, which provides the fastest route according to the present situation.

TomTom’s Waypoint Optimization API can support up to 30 waypoints, and we can use that API with similar truck- and car-specific options. Here are JSON files that contain 30 waypoints for the request body:

• Car
• Truck

The response will be similar to the previous one, but now it will show optimization for an order for all 30 waypoints. In this instance, the optimized order is the same for the truck-specific options.

You can view the final project code on GitHub.

Next Steps

The traveling salesman problem (TSP) is one of the most widely known problems in the NP-hard category, which are often tricky or impossible to solve with multiple waypoints. TSP is directly associated with the real-world problem of vehicle routing, in which efficient routing is key to profitability.

TomTom’s Waypoint Optimization API can be your fleet’s driving force if they struggle with finding the optimized route. They support up to 30 different waypoints and returns optimized route according to your selected options. Their ability to provide an optimized route based on the selected vehicle can be crucial in many situations and save significant resources and the workforce by offering an optimized path.

Check out TomTom’s Waypoint Optimization API to better plan your fleet’s routine.