Taxi services
Food delivery
Taxi services
Courier services
Logistics & Transportation
Courier services
Logistics & Transportation
Seeking the ideal traveling salesman problem solution for business
The task of optimal route finding is crucial for many businesses. It is known as the Traveling Salesman Problem or TSP and is of particular relevance in situations when the supply expenses are nearly compared to the cost of the product itself, and the speed of delivery is one of the main priorities. Let's take a look at the insight of this issue in more detail and learn what helpful solutions have been developed.
What is the Traveling Salesman Problem?
It is a well-known and intensely investigated issue. Challenge is to create the most optimal route passing through all specified points or cities only once and coming back to the beginning point. The task also should contain optimality route criteria: the shortest, the fastest, the cheapest, or all together and initial data of the route such as distance, cost, time, etc.
The TSP is based on the Hamilton cycle, which deals with finding a path visiting every node once, and returning to the beginning within the graph, but TSP is concerned with calculating a Hamiltonian circuit with the lowest cost.
The peculiarity of the TSP is that it is simple enough to formulate, and it is also relatively easy to get a good decision for it, but finding an optimal route for a large data set is not an easy and resource-intensive process.
The peculiarity of the TSP is that it is simple enough to formulate, and it is also relatively easy to get a good decision for it, but finding an optimal route for a large data set is not an easy and resource-intensive process.
Approaches for the traveling salesman problem solution
There are many different ways to solve this problem, which can be divided into several groups:
1. Exact algorithms find an assured right solution.
This group includes:
The brute force method - is a sequential consideration of all possible routes and choosing the optimal one.
The branch-and-bound method is a variation of the exhaustive search that differs by screening out from the calculating process subsets of ineffective solutions.
The key idea of dynamic programming is to calculate and memorize the distance traveled from the original city to all the others, then add to them the distances from the current cities to the remaining ones, and so on. The first application of dynamic programming is the Held - Karp Algorithm. Compared to exhaustive search, this tool can significantly reduce the amount of computation.
The main advantage of the group techniques is that they assure to find the right solution, which is not possible for algorithms from other groups. However, in practice, these algorithms are rarely applied due to the enormous time spent even for small values of N.
2. Heuristic algorithms determine good or near-optimal solutions but are sufficient to solve the problem.
Examples:
The wooden algorithm is a procedure for solving through the construction of the shortest spanning tree.
Greedy algorithms are based on finding locally optimal solutions at each stage of computations and assume that the final found solution will be globally optimal. So at each iteration, the best section of the path is selected, which is included in the final route. The most popular application of greedy algorithms is the Nearest Neighbor algorithm that builds a path by finding the vertex closest to a given vertex.
1. Exact algorithms find an assured right solution.
This group includes:
The brute force method - is a sequential consideration of all possible routes and choosing the optimal one.
The branch-and-bound method is a variation of the exhaustive search that differs by screening out from the calculating process subsets of ineffective solutions.
The key idea of dynamic programming is to calculate and memorize the distance traveled from the original city to all the others, then add to them the distances from the current cities to the remaining ones, and so on. The first application of dynamic programming is the Held - Karp Algorithm. Compared to exhaustive search, this tool can significantly reduce the amount of computation.
The main advantage of the group techniques is that they assure to find the right solution, which is not possible for algorithms from other groups. However, in practice, these algorithms are rarely applied due to the enormous time spent even for small values of N.
2. Heuristic algorithms determine good or near-optimal solutions but are sufficient to solve the problem.
Examples:
The wooden algorithm is a procedure for solving through the construction of the shortest spanning tree.
Greedy algorithms are based on finding locally optimal solutions at each stage of computations and assume that the final found solution will be globally optimal. So at each iteration, the best section of the path is selected, which is included in the final route. The most popular application of greedy algorithms is the Nearest Neighbor algorithm that builds a path by finding the vertex closest to a given vertex.
The 2-opt algorithm reduces to removing two intersecting edges and inserting new edges that do not break the correctness of the solution.
The advantages of these algorithms are the speed strict dependence of a solution finding on the initial data size. They also have the disadvantages - the low quality of the response with an increase in the number of cities.
3. Metaheuristic algorithms - generalized strategies for finding the optimum in the space of solutions, depending on randomness.
They include:
Ant algorithm - an algorithm that mimics the behavior of an ant colony seeking a path to a food source.
Simulated annealing is an algorithm that simulates the physical process of a substance crystallization at a decreasing temperature.
A genetic algorithm mimics the evolutionary process in nature.
The algorithm of cloning selection is a form of a genetic algorithm that does not use inheritance from multiple ancestors.
The advantages of these algorithms are implementation simplicity, finding more optimal paths in comparison with heuristic algorithms. The disadvantages of these algorithms include the dependence on hyperparameters, which are selected individually for different sets of initial data, as well as the complexity of the asymptotic analysis due to differing hyperparameters.
The advantages of these algorithms are the speed strict dependence of a solution finding on the initial data size. They also have the disadvantages - the low quality of the response with an increase in the number of cities.
3. Metaheuristic algorithms - generalized strategies for finding the optimum in the space of solutions, depending on randomness.
They include:
Ant algorithm - an algorithm that mimics the behavior of an ant colony seeking a path to a food source.
Simulated annealing is an algorithm that simulates the physical process of a substance crystallization at a decreasing temperature.
A genetic algorithm mimics the evolutionary process in nature.
The algorithm of cloning selection is a form of a genetic algorithm that does not use inheritance from multiple ancestors.
The advantages of these algorithms are implementation simplicity, finding more optimal paths in comparison with heuristic algorithms. The disadvantages of these algorithms include the dependence on hyperparameters, which are selected individually for different sets of initial data, as well as the complexity of the asymptotic analysis due to differing hyperparameters.
What approach to deal with the problem is better?
The choice of one or another approach to the traveling salesman problem solving is due to the initial data size, available production information, the definite implementing time, and the required goals. For example, use navigators require accuracy on a small amount of the original data with low performance and limited time. So it is justified to use precise algorithms. In the case of selecting the optimal routes for the goods delivery, the best solution is using heuristic algorithms that have predictable enough speed and no need to tune hyperparameters, also have good results with an insignificant amount of the initial data. If reliability is required for a significant number of points combined with high performance and limited time, it is worth using the metaheuristic algorithms.
Practical Significance of the Traveling Salesman Problem
The application of the TSP is quite extensive. The task is used in logistics, transport, various communication systems designing, even in psychology and pedagogy.
Examples of the possible options for using the traveling salesman problem in logistic practices are determining the optimal route for cargo transportation; calculation of the best way for couriers, in telecommunications and communications - satellite management, telecommunication systems design, informatics - data array clustering, energy and utilities - connecting settlements with power lines and gas supply), electronics (designing microcircuit topologies).
In addition to logistics, the task is also applied in the economy and human activity: finance (optimization of cash flows, for example, finding ways to transfer funds with minimal transaction costs), tourism (calculating routes for excursions and tours), show business (organizing tours of music groups), biology (genome assembly), etc.
In this regard, developing algorithms and methods for successful TSP solutions are in great demand.
Examples of the possible options for using the traveling salesman problem in logistic practices are determining the optimal route for cargo transportation; calculation of the best way for couriers, in telecommunications and communications - satellite management, telecommunication systems design, informatics - data array clustering, energy and utilities - connecting settlements with power lines and gas supply), electronics (designing microcircuit topologies).
In addition to logistics, the task is also applied in the economy and human activity: finance (optimization of cash flows, for example, finding ways to transfer funds with minimal transaction costs), tourism (calculating routes for excursions and tours), show business (organizing tours of music groups), biology (genome assembly), etc.
In this regard, developing algorithms and methods for successful TSP solutions are in great demand.
Popular solution in business practice — DistanceMatrix.ai API
Academic TSP solutions try to generate an ideal one for this vital issue but the vast majority are not suitable as real-life decisions. The reason is that creating the best decision is time-consuming. In real life, time frequently is a crucial choice factor. For instance, a logistics company needs to figure out a route in minutes when planning its daily schedule because its results depend on both these shipping route planning decisions and avoiding drivers' downtime. So the business world requires not optimal TSP solutions but near-optimal ones in the shortest possible time, providing companies with the opportunity to plan routes quickly and efficiently.
There are different ways to solve the TSP problem other than the academic approaches. There are a lot of API solutions for optimization, but they are significantly limited by the number of waypoints to be optimized, with no time windows, no round trips, no capacity constraints, etc.
Applying the Distance Matrix API, you can calculate the distance and the route time between each pair of locations taking into account real-time data. Keep in mind that depending on the particular task, you can make calculations taking into account the real-time traffic or not. Besides, the request calculation time is up to 50 elements per second, and you can get the API response in less than a second.
Distancematrix.ai API tool supports roads all over the world. Using it, you can assign the nearest driver based on proximity, provide job opportunities only for a particular drive time, and determine the nearest goods delivery point to a customer. Also, you can create a standard distance matrix or use a single origin with multiple destinations.
Distancematrix.ai also considerably facilitates the process when it is required to request a big matrix.
There are different ways to solve the TSP problem other than the academic approaches. There are a lot of API solutions for optimization, but they are significantly limited by the number of waypoints to be optimized, with no time windows, no round trips, no capacity constraints, etc.
Applying the Distance Matrix API, you can calculate the distance and the route time between each pair of locations taking into account real-time data. Keep in mind that depending on the particular task, you can make calculations taking into account the real-time traffic or not. Besides, the request calculation time is up to 50 elements per second, and you can get the API response in less than a second.
Distancematrix.ai API tool supports roads all over the world. Using it, you can assign the nearest driver based on proximity, provide job opportunities only for a particular drive time, and determine the nearest goods delivery point to a customer. Also, you can create a standard distance matrix or use a single origin with multiple destinations.
Distancematrix.ai also considerably facilitates the process when it is required to request a big matrix.
Conclusion
As you can see, efficient TSP resolving in your business practice can help you reduce the cost of the order and the delivery time, optimize trips and delivery for suppliers and distributors, etc. You can choose any of the many different tools for this purpose, but remember that Distancematrix.ai is a reliable one that can make things easier as it was designed for this. We strongly believe it's a great option to enhance the effectiveness of your business performance.
Sources:
1. Weiqi Li (February 9th 2021). How to Solve the Traveling Salesman Problem, Theory of Complexity - Definitions, Models, and Applications, Ricardo López-Ruiz, IntechOpen, DOI: 10.5772/intechopen.96129. Available from: https://www.intechopen.com/chapters/75156
2. Ćwik, M., & Józefczyk, J. (2018). Heuristic algorithms for the minmax regret flow-shop problem with interval processing times. Central European journal of operations research, 26(1), 215–238. https://doi.org/10.1007/s10100-017-0485-8
2. Ćwik, M., & Józefczyk, J. (2018). Heuristic algorithms for the minmax regret flow-shop problem with interval processing times. Central European journal of operations research, 26(1), 215–238. https://doi.org/10.1007/s10100-017-0485-8
Policies and terms
Distancematrix.ai © 2022. All rights reserved.
Products
Resources
