Seeking the ideal traveling salesman problem solution for business

Written by:

Casey Lane

11

min read

Date:

December 22, 2022

Every day, millions of couriers, technicians, and delivery drivers face the same challenge: how to get to all their destinations as quickly and economically as possible? Large logistics companies save millions of dollars each year by optimizing their couriers' routes. 

Service organizations significantly reduce travel time by properly scheduling technician visits to customers. And food delivery services have built their success on their ability to quickly find optimal routes.

All of these companies are solving variations of one classic mathematical problem — the Traveling Salesman Problem (TSP). But this is far from an abstract theory from textbooks. TSP is the foundation of modern logistics, which directly impacts operating costs, service speed, and customer satisfaction.

When a courier spends 30% more time due to a suboptimal route, that means more fuel consumption, fewer orders per day, and dissatisfied customers. When a service company inefficiently schedules technician outings, it leads to downtime, rework, and lost revenue.

In this article, we'll explore how the traveling salesman problem works in practice, what algorithms help solve it, and how Distance Matrix APIs allow you to implement TSP solutions without having to develop complex algorithms from scratch.

Traveling Salesman Distance Matrix: What is the TSP?

The traveling salesman problem is a classic optimization problem that sounds deceptively simple: find the shortest route that passes through all specified points exactly once and returns to the starting point.

Imagine a courier in rush hour in the center of a big city. He has 12 parcels in his trunk that need to be delivered: an office document to the 15th floor of a business center, flowers for a birthday by 2 p.m., urgent medicine for an elderly woman, and 9 more addresses scattered across different areas. 

Traffic jams, one-way streets, delivery time restrictions — and only 4 hours left until the end of the working day. How do you choose a route so that you can get everywhere on time? Finding such an optimal path is the essence of the traveling salesman problem.

Similar tasks are solved by ATM technicians, drivers delivering bread to stores, or food delivery couriers. The goal is always the same: to find the optimal order of visits to locations based on time, distance, or cost criteria.

The task is based on the Hamiltonian cycle, but it searches for the route with the lowest cost. The simplicity of the formulation is deceptive — for dozens of locations, the number of possible routes grows exponentially, and searching for the optimal solution is an extremely complex computational task.

Approaches for the traveling salesman problem solution

Many algorithms have been developed to solve the traveling salesman problem, which can be categorized into three main groups based on the approach used to find a solution and the requirements for the accuracy of the result.

Exact algorithms

Precise algorithms guarantee finding the optimal solution, but require significant computing resources.

Basic methods:

  • Brute force method — systematically examines every potential route and chooses the most efficient one.
  • Branch and bound method — an improved version of exhaustive search that excludes inefficient options at an early stage.
  • Dynamic programming — remembers already calculated distances between cities to avoid repeated calculations. The Held-Karp algorithm represents the most recognized implementation of this method.

The main advantage of exact algorithms is that they guarantee optimal results. The disadvantage is that they require a huge amount of computation time even for a small number of points, which makes them impractical for real-world business applications.

Heuristic algorithms

Heuristic algorithms find good, but not always optimal, solutions within a reasonable amount of time.

Popular methods:

  • Nearest neighbor algorithm — identifies and moves to the closest unvisited location at each decision point.
  • Greedy algorithms — choose the most advantageous option available at each decision point.
  • 2-opt algorithm — enhances current routes by removing crossing points between path segments.

These algorithms work quickly and produce results in a predictable amount of time, which is important for daily route planning. However, the more points there are to visit, the less optimal the route found becomes.

Metaheuristic algorithms

Metaheuristic algorithms use randomness and principles borrowed from nature to find solutions close to optimal ones.

Main types:

  • Ant algorithm — imitates the behavior of an ant colony when searching for a path to food.
  • Simulated annealing — mimics the cooling and solidification process of materials as temperatures decrease.
  • Genetic algorithm — reproduces the principles of evolution and natural selection.

These algorithms find better routes than simple heuristic methods and can handle large amounts of data. However, they require individual configuration for each task, and it is difficult to predict how long the calculation will take.

Which method provides the most effective solution for the problem?

The choice of algorithm for solving the traveling salesman problem depends on specific business requirements: the number of points, the time available for calculations, and the required accuracy of the result.

When to use precise algorithms:

This approach works best for small-scale projects demanding maximum accuracy. For example, integration into navigation systems. The system will help save fuel and time by building a route for ATM maintenance. There are dozens of real-life examples. Such optimization helps save resources in the long term. The user receives the optimal route within seconds.

When to use heuristic algorithms:

Anywhere where high calculation speed and acceptable quality of results without complex configuration are important. The system will help plan deliveries of medium complexity (10–50 points). Who can use it:

  • Courier services that deliver parcels within the city;
  • Food delivery services;
  • Garbage collection routes, etc.

When to use metaheuristic algorithms:

If you want to save resources, it is worth spending more time on calculations:

  • Planning regional freight routes;
  • Optimizing delivery networks for large retailers;
  • Sales representative routes.

Metaheuristic algorithms solve large logistics problems (50+ points). They help create high-quality routes. Most companies do not develop their own TSP algorithms. Instead, they integrate ready-made solutions — a traveling salesman problem calculator or specialized APIs. These already contain optimized algorithms and are ready to use.

How to Solve the Traveling Salesman Problem. Different Programming Languages

The traveling salesman problem can be solved using various programming languages. The most popular options for TSP are Java, Python, C++, and C#, which offer powerful libraries and ready-made tools for working with optimization algorithms.

The main stages of software implementation are:

  • Creating a distance matrix between all pairs of points;
  • Selecting an algorithm (exact, heuristic, or metaheuristic);
  • Implementing the logic for finding the optimal route;
  • Returning the result as a sequence of points and the total cost.

Example of a practical task

Let's consider a simple case with 4 cities and the following distances:

Graph of the traveling salesman problem

Optimal route: 1→2→4→3→1 with a total cost of 80 km.

Popular languages and their advantages:

  • Python offers the scipy, networkx, and OR-Tools libraries, which contain ready-made implementations of TSP algorithms. The simplicity of its syntax makes Python ideal for prototyping and research.
  • Java has powerful libraries such as JGRAPHT and is optimized for high-performance enterprise applications.
  • C++ with the Boost Graph Library provides maximum execution speed, which is critical for processing large data arrays.
import java.io.*;
import java.util.*;

public class TSE {
    // there are four nodes in example graph (graph is 1-based)
    static int n = 4;
    // give appropriate maximum to avoid overflow
    static int MAX = 1000000;

    // dist[i][j] represents shortest distance to go from i to j
    // this matrix can be calculated for any given graph using all-pair shortest path algorithms
    static int[][] dist = {
        { 0, 0, 0, 0, 0 },
        { 0, 0, 10, 15, 20 },
        { 0, 10, 0, 35, 25 },
        { 0, 15, 35, 0, 30 },
        { 0, 20, 25, 30, 0 }
    };

    // memoization for top down recursion
    static int[][] memo = new int[n + 1][1 << (n + 1)];

    static int fun(int i, int mask) {
        // base case
        // if only ith bit and 1st bit is set in our mask,
        // it implies we have visited all other nodes already
        if (mask == ((1 << i) | 3))
            return dist[1][i];

        // memoization
        if (memo[i][mask] != 0)
            return memo[i][mask];

        int res = MAX; // result of this sub-problem

        // we have to travel all nodes j in mask and end the path at ith node
        // so for every node j in mask,
        // recursively calculate cost of travelling all nodes in mask
        // except i and then travel back from node j to node i
        // taking the shortest path take the minimum of all possible j nodes
        for (int j = 1; j <= n; j++) {
            if ((mask & (1 << j)) != 0 && j != i && j != 1)
                res = Math.min(res, fun(j, mask & (~(1 << i))) + dist[j][i]);
        }

        return memo[i][mask] = res;
    }

    // Driver program to test above logic
    public static void main(String[] args) {
        int ans = MAX;
        for (int i = 1; i <= n; i++) {
            // try to go from node 1 visiting all nodes in between to i
            // then return from i taking the shortest route to 1
            ans = Math.min(ans, fun(i, (1 << (n + 1)) - 1) + dist[i][1]);
        }

        System.out.println("The cost of most efficient tour = " + ans);
    }
}

An example of solving the traveling salesman problem using the Java programming language

For small educational projects, you can implement a simple nearest neighbor algorithm yourself. However, for commercial applications, it is recommended to use proven libraries or ready-made API services.

Modern specialized APIs eliminate the need to study TSP algorithms in depth and allow you to focus on solving business problems. They provide optimized solutions that take into account real road conditions, traffic, and restrictions.

Travelling Salesman Distance Matrix

One of the key tools for solving the travelling salesman problem is the distance matrix — a table that shows the distance or travel time between each pair of points. It serves as the basis for algorithms that search for the shortest or fastest route.

What is a traveling salesman distance matrix

A traveling salesman distance matrix is a two-dimensional table of size N×N, where N is the number of points on the route. The rows and columns correspond to the destination points, and the cells indicate the distances, travel times, or costs of moving between them. For example, for a courier with 8 delivery addresses, the matrix will be 8×8 in size and contain 64 values.

Features of such a matrix:

  • Diagonal elements are zero (the distance from a point to itself);
  • Symmetrical structure in most cases (the distance from A to B is equal to the distance from B to A);
  • Triangular filling is often sufficient for symmetrical tasks.

These properties allow you to optimize TSP algorithms and reduce the amount of necessary calculations.

Problems with manual matrix creation

Creating such a matrix manually is an extremely difficult and resource-intensive task. Imagine a courier who has to plan a route to 20 addresses in a large city. He will need to:

  • Calculate 400 unique distances (20×20);
  • Take into account traffic jams at different times of the day;
  • Take into account one-way streets;
  • Take into account traffic restrictions for freight transport;
  • Constantly update data as the traffic situation changes.

Manual calculation of such a matrix can take hours or even days, while the traffic situation is constantly changing.

The role of the Distance Matrix API in solving TSP

Modern TSP algorithms are critically dependent on the accuracy of input data. Inaccurate distance information can lead to suboptimal routes and unnecessary costs. The Distance Matrix API automates the process of creating a matrix, taking into account:

  1. Real road conditions:
    • Current traffic situation and traffic jams;
    • Road works and temporary restrictions.
  2. Different types of transport:
    • Cars;
    • Bicycle paths;
    • Public transport.
  3. Time factors:
    • Departure and arrival times;
    • Time windows for delivery.

Such data processing ensures high accuracy of TSP solutions and their practical applicability in real conditions.

Distance Matrix API from Distancematrix.ai in the TSP solution

The Distance Matrix API from Distancematrix.ai provides a comprehensive solution for TSP tasks.

Technical capabilities:

  • Processing of up to 100 elements per second for tasks with traffic;
  • Up to 500 elements per second for tasks without traffic consideration;
  • API response in less than a second;
  • Support for both synchronous and asynchronous requests.

Flexibility in use:

  • Transfer of coordinates or addresses in any format;
  • Receipt of a matrix with distances and travel times;
  • Real-time traffic conditions;
  • Support for various units of measurement.

Global coverage:

The API supports roads around the world, making it a universal solution for international logistics and companies operating in different countries.

Practical benefits of integration

Businesses and developers can:

  • save resources on collecting and updating geodata by focusing on routing logic;
  • abandon their own geoinformation infrastructure and receive up-to-date information;
  • scale solutions from small local tasks to large logistics operations;
  • integrate TSP functionality into existing systems with minimal code changes.

The result is a reliable, scalable, and accurate solution for TSP tasks of any complexity. No deep technical knowledge of optimization algorithms is required to use it.

Where is the Travelling salesman problem calculator used?

A traveling salesman calculator has become increasingly popular in recent years due to its ability to optimize complex routing problems in a fraction of the time it would take a human to solve them manually. It has practical applications in a wide range of fields, from logistics and transportation to finance and biology. TSP calculators use advanced algorithms to find the shortest possible route that visits a set of locations and returns to the starting point. 

This can be a valuable tool for businesses looking to optimize their delivery or sales routes, as well as for researchers looking to solve complex routing problems in their fields. By leveraging the power of a traveling salesman problem solver, organizations can save time, reduce costs, and increase efficiency.

Choosing the Right TSP Solution

When choosing an algorithm, the scale of the task plays a key role. Exact algorithms or simple heuristic methods are suitable for small tasks with 5-20 points. 

Heuristic algorithms with a good balance of speed and quality will help solve medium-sized tasks with 20-100 points. Metaheuristic algorithms are needed for large tasks with more than 100 points. Specialized solutions need to be created in special cases.

Accuracy requirements are crucial. Invest in complex algorithms if you are planning expensive shipments, and maximum savings are important to you. Fast heuristic methods are suitable for planning daily courier shipments.

You must take time constraints into account. It is important to find a balance between quality and speed. Be prepared to always have to compromise. Accuracy takes time. 

Categories of TSP solutions

Universities offer academic solutions. These are optimal algorithms from a theoretical point of view. However, it is impossible to implement them in practice without in-depth theoretical knowledge. Conclusion: academic solutions are not suitable for commercial use.

Ready-made libraries such as OR-Tools from Google, CPLEX, or Gurobi provide powerful tools for developers. They are suitable for companies with a strong technical team ready for customization and integration.

Commercial software packages for logistics offer ready-made functionality but may be limited in terms of configuration flexibility. API services provide professional quality without the need to develop your own algorithms.

Practical recommendations

Startups and small businesses do not need large investments in development to quickly launch a project. API integration allows them to scale as their business grows.

To balance control over logic and speed of implementation, medium-sized companies often choose a combination of ready-made libraries and API services. 

Large corporations can develop their own solutions based on academic algorithms. This allows them to fully meet the needs of their business. To speed up development and save company resources, you can choose licensed commercial solutions with deep customization.

Current trends

Most successful companies do not reinvent the wheel, but integrate proven solutions. This allows them to focus on their core business rather than complex routing mathematics.

Cloud API services are becoming the industry standard thanks to constant algorithm updates, consideration of real road conditions, scalability for any volume, and no need for proprietary infrastructure.

The best TSP solver is the one that solves your specific problem with the optimal balance of quality, speed, and cost. Specialized APIs are the best choice for most practical applications. They provide professional-level optimization without the technical complexity of development.

The Best TSP Solver

The Traveling Salesman Problem has no universal solution — success depends on the right approach to specific business requirements. However, the most important conclusion from the current implementation of TSPs is that successful companies rarely create routing algorithms in-house. 

The trend has shifted decisively toward API-based solutions that combine algorithmic complexity with practical simplicity. Modern distance matrix APIs provide real-time integration of traffic data, global road network coverage, instant scalability from small routes to enterprise-level operations, and do not require infrastructure investments or algorithm maintenance costs. 

Whether you're running a startup delivery service, optimizing mid-sized logistics operations, or managing enterprise distribution networks, professionally developed APIs are the most efficient way to achieve reliable routing optimization, allowing businesses to focus on growth rather than mathematical complexity.

Table of content

Start for free and get instant access to all Distancematrix.ai products and features

Read API documentation

Ready to Elevate Your Routing and Logistics with the Right Distance Matrix API?

  • Real-time traffic

  • Travel modes

  • Forecasting

  • Quick response

FAQ

What is the traveling salesman problem?

A classic optimization problem is the traveling salesman problem. You need to find the shortest route through all the specified points. Each point can only be crossed once. At the end, you must return to the starting point.

How to solve the traveling salesman problem?

There are three main ways: 

  • For small tasks that need the best solution, precise algorithms work well.
  • For medium-sized tasks that need quick results, heuristic algorithms are used.
  • Complex routing tasks can only be solved by metaheuristic algorithms.

Modern companies choose ready-made APIs or software. Developing your own algorithms from scratch is expensive and time-consuming.