travelling salesman problem history

Traveling salesman problem

This web page is a duplicate of https://optimization.mccormick.northwestern.edu/index.php/Traveling_salesman_problems

Author: Jessica Yu (ChE 345 Spring 2014)

Steward: Dajun Yue, Fengqi You

The traveling salesman problem (TSP) is a widely studied combinatorial optimization problem, which, given a set of cities and a cost to travel from one city to another, seeks to identify the tour that will allow a salesman to visit each city only once, starting and ending in the same city, at the minimum cost. 1

• 2.1 Graph Theory
• 2.2 Classifications of the TSP
• 2.3 Variations of the TSP
• 3.1 aTSP ILP Formulation
• 3.2 sTSP ILP Formulation
• 4.1 Exact algorithms
• 4.2.1 Tour construction procedures
• 4.2.2 Tour improvement procedures
• 5 Applications
• 7 References

The origins of the traveling salesman problem are obscure; it is mentioned in an 1832 manual for traveling salesman, which included example tours of 45 German cities but gave no mathematical consideration. 2 W. R. Hamilton and Thomas Kirkman devised mathematical formulations of the problem in the 1800s. 2

It is believed that the general form was first studied by Karl Menger in Vienna and Harvard in the 1930s. 2,3

Hassler Whitney, who was working on his Ph.D. research at Harvard when Menger was a visiting lecturer, is believed to have posed the problem of finding the shortest route between the 48 states of the United States during either his 1931-1932 or 1934 seminar talks. 2 There is also uncertainty surrounding the individual who coined the name “traveling salesman problem” for Whitney’s problem. 2

The problem became increasingly popular in the 1950s and 1960s. Notably, George Dantzig, Delber R. Fulkerson, and Selmer M. Johnson at the RAND Corporation in Santa Monica, California solved the 48 state problem by formulating it as a linear programming problem. 2 The methods described in the paper set the foundation for future work in combinatorial optimization, especially highlighting the importance of cutting planes. 2,4

In the early 1970s, the concept of P vs. NP problems created buzz in the theoretical computer science community. In 1972, Richard Karp demonstrated that the Hamiltonian cycle problem was NP-complete, implying that the traveling salesman problem was NP-hard. 4

Increasingly sophisticated codes led to rapid increases in the sizes of the traveling salesman problems solved. Dantzig, Fulkerson, and Johnson had solved a 48 city instance of the problem in 1954. 5 Martin Grötechel more than doubled this 23 years later, solving a 120 city instance in 1977. 5 Enoch Crowder and Manfred W. Padberg again more than doubled this in just 3 years, with a 318 city solution. 5

In 1987, rapid improvements were made, culminating in a 2,392 city solution by Padberg and Giovanni Rinaldi. In the following two decades, David L. Appelgate, Robert E. Bixby, Vasek Chvátal, & William J. Cook led the cutting edge, solving a 7,397 city instance in 1994 up to the current largest solved problem of 24,978 cities in 2004. 5

Description

Graph theory.

In the context of the traveling salesman problem, the verticies correspond to cities and the edges correspond to the path between those cities. When modeled as a complete graph, paths that do not exist between cities can be modeled as edges of very large cost without loss of generality. 6 Minimizing the sum of the costs for Hamiltonian cycle is equivalent to identifying the shortest path in which each city is visiting only once.

Classifications of the TSP

The TRP can be divided into two classes depending on the nature of the cost matrix. 3,6

• Applies when the distance between cities is the same in both directions

• Applies when there are differences in distances (e.g. one-way streets)

An ATSP can be formulated as an STSP by doubling the number of nodes. 6

Variations of the TSP

Formulation

The objective function is then given by

To ensure that the result is a valid tour, several contraints must be added. 1,3

There are several other formulations for the subtour elimnation contraint, including circuit packing contraints, MTZ constraints, and network flow constraints.

aTSP ILP Formulation

The integer linear programming formulation for an aTSP is given by

sTSP ILP Formulation

The symmetric case is a special case of the asymmetric case and the above formulation is valid. 3, 6 The integer linear programming formulation for an sTSP is given by

Exact algorithms

Branch-and-bound algorithms are commonly used to find solutions for TSPs. 7 The ILP is first relaxed and solved as an LP using the Simplex method, then feasibility is regained by enumeration of the integer variables. 7

Other exact solution methods include the cutting plane method and branch-and-cut. 8

Heuristic algorithms

Given that the TSP is an NP-hard problem, heuristic algorithms are commonly used to give a approximate solutions that are good, though not necessarily optimal. The algorithms do not guarantee an optimal solution, but gives near-optimal solutions in reasonable computational time. 3 The Held-Karp lower bound can be calculated and used to judge the performance of a heuristic algorithm. 3

There are two general heuristic classifications 7 :

• Tour construction procedures where a solution is gradually built by adding a new vertex at each step
• Tour improvement procedures where a feasbile solution is improved upon by performing various exchanges

The best methods tend to be composite algorithms that combine these features. 7

Tour construction procedures

Tour improvement procedures

Applications

The importance of the traveling salesman problem is two fold. First its ubiquity as a platform for the study of general methods than can then be applied to a variety of other discrete optimization problems. 5 Second is its diverse range of applications, in fields including mathematics, computer science, genetics, and engineering. 5,6

Suppose a Northwestern student, who lives in Foster-Walker , has to accomplish the following tasks:

• Drop off a homework set at Tech
• Work out a SPAC
• Complete a group project at Annenberg

Distances between buildings can be found using Google Maps. Note that there is particularly strong western wind and walking east takes 1.5 times as long.

It is the middle of winter and the student wants to spend the least possible time walking. Determine the path the student should take in order to minimize walking time, starting and ending at Foster-Walker.

Start with the cost matrix (with altered distances taken into account):

Method 1: Complete Enumeration

All possible paths are considered and the path of least cost is the optimal solution. Note that this method is only feasible given the small size of the problem.

From inspection, we see that Path 4 is the shortest. So, the student should walk 2.28 miles in the following order: Foster-Walker → Annenberg → SPAC → Tech → Foster-Walker

Method 2: Nearest neighbor

Starting from Foster-Walker, the next building is simply the closest building that has not yet been visited. With only four nodes, this can be done by inspection:

• Smallest distance is from Foster-Walker is to Annenberg
• Smallest distance from Annenberg is to Tech
• Smallest distance from Tech is to Annenberg ( creates a subtour, therefore skip )
• Next smallest distance from Tech is to Foster-Walker ( creates a subtour, therefore skip )
• Next smallest distance from Tech is to SPAC
• Smallest distance from SPAC is to Annenberg ( creates a subtour, therefore skip )
• Next smallest distance from SPAC is to Tech ( creates a subtour, therefore skip )
• Next smallest distance from SPAC is to Foster-Walker

So, the student would walk 2.54 miles in the following order: Foster-Walker → Annenberg → Tech → SPAC → Foster-Walker

Method 3: Greedy

With this method, the shortest paths that do not create a subtour are selected until a complete tour is created.

• Smallest distance is Annenberg → Tech
• Next smallest is SPAC → Annenberg
• Next smallest is Tech → Annenberg ( creates a subtour, therefore skip )
• Next smallest is Anneberg → Foster-Walker ( creates a subtour, therefore skip )
• Next smallest is SPAC → Tech ( creates a subtour, therefore skip )
• Next smallest is Tech → Foster-Walker
• Next smallest is Annenberg → SPAC ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → Annenberg ( creates a subtour, therefore skip )
• Next smallest is Tech → SPAC ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → Tech ( creates a subtour, therefore skip )
• Next smallest is SPAC → Foster-Walker ( creates a subtour, therefore skip )
• Next smallest is Foster-Walker → SPAC

So, the student would walk 2.40 miles in the following order: Foster-Walker → SPAC → Annenberg → Tech → Foster-Walker

As we can see in the figure to the right, the heuristic methods did not give the optimal solution. That is not to say that heuristics can never give the optimal solution, just that it is not guaranteed.

Both the optimal and the nearest neighbor algorithms suggest that Annenberg is the optimal first building to visit. However, the optimal solution then goes to SPAC, while both heuristic methods suggest Tech. This is in part due to the large cost of SPAC → Foster-Walker. The heuristic algorithms cannot take this future cost into account, and therefore fall into that local optimum.

We note that the nearest neighbor and greedy algorithms give solutions that are 11.4% and 5.3%, respectively, above the optimal solution. In the scale of this problem, this corresponds to fractions of a mile. We also note that neither heuristic gave the worst case result, Foster-Walker → SPAC → Tech → Annenberg → Foster-Walker.

Only tour building heuristics were used. Combined with a tour improvement algorithm (such as 2-opt or simulated annealing), we imagine that we may be able to locate solutions that are closer to the optimum.

The exact algorithm used was complete enumeration, but we note that this is impractical even for 7 nodes (6! or 720 different possibilities). Commonly, the problem would be formulated and solved as an ILP to obtain exact solutions.

• Vanderbei, R. J. (2001). Linear programming: Foundations and extensions (2nd ed.). Boston: Kluwer Academic.
• Schrijver, A. (n.d.). On the history of combinatorial optimization (till 1960).
• Matai, R., Singh, S., & Lal, M. (2010). Traveling salesman problem: An overview of applications, formulations, and solution approaches. In D. Davendra (Ed.), Traveling Salesman Problem, Theory and Applications . InTech.
• Junger, M., Liebling, T., Naddef, D., Nemhauser, G., Pulleyblank, W., Reinelt, G., Rinaldi, G., & Wolsey, L. (Eds.). (2009). 50 years of integer programming, 1958-2008: The early years and state-of-the-art surveys . Heidelberg: Springer.
• Cook, W. (2007). History of the TSP. The Traveling Salesman Problem . Retrieved from http://www.math.uwaterloo.ca/tsp/history/index.htm
• Punnen, A. P. (2002). The traveling salesman problem: Applications, formulations and variations. In G. Gutin & A. P. Punnen (Eds.), The Traveling Salesman Problem and its Variations . Netherlands: Kluwer Academic Publishers.
• Laporte, G. (1992). The traveling salesman problem: An overview of exact and approximate algorithms. European Journal of Operational Research, 59 (2), 231–247.
• Goyal, S. (n.d.). A suvey on travlling salesman problem.

Navigation menu

Learning center series

Travelling salesman problem explained

• Published on April 26, 2024
• by Oguzhan Uyar
• Last updated: 2 months ago

Revolutionize your understanding of the Travelling Salesman Problem (TSP); a mind-boggling conundrum that has compelled academia and industry alike. In the upcoming lines, we decode the key concepts, algorithms, and anticipated solutions for 2024 to this age-old dilemma.

Now, picture the TSP as a globetrotting traveling salesman who’s whirlwind journey. He must stop at every city once, only the origin city once, and find the quickest shortest possible route back home. If daunting to visualize, consider this: the possible number of routes in the problem concerning just 20 cities exceeds the number of atoms in the observable universe.

Fathom the sheer magnitude?

So, what is the Travelling Salesman Problem, and why has it remained unsolved for years? Let’s snap together the puzzle of this notorious problem that spans mathematics, computer science, and beyond. Welcome to an insightful voyage into the astonishing world of the TSP.

Understanding the Travelling Salesman Problem (TSP): Key Concepts and Algorithms

Defining the travelling salesman problem: a comprehensive overview.

The Travelling Salesman Problem, often abbreviated as TSP, has a strong footing in the realm of computer science. To the untrained eye, it presents itself as a puzzle: a salesperson or traveling salesman must traverse through a number of specific cities before an ending point and return to their ending point as of origin, managing to do so in the shortest possible distance. But this problem is not simply a conundrum for those fond of riddles; it holds immense significance in the broad field of computer science and optimization. Optimizing travel routes is the key to solving the Travelling Salesman Problem efficiently, ensuring the shortest and most cost-effective journey for salespeople or travelers.

The sheer computational complexity of TSP is what sets it apart, and incidentally, why it is considered a challenging problem to solve. Its complexity derives from the factorial nature of the problem: whenever a new city is added, the total number of possibilities increases exponentially. Thus, as the problem scope enlarges, it swiftly becomes computationally prohibitive to simply calculate all possible solutions to identify an optimal shortest route through. Consequently, developing effective and efficient algorithms to solve the TSP has become a priority in the world of computational complexity.

Polynomial Time Solution: The TSP can be solved by a deterministic Turing machine in polynomial time, which means that the number of steps to solve the problem can be at most 1.5 times the optimal global solution.

One such algorithm is the dynamic programming approach that can solve TSP problems in polynomial time. The approach uses a recursive formula to compute the shortest possible route that visits all other nodes in the cities exactly once and ends at all nodes in the starting point or city. Moreover, linear programming and approximation algorithms have also been used to find near-optimal solutions.

Unraveling TSP Algorithms: From Brute Force to Heuristics

A multitude of algorithms have been developed to contend with the TSP. The brute force method, for example, entails considering the shortest distance for all possible permutations of cities, calculating the total distance for six cities along each route, and selecting the shortest distance for one. While brute force promises an optimal solution, it suffers from exponential computational complexity, rendering it unfeasible for large datasets.

TSP Complexity: A TSP with just 10 cities has 362,880 possible routes , making brute force infeasible for larger instances.

On the other hand, we have heuristic algorithms that generate good, albeit non-optimal, solutions in reasonable timeframes. The greedy algorithm, for instance, initiates from a starting city and looks for the shortest distance from other nodes to the next node minimizes the distance, and guarantees speed but is not necessarily an optimal solution.

Algorithmic Potential: Local Solutions 4/3 Times Optimal Global: The theoretical conjecture suggests an algorithm that can provide a local solution within 4/3 times the optimal global solution.

Record Local TSP Solution: The record for a local solution to the Traveling Salesman Problem (TSP) is 1.4 times the optimal global solution, achieved in September 2012 by Andr´as Seb˝o and Jens Vygen.

Exploring further, we encounter more refined heuristic solutions such as the genetic algorithm and simulated annealing algorithm. These algorithms deploy probabilistic rules, with the former incorporating principles of natural evolution and the latter being inspired by the cooling process in metallurgy. They differ significantly from each other in terms of how they search for solutions, but when compared to brute force, they often offer a promising trade-off between quality and computational effort.

Certainly, the TSP is far more than a problem to puzzle over during a Sunday afternoon tea. It’s a complex computational task with real-world implications, and unraveling it requires more than brute force; it demands the application of sophisticated algorithms designed to balance efficiency and quality of results. Nevertheless, with a better understanding of the problem statement and its dynamics, you can unlock the potential to not just solve problems faster, but to do so more intelligently.

Practical Solutions to the Travelling Salesman Problem

Implementing tsp solutions: a step-by-step guide, a comprehensive process for implementing tsp solutions.

Developing complete, practical solutions for the Travelling Salesman Problem (TSP) requires a good grasp of specific algorithms. Visual aids, for example, such as finding all the edges leading out of a given city, can help to simplify the process. Enhance your ability to solve the Travelling Salesman Problem by mastering route optimization with Google Maps , streamlining your path and saving significant time on the go.

TSP's Computer Science Quest for Shortest Routes: The TSP involves finding the shortest route to visit a set of cities exactly once before returning to the starting city, aiming to minimize travel distance.

One popular approach to TSP problem solving is the dynamic programming approach, which involves breaking down the problem into smaller sub-problems and recursively solving them. Other approaches include approximation algorithms, which generate near-optimal solutions to small problems in polynomial time, and bound algorithms, which aim to find an upper bound on the optimal solution given graph top.

TSP Variants: ASTP and STSP The TSP can be divided into two types: the asymmetric traveling salesman problem (ASTP) and the symmetric traveling salesman problem (STSP)

Practical code implementation

Before diving into code manipulations, it’s worth noting that practical implementation varies based on the specifics of the problem and the chosen algorithm. Let’s further deconstruct these notions by examining the steps for code implementation for a pre-determined shortest path first. It’s crucial to efficiently concede each point of the shortest path, call other nodes, connect each node, and conclude each route. Hereby, I shall delve into the practicalities of coding from an output standpoint, concentrating on readability, scalability, and execution efficiency.

TSP Instance Size: The size of the TSP instances used in the studies is 100 nodes.

Cluster Quantity in TSP Instances: The number of clusters in the TSP instances used in the studies is 10 .

The Quantity of Instances per Cluster in Studies: The number of instances in each cluster used in the studies is 100.

Optimizing TSP Solutions: Tips and Tricks

Tsp solutions optimization techniques.

An optimized solution for the TSP is often accomplished using advanced algorithms and techniques. Optimization techniques allow professionals to solve more intricate problems, rendering them invaluable tools when handling large datasets and attempting to achieve the best possible solution. Several approaches can be taken, such as heuristic and metaheuristic approaches, that can provide near-optimal solutions with less use of resources.

Expert Advice for Maximum Efficiency Minimum Cost

Even the most proficient problem solvers can gain from learning expert tips and tricks. These nuggets of wisdom often provide the breakthrough needed to turn a good solution into a great one. The TSP is no exception. Peering into the realm of experts can provide novel and creative ways to save time, increase computation speed, manage datasets, and achieve the most efficient shortest route around.

By comprehending and implementing these solutions to the Travelling Salesman Problem, one can unravel the complex web of nodes and paths. This equips any problem-solver with invaluable insights that make navigating through real-world TSP applications much more manageable. By adopting sophisticated routing planner software , businesses can significantly streamline their delivery operations, ensuring a more predictable and cost-effective way of dealing with the challenges presented by the Travelling Salesman Problem.

Real-World Applications of the Travelling Salesman Problem

Tsp in logistics and supply chain management.

The Travelling Salesman Problem (TSP) is not confined to theoretical mathematics or theoretical computer science either, it shines in real-world applications too. One of its most potent applications resides in the field of logistics and supply chain management. Explore how the latest gratis route planning applications can revolutionize logistics and supply chain efficiency by uncovering the top 10 free software tools for 2024.

With globalization, the importance of more efficient routes for logistics and supply chain operations has risen dramatically. Optimizing routes and decreasing costs hold the key to success in this arena. Here’s where TSP comes into play. Discover how Planning for Multiple Stops can revolutionize your logistics, ensuring the most efficient paths are taken. Dive into our post to see how it streamlines operations and reduces expenses.

In the vast complexity of supply chain networks, routing can be a colossal task. TSP algorithms bring clarity to the chaos, eliminating redundant paths and pointing to the optimal route covering the most distance, shortest path, and least distance between all the necessary points—leading to a drastic dip in transportation costs and delivery times. Uncover how optimizing delivery routes can revolutionize your logistics, ensuring efficiency and cost-effectiveness in your delivery operations.

Real-World Examples

Consider the case of UPS – the multinational package delivery company. They’ve reportedly saved hundreds of millions of dollars yearly by implementing route optimization algorithms originating from the Travelling Salesman Problem. The solution, named ORION, helped UPS reduce the distance driven by their drivers roughly by 100 million miles annually.

TSP in GIS and Urban Planning: Optimal Route

TSP’s contributions to cities aren’t confined to logistics; it is invaluable in Geographic Information Systems (GIS) and urban planning as well. A city’s efficiency revolves around transportation. The better the transport networks and systems, the higher the city’s productivity. And as city authorities continuously strive to upgrade transportation systems, they find an ally in TSP. Discover how TSP enhances road architecture by integrating specialized truck routing solutions , elevating urban transport strategies.

Advanced GIS systems apply TSP to design more efficient routes and routing systems for public transportation. The aim of the route is to reach maximum locations with the least travel time and least distance, ensuring essential amenities are accessible to everyone in the city.

The city of Singapore, known for its efficient public transportation system, owes part of its success to similar routing algorithms. The Land Transport Authority uses TSP-related solutions to plan bus routes, reducing travel durations and enhancing accessibility across the city.

Delving Deeper: The Complexity and History of the Travelling Salesman Problem

Understanding the complexity of tsp.

TSP is fascinating not just for its inherent practicality but also for the complexity it brings along. TSP belongs to a class of problems known as NP-hard, a category that houses some of the most complex problems in computer science. But what makes TSP so gnarled?

Unravel the Intricacies: Why is TSP complex?

TSP is a combinatorial optimization problem, which simply means that it’s all about figuring out the most often optimal solution among a vast number of possible solutions or combinations of approximate solutions. The real challenge comes from an innocent-sounding feature of TSP: As the number of cities (we call them nodes) increases, the complexity heightens exponentially, not linearly. The number of possible routes takes a dramatic upward turn as you add more nodes, clearly exemplifying why TSP is no walk-in-the-park problem.

NP-hard and TSP: A Connection Explored

In computer science, we use the terms P and NP for classifying problems. P stands for problems where a solution can be found in ‘polynomial time’. NP stands for ‘nondeterministic polynomial time’, which includes problems where a solution can be verified in polynomial time. The concept of ‘NP-hardness’ applies to TSP. Any problem that can be ‘reduced’ to an NP problem in polynomial time is described as NP-hard. In simpler terms, it’s harder than the hardest problems of NP. TSP holds a famed position in this class, making it a noteworthy example of an NP-hard problem. Discovering efficient solutions for the Traveling Salesman Problem (TSP) exemplifies how optimizing routes can streamline complex logistical challenges, showcasing the practical impact of advancements in algorithmic route optimization.

A Look Back: The History of the Travelling Salesman Problem

TSP is not a new kid on the block. Its roots can be traced back to the 1800s, and the journey since then has been nothing short of a compelling tale of mathematical and computational advancements.

The Origins and Evolution of TSP

Believe it or not, the Travelling Salesman Problem was first formulated as a mathematical problem in the 1800s. This was way before the advent of modern computers. Mathematicians and logisticians were intrigued by the problem and its implications. However, it wasn’t until the mid-20th century that the problem started to gain more widespread attention. Over the years, the TSP has transformed from a theoretical model to a practical problem that helps solve real-world issues.

A Classic Shortest Route Problem Since 1930s: The TSP is a classic optimization problem within the field of operations research, first studied during the 1930s.

Milestones in TSP Research

Looking at all the cities and milestones in TSP research, the story is truly impressive. From some of the initial heuristic algorithms to solve smaller instances of TSP, to geometric methods and then approximation algorithms, TSP research has seen a lot. More recently, we have also seen practical solutions to TSP using quantum computing — a testament to how far we’ve come. Each of these milestones signifies an innovative shift in how we understand and solve TSP. Discovering the top delivery route planning software in 2024, we navigated through the advancements in TSP solutions to identify which applications excel in streamlining delivery logistics.

Wrapping Up The Journey With Algorithms and Solutions

The Travelling Salesman Problem (TSP) remains a complex enigma of business logistics, yet, the advent of sophisticated algorithms and innovative solutions are paving avenues to optimize routing, reduce travel costs further, and enhance customer interactions.

Navigating the TSP intricacies is no longer a daunting challenge but a worthwhile investment in refining operational efficiency and delivering unparalleled customer experiences. With advanced toolsets and intelligent systems, businesses are closer to making more informed, strategic decisions.

Now, it’s your turn. Reflect on your current logistics complexities. How can your business benefit from implementing these key concepts and algorithms? Consider where you could incorporate these practices to streamline and revolutionize your daily operations.

Remember, in the world of dynamic business operations, mastering the TSP is not just an option, but a strategic imperative. As you move forward into 2024, embrace the art of solving the TSP. Unravel the potential, decipher the complexities, and unlock new horizons for your business.

Ready for the challenge?

What is route optimization?

Top route optimization algorithms

What is multi-stop route planning and why is it important?

What is multi stop route planning and why is it important?

How to optimize routes with Google Maps

7 benefits of using route scheduling software

Benefits of using route scheduling software

Why delivery route optimization is crucial

What does a route planning software do?

Truck route planning vs common route planning

‟Reliability, Accuracy & Timeliness”

Bartleby’s Ice Cream Cakes

‟It was just invaluable for us to be able to just hand off the delivery process”

Smart Lunches

‟Thanks to Metrobi we powered our consumer deliveries and started wholesale deliveries”

Dorchester Brewing Company

‟We were able to cut costs by 30%, saving thousands of dollars each month”

Flamingo Estate

• Route Optimization
• travelling salesman problem

• dynamic route optimization

• vehicle routing problem

• free route planning software

• truck route

• route planning software

• Operate a Brewery
• operate a brewery

• Brewery Menu
• brewery menu

• Brewery Business Plan
• brewery business plan

• Brewery Marketing
• brewery marketing

• Brewery Supplies and Equipment
• brewery supplies

• Restaurant Marketing
• restaurant marketing

• Types of Shipping Methods
• International shipping

• Click and collect shipping

• omnichannel logistics

• Last Mile Delivery Glossary
• green transportation

• payload capacity

Success Stories

Anna’s Taqueria

Fleurs to You

GrandTen Distilling

Field Trip Flowers

P’s Patties

DELIVER WITH METROBI

Grow with confidence

• 55 Court St floor 2, Boston, MA 02108
• [email protected]
• Team Metrobi
• Privacy policy
• Terms of service
• Write for us

Refer us to a company, you earn $250 and they earn $250. Learn more

• Shopify Delivery Planner App
• Delivery Management Software
• Atlanta courier service
• Boston courier service
• Chicago courier service
• Denver courier service
• Miami courier service
• New York City courier service
• Los Angeles courier service
• Philadelphia courier service
• San Francisco courier service
• Washington DC courier service
• See all locations
• Bulk Order Delivery Service
• Express Urgent Delivery Service
• Fixed Route Delivery Service
• On Demand Delivery Service
• Overnight Delivery Service
• Same Day Delivery Service
• Scheduled Delivery Service
• Wholesale Delivery Service
• See all delivery services
• Metrobi vs. Onfleet
• Metrobi vs. Roadie
• Metrobi vs. Roadie Support
• Artisan Food
• Food Producers

Want to access our large pool of drivers?

We started Metrobi to take operations off your plate. We provide drivers (rated 4.97/5), dedicated operation managers (70% cheaper), and routing software with a receiver notification system.

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Travelling salesman problem

2020 Mathematics Subject Classification: Primary: 90C35 Secondary: 90C27 [ MSN ][ ZBL ]

A generic name for a number of very different problems. For instance, suppose that a facility (a "machine" ) starting from an "idle" position is assigned to process a finite set of "jobs" (say $n$, $n\geq3$ jobs). If the machine has to be "calibrated" (or "set-up" ) for processing each of these jobs and if the machine's "calibration time" (the distance metric) between processing of a pair of jobs in succession is dependent on the particular pair, then a reasonable objective is to organize this job assignment so it will minimize the total machine calibration time. One might want to assume that after the last job is processed the machine returns to its idle position.

A very similar problem exists when the "machine" corresponds to a computer centre which has $n$ programs to run, and each program requires resources such as a compiler, a certain portion of the main memory, and perhaps some other "devices" . I.e., each program requires a specific configuration of devices. Conversion cost (or time) from one configuration to another, say from the configuration of program $i$ to that of program $j$ is denoted by $c_{ij}$ ($\geq0$). Thus, the question becomes that of determining the cost minimizing order in which all the programs ought to be run.

If at the end of running all the programs by the computer centre the system returns to an "idle" configuration, then the number of possible ways to run these programs one after the other equals $n!$ (for $n+1$ configurations).

This is the same problem as that in the story about the lonely salesman who has to visit $n$ sales outlets (starting from his home) and wishes to travel the shortest total distance in the process. It is the salesman's problem to select a distance-minimizing travel order of outlet visits. Thus, the name travelling salesman problem.

In graph terminology terms, the problem is presented as that of a graph $G=(V,E)$, where$V$ is a finite set of nodes ( "cities" ) and $E\subset V\times V$ is the set of edges connecting the node pairs in $V$. If one associates a real-valued "cost" matrix $(c_{ij})$, $i,j=1,\ldots,\lvert V\rvert$, with the set of edges $E$, the travelling salesman dilemma becomes that of constructing a cost-minimizing circuit on $G$ that visits all the nodes in $V$ exactly once, if such a circuit exists (cf. also Graph circuit ).

If the requirement is that all the nodes in $V$ are visited in a cost-minimizing fashion but without necessarily forming a circuit, then the problem is referred to as a travelling salesman path problem, or travelling salesman walk problem. Again, the question of the existence of such a path has to be addressed first.

If the graph $G=(V,A)$, $A\subset V\times V$, assigns a "direction" to each element in $A$ (a subset of arcs), then the corresponding travelling salesman problem is of the "directed" variety. Clearly, there is the option of the mixed problem, where some of the node pairs are connected by arcs and some by edges.

The question of whether a circuit exists in a graph $G$ which visits each node in $V$ exactly once is commonly referred to as that of determining the existence of a Hamiltonian circuit (or path; cf. also Hamiltonian tour ). Graphs for which such a circuit (path) is guaranteed to exist are called Hamiltonian graphs.

The difficulty of determining the existence of a Hamiltonian circuit for a graph $G$ and that of constructing a cost-minimizing travelling salesman circuit on a graph $G$ are very much the same when measured by the worst possible order magnitude of the required number of computer operations. This casts these problems (the travelling salesman and the Hamiltonian circuit problems) as being "hard" (cf. also $\mathcal{NP}$ ). Essentially, for this sort of problems, one does not presently (2000) know of any solution scheme which does not require some sort of enumeration of all possible "configuration" sequences.

See [a1] , [a2] for recent overviews of the problem.

• Mathematics in science and technology
• Operations research, mathematical programming
• This page was last edited on 19 April 2012, at 22:51.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

Traveling Salesman Problem

• Reference work entry
• First Online: 01 January 2016
• pp 1573–1578
• Cite this reference work entry

• Karla L. Hoffman 3 ,
• Manfred Padberg 4 &
• Giovanni Rinaldi 5  

7022 Accesses

106 Citations

1 Altmetric

Introduction

The traveling salesman problem (TSP) has commanded much attention from mathematicians and computer scientists specifically because it is so easy to describe and so difficult to solve. The problem can simply be stated as: if a traveling salesman wishes to visit exactly once each of a list of m cities (where the cost of traveling from city i to city j is c ij ) and then return to the home city, what is the least costly route the traveling salesman can take? A complete historical development of this and related problems can be found in Hoffman and Wolfe ( 1985 ), Applegate et al. ( 2006 ), and Cook ( 2011 ).

The importance of the TSP is that it is representative of a larger class of problems known as combinatorial optimization problems. The TSP problem belongs in the class of such problems known as NP -complete. Specifically, if one can find an efficient (i.e., polynomial-time) algorithm for the traveling salesman problem, then efficient algorithms could be found for all other...

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Durable hardcover edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Aarts, E. H. L., Korst, J. H. M., & Laarhoven, P. J. M. (1988). A quantitative analysis of the simulated annealing algorithm: A case study for the traveling salesman problem. Journal of Statistical Physics, 50 , 189–206.

Article   Google Scholar  

Applegate, D., Bixby, R. E., Chvátal, V., & Cook, W. (1995). Finding cuts in the TSP(A preliminary report) DIMACS (Technical Report 95–05). New Brunswick, USA: Rutgers University.

Google Scholar  

Applegate, D., Bixby, R. E., Chvátal, V., & Cook, W. (2006). The traveling salesman problem: A computational study . Princeton: Princeton University Press.

Arora, S. (2002). Approximation algorithms for geometric TSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 207–222). Dordrecht, The Netherlands: Kluwer.

Balas, E. (2002). The prize collecting traveling salesman problem and its applications. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 663–696). Dordrecht, The Netherlands: Kluwer.

Balas, E., & Fischetti, M. (2002). Polyhedral theory for the asymmetric traveling salesman problem. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 117–168). Dordrecht, The Netherlands: Kluwer.

Ben-Dor, A., & Chor, B. (1997). On constructing radiation hybrid maps. Journal of Computational Biology, 4 , 517–533.

Ben-Dor, A., Chor, B., & Pelleg, D. (2000). RHO-radiation hybrid ordering. Genome Research, 10 , 365–378.

Bland, R. E., & Shallcross, D. F. (1987). Large traveling salesman problem arising from experiments in X-ray crystallography: A preliminary report on computation (Technical Report No. 730). Ithaca, New York: School of OR/ IE, Cornell University.

Burkard, R. E., Deineko, V. G., van Dal, R., van der Veen, J. A. A., & Woeginger, G. J. (1998). Well-solvable cases of the traveling salesman problem: A survey. SIAM Review, 40 , 496–546.

Cook, W. (2011). In pursuit of the salesman: Mathematics at the limits of computation . Princeton: Princeton University Press.

Dantzig, G. B., Fulkerson, D. R., & Johnson, S. M. (1954). Solution of a large-scale traveling salesman problem. Operations Research, 2 , 393–410.

Fiechter, C. N. (1990). A parallel tabu search algorithm for large scale traveling salesman problems (Working Paper 90/1). Switzerland: Department of Mathematics, Ecole Polytechnique Federale de Lausanne.

Fisher, M. L. (1988). Lagrangian optimization algorithms for vehicle routing problems. In G. K. Rand (Ed.), Operational research ’87 , pp. 635–649.

Golden, B. L., Levy, L., & Vohra, R. (1987). The orienteering problem. Naval Research Logistics, 34 , 307–318.

Golden, B. L., & Stewart, W. R. (1985). Empirical analysis of heuristics. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 207–250). Chichester: John Wiley.

Grötschel, M., & Holland, O. (1991). Solution of large scale symmetric traveling salesman problems. Mathematical Programming, 51 , 141–202.

Grötschel, M., & Padberg, M. W. (1985). Polyhedral theory. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 251–306). Chichester: John Wiley.

Gutin, G., & Punnen, A. P. (Eds.). (2002). The traveling salesman problem and its variations . Dordrecht, The Netherlands: Kluwer.

Helsgun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126 , 106–130.

Hoffman, A. J., & Wolfe, P. (1985). History. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 1–16). Chichester: John Wiley.

Johnson, D. S., & McGeoch, L. A. (2002). Experimental analysis of heuristics for the STSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 369–444). Dordrecht: Kluwer.

Johnson, D. S., & Papadimitriou, C. H. (1985). Performance guarantees for heuristics. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 145–180). Chichester: John Wiley.

Johnson, D. S., Gutin, G., McGeoch, L. A., Yeo, A., Zhang, W., & Zverovitch, A. (2002). Experimental analysis of heuristics for the ATSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 485–488). Dordrecht, The Netherlands: Kluwer.

Jünger, M., Reinelt, G., & Rinaldi, G. (1994). The traveling salesman problem. In M. Ball, T. Magnanti, C. Monma, & G. Nemhauser (Eds.), Handbook on operations research and the management sciences (pp. 225–330). Amsterdam: North Holland.

Jünger, M., Reinelt, G., & Rinaldi, G. (1997). The traveling salesman problem. In M. Dell'Amico, F. Maffioli, & S. Martello (Eds.), Annotated bibliographies in combinatorial optimization (pp. 199–221). New York: Wiley.

Karp, R., & Steele, J. M. (1985). Probabilistic analysis of heuristics. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 181–205). Chichester: John Wiley.

Lawler, E. L., Lenstra, J. K., Rinnooy Kan, A. H. G., & Shmoys, D. B. (Eds.). (1985). The traveling salesman problem . Chichester, UK: John Wiley.

Miller, D., & Pekny, J. (1991). Exact solution of large asymmetric traveling salesman problems. Science, 251 , 754–761.

Naddef, D. (2002). Polyhedral theory and branch-and-cut algorithm for the symmetric TSP. In G. Gutin & A. P. Punnen (Eds.), The traveling salesman problem and its variations (pp. 21–116). Dordrecht, The Netherlands: Kluwer.

Nagata, Y. (2006). New EAX crossover for large TSP instances. Lecture Notes in Computer Science, 4193 , 372–381.

Padberg, M. W., & Grötschel, M. (1985). Polyhedral computations. In E. L. Lawler, J. K. Lenstra, A. H. G. Rinooy Kan, & D. B. Shmoys (Eds.), The traveling salesman problem (pp. 307–360). Chichester: John Wiley.

Padberg, M. W., & Rinaldi, G. (1991). A branch and cut algorithm for the resolution of large-scale symmetric traveling salesmen problems. SIAM Review, 33 , 60–100.

Potvin, J. V. (1993). The traveling salesman problem: A neural network perspective. INFORMS Journal on Computing, 5 , 328–348.

Potvin, J. V. (1996). Genetic algorithms for the traveling salesman problem. Annals of Operations Research, 63 , 339–370.

Ratliff, H. D., & Rosenthal, A. S. (1981). Order-picking in a rectangular warehouse: A solvable case for the traveling salesman problem (PDRC Report Series No. 81–10). Atlanta: Georgia Institute of Technology.

Reinelt, G. (1991). TSPLIB–A traveling salesman library. ORSA Journal on Computing, 3 , 376–384.

Reinelt, G. (1994). The traveling salesman: Computational solutions for TSP applications . Berlin: Springer-Verlag.

Toth, P., & Vigo, D. (2001). The vehicle routing problem . Philadelphia: SIAM.

Download references

Author information

Authors and affiliations.

George Mason University, Fairfax, VA, USA

Karla L. Hoffman

New York University, New York, NY, USA

Manfred Padberg

CNR – Istituto di Analisi dei Sistemi ed Informatica (IASI), Viale Manzoni 30, 00185, Rome, Italy

Giovanni Rinaldi

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Karla L. Hoffman .

Editor information

Editors and affiliations.

Robert H. Smith School of Business, University of Maryland, College Park, MD, USA

Saul I. Gass

Robert H. Smith School of Business and Institute for Systems Research, University of Maryland, College Park, MD, USA

Michael C. Fu

Rights and permissions

Reprints and permissions

Copyright information

© 2013 Springer Science+Business Media New York

About this entry

Cite this entry.

Hoffman, K.L., Padberg, M., Rinaldi, G. (2013). Traveling Salesman Problem. In: Gass, S.I., Fu, M.C. (eds) Encyclopedia of Operations Research and Management Science. Springer, Boston, MA. https://doi.org/10.1007/978-1-4419-1153-7_1068

Download citation

DOI : https://doi.org/10.1007/978-1-4419-1153-7_1068

Published : 23 January 2016

Publisher Name : Springer, Boston, MA

Print ISBN : 978-1-4419-1137-7

Online ISBN : 978-1-4419-1153-7

eBook Packages : Business and Economics

Share this entry

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Open Access is an initiative that aims to make scientific research freely available to all. To date our community has made over 100 million downloads. It’s based on principles of collaboration, unobstructed discovery, and, most importantly, scientific progression. As PhD students, we found it difficult to access the research we needed, so we decided to create a new Open Access publisher that levels the playing field for scientists across the world. How? By making research easy to access, and puts the academic needs of the researchers before the business interests of publishers.

We are a community of more than 103,000 authors and editors from 3,291 institutions spanning 160 countries, including Nobel Prize winners and some of the world’s most-cited researchers. Publishing on IntechOpen allows authors to earn citations and find new collaborators, meaning more people see your work not only from your own field of study, but from other related fields too.

Brief introduction to this section that descibes Open Access especially from an IntechOpen perspective

Want to get in touch? Contact our London head office or media team here

Our team is growing all the time, so we’re always on the lookout for smart people who want to help us reshape the world of scientific publishing.

Home > Books > Novel Trends in the Traveling Salesman Problem

Introductory Chapter: Traveling Salesman Problem - An Overview

Submitted: 20 August 2020 Published: 09 December 2020

DOI: 10.5772/intechopen.94435

Cite this chapter

There are two ways to cite this chapter:

From the Edited Volume

Novel Trends in the Traveling Salesman Problem

Edited by Donald Davendra and Magdalena Bialic-Davendra

To purchase hard copies of this book, please contact the representative in India: CBS Publishers & Distributors Pvt. Ltd. www.cbspd.com | [email protected]

Chapter metrics overview

992 Chapter Downloads

Impact of this chapter

Total Chapter Downloads on intechopen.com

Total Chapter Views on intechopen.com

Author Information

Donald davendra *.

• Central Washington University, Ellensburg, USA

Magdalena Bialic-Davendra

*Address all correspondence to: [email protected]

1. Introduction

The traveling salesman problem (TSP) is considered one of the seminal problems in computational mathematics. Considered as part of the Clay Mathematics Institute Millennium Problem with its assertion of P = N P [ 1 ], the TSP problem has been well researched during the past five decades.

The TSP problem can be described as the following: consider a number of cities which must be visited by a traveling salesman, only once, arriving once and departing once and starting and ending at the same city. Given the pairwise distances between cities, what is the best order in which to visit them, so as to minimize the overall distance traveled?

Mathematically, the equation for the TSP can be given as in Eq. (1) :

where x ij = 1 if city i is connected with city j , and x ij = 0 otherwise. For i = 0 , … , n , let u i be an artificial variable and finally take c ij to be the distance from city i to city j . The objective function can be then formulated as Eq. (2) :

2. Complexity

The complexity of the TSP is still unknown. Using a brute force approach to test each and every tour, for a tour of n cities, it will be ( n-1 )! possibilities and it will have a time complexity of O n ! . However, using the dynamic programming approach, the complexity can be derived of a tour of n cities, which can be divided into n-2 subsets each of size n-1 , with the constraint that all such subsets don’t have the n th city in them. Therefore, there are a maximum of O n 2 n such subproblems, which can be solved in linear time. The time complexity is therefore O n 2 2 n . Both space and time complexity of the TSP problem can be considered as exponential .

The genesis of the TSP problem is difficult to pinpoint. Some literature point to widespread usage since the 1950’s [ 2 ], after the 48 state problem posed by Hassler Whitney in the 1930’s induced a lot of interest. The subsequent second world war really ingrained the use of operations research into this domain. An excellent detailed history is given in [ 3 ], where TSP is considered as a part of the history of Combinatorial Optimization.

The TSP problem over time has evolved into many different branches, each with different constraints:

Symmetric TSP (STSP) - the basic TSP problem, where the distance between city i and city j is the same as from city j and city i .

Asymmetric TSP (ATSP) - modified TSP, where the distance between city i and city j is not the same as from city j and city i .

Hamiltonian Cycle Problem (HCP) - is a problem where finding if a path in an undirected or directed graph G that visits each vertex V exactly once exists.

Sequential Ordering Problem (SOP) - Given a set of n cities and distances for each pair of cities, find a Hamiltonian path from city 1 to city n of minimal length, which takes given precedence constraints (such as requiring some nodes to be visited prior) into account.

Capacitated Vehicle Routing Problem (CVRP) - Given n-1 nodes, 1 depot (with resources) and distances between the nodes, the objective is to satisfy demand at each node using vehicles with identical capacity with the shortest tour.

Case Enough TSP (CETSP) - a problem developed for radio frequency identification (RFID), where close proximity is enough to a node. The objective is to trace the shortest path interlinking the different nodes.

TSP with Neighborhoods (TSPN) - where a collection of L regions in the plane, called neighborhoods is given and the objective is to seek the shortest tour to visit all these neighborhoods.

4. Current literature

Linear programming and deterministic methods have been seen as the early solvers, however, intractability of this problem has led to a general decline in these mathematical formulations. Within the past few decades with the rise of computational power, a new branch of algorithms called meta-heuristics generally based on evolutionary dynamics have become more synonymous with solving combinatorial optimization problems. Based around naturally occurring phenomena, these algorithms treat each problem as a black box with the aim of finding feasibly good solutions within acceptable space and time constraints. A vast repository of literature exists for the TSP problem, and the TSP Library is an excellent starting off resource point [ 4 ].

4.1 Deterministic approaches

2-Opt Algorithm [ 5 ]

Branch and Cut Algorithm [ 6 ]

Approximate and Exact Algorithms [ 7 ]

Branch and Bound [ 8 ]

4.2 Evolutionary approaches

Artificial Bee Colony [ 10 ]

Differential Evolution [ 11 ]

Genetic Algorithm [ 12 ]

Tree Seed Algorithm [ 13 ]

Spider Monkey [ 14 ]

Ant Colony Optimization [ 15 ]

Harmony Search Algorithm [ 16 ]

Pigeon Inspired Optimization [ 17 ]

4.3 High performance computing

Multi-Core approach [ 18 ]

OpenMP [ 19 ]

CUDA [ 20 ]

5. Future direction

Even though a number of problems, especially in the combinatorial and scheduling domain have increased over the past decade, the TSP problem have remained a vital area of research. This is primarily for it being generally equated to the intractably quandary of P = N P , with its far reaching consequences in other fields such as encryption etc. It is the belief that a combination of smart heuristics employed on super-computers with parallel programming paradigms will be the future direction of tacking large-scale TSP problems.

• 1. Clay Mathematics Institute https://www.claymath.org/millennium-problems/p-vs-np-problem [Accessed: 10 October 2020]
• 2. Applegate DL, Bixby RE, Chvatal V, Cook WJ. The Traveling Salesman Problem: A Computational Study. Princeton. Oxford: Princeton University Press; 2006
• 3. Alexander S. On the History of Combinatorial Optimization (Till 1960), Editor(s): K. Aardal, G.L., Nemhauser, R., Weismantel, Handbooks in Operations Research and Management Science, Elsevier, Vol 12, Pages 1-68, 2005
• 4. TSP Library. http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/ [Accessed: 10 October 2020]
• 5. Hougardy S, Zaiser F, Zhong X. The approximation ratio of the 2-Opt Heuristic for the metric Traveling Salesman Problem. Operations Research Letters. 2020; 48 (4):401-404
• 6. Yuan Y, Cattaruzza D, Ogier M, Semet F. A branch-and-cut algorithm for the generalized traveling salesman problem with time windows. European Journal of Operational Research. 2020; 286 (3):849-866, ISSN 0377-2217. DOI: 10.1016/j.ejor.2020.04.024
• 7. Wang S, Liu M, Chu F. Approximate and exact algorithms for an energy minimization traveling salesman problem. Journal of Cleaner Production. 2020; 249 :119433, ISSN 0959-6526. DOI: 10.1016/j.jclepro.2019.119433
• 8. Salman R, Ekstedt F, Damaschke P. Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem. Operations Research Letters. 2020; 48 (2):163-166, ISSN 0167-6377. DOI: 10.1016/j.orl.2020.01.009
• 9. Dorigo M, Gambardella L. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. April 1997; 1 (1):53-66. DOI: 10.1109/4235.585892
• 10. Pandiri V, Singh A. An artificial bee colony algorithm with variable degree of perturbation for the generalized covering traveling salesman problem. Applied Soft Computing. 2019; 78 :481-495, ISSN 1568-4946. DOI: 10.1016/j.asoc.2019.03.001
• 11. Ali I, Essam D, Kasmarik K. A novel design of differential evolution for solving discrete traveling salesman problems. Swarm and Evolutionary Computation. 2020; 52 :100607, ISSN 2210-6502. DOI: 10.1016/j.swevo.2019.100607
• 12. Dong X, Cai Y. A novel genetic algorithm for large scale colored balanced traveling salesman problem. Future Generation Computer Systems. 2019; 95 :727-742, ISSN 0167-739X. DOI: 10.1016/j.future.2018.12.065
• 13. Cinar A, Korkmaz S, Kiran M. A discrete tree-seed algorithm for solving symmetric traveling salesman problem. Engineering Science and Technology, an International Journal. 2020; 23 (4):879-890, ISSN 2215-0986. DOI: 10.1016/j.jestch.2019.11.005
• 14. Akhand MAH, Ayon I, Shahriyar SA, Siddique N, Adeli H. Discrete Spider Monkey Optimization for Travelling Salesman Problem. Applied Soft Computing. 2020; 86 :105887, ISSN 1568-4946. DOI: 10.1016/j.asoc.2019.105887
• 15. Tuani A, Keedwell E, Collett M. Heterogenous Adaptive Ant Colony Optimization with 3-opt local search for the Travelling Salesman Problem. Applied Soft Computing. 2020; 106720 , ISSN 1568-4946. DOI: 10.1016/j.asoc.2020.106720
• 16. Boryczka U, Szwarc K. The Harmony Search algorithm with additional improvement of harmony memory for Asymmetric Traveling Salesman Problem. Expert Systems with Applications. 2019; 122 :43-53, ISSN 0957-4174. DOI: 10.1016/j.eswa.2018.12.044
• 17. Zhong Y, Wang L, Lin M, Zhang H. Discrete pigeon-inspired optimization algorithm with Metropolis acceptance criterion for large-scale traveling salesman problem. Swarm and Evolutionary Computation. 2019; 48 :134-144, ISSN 2210-6502. DOI: 10.1016/j.swevo.2019.04.002
• 18. Wei X, Ma L, Zhang H, Liu Y. Multi-core-, multi-thread-based optimization algorithm for large-scale traveling salesman problem. Alexandria Engineering Journal. 2020. DOI: 10.1016/j.aej.2020.06.055
• 19. Burkhovetskiy V, Steinberg B. Parallelizing an exact algorithm for the traveling salesman problem. Procedia Computer Science. 2017; 119 :97-102, ISSN 1877-0509. DOI: 10.1016/j.procs.2017.11.165
• 20. Ermis G, Catay B. Accelerating local search algorithms for the travelling salesman problem through the effective use of GPU. Transportation Research Procedia. 2017; 22 :409-418, ISSN 2352-1465. DOI: 10.1016/j.trpro.2017.03.012

© 2020 The Author(s). Licensee IntechOpen. This chapter is distributed under the terms of the Creative Commons Attribution 3.0 License , which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

Continue reading from the same book

Edited by Donald Davendra

Published: 09 December 2020

By Donald Davendra, Magdalena Metlicka and Magdalena ...

938 downloads

By Weiqi Li

785 downloads

By Fusheng Xiong, Michael Kuby and Wayne D. Frasch

1029 downloads

Pictoral History of the TSP

Given a finite number of "cities" along with the cost of travel between each pair of them, find the cheapest way of visiting all the cities and returning to your starting point.

Route Optimization

Traveling salesman problem (tsp) and how tech can solve it.

Mar 2, 2020

11 mins read

Updated: Mar 9, 2023

Salespersons are required to travel frequently as a part of their job, with the aim of maximizing their business opportunities. However, their daily schedules are often subject to sudden changes due to scheduled and last-minute customer appointments, making it difficult for them to plan optimal travel routes. As a result, salespersons are forced to take longer routes to reach their destinations, which can result in missed appointments and lost business opportunities.

What is the Traveling Salesman Problem (TSP)? 

The Traveling Salesman Problem (TSP) involves finding the shortest possible route to multiple destinations and returning to the starting point. However, this is a complex task due to various constraints such as traffic, last-minute customer requests, and strict delivery windows. Successfully solving the TSP challenge can optimize supply chains and reduce logistics costs, making it an important problem to tackle.

Despite its seemingly simple definition, the TSP becomes increasingly difficult as more cities are added to the itinerary. For example, when delivering to six cities, there could be up to 360 possible routes to consider. Finding the most efficient and feasible path requires evaluating every possible route, which is a computationally challenging task. This has been an ongoing problem since the 1990s.

The TSP has relevance in various industries, such as astronomy, computer science, car navigation, agri-business, airline crew scheduling, computer-generated art, internet planning, logistics planning and scheduling, and microchip production.

What is the objective of TSP?

The problem statement for the Traveling Salesman Problem (TSP) has remained the same over the years: “Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city and returns to the origin city?” This was one of the most well-formulated optimizations in 1930 and remains a powerful solution for logistics-related problems. Variations in TSP problems have since made a disruptive difference in many other areas, including DNA sequencing.

TSP is no longer just about the problem of a salesman traveling to multiple cities in the least amount of time, using the least amount of money, while traveling the shortest distance. It now involves the world gearing towards the Fourth Industrial Revolution.

As cutting-edge technology is being integrated into manufacturing, TSP provides access to a wide variety of operations. For instance, a TSP variation could help design an efficient microchip. Similarly, an asymmetric version of TSP can optimize the set-up cost of a paint manufacturing plant by rearranging the vicinity of colors.

Is the Traveling Salesman Problem solvable?

Considering the basic problem itself, optimizing the logistics of a traveling salesman is under more monetary pressure than ever in history. Even if the problem is kept within city limits, it would be significant enough to become news. This is a real problem at a time when convenience is preferred over everything. A country’s GDP depends on its e-commerce purchases, which is something TSP enthusiasts didn’t foresee five decades ago.

India’s e-commerce industry is expected to contribute $300 billion by 2030, and the entire burden of it rests on the backseat of a delivery bike or transport. There are significant costs associated with this, particularly with return logistics being a pain point. What complicates the TSP logic further is the ground reality where the whole market is dependent upon cash-on-delivery, making it impossible to determine if a delivery will earn its cost back at times.

The problem also manifests itself in ride-sharing. Those who carpool to work heavily depend on affordable and comfortable transportation, and the twice-a-day practice that occurs during rush hour is not easy on anyone. There is added time and pressure for picking up each passenger, constant deviation from the main route to drop off others, and stress associated with it cannot be optimized.

Why is the Traveling Salesman Problem crucial to solve?

The Traveling Salesman Problem is a serious challenge for the logistics and supply chain industry because it involves optimizing the delivery routes for multiple destinations while considering various constraints such as traffic, delivery windows, and customer requests.

With multiple vehicles, more cities and multiple sales professionals, TSP becomes more challenging to solve. Not solving the TSP makes it difficult for sales professionals to efficiently reach their customers, and lead to a fall in business revenues.

Solving traveling salesman problems benefit businesses in numerous ways:

• Saves fuel and reduces the hours traveled by the sales and field professionals 
• Minimizes the distance traveled, thereby reducing the carbon footprint considerably
• Timely meetings with clients and on-time delivery of goods 
• Elevate last-mile customer experience for delivery and field service businesses

Why is Traveling Salesman Problem challenging to solve? 

In theory, solving the Traveling Salesman Problem (TSP) is relatively simple as it involves finding the shortest route for every trip within a city. However, as the number of cities increases, manually solving TSP becomes increasingly difficult. With just 10 cities, the permutations and combinations are already numerous. Adding just five more cities can exponentially increase the number of possible solutions.

It’s impossible to find an algorithm that solves every single TSP problem. There are also some constraints that make TSP more challenging to solve:

• No automated records of scheduled and last-minute business appointments 
• Traffic congestion
• Sudden change of routes 
• Increasing number of last-minute business appointments 
• Stricter customer time windows 
• Rising operational fleet costs

All these constraints give a clear insight that TSP is a real-world problem. It is impossible to solve this challenge with even the best of your manual efforts. Thus, it is necessary to harness the power of technology to manage the TSP problem efficiently.

Using the Hungarian method to solve the Travelling Salesman Problem

To feel the intensity of the problem closely, one can try solving it using the Hungarian method. If one assumes that a delivery executive makes 15 stops in a day, it would still be too large to optimize by hand. In the ride-sharing example where the car has to make four stops—picking up three passengers and returning to the point of origin—costs need to be allocated between rides. It is important not to repeat the same route twice and to solve the TSP to arrive at the minimum cost.

The calculation may seem quite simple at the moment, but scaling the execution of such optimized routes to handle deliveries worth $300 billion is a huge challenge. It would not only overwhelm one’s mind but quite possibly the RAM of one’s computer too. It seems unfair that such a large computational problem, which has taken decades to solve, has suddenly become so large that only a few have the power to tackle it.

How does Artificial Intelligence technology help in solving the Traveling Salesman Problem? 

Modern enterprises want to attract customers by providing superior service. A customer that interacts with an enterprise for a business opportunity wants the business to value their needs. 

Most customers make business decisions based on how salespeople from an enterprise respond to their requirements. The crucial aspect that they look out for in a salesperson is whether they are able to be on time for business appointments. A salesperson that travels to multiple locations should ensure they attend business appointments on time.

The Traveling Salesman Problem makes it way more difficult for salespersons to make their business appointments on time and reach their sales targets. With a lot of complexities involved in routes traveled, it is necessary for them to employ the right technology to counter them. Artificial Intelligence (AI) plays an active role in helping businesses counter route inefficiencies and solve TSP.

AI combines human intuition with complex mathematics in real-time. It analyzes a massive amount of data clearly and quickly. It mainly helps a modern enterprise to make operational, strategic and tactical decisions.

Here’s how AI solved TSP in many modern enterprises. 

Makes optimized decisions for each vehicle and route

With increasing business appointments, it would be difficult for enterprise businesses to control operational fleet costs . It is highly challenging to manage crucial business appointments without the help of technology, especially when the business handles multiple vehicles and multiple salespersons.

AI technology helps operation managers in a business to prepare and assign optimal sales schedules for their workforce. By taking into account vicinity, vehicle capacity, customer time window, skills of sales professionals, driver skills and so on, it generates optimal appointment schedules. These optimal schedules help the businesses strictly adhere to the Service Line of Agreement (SLA)

Read:      The Definitive Guide to Logistics Route Optimization

Saves fuel and labor costs

According to the “An Analysis of the Operational Costs of Trucking: 2022 Update”, the average fuel cost per mile decreased further from $0.308 in 2020 to $0.296 in 2021.

Since the outbreak of the Covid-19 pandemic in 2020, fuel costs have been at record low levels. However, as the world moves towards a post-pandemic stage in 2023, fuel costs have started to rise steadily. The Ukraine-Russia war in 2022 and its trade shocks have had a significant impact on fuel prices, resulting in a sharp increase. As a result, fuel costs have become a larger proportion of operational costs for carriers in 2023.

The increasing number of appointments on a daily basis for salespersons makes it difficult for businesses to minimize fuel costs.

Employing the right technology like AI will help salespersons complete the maximum number of customer appointments by traveling a minimal distance. Its optimally allocated route plans reduce the traveling time and help businesses avoid wastage of fuel and labor costs.

Recognize the right addresses

When you are in a rush to complete your sales visits, unclear addresses can induce delays. If the driver is going to ride in an unfamiliar area, delays will increase. These delays can even cause missed appointments.

By using an AI application like route optimization software , enterprise businesses can avoid delays caused due to incorrect addresses. Its competent geocoding capabilities convert unclear or incomplete text addresses into geographical coordinates , thereby reducing the chances of reaching wrong customer locations.

Reduces cost per mile

According to the “An Analysis of the Operational Costs of Trucking: 2022 Update” by the American Transport Research Institute, the average cost per mile of trucks continued to decrease from $1.646 in 2020 to $1.585 in 2021.

As fuel costs continue to rise and the world moves towards a post-pandemic period, there is a potential for an increase in the average cost per mile for trucks. This poses a challenge for modern enterprise businesses who want their salespersons to reach their targets without increasing operational fleet costs. To achieve their sales targets, salespersons need to attend more business appointments.

AI technology with its algorithms factors business goals and delivery constraints to come up with efficient routes. Its optimal route recommendations enable salespersons to take the cost-minimizing route, thereby attending a maximum number of business appointments in a day and minimizing cost per mile. 

Improves productivity 

What happens when salespersons attend business appointments in locations where they may not have many opportunities? It results in deadhead or empty miles. Empty miles kill the productivity of the fleet, and drive up operational costs considerably. 

AI technology coupled with data insights helps modern enterprise businesses analyze their past performance of sales appointments. It helps them identify business opportunities that incur huge costs and work out new ways to counter them. Based on historical data, it assists stakeholders of a business to rightsize their fleet requirements and direct them to locations where higher demand is expected. The past data records and predictive capabilities of AI help them implement strategies that improve productivity of their sales professionals.

With modern enterprise businesses struggling from incorrect routes and delays, it has become highly-crucial to solve TSP situations. Scientists have been working on solving the TSP problem for decades. But the modern AI-backed routing software has gone closer towards solving traveling salesman problems with their complex algorithms and enhanced route planning capabilities.

The Locus Dispatch Management Platform is the best-in-class tool that has helped many enterprise businesses solve their traveling salesman problems. Its algorithms help sales professionals generate the most efficient schedules for any complicated routes without any manual interference. By employing its AI capabilities, you can increase the number of appointments with your customers by traveling a minimal distance, thereby making sales visits more optimal.

To build the most efficient routes for your sales schedules and counter TSP effectively, try a demo with Locus now!

Related Tags:

Healthcare / Pharmaceutical

Route optimization for the pharmaceutical industry: countering last-mile delivery problems.

Feb 28, 2020

Pharmaceutical organizations spend on average 6% of their revenue on logistics- World Health Organization and Parenteral Drug Association statistics (WHO and PDA).  The pharmaceutical industry has been successful in creating life-saving drugs through advanced research and clinical trials. Transportation and storage determine the major success of pharma products globally. A small mistake in logistics can […]

CEP and 3PL

The future of e-commerce lies in achieving same-day and slot-based deliveries.

Mar 4, 2020

Convenience. That’s the word of our times.  With all the apps doing the rounds, everything happens in an instant. Have a thought that the world should know? Type it, tweet it. Have a photo that you took on your weekend cycling trip, upload and post it with a crazy caption on Instagram. Hungry? Food from […]

• Schedule a Demo

MOST POPULAR

The Rise of Hub and Spoke Distribution Model in Modern Supply Chains

Shweta Sarma

Apr 24, 2020

How to Calculate the Cost of Transport

Jun 9, 2023

EDITOR’S PICKS

Top 4 Mid-Mile Logistics Challenges and How to Solve Them 

Dec 7, 2023

Navigating Returns: Five Strategies for Shippers to Reduce Return to Origin

Prateek Shetty

Nov 28, 2023

Last Mile Automation: Intelligent Routing is Key to Success

Mar 28, 2023

SUBSCRIBE TO OUR NEWSLETTER

Stay up to date with the latest marketing, sales, and service tips and news

Discover more from Locus Blog

Subscribe now to keep reading and get access to the full archive.

Type your email…

Continue reading

• Data Structures
• Linked List
• Binary Tree
• Binary Search Tree
• Segment Tree
• Disjoint Set Union
• Fenwick Tree
• Red-Black Tree
• Advanced Data Structures
• Graph Data Structure And Algorithms
• Introduction to Graph Data Structure
• Graph and its representations
• Types of Graphs with Examples
• Basic Properties of a Graph
• Applications, Advantages and Disadvantages of Graph
• Transpose graph
• Difference Between Graph and Tree

BFS and DFS on Graph

• Breadth First Search or BFS for a Graph
• Depth First Search or DFS for a Graph
• Applications, Advantages and Disadvantages of Depth First Search (DFS)
• Applications, Advantages and Disadvantages of Breadth First Search (BFS)
• Iterative Depth First Traversal of Graph
• BFS for Disconnected Graph
• Transitive Closure of a Graph using DFS
• Difference between BFS and DFS

Cycle in a Graph

• Detect Cycle in a Directed Graph
• Detect cycle in an undirected graph
• Detect Cycle in a directed graph using colors
• Detect a negative cycle in a Graph | (Bellman Ford)
• Cycles of length n in an undirected and connected graph
• Detecting negative cycle using Floyd Warshall
• Clone a Directed Acyclic Graph

Shortest Paths in Graph

• How to find Shortest Paths from Source to all Vertices using Dijkstra's Algorithm
• Bellman–Ford Algorithm
• Floyd Warshall Algorithm
• Johnson's algorithm for All-pairs shortest paths
• Shortest Path in Directed Acyclic Graph
• Multistage Graph (Shortest Path)
• Shortest path in an unweighted graph
• Karp's minimum mean (or average) weight cycle algorithm
• 0-1 BFS (Shortest Path in a Binary Weight Graph)
• Find minimum weight cycle in an undirected graph

Minimum Spanning Tree in Graph

• Kruskal’s Minimum Spanning Tree (MST) Algorithm
• Difference between Prim's and Kruskal's algorithm for MST
• Applications of Minimum Spanning Tree
• Total number of Spanning Trees in a Graph
• Minimum Product Spanning Tree
• Reverse Delete Algorithm for Minimum Spanning Tree

Topological Sorting in Graph

• Topological Sorting
• All Topological Sorts of a Directed Acyclic Graph
• Kahn's algorithm for Topological Sorting
• Maximum edges that can be added to DAG so that it remains DAG
• Longest Path in a Directed Acyclic Graph
• Topological Sort of a graph using departure time of vertex

Connectivity of Graph

• Articulation Points (or Cut Vertices) in a Graph
• Biconnected Components
• Bridges in a graph
• Eulerian path and circuit for undirected graph
• Fleury's Algorithm for printing Eulerian Path or Circuit
• Strongly Connected Components
• Count all possible walks from a source to a destination with exactly k edges
• Euler Circuit in a Directed Graph
• Word Ladder (Length of shortest chain to reach a target word)
• Find if an array of strings can be chained to form a circle | Set 1
• Tarjan's Algorithm to find Strongly Connected Components
• Paths to travel each nodes using each edge (Seven Bridges of Königsberg)
• Dynamic Connectivity | Set 1 (Incremental)

Maximum flow in a Graph

• Max Flow Problem Introduction
• Ford-Fulkerson Algorithm for Maximum Flow Problem
• Find maximum number of edge disjoint paths between two vertices
• Find minimum s-t cut in a flow network
• Maximum Bipartite Matching
• Channel Assignment Problem
• Introduction to Push Relabel Algorithm
• Introduction and implementation of Karger's algorithm for Minimum Cut
• Dinic's algorithm for Maximum Flow

Some must do problems on Graph

• Find size of the largest region in Boolean Matrix
• Count number of trees in a forest
• A Peterson Graph Problem
• Clone an Undirected Graph
• Introduction to Graph Coloring

Traveling Salesman Problem (TSP) Implementation

• Introduction and Approximate Solution for Vertex Cover Problem
• Erdos Renyl Model (for generating Random Graphs)
• Chinese Postman or Route Inspection | Set 1 (introduction)
• Hierholzer's Algorithm for directed graph
• Boggle (Find all possible words in a board of characters) | Set 1
• Hopcroft–Karp Algorithm for Maximum Matching | Set 1 (Introduction)
• Construct a graph from given degrees of all vertices
• Determine whether a universal sink exists in a directed graph
• Number of sink nodes in a graph
• Two Clique Problem (Check if Graph can be divided in two Cliques)

Travelling Salesman Problem (TSP) : Given a set of cities and distances between every pair of cities, the problem is to find the shortest possible route that visits every city exactly once and returns to the starting point.  Note the difference between Hamiltonian Cycle and TSP. The Hamiltonian cycle problem is to find if there exists a tour that visits every city exactly once. Here we know that Hamiltonian Tour exists (because the graph is complete) and in fact, many such tours exist, the problem is to find a minimum weight Hamiltonian Cycle.  For example, consider the graph shown in the figure on the right side. A TSP tour in the graph is 1-2-4-3-1. The cost of the tour is 10+25+30+15 which is 80. The problem is a famous NP-hard problem. There is no polynomial-time known solution for this problem.   

Examples: 

In this post, the implementation of a simple solution is discussed.

• Consider city 1 as the starting and ending point. Since the route is cyclic, we can consider any point as a starting point.
• Generate all (n-1)! permutations of cities.
• Calculate the cost of every permutation and keep track of the minimum cost permutation.
• Return the permutation with minimum cost.

Below is the implementation of the above idea 

Time complexity:  O(n!) where n is the number of vertices in the graph. This is because the algorithm uses the next_permutation function which generates all the possible permutations of the vertex set.  Auxiliary Space: O(n) as we are using a vector to store all the vertices.

Please Login to comment...

Similar reads.

• NP Complete

Improve your Coding Skills with Practice

What kind of Experience do you want to share?