travelling salesman explained

What is a Travelling Salesman Problem (TSP)? Explained!

• Author: Diksha Bhandari
• Read Time: 9 min
• Published: September 14, 2023
• Last Update: November 8th, 2023

Table of Contents

• Asset Tracking
• Dispatch Management
• Driver Behaviour
• Electric Vehicle
• Employee Management
• Field Sales And Service
• Fleet Management
• Fuel Management
• GPS Software
• GPS Trackers and Hardware
• Last Mile Delivery
• Lead Management
• Leave And Attendance
• Roster Management
• Route Optimisation
• Route Planning
• Sensor Integration
• Task and Workflow
• Tech and Beyond
• TrackoBit Industries
• TrackoField
• TrackoField Industries
• TrackoMile Industries
• Vehicle Tracking
• Video telematics
• What's New

Want to know what a travelling salesman problem (TSP) is? Need solutions to real-life TSP challenges. Learn here. 

Do you also look for the shortest route on Google Maps before embarking on a trip?

I am sure, you know multiple routes to reach the office, the mall, or your desired location, but checking on the internet before leaving home has become a ritual. It becomes all the more important to refer to maps when you have to pick up friends or colleagues along the way.

‘ADD STOPS’

Yes, you are right! 💯

That’s what solving the TSP challenge using software means!

What is a Travelling Salesman Problem (TSP)?

The traveling salesman problem is the popular combinatorial optimisation challenge in mathematics and computer science. The prime objective of the problem is to determine the shortest possible route a salesperson must take to cover a set of locations in one go and then return to the starting point.

Addressing travelling salesman challenges and their optimisation are more relevant in this time and age, especially in the supply chain, logistics and delivery space.

TSP may result in delayed deliveries and slimming profits as it’s not easy for delivery agents to choose the most viable and cost-effective route in real-time.

What are Traveling Salesman Problem Challenges to Solve?

When a salesperson is in the field hopping from one client site to another, finding out the best and the shortest route is an added pressure on the agent. In today’s day and age, distance isn’t the only factor that defines efficiency. There are several factors, such as time, fuel consumption, capacity, etc. that together define efficiency.

However, addressing the travelling salesman challenges involves mitigating a few unavoidable challenges along the way that field agents face themselves.

1. Time Constraints

Sales agents often have a tight schedule with multiple deliveries to make with a short TAT. Similarly, in TSP, optimising routes to minimise travel time is a fundamental challenge.

2. Last-minute Changes

Eleventh-hour changes are not a new concept for salespeople. They encounter urgent visits and last-minute cancellations a lot. Similarly, TSP solutions must be adaptable to handle dynamic scenarios and route modifications.

3. Resource Efficiency

Just as salespersons aim at reducing fuel costs and ensuring on-time deliveries, TSP solutions such as TrackoMile must strive for resource optimisation by reducing travel distances and delivery TAT.

4. Objective Diversification

While solving the travelling salesman problem (TSP) , optimising multiple objectives such as cost, time, and environmental factors adds complexity as solutions need to balance conflicting goals.

5. Combinatorial Complexity

TSP is a combinatorial optimisation problem, which means it involves complicated mathematical calculations with numerous variables. Sometimes, complex scenarios get further intricate as multiple variables are involved.

6. Adaptability and Scalability

Similarly, how sales agents adjust to the routes on the fly, the route algorithm must be flexible and responsive to real-time changes such as spiking volumes, vehicle breakdown or traffic slow down. A TSP solution must have a good appetite to handle large datasets and complex networks.

Also Read 4 Key Solutions for Fuel Management System 2023

Top 5 Solutions to The Travelling Salesman Problem

The traveling salesman problem solutions offer various trade-offs between computational intricacies and the quality of the resolution, allowing practitioners to choose the best-suited approach based on their needs and problems.

Here are the Top 5 solutions to the Traveling Salesman Problem (TSP) :

1. Brute Force Algorithm

The Brute Force algorithm is a straight approach to solving the Traveling Salesman Problem (TSP). It systematically explores all possible routes to identify the shortest one among them all. While it guarantees an optimal solution, its downside lies in its major time complexity, making it practical only for small TSP challenges.

2. Nearest Neighbour Algorithm

The Nearest Neighbour method is the simplest heuristic for the TSP. It starts from the first location and repeatedly selects the closest unvisited location to form a tour. Although it is quick to implement this method, it may always yield the optimal solution for it prioritises proximity over other factors.

3. Genetic Algorithm

This technique or method draws inspiration from nature itself. They evolve TSP solutions through selection, crossovers and mutation. They pick the best routes and mix them up. This creates new routes that might be even better. Then, they keep the best ones and repeat the mixing and picking process. Survival of the fittest in the true sense.

4. Ant Colony Optimisation (ACO)

Ants have a tendency to leave pheromones on the shorter routes they find, calling fellow ants on the same route. They keep leaving more pheromones on the shorter routes they find. Over time, the collective behaviour of the ants causes them to converge on the shortest route. Inspired by the nature of ants, ACO finds the shortest route by analysing the trails of data left by artificial ants based on the strength of these data trails.

5. Dynamic Programming

Dynamic Programming is like solving a puzzle, step-by-step, by breaking it into smaller pieces. In TSP challenges, it finds the best route to visit all locations. It begins with figuring out the shortest route between two locations; then it builds on that to find ways to more locations. It’s a smart TSP solution for small scenarios but may require significant memory resources for larger and more complex problems.

What Are Real-world Travelling Salesman Problem Applications?

The Traveling Salesman Problem (TSP) has a wide array of applications across various domains due to its relevance in optimising routes and sequences. Here are several crucial real-word TSP applications and implementations in the real world.

1. TSP implementation in Logistics and Delivery Services

The logistics and supply chain sectors have the widest TSP applications.

• Courier, Express & Parcel : Companies like FedEx, UPS, and DHL rely on TSP algorithms to optimise delivery routes for their fleet of delivery trucks. By finding the most efficient sequence of stops, they minimise fuel consumption , reduce delivery TAT, and save on operational overheads too.
• On-demand Delivery : Food delivery companies, instant grocery delivery apps and at-home appointment platforms like Swiggy, BlinkIt and UrbanCompany, respectively, leverage TSP solutions to ensure timely delivery. Enhancing the customer experience and increasing the number of deliveries each rider can make.

2. TSP Applications in Transportation and Urban Planning Waste collection routes, Traffic light synchronisation, optic cable installation, etc. are some areas where TSP Solutions works like a knight in shining armour. Other real-world TSP applications include

• Public Transport : City planners and public transport agencies use TSP principles to design bus, tram and train routes that reduce travel for passengers.
• Emergency Service Dispatch : Ambulance services, Police PCR vans employ TSP algorithms to dispatch vehicles quickly and efficiently in response to emergency calls. Finding the shortest route to reach the incident location can save lives.
• Urban Mobility Solution : In the era of ride-sharing and on-demand mobility apps like Uber, Ola, Lyft, etc., real-world TSP applications become prominent. TSP solutions optimise the route to destinations, ensuring quick and cost-effective transportation.

Other significant real-life applications of the Travelling Salesman Problem are

• TSP in Healthcare and Medical Research – for DNA sequencing and understanding genetic patterns and diseases.
• TSP in Manufacturing and Production – In circuit board manufacturing and job scheduling of technicians.
• TSP in Robotics and Autonomous Vehicles -Self-driving cars and drones use TSP-like algorithms for efficient navigation.

Solving the Travelling Salesman Problem – Last Mile Delivery Route Optimisation

Route optimisation is the key to efficient last-mile delivery . In order to attain flawless route optimisation, the software must solve the traveling salesman problem every step of the way.

Why it’s essential to solve TSP for Last Mile Delivery?

In simple and minimal words, solving TSP problems helps in many ways:

• Saves Time : It makes deliveries faster, so your customers get orders sooner.
• Customer Satisfaction : Fast deliveries give you an edge over the competition and enhance customer experience too.
• Saves Money : It reduces fuel wastage and vehicle wear, making deliveries cheaper.
• Environment Friendly : It lowers pollution by using fewer vehicles and shorter routes.
• Happy Staff: Drivers and dispatchers have less stress and can finish their work faster.

How do we solve the travelling salesman problem for last-mile delivery?

Solving TSP challenges for Last-mile delivery is like solving a big jigsaw puzzle. There are a hundred thousand addresses to visit daily. The software must find the shortest and most optimised route to them and come back to the starting point at the end.

• Our route optimisation software , TrackoMile, leverages capacity management , routing algorithms and robust rule engines to present the most optimal combination of delivery addresses. Thereby giving the most optimally planned routes or trips.
• All delivery managers have to do is upload the CSV file of the addresses or integrate TrackoMile to their CRM to fetch the delivery addresses. Now trip allocation, route optimisation, dispatch and everything else happen in a few clicks.
• ETA when the delivery is en route, POD when the order is delivered successfully, and trip analysis, are added features to simplify overall operations.

The Vehicle Routing Problem is very similar to TSP, with wide applications in logistics, delivery services and transportation. While TSP focuses on finding the shortest route for a single traveller visiting various locations, VRP deals with multiple vehicles serving multiple customers, considering added constraints like vehicle capacity, TATs and more.

How Can AI Help in Solving Traveling Salesman Problem (TSP)?

AI or Artificial Intelligence are becoming the driving force for business growth across various industrial sectors. AI particularly aids in solving the Traveling Salesman Problem(TSP) in the logistics and delivery sector by employing advanced algorithms and techniques. What are a few tricks up AI’s sleeves that help in automating TSP resolution? Let’s find out!

1. Advanced Algorithms

AI algorithms such as Genetic Algorithms, ACO, simulated annealing and a few others mentioned above, tackle complex Travelling Salesman Problem scenarios.

2. Machine Learning

Gathering information from historical data and optimising routes based on real-time insights is what AI is best for. Machine learning models are trained to adapt to changing conditions, like traffic, weather and delivery constraints, to provide a more accurate plan of action.

3. Parallel Computing

AIi enables the use of a parallel computing process, which means solving multiple segments of TSP simultaneously. This accelerates the problem-solving process for large-scale challenges.

4. Heuristic Improvement

TSP Heuristics powered by AI can groom initial solutions, gradually improving their results over time. These heuristics can be applied iteratively by AI to reach better results.

5. Hybrid Approaches

Applying hybrid algorithms is not a new technique to refine techniques and produce more accurate results. AI on top of it singles out data-oriented combinations that work the best in varied use cases.

Wrapping Up!

The travelling salesman problem’s importance lies in its real-world applications. Whether optimising delivery routes, planning manufacturing processes or organising circuit board drilling, finding the most efficient way to cover multiple locations is crucial to minimise costs and save time.

The TSP problems have evolved over the years, and so have TSP algorithms, heuristics and solutions. With the advent of advanced technologies such as GPS and machine learning, TSP continues to adapt and find new applications in emerging fields, cementing its status as a fundamental problem in optimization theory and a valuable tool for various industries. Mobility automation software like Trackobit, TrackoMile and TrackoField resort to TSP heuristics to solve challenges along the way.

Read Blog – Best Delivery Route Planner Apps for 2023

Traveling Salesman Problem FAQs

What is tsp.

TSP is an abbreviation for Traveling Salesman Problem. It’s the routing problem that deals with finding the shortest route to travel to a combination of locations in the most optimal manner.

Is Travelling Salesman Problem Solvable?

Yes, the Traveling Salesman Problem (TSP) is solvable, but the time to find the solution can grow proportionately with an increase in the number of locations. With the evolution of travelling salesman problem applications, various TSP algorithms and heuristics, their hybrids have also emerged.

Wh at is the objective of TSP?

The objective of the Traveling Salesman Problem (TSP) is to find the shortest possible route that covers all given locations or waypoints and comes back to the starting point with the least resource utilisation.

Diksha Bhandari

Currently creating SaaSy content strategies for TrackoBit and TrackoField, this content professional has dedicated a decade of her life to enriching her portfolio and continues to do so. In addition to playing with words and spilling SaaS, she has a passion for traveling to the mountains and sipping on adrak wali chai.

• Author Showcase
• All Blog Post

Never Miss a Beat

Related Blog

Top 12 Google Map Alternatives – Offering Precise Navigation

Explore our best picks for 12 free Google map alternatives that offer accurate and secure location and navigational solutions. 

Food Delivery Trends to Watch in 2024 & Beyond

Food and technology are both revolving along with consumer demands. Here are some of the food delivery trends to watch in 2024.

Biofuel – An Alternative to Fossil Fuels in Transportation | G20

Transportation industries are moving towards a greener future through the sustainable use of biofuels like Ethanol — discussed in the G20 2023 summit.

Top 10 Navigation Apps for Android and iOS | 2024

Discover the 10 best navigation apps in 2024 that offer personalised navigation just like Sherpas (experienced guides of Himalayan terrain) do.

What are Thematic Maps? Types, Applications And Advantages

Maps have come a long way, and their usage has gone beyond just navigating distances. Thematic maps are now being used to interpret data, gain information, etc. 

From a Bachelor Pad to a Multinational Firm: Tracking TrackoBit’s 5-year Journey

“It’s when ordinary people rise above the expectations and seize the opportunity that milestones truly are reached.” – Mike Huckabee

Stay Updated on tech, telematics and mobility. Don't miss out on the latest in the industry.

Thank you for reaching out! We'll speak to you soon.

In the meantime, why not find out more about us, explore our products, or visit our blog?

Cookie Consent

We use cookies to enhance and personalize your browsing experience. By continuing to use our website, you agree to our Privacy Policy.

Learning center series

Travelling salesman problem explained

• Published on April 26, 2024
• by Oguzhan Uyar
• Last updated: 1 day 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.

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.

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.

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.

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.

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.

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.

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.

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.

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?

7 reasons for delivery route optimization

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

Truck route planning vs common route planning

Best delivery route planning software for 2024

Top 10 free route planning software of 2024

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

Dorchester Brewing Company

‟Metrobi does exactly what I wanted my drivers to do”

LuNo Culinary

‟The quality of customer service is great!”

‟Great service and support from Metrobi”

Anna’s Taqueria

Success Stories

Smart Lunches

Urban Agriculture Cooperative

Secret Garden Rose

Wicked Bagel

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
• 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.

Explained: What is Traveling Salesman Problem (TSP)

• Last Updated: January 24, 2023

• A well-known mathematical problem called the Traveling Salesman Problem (TSP) aims to determine the shortest path between a number of places.
• Logistics, transportation, and manufacturing are just a few of the industries where the TSP is useful.
• The number of points, the form of the point set, and the algorithm employed can all have an impact on how the TSP is solved.
• Technology advancements like cloud computing and parallel processing have made it possible to solve the Traveling Salesman Problem effectively for larger and more complicated situations.

Traveling salesman problem is not new for delivery-based businesses. Its recent expansion has insisted that industry experts find optimal solutions in order to facilitate delivery operations.

The major challenge is to find the most efficient routes for performing multi-stop deliveries. Without the shortest routes, your delivery agent will take more time to reach the final destination. Sometimes problems may arise if you have multiple route options but fail to recognize the efficient one.

Eventually, traveling salesman problem would cost you time and result in late deliveries . So, before it becomes an irreparable issue for your delivery company, let us understand the traveling salesman problem and find optimal solutions in this blog.

Table of Content

• What is the Traveling Salesman Problem (TSP)?
• Commom challenges of Traveling Salesman Problem (TSP)

What are Some Popular Solutions to Traveling Salesman Problem?

What are other optimal solutions to the traveling salesman problem, what are some real-life applications of traveling salesman problem.

• How TSP and VRP Combinedly Pile up Challenges?
• Can a route planner resolve Traveling Salesman Problem (TSP)?

What is Traveling Salesman Problem (TSP)?

The traveling Salesman Problem (TSP) is a combinatorial problem that deals with finding the shortest and most efficient route to follow for reaching a list of specific destinations.

It is a common algorithmic problem in the field of delivery operations that might hamper the multiple delivery process and result in financial loss. TSP turns out when you have multiple routes available but choosing a minimum cost path is really hard for you or a traveling person.

How difficult is it to solve?

It is quite difficult to solve TSP as it is known as NP-hard, which means there is no polynomial time algorithm to solve it for more numbers of addresses. So, with an increasing amount of addresses, the complexity of solving TSP increases exponentially.

So, it is impossible to find TSP solutions manually. Also, many mathematical algorithms and the fastest computers fail to solve TSP.

However, TSP can be eliminated by determining the optimized and efficient path using approximation algorithms or automated processes.

Common Challenges of Traveling Salesman Problem (TSP)

Being a salesman is not easy, as you need to face various unavoidable challenges in your everyday schedules.

• Firstly, every day, salespeople have to carry out a number of deliveries in a very limited time, so there are a lot of time constraints. To overcome this, you need to plan your routes in a way that you make the most out of them.
• Secondly, there are chances of last-minute changes. Sometimes you get extra and urgent visits to make, while sometimes, some visits are postponed or canceled due to the customer’s unavailability.
• Lastly, a math problem, a combinatorial optimization problem, arises. A combinatorial optimization problem is a problem that is mathematically complex to solve as you have to deal with many variables.

These are major challenges in the Traveling Salesman Problem (TSP) as you are required to create a route with the shortest distances using hundreds and thousands of permutations and combinations that asks for less fuel, fulfill on-time delivery to customers, and are ready to modify routes considering last minute changes.

These are some of the near-optimal solutions to find the shortest route to a combinatorial optimization problem.

1. Nearest Neighbor (NN)

The Nearest Neighbor Method is probably the most basic TSP heuristic. The method followed by this algorithm states that the driver must start by visiting the nearest destination or closest city. Once all the cities in the loop are covered, the driver can head back to the starting point.

Solving TSP using this efficient method, requires the user to choose a city at random and then move on to the closest unvisited city and so on. Once all the cities on the map are covered, you must return to the city you started from.

2. The Branch and Bound Algorithm

The Branch & Bound method follows the technique of breaking one problem into several little chunks of problems. So it solves a series of problems. Each of these sub-problems may have multiple solutions. The solution you choose for one problem may have an effect on the solutions of subsequent sub-problems.

3. The Brute Force Algorithm

The Brute Force Approach takes into consideration all possible minimum cost permutation of routes using a dynamic programming approach. First, calculate the total number of routes. Draw and list all the possible routes that you get from the calculation. The distance of each route must be calculated and the shortest route will be the most optimal solution.

• Multi-Agent System : Involves distributing the pair of cities into groups. Then assign a single agent to discover the shortest path, covering all the cities in the assigned group.
• Zero Suffix Method : This method solves the classical symmetric TSP and was introduced by Indian researchers.
• Multi-Objective Evolutionary Algorithm : This method solves the TSP using NSGA-II
• Biogeography-based Optimization Algorithm : This method is based on the migration strategy of animals for solving optimization issues.
• Meta-Heuristic Multi Restart Iterated Local Search : This method states that the technique is more efficient compared to genetic algorithms.

Blow Away TSP using Upper

Need a permanent solution for recurring TSP? Sign up with Upper to keep your tradesmen updated all the time. Lay off your manual calculation and adopt an automated process now!

Most businesses see a rise in the Traveling Salesman Problem (TSP) due to the last mile delivery challenges . The last mile delivery is the process of delivering goods from the warehouse (or a depot) to the customer’s preferred location. Considering the supply chain management, it is the last mile deliveries that cost you a wholesome amount.

At the same time, you need to sacrifice financial loss in order to maintain your current position in the market. Suppose last mile delivery costs you $11, the customer will pay $8 and you would suffer a loss. This is because of pre-defined norms which may favor the customer to pay less amount.

This hefty last mile delivery cost is the result of a lack of Vehicle routing problem(VRP) software. VRP finds you the most efficient routes so that operational costs will not get increase. So, by using the right VRP software, you would not have to bother about TSP.

Such delivery management software uses an automated process that doesn’t need manual intervention or calculations to pick the best routes. Hence, it is the easiest way to get rid of the traveling Salesman Problem (TSP).

How TSP and VRP Combinedly Pile Up Challenges?

The traveling Salesman Problem is an optimization problem studied in graph theory and the field of operations research. In this optimization problem, the nodes or cities on the graph are all connected using direct edges or routes. The weight of each edge indicates the distance covered on the route between the two cities.

The problem is about finding an optimal route that visits each city once and returns to the starting and ending point after covering all cities once.

The TSP is often studied in a generalized version which is the Vehicle Routing Problem . It is one of the most broadly worked on problems in mathematical optimization. VRP deals with finding or creating a set of routes for reducing time, fuel, and delivery costs.

Is there any real world solution to TSP and VRP?

Many solutions for TSP and VRP are based on academics which means they are not so practical in everyday life. The reason is that many of them are just limited to perfection, but need a dynamic programming-based solution. So, if businesses really want to get rid of them, they need a TSP solver integrated with route optimization software.

The right TSP solver will help you disperse such modern challenges. It offers in-built route planning and optimization solutions in such a way that your tradesman doesn’t get stranded while delivering the parcel. Also, it is equipped with an efficient algorithm that provides true solutions to the TSP. As a result, the delivery manager can create a route plan hassle-free in a few minutes.

Can a Route Planner Resolve the Traveling Salesman Problem (TSP)?

In the general case, the Traveling Salesman Problem (TSP) involves finding the shortest optimized and possible route that includes a set of stops and returns to the starting point. The number of possible routes increases exponentially as the number of locations increases. Finding the best solution becomes difficult computationally, even for moderately sized problems.

But, Upper Route Planner, a route optimization software , is built differently. Upper has all the solutions you need when talking about TSP.

For example, if you are in charge of planning delivery routes with more than 500 stops in them, all you need to do is import an Excel or CSV file with multiple addresses into Upper, review, allot delivery drivers, optimize, and dispatch with a single click. This delivery route planning solution saves you hours of time spent on planning delivery routes and optimizing them.

Also, once the delivery is completed, Upper lets you collect proof of delivery. This is how the Upper Route Planner is a simple solution to the Traveling Salesman Problem.

Upper Route Planner

A simple-to-use route planner that every one is talking about

TSP stands for traveling Salesman Problem, while VRP is an abbreviation form of vehicle routing problem (VRP). In the delivery industry, both of them are widely known by their abbreviation form.

Yes, you can prevent TSP by using the right route planner. The online route planner helps you get the optimized path so that your delivery agents don’t have to deal with such challenges. In addition, they don’t struggle with multiple routes. Instead, they can progress on the shortest route.

The new method has made it possible to find solutions that are almost as good. This was done by the Christofides algorithm, the popular algorithm in theoretical computer science. This algorithm plugs into an alternate version of the problem that finds a combination of paths as per permutations of cities. It made the round trip route much longer. The round trip produced by the new method, while still not being efficient enough is better than the old one.

The vehicle routing problem (VRP) reduces the transportation costs as well as drivers’ expenses. It helps you serve more customers with fewer fleets and drivers. Thus, you don’t have any variation in the time taken to travel.

Create Optimized Routes Using Upper and Bid Goodbye to Traveling Salesman Problem

As a business owner, If you are dealing with TSP and want to get rid of them, we recommend using a TSP solver like Upper Route Planner. The online route planner is capable of plucking out the most efficient routes no matter how big your TSP is. It has an in-built sophisticated algorithm that helps you get the optimized path in a matter of seconds.

Therefore, you won’t fall prey to such real-world problems and perform deliveries in minimum time. Upper’s delivery route planner offers a dedicated driver app that makes sure your tradesman doesn’t go wrongfooted and quickly wraps up pending deliveries. Don’t just agree with our words, book a demo on Upper and disperse TSP once and for all.

Rakesh Patel, author of two defining books on reverse geotagging, is a trusted authority in routing and logistics. His innovative solutions at Upper Route Planner have simplified logistics for businesses across the board. A thought leader in the field, Rakesh's insights are shaping the future of modern-day logistics, making him your go-to expert for all things route optimization. Read more.

Sign Up Now!

Get weekly updates from Upper Route Planner.

Tired of Manual Routing?

Related Posts

Sales Route Planning Guide: Know How to Plan the Best Sales Routes

Sign Up with Upper Route Planner and automate your daily business process route planning, scheduling, and optimizing!

Life's Complicated Enough. Your Routing doesn't have to be.

Plan routes, manage drivers and stops, send timely customer notifications, collect proof of delivery and much more with just a few clicks.

https://www.upperinc.com/guides/travelling-salesman-problem/

Grab a FREE Trial of Upper

• Plan routes with hundreds of stops in a minute
• Schedule routes months in advance
• Collect reliable proof of delivery
• Track drivers live for real-time updates
• Experience unparalleled customer support

Grab a FREE Trial of Upper TODAY!

• Schedule routes in advance for weeks
• Collect proof of delivery to maintain accountability
• Experience 24/7 customer support
• Smart reporting to get real-time insights

Reset password New user? Sign up

Existing user? Log in

Traveling Salesperson Problem

Already have an account? Log in here.

A salesperson needs to visit a set of cities to sell their goods. They know how many cities they need to go to and the distances between each city. In what order should the salesperson visit each city exactly once so that they minimize their travel time and so that they end their journey in their city of origin?

The traveling salesperson problem is an extremely old problem in computer science that is an extension of the Hamiltonian Circuit Problem . It has important implications in complexity theory and the P versus NP problem because it is an NP-Complete problem . This means that a solution to this problem cannot be found in polynomial time (it takes superpolynomial time to compute an answer). In other words, as the number of vertices increases linearly, the computation time to solve the problem increases exponentially.

The following image is a simple example of a network of cities connected by edges of a specific distance. The origin city is also marked.

Network of cities

Here is the solution for that network, it has a distance traveled of only 14. Any other path that the salesman can takes will result in a path length that is more than 14.

Relationship to Graphs

Special kinds of tsp, importance for p vs np, applications.

The traveling salesperson problem can be modeled as a graph . Specifically, it is typical a directed, weighted graph. Each city acts as a vertex and each path between cities is an edge. Instead of distances, each edge has a weight associated with it. In this model, the goal of the traveling salesperson problem can be defined as finding a path that visits every vertex, returns to the original vertex, and minimizes total weight.

To that end, many graph algorithms can be used on this model. Search algorithms like breadth-first search (BFS) , depth-first search (DFS) , and Dijkstra's shortest path algorithm can certainly be used, however, they do not take into consideration that fact that every vertex must be visited.

The Traveling Salesperson Problem (TSP), an NP-Complete problem, is notoriously complicated to solve. That is because the greedy approach is so computational intensive. The greedy approach to solving this problem would be to try every single possible path and see which one is the fastest. Try this conceptual question to see if you have a grasp for how hard it is to solve.

For a fully connected map with \(n\) cities, how many total paths are possible for the traveling salesperson? Show Answer There are (n-1)! total paths the salesperson can take. The computation needed to solve this problem in this way grows far too quickly to be a reasonable solution. If this map has only 5 cities, there are \(4!\), or 24, paths. However, if the size of this map is increased to 20 cities, there will be \(1.22 \cdot 10^{17}\) paths!

The greedy approach to TSP would go like this:

• Find all possible paths.
• Find the cost of every paths.
• Choose the path with the lowest cost.

Another version of a greedy approach might be: At every step in the algorithm, choose the best possible path. This version might go a little quicker, but it's not guaranteed to find the best answer, or an answer at all since it might hit a dead end.

For NP-Hard problems (a subset of NP-Complete problems) like TSP, exact solutions can only be implemented in a reasonable amount of time for small input sizes (maps with few cities). Otherwise, the best approach we can do is provide a heuristic to help the problem move forward in an optimal way. However, these approaches cannot be proven to be optimal because they always have some sort of downside.

Small input sizes

As described, in a previous section , the greedy approach to this problem has a complexity of \(O(n!)\). However, there are some approaches that decrease this computation time.

The Held-Karp Algorithm is one of the earliest applications of dynamic programming . Its complexity is much lower than the greedy approach at \(O(n^2 2^n)\). Basically what this algorithm says is that every sub path along an optimal path is itself an optimal path. So, computing an optimal path is the same as computing many smaller subpaths and adding them together.

Heuristics are a way of ranking possible next steps in an algorithm in the hopes of cutting down computation time for the entire algorithm. They are often a tradeoff of some attribute - such as completeness, accuracy, or precision - in favor of speed. Heuristics exist for the traveling salesperson problem as well.

The most simple heuristic for this problem is the greedy heuristic. This heuristic simply says, at each step of the network traversal, choose the best next step. In other words, always choose the closest city that you have not yet visited. This heuristic seems like a good one because it is simple and intuitive, and it is even used in practice sometimes, however there are heuristics that are proven to be more effective.

Christofides algorithm is another heuristic. It produces at most 1.5 times the optimal weight for TSP. This algorithm involves finding a minimum spanning tree for the network. Next, it creates matchings for the cities of an odd degree (meaning they have an odd number of edges coming out of them), calculates an eulerian path , and converts back to a TSP path.

Even though it is typically impossible to optimally solve TSP problems, there are cases of TSP problems that can be solved if certain conditions hold.

The metric-TSP is an instance of TSP that satisfies this condition: The distance from city A to city B is less than or equal to the distance from city A to city C plus the distance from city C to city B. Or,

\[distance_{AB} \leq distance_{AC} + distance_{CB}\]

This is a condition that holds in the real world, but it can't always be expected to hold for every TSP problem. But, with this inequality in place, the approximated path will be no more than twice the optimal path. Even better, we can bound the solution to a \(3/2\) approximation by using Christofide's Algorithm .

The euclidean-TSP has an even stricter constraint on the TSP input. It states that all cities' edges in the network must obey euclidean distances . Recent advances have shown that approximation algorithms using euclidean minimum spanning trees have reduced the runtime of euclidean-TSP, even though they are also NP-hard. In practice, though, simpler heuristics are still used.

The P versus NP problem is one of the leading questions in modern computer science. It asks whether or not every problem whose solution can be verified in polynomial time by a computer can also be solved in polynomial time by a computer. TSP, for example, cannot be solved in polynomial time (at least that's what is currently theorized). However, TSP can be solved in polynomial time when it is phrased like this: Given a graph and an integer, x, decide if there is a path of length x or less than x . It's easy to see that given a proposed answer to this question, it is simple to check if it is less than or equal to x.

The traveling salesperson problem, like other problems that are NP-Complete, are very important to this debate. That is because if a polynomial time solution can be found to this problems, then \(P = NP\). As it stands, most scientists believe that \(P \ne NP\).

The traveling salesperson problem has many applications. The obvious ones are in the transportation space. Planning delivery routes or flight patterns, for example, would benefit immensly from breakthroughs is this problem or in the P versus NP problem .

However, this same logic can be applied to many facets of planning as well. In robotics, for instance, planning the order in which to drill holes in a circuit board is a complex task due to the sheer number of holes that must be drawn.

The best and most important application of TSP, however, comes from the fact that it is an NP-Complete problem. That means that its practical applications amount to the applications of any problem that is NP-Complete. So, if there are significant breakthroughs for TSP, that means that those exact same breakthrough can be applied to any problem in the NP-Complete class.

Problem Loading...

Note Loading...

Set Loading...

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

The traveling salesman problem

The traveling salesman problem (TSP) is one of the most intensely studied problems in computational mathematics. Its name reflects the real-life problem traveling salesmen face when taking their business from city to city – finding the shortest roundtrip possible while visiting each location only once. The bigger challenge lies in keeping travel costs at a minimum while maximizing the amount of stops possible in a single trip. To find the optimal solution to this problem, mathematicians need to map out and compare every possibility. 

William Cook, professor of combinatorics and optimization at the University of Waterloo, is the researcher behind  Concorde – incredibly efficient computer code for optimally solving the symmetric TSP and related network optimization problems. It has been used to calculate the optimal solutions to the full set of 110  TSPLIB  problems, the largest having over 85,000 cities. This positions Concorde’s TSP solver as one of the most reliable tools for the problem.

Data points (above) were computed using the traveling salesman problem to create the optimal tour (below) at the University of Waterloo in 2017. 

Naturally, the TSP lends itself to being useful in modeling transportation and logistics applications, such as the routing of trucks for parcel post pickup or delivery. Its applications go beyond physical movements between places – the simplicity of the model and the importance of efficiency in operations makes it useful across many industries and domains. 

Concorde’s TSP solver finds the optimal solution to a problem and identifies which inefficiencies can be controlled by modeling optimal and different situations. The National Institute of Health found the tool integral to ongoing work in genome sequencing to compute DNA sequence variations. The Worldwide Airport Path Finder web site uses Concorde to find the shortest routes through selections of airports all over the world.

With limited resources, companies can use optimization and operations research to create tools to use these resources as efficiently as possible. The study of mathematical problems like TSP can be used to build powerful tools like Cook’s Concorde to increase efficiencies in complex industrial applications.  

• Data Structures & Algorithms
• DSA - Overview
• DSA - Environment Setup
• DSA - Algorithms Basics
• DSA - Asymptotic Analysis
• Data Structures
• DSA - Data Structure Basics
• DSA - Data Structures and Types
• DSA - Array Data Structure
• Linked Lists
• DSA - Linked List Data Structure
• DSA - Doubly Linked List Data Structure
• DSA - Circular Linked List Data Structure
• Stack & Queue
• DSA - Stack Data Structure
• DSA - Expression Parsing
• DSA - Queue Data Structure
• Searching Algorithms
• DSA - Searching Algorithms
• DSA - Linear Search Algorithm
• DSA - Binary Search Algorithm
• DSA - Interpolation Search
• DSA - Jump Search Algorithm
• DSA - Exponential Search
• DSA - Fibonacci Search
• DSA - Sublist Search
• DSA - Hash Table
• Sorting Algorithms
• DSA - Sorting Algorithms
• DSA - Bubble Sort Algorithm
• DSA - Insertion Sort Algorithm
• DSA - Selection Sort Algorithm
• DSA - Merge Sort Algorithm
• DSA - Shell Sort Algorithm
• DSA - Heap Sort
• DSA - Bucket Sort Algorithm
• DSA - Counting Sort Algorithm
• DSA - Radix Sort Algorithm
• DSA - Quick Sort Algorithm
• Graph Data Structure
• DSA - Graph Data Structure
• DSA - Depth First Traversal
• DSA - Breadth First Traversal
• DSA - Spanning Tree
• Tree Data Structure
• DSA - Tree Data Structure
• DSA - Tree Traversal
• DSA - Binary Search Tree
• DSA - AVL Tree
• DSA - Red Black Trees
• DSA - B Trees
• DSA - B+ Trees
• DSA - Splay Trees
• DSA - Tries
• DSA - Heap Data Structure
• DSA - Recursion Algorithms
• DSA - Tower of Hanoi Using Recursion
• DSA - Fibonacci Series Using Recursion
• Divide and Conquer
• DSA - Divide and Conquer
• DSA - Max-Min Problem
• DSA - Strassen's Matrix Multiplication
• DSA - Karatsuba Algorithm
• Greedy Algorithms
• DSA - Greedy Algorithms
• DSA - Travelling Salesman Problem (Greedy Approach)
• DSA - Prim's Minimal Spanning Tree
• DSA - Kruskal's Minimal Spanning Tree
• DSA - Dijkstra's Shortest Path Algorithm
• DSA - Map Colouring Algorithm
• DSA - Fractional Knapsack Problem
• DSA - Job Sequencing with Deadline
• DSA - Optimal Merge Pattern Algorithm
• Dynamic Programming
• DSA - Dynamic Programming
• DSA - Matrix Chain Multiplication
• DSA - Floyd Warshall Algorithm
• DSA - 0-1 Knapsack Problem
• DSA - Longest Common Subsequence Algorithm
• DSA - Travelling Salesman Problem (Dynamic Approach)
• Approximation Algorithms
• DSA - Approximation Algorithms
• DSA - Vertex Cover Algorithm
• DSA - Set Cover Problem
• DSA - Travelling Salesman Problem (Approximation Approach)
• Randomized Algorithms
• DSA - Randomized Algorithms
• DSA - Randomized Quick Sort Algorithm
• DSA - Karger’s Minimum Cut Algorithm
• DSA - Fisher-Yates Shuffle Algorithm
• DSA Useful Resources
• DSA - Questions and Answers
• DSA - Quick Guide
• DSA - Useful Resources
• DSA - Discussion
• Selected Reading
• UPSC IAS Exams Notes
• Developer's Best Practices
• Questions and Answers
• Effective Resume Writing
• HR Interview Questions
• Computer Glossary

Travelling Salesman Problem (Greedy Approach)

Travelling salesperson algorithm.

The travelling salesman problem is a graph computational problem where the salesman needs to visit all cities (represented using nodes in a graph) in a list just once and the distances (represented using edges in the graph) between all these cities are known. The solution that is needed to be found for this problem is the shortest possible route in which the salesman visits all the cities and returns to the origin city.

If you look at the graph below, considering that the salesman starts from the vertex ‘a’, they need to travel through all the remaining vertices b, c, d, e, f and get back to ‘a’ while making sure that the cost taken is minimum.

There are various approaches to find the solution to the travelling salesman problem: naive approach, greedy approach, dynamic programming approach, etc. In this tutorial we will be learning about solving travelling salesman problem using greedy approach.

As the definition for greedy approach states, we need to find the best optimal solution locally to figure out the global optimal solution. The inputs taken by the algorithm are the graph G {V, E}, where V is the set of vertices and E is the set of edges. The shortest path of graph G starting from one vertex returning to the same vertex is obtained as the output.

Travelling salesman problem takes a graph G {V, E} as an input and declare another graph as the output (say G’) which will record the path the salesman is going to take from one node to another.

The algorithm begins by sorting all the edges in the input graph G from the least distance to the largest distance.

The first edge selected is the edge with least distance, and one of the two vertices (say A and B) being the origin node (say A).

Then among the adjacent edges of the node other than the origin node (B), find the least cost edge and add it onto the output graph.

Continue the process with further nodes making sure there are no cycles in the output graph and the path reaches back to the origin node A.

However, if the origin is mentioned in the given problem, then the solution must always start from that node only. Let us look at some example problems to understand this better.

Consider the following graph with six cities and the distances between them −

From the given graph, since the origin is already mentioned, the solution must always start from that node. Among the edges leading from A, A → B has the shortest distance.

Then, B → C has the shortest and only edge between, therefore it is included in the output graph.

There’s only one edge between C → D, therefore it is added to the output graph.

There’s two outward edges from D. Even though, D → B has lower distance than D → E, B is already visited once and it would form a cycle if added to the output graph. Therefore, D → E is added into the output graph.

There’s only one edge from e, that is E → F. Therefore, it is added into the output graph.

Again, even though F → C has lower distance than F → A, F → A is added into the output graph in order to avoid the cycle that would form and C is already visited once.

The shortest path that originates and ends at A is A → B → C → D → E → F → A

The cost of the path is: 16 + 21 + 12 + 15 + 16 + 34 = 114.

Even though, the cost of path could be decreased if it originates from other nodes but the question is not raised with respect to that.

The complete implementation of Travelling Salesman Problem using Greedy Approach is given below −

399: Travelling Salesman Problem

Explanation [ edit ].

The travelling salesman problem is a classic problem in computer science. An intuitive way of stating this problem is that given a list of cities and the distances between pairs of them, the task is to find the shortest possible route that visits each city exactly once and then returns to the origin city. A naïve solution solves the problem in O(n!) time (where n is the size of the list), simply by checking all possible routes, and selecting the shortest one. However, this approach will take a long time as the number of possible routes increases superexponentially as more nodes are included.

A more efficient dynamic programming approach, the Held-Karp algorithm , yields a solution in O(n 2 2 n ) time. These times are given using Big O notation , which is commonly used in computer science to show the efficiency or complexity of a solution or algorithm.

The joke is that the salesman selling online (say on eBay , Amazon Marketplace , or other virtual marketplace) does not have to worry about this problem, since he does not need to travel (which makes the time to find the best solution O(1)), to which the travelling salesman angrily responds, "Shut the hell up."

The title text wonders about the time complexity of the cutting-plane method , which is sometimes used to solve optimization problems.

The last sentence suggests the downside for Randall of drawing comics about computer science; he sometimes encounters problems to which he cannot find the answer, whereas authors of simpler comics such as Garfield do not have this problem. This is also likely a reference to 78: Garfield , which parodies Garfield's simplicity.

The map almost certainly depicts the United States, with the locations highlighted suspected to be (from left to right): Seattle, San Francisco, Los Angeles, Phoenix, Denver, Minneapolis, Dallas, San Antonio, Houston, Chicago (cut off), Detroit, Atlanta, Miami, Washington D.C., Philadelphia, New York, and Boston.

This is so far the only comic featuring the Brown Hat character.

Also see earlier strip 287: NP-Complete .

Transcript [ edit ]

Does anyone remember if the Brown Hat appears in any other comics?

It's probably not in the least important, but the network appears to be a collection of key cities in the US arranged by geographical location. 130.160.145.185 23:07, 9 March 2013 (UTC)

added a better explanation of the title text. -- Nick,5 Oct 2013 69.193.7.67 ( talk ) (please sign your comments with ~~~~)

Has anyone answered the question in the title text? -- Ricketybridge ( talk ) 23:55, 9 January 2014 (UTC)

Doesn't someone at ebay still have to solve the TSP? I guess that's the entire point though. 141.101.85.223 08:48, 27 July 2014 (UTC)

Oh god, wish I could vote this up... somehow... 108.162.219.108 15:43, 11 June 2015 (UTC)

It is curious that nobody here appears to have noticed that O(n!) is equivalent to O(n log(n)). Last time I checked, I seem to recall finding that O(n log(n)) was under O(n^2), and therefore under O(n^2.2^n). Or have I missed something? Certainly the worst-case can't be over O(n log(n)), as this is the class of the number of ways to sort a list of the cities. So, then, the O(n^2.2^n) must be better by some other multiplier. Come to that, O(n^2.2^n) seems to be within O(2^n). What am I missing here? 108.162.250.134 22:27, 9 August 2015 (UTC)

• Comics from 2008
• Comics from March
• Friday comics
• Comics with color
• Programming

Navigation menu

Personal tools.

• Not logged in
• Contributions
• Create account
• View history
• Latest comic
• Community portal
• Recent changes
• Random page
• Browse comics
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information

• This page was last edited on 1 April 2024, at 11:04.
• Privacy policy
• About explain xkcd
• Disclaimers

• Speakers & Mentors
• AI services

The Travelling Salesman Problem in Artificial Intelligence – Strategies, Solutions, and Future Directions

The Travelling Salesman Problem (TSP) is a classic challenge in computer science and optimization. It involves finding the shortest possible route for a salesman or salesperson to travel between a set of cities, visiting each city exactly once and returning to the starting city. This problem has numerous real-life applications, such as route planning for delivery drivers, scheduling for sales representatives, and optimizing circuit board designs.

Artificial Intelligence (AI) techniques have proven to be incredibly effective in solving complex problems like the TSP. By leveraging the power of machine learning algorithms and advanced optimization techniques, researchers have developed intelligent approaches to tackle this challenging problem. These AI techniques not only provide optimal solutions but also significantly reduce the computation time required to solve large-scale instances of the TSP.

One popular AI technique used to solve the TSP is the use of genetic algorithms. These algorithms mimic the process of natural selection and evolution to generate a set of candidate solutions, and then iterate and refine these solutions over multiple generations. With each iteration, the genetic algorithm applies genetic operators, such as crossover and mutation, to create new, potentially better solutions. The algorithm evaluates the fitness of each solution based on the distance traveled and selects the best solutions to form the next generation. Through this iterative process, the genetic algorithm gradually converges towards an optimal solution for the TSP.

Another AI technique that has shown promise in solving the TSP is the use of reinforcement learning. Reinforcement learning is a type of machine learning where an agent learns to make decisions based on feedback from its environment. In the context of the TSP, the agent learns to select the next city to visit based on the current state of the solution. Through trial and error, the agent discovers the optimal sequence of cities to visit, resulting in the shortest possible route for the salesman. By using techniques such as deep Q-learning, researchers have achieved impressive results in solving the TSP, even for large problem instances.

Travelling Salesman Problem Explained

The Travelling Salesman Problem (TSP) is a well-known problem in the field of artificial intelligence and operations research. It is a classic combinatorial optimization problem that involves finding the shortest possible route for a salesperson to travel to a number of cities and return back to the starting city, visiting each city only once.

In the TSP, a salesperson is given a list of cities and the distances between each pair of cities. The goal is to find a route that minimizes the total distance traveled. This problem is NP-hard, which means that as the number of cities increases, the amount of time it takes to solve the problem grows exponentially.

There are various algorithms that have been developed to solve the TSP, ranging from exact algorithms that guarantee finding the optimal solution, to heuristic algorithms that provide near-optimal solutions. Some of the popular techniques used to solve the TSP include genetic algorithms, simulated annealing, and ant colony optimization.

Artificial Intelligence and the TSP

Artificial intelligence (AI) techniques have been widely used to solve the TSP. These techniques not only provide efficient solutions but also allow for the exploration of large search spaces. Machine learning, in particular, has been utilized to learn patterns and generate solutions to the TSP. By training machine learning models on large datasets, it is possible to find solutions that are close to optimal or even optimal in some cases.

AI algorithms can be used to find solutions to the TSP in real-time by taking into account various factors such as traffic conditions, time constraints, and cost optimization. These algorithms can be integrated into navigation systems or logistics planning tools to help salespersons and logistics coordinators optimize their routes and minimize their travel time.

The Travelling Salesman Problem is a complex problem in the field of artificial intelligence and operations research. It involves finding the shortest possible route for a salesperson to travel to a number of cities and return back to the starting city. AI techniques, such as machine learning, have been utilized to solve the TSP and find near-optimal solutions. These solutions can be used to optimize travel routes and minimize travel time for salespersons and logistics coordinators.

By leveraging the power of AI, the TSP can be efficiently solved, leading to improved efficiency and cost savings in various industries that require optimal route planning.

Importance of Solving the TSP

The Travelling Salesman Problem (TSP) is a classic problem in the field of artificial intelligence and machine learning. It is a mathematical problem that involves finding the shortest possible route between a set of cities, with the constraint that each city must be visited exactly once and the salesman must return to the starting city.

Solving the TSP is important for various reasons. Firstly, it has practical applications in various industries such as logistics and transportation. For example, a salesperson visiting multiple cities needs to find the most efficient route to minimize travel time and expenses. By solving the TSP, companies can optimize their routes and save resources.

Secondly, solving the TSP has significant theoretical implications. It is classified as an NP-hard problem, which means that finding the optimal solution becomes exponentially difficult as the size of the problem increases. Therefore, developing efficient algorithms to solve the TSP contributes to the advancement of algorithms and complexity theory.

Moreover, solving the TSP can lead to insights and improvements in other optimization problems. Many problems in various domains can be reduced to the TSP, allowing researchers to apply TSP-solving techniques to solve other complex problems more effectively.

Overall, the TSP is not only a challenging problem in itself but it also has practical and theoretical importance. Solving the TSP using artificial intelligence techniques can lead to more efficient routes, cost savings, and advancements in algorithmic research.

Artificial Intelligence Techniques for Solving TSP

The Traveling Salesman Problem (TSP) is a well-known optimization problem in computer science and operations research. It involves finding the shortest possible route that a salesperson must take to visit a set of cities and return to the starting city, while visiting each city only once.

Artificial Intelligence (AI) techniques have been widely used to tackle the TSP and find near-optimal solutions. These techniques leverage the power of machine learning and optimization algorithms to solve the problem efficiently and effectively.

1. Genetic Algorithms

Genetic algorithms are a popular AI technique for solving the TSP. They mimic the process of natural selection, where a population of potential solutions evolves over time to find the optimal solution. In the context of the TSP, each individual in the population represents a possible tour, and the fitness of the tour is evaluated based on its length. Through the use of genetic operators, such as mutation and crossover, the algorithm explores different combinations of tours to converge towards the shortest route.

2. Ant Colony Optimization

Ant Colony Optimization (ACO) is another AI technique that has been successfully applied to the TSP. Inspired by the behavior of real ants searching for food, ACO algorithms simulate the movement of artificial ants on a graph representing the cities. Each ant probabilistically chooses its next move based on pheromone trails left by other ants and the distance to the neighboring cities. Over time, the pheromone trails are updated based on the quality of the tours, allowing the algorithm to discover better routes.

These are just two examples of the many AI techniques that have been employed to solve the TSP. Other techniques, such as simulated annealing, particle swarm optimization, and reinforcement learning, have also been used with success. Each technique offers its own advantages and trade-offs in terms of solution quality, runtime, and scalability.

In conclusion, artificial intelligence techniques provide powerful tools for solving the TSP. These techniques leverage the intelligence and learning capabilities of machines to explore the vast search space of possible tours and find near-optimal solutions. By combining different AI techniques and tailoring them to the specific problem instance, researchers and practitioners can tackle the TSP efficiently and effectively.

Genetic Algorithms for TSP

Genetic Algorithms (GAs) have been widely used to solve complex optimization problems, including the Traveling Salesman Problem (TSP). The TSP is a classic problem in the field of artificial intelligence, where a salesman or salesperson needs to visit a set of cities and return to the starting point while minimizing the total distance traveled.

GAs are a type of machine learning algorithm inspired by the process of natural selection. They work by evolving a population of potential solutions through generations, mimicking the process of evolution in nature. In the context of the TSP, each potential solution represents a possible route that the salesman can take to visit all the cities.

The GA starts by randomly generating an initial population of potential solutions, also known as individuals or chromosomes. Each individual is represented as a sequence of cities, encoding a possible route for the salesman. The fitness of each individual is then calculated based on the total distance of the route. The goal of the GA is to find the individual with the shortest distance, representing the optimal solution to the TSP.

During each iteration, the GA selects individuals from the population to undergo genetic operations such as crossover and mutation. Crossover involves combining the genetic material of two individuals to create new offspring, while mutation introduces small random changes to the genetic material of an individual. These operations help explore the search space and potentially find better solutions.

After the genetic operations, a new population is created using the offspring and a selection process, where individuals with higher fitness have a higher chance of being selected. This process is repeated for a fixed number of generations or until a stopping criterion is met, such as reaching a satisfactory solution.

The use of GAs for solving the TSP has been successful, as they can efficiently explore the vast search space of possible routes and converge to near-optimal solutions. However, the performance of GAs can be affected by various factors, such as the population size, selection method, and genetic operators. Parameters need to be carefully tuned to achieve good results.

In summary, Genetic Algorithms provide an effective approach to solving the Traveling Salesman Problem and have been applied successfully in various real-world scenarios. Their ability to explore the search space and find near-optimal solutions makes them a valuable tool in the field of artificial intelligence and optimization.

Ant Colony Optimization for TSP

Ant Colony Optimization (ACO) is a metaheuristic algorithm inspired by the behavior of ants in finding the shortest paths between their nest and food sources. It has been successfully applied to solve the Traveling Salesperson Problem (TSP), which is a classic optimization problem in computer science.

The TSP involves finding the shortest route that a salesperson can take to visit a given set of cities and return to the starting city, having visited each city only once. The problem is NP-hard, meaning that it becomes computationally infeasible for large problem instances. ACO is an intelligent technique that provides a good approximation solution to the TSP.

How does ACO work?

In ACO, a population of artificial ants are used to find near-optimal solutions to the TSP. Each ant constructs a solution by probabilistically choosing the next city to visit based on a combination of pheromone trails and distance information. Pheromone trails represent the accumulated historic information about good routes, and evaporation and reinforcement mechanisms are used to update the pheromone trail strengths.

During the construction of solutions, ants deposit pheromone on the edges they traverse, with stronger pheromone concentration on shorter edges. This pheromone trail guides subsequent ants to select edges with higher pheromone concentration, increasing the likelihood of finding shorter routes. The pheromone trails also gradually evaporate over time, allowing exploration of new routes.

Benefits of ACO for TSP

ACO offers several advantages for solving the TSP:

• Efficiency: ACO is capable of producing good-quality solutions to large-scale TSP instances in a reasonable amount of time, outperforming many other traditional optimization algorithms.
• Scalability: ACO scales well with the problem size, making it suitable for solving real-world TSP instances with a large number of cities.
• Adaptability: ACO is adaptable to dynamic TSP instances, as it can quickly react to changes in the problem by updating the pheromone trails.

Overall, ACO has proven to be a powerful technique for solving the TSP, providing solutions that are close to the optimal ones. Its ability to leverage the collective intelligence of a population of artificial ants makes it a popular choice in the field of artificial intelligence and machine learning.

Simulated Annealing for TSP

The Travelling Salesman Problem (TSP) is a classic problem in the field of artificial intelligence and machine learning. It involves finding the most efficient route that a salesperson can take to visit a given set of cities and return to the starting city, while minimizing the total distance traveled.

Simulated annealing is a metaheuristic algorithm that is often used to solve optimization problems like the TSP. It is inspired by the annealing process in metallurgy, where a material is heated and slowly cooled to reduce its defects and increase its strength.

In the context of the TSP, simulated annealing works by iteratively improving a solution while allowing for occasional “worse” moves, in order to explore the solution space and avoid getting stuck in local optima. The algorithm starts with an initial solution and iteratively adjusts it by swapping two cities in the tour. Whether or not a new solution is accepted depends on its cost and a temperature parameter, which controls the likelihood of accepting worse solutions as the algorithm progresses.

At each iteration, the temperature is decreased, simulating the cooling process in annealing. This allows the algorithm to explore a larger portion of the solution space in the beginning, and gradually focus on areas with lower costs as the temperature decreases. The cooling schedule is an important parameter that affects the algorithm’s performance, as a schedule that cools too quickly may result in premature convergence to a suboptimal solution.

Simulated annealing for the TSP has been widely studied and proven to be effective in finding near-optimal solutions for large problem instances. Various strategies for generating initial solutions and updating the temperature schedule have been proposed, and the algorithm has been combined with other techniques such as local search and genetic algorithms to further improve its performance.

In conclusion, simulated annealing is an effective technique for solving the Travelling Salesman Problem. It utilizes the concept of annealing to explore the solution space and find near-optimal solutions. By allowing for occasional “worse” moves, it avoids getting stuck in local optima and provides a good balance between exploration and exploitation. With appropriate parameter tuning, simulated annealing can offer high-quality solutions for large-scale TSP instances.

Tabu Search for TSP

Travelling Salesman Problem (TSP) is a well-known optimization problem in the field of artificial intelligence and machine learning. It involves finding the shortest possible route that a salesperson can take to visit a given set of cities and return to the starting city. TSP is known to be a difficult problem and has been extensively studied due to its practical applications in logistics, routing, and planning.

One of the popular approaches to solve TSP is using the Tabu Search algorithm. Tabu Search is a metaheuristic algorithm that is inspired by the concept of memory in human cognition. The algorithm maintains a memory structure called the “tabu list” to keep track of recently visited solutions and prevents the search from getting trapped in repetitive cycles.

How Tabu Search works for TSP

The Tabu Search algorithm for TSP starts with an initial random solution or a known good solution. It then iteratively explores the solution space by making small modifications to the current solution. These modifications are guided by certain rules and heuristics, and new solutions are evaluated based on a cost function that measures the length of the tour.

The algorithm maintains a tabu list that stores recently visited solutions and prevents revisiting them in subsequent iterations. This helps the algorithm to escape local optima and explore new regions of the solution space. Additionally, the algorithm uses a strategy called “aspiration criteria” that allows revisiting a solution in the tabu list if it leads to a better solution than the current best solution.

The Tabu Search algorithm continues the search until a termination criterion is met, such as reaching a predefined number of iterations or a specific improvement threshold. The best solution found during the search is then returned as the final solution to the TSP problem.

Benefits of using Tabu Search for TSP

Tabu Search has several advantages when applied to the Travelling Salesman Problem:

• It is a versatile and flexible algorithm that can handle TSP instances of various sizes and complexities.
• Tabu Search is able to escape local optima and converge towards good quality solutions.
• It can be easily combined with other optimization techniques and heuristics to further improve the solution quality.

In conclusion, Tabu Search is an effective and popular algorithm for solving the Travelling Salesman Problem. Its ability to explore the solution space while avoiding repetitive cycles makes it a valuable tool in the field of artificial intelligence and machine learning.

Particle Swarm Optimization for TSP

The Travelling Salesman Problem (TSP) is a classic optimization problem in the field of artificial intelligence (AI). It involves finding the shortest possible route that a salesperson can take to visit a set of cities and return to the starting city. TSP is a challenging problem that has applications in logistics, transportation, and many other fields.

One popular technique for solving TSP is Particle Swarm Optimization (PSO). PSO is a population-based optimization algorithm inspired by the behavior of bird flocking or fish schooling. In PSO, a set of particles move through the problem’s solution space, searching for the optimal solution.

Each particle in the swarm represents a potential solution to the TSP problem. The particles move towards better solutions by adjusting their positions based on their own best solution and the best solution found by the swarm so far. This enables the particles to explore the search space efficiently and converge towards a good solution.

The optimization process in PSO involves iterating through multiple generations of particles. In each iteration, the particles evaluate their positions using a fitness function that measures the quality of their solutions. The fitness function for TSP typically calculates the total distance travelled by the salesperson.

Advantages of PSO for TSP

PSO has several advantages for solving the TSP:

• PSO is a global optimization algorithm, meaning it is able to find the global optimum rather than getting stuck in local optima.
• PSO is a population-based algorithm, allowing multiple solutions to be explored concurrently.
• PSO can handle TSP instances with a large number of cities efficiently.
• PSO is easy to implement and tune for different TSP instances.

Limitations of PSO for TSP

Despite its advantages, PSO also has some limitations when applied to the TSP:

• PSO may require a large number of particles to find good solutions for complex TSP instances.
• PSO may converge prematurely to suboptimal solutions.
• PSO performance can be sensitive to the choice of parameters, such as the swarm size and velocity update equations.

In conclusion, Particle Swarm Optimization is a powerful technique for solving the TSP, leveraging AI and optimization principles. It offers advantages like global optimization and population-based search, but also has some limitations. When applied correctly and fine-tuned, PSO can provide efficient and effective solutions to the TSP.

Neural Networks for TSP

The Traveling Salesman Problem (TSP) is a well-known problem in the field of artificial intelligence and machine learning. It involves finding the shortest possible route that a salesperson can take to visit a given set of cities and return to the starting city. TSP is known to be an NP-hard problem, meaning that finding the optimal solution becomes exponentially difficult with an increase in the number of cities.

Artificial neural networks (ANN) have been widely used to solve TSP due to their ability to learn complex patterns and relationships. ANN is a computational model inspired by the human brain, consisting of interconnected nodes, or artificial neurons, that process and transmit information. By training the neural network on a set of training data, it can learn the optimal routes for different instances of the TSP problem.

There are several approaches to using neural networks for solving TSP. One common method is to represent the TSP problem as a graph, where the cities are nodes and the distances between them are edges. The neural network is then trained to predict the optimal route by adjusting the weights of its connections. Another approach is to use a recurrent neural network (RNN) that takes into account the order in which the cities are visited, as the order can greatly affect the total distance traveled.

Benefits of using neural networks for solving TSP

Using neural networks for TSP has several advantages. Firstly, neural networks can handle large amounts of data and complex relationships, making them suitable for solving the TSP problem with a large number of cities. Secondly, neural networks can be trained on a variety of inputs and can generalize their learning to solve TSP instances that were not part of the training set. This makes them more flexible and adaptable compared to traditional algorithms for TSP.

Challenges and future directions

Despite the benefits, there are some challenges in using neural networks for TSP. The main challenge is the training process, as it requires a large amount of training data and computational resources. Additionally, finding the optimal architecture and parameters for the neural network can be a challenging task in itself.

Future research directions for using neural networks in solving TSP include developing more efficient training algorithms, exploring different network architectures, and integrating other optimization techniques with neural networks. The goal is to further improve the performance and efficiency of neural network approaches in solving the TSP problem and pave the way for more effective AI-based solutions in the field of traveling salesman problem.

Machine Learning Approaches for TSP

The Traveling Salesman Problem (TSP) is a classic optimization problem in artificial intelligence (AI) that involves finding the shortest possible route for a salesperson to visit a given set of cities and return to the starting point. This problem is known to be NP-hard, which means that finding the optimal solution becomes computationally expensive as the number of cities increases.

In recent years, machine learning has emerged as a powerful tool for solving complex problems like the TSP. Researchers have developed various approaches using AI techniques to tackle the TSP and improve upon traditional optimization algorithms. These machine learning approaches aim to find approximate solutions that are close to the optimal solution while reducing the computational burden.

Reinforcement Learning

One popular approach for solving TSP using machine learning is reinforcement learning (RL). RL is a type of AI technique where an agent learns to make decisions by interacting with an environment and receiving rewards or penalties based on its actions. In the context of TSP, the agent can be trained to learn a policy that guides it in choosing the next city to visit. The agent takes into account the current city, the remaining cities, and the distances between them to make the decision. Through trial and error, the agent improves its policy to find better and better solutions to the TSP.

Genetic Algorithms

Another popular machine learning approach for solving TSP is genetic algorithms (GA). GA is a metaheuristic optimization algorithm inspired by the process of natural selection in genetics. In the context of TSP, a population of potential solutions (called chromosomes) is evolved over multiple generations. Each chromosome represents a possible route for the salesperson. Through processes like selection, crossover, and mutation, the genetic algorithm explores different combinations of cities to find better solutions. The fittest individuals from each generation are selected to produce the next generation, leading to the evolution of the population towards better solutions.

Overall, machine learning approaches offer promising solutions to the TSP and have the potential to outperform traditional optimization algorithms. As research in AI continues to evolve, we can expect further advancements in solving the traveling salesman problem and similar optimization problems using intelligent techniques.

Supervised Learning for TSP

The Traveling Salesman Problem (TSP) is a well-known optimization problem that involves finding the shortest possible route for a salesman to visit a given set of cities and return to the starting city. This problem has been extensively studied and has numerous applications in various industries.

One approach to solving the TSP is to use supervised learning techniques, which involve training a machine learning model to predict the optimal solution for a given set of cities. By using artificial intelligence (AI) and learning from existing solutions, the model can make predictions and find near-optimal solutions for new instances of the problem.

Training Data

To train the supervised learning model for TSP, a dataset consisting of input-output pairs is needed. Each input corresponds to a set of cities, represented by their coordinates, and the corresponding output is the optimal solution for that set of cities. The training data should cover a wide range of instances with different numbers of cities and complexities to ensure the model learns to generalize well.

Feature Engineering

Before training the model, feature engineering techniques can be applied to transform the raw input data into a format suitable for learning. This may involve calculating additional features such as distances between cities, angles between city coordinates, or any other relevant characteristics that can help the model learn patterns and make accurate predictions.

Training the Model

Various supervised learning algorithms can be used to train the model for TSP, such as decision trees, neural networks, or support vector machines. The choice of algorithm depends on factors such as dataset size, complexity, and desired performance.

The model is trained using the input-output pairs, and the objective is to minimize the prediction error by adjusting the model’s parameters or hyperparameters. Cross-validation techniques can be used to evaluate the model’s performance and prevent overfitting.

Once the model is trained, it can be used to predict the optimal solution for new sets of cities. The predicted solution may not always be the absolute optimal solution due to the complexity of the TSP, but supervised learning can provide good approximate solutions.

In conclusion, supervised learning techniques offer a promising approach to solving the Traveling Salesman Problem. By training a machine learning model using existing solutions, it can make predictions and provide near-optimal solutions for new instances of the problem. This application of artificial intelligence and learning has the potential to improve efficiency and decision-making in various industries that face similar optimization challenges.

Unsupervised Learning for TSP

The Traveling Salesman Problem (TSP) is a well-known problem in the field of artificial intelligence and machine learning. It involves finding the shortest possible route that a salesperson can take to visit a set of cities and return to the starting city. This problem is often used as a benchmark for testing optimization algorithms and techniques.

Traditionally, solving the TSP has been a challenging task, requiring the use of combinatorial optimization algorithms and heuristics. However, recent advancements in machine learning, particularly unsupervised learning techniques, have shown promise in tackling this problem.

Unsupervised learning is a branch of machine learning where the algorithm learns patterns and relationships within the data without any specific guidance or labeled examples. In the context of the TSP, unsupervised learning algorithms can be used to analyze the spatial relationships between the cities and learn optimal routes.

One approach is to use clustering algorithms to group cities that are close to each other. The algorithm can then find the optimal order to visit these clusters, reducing the complexity of the problem. Another approach is to use deep learning techniques, such as autoencoders, to learn a lower-dimensional representation of the cities and use this representation to find the shortest path.

By using unsupervised learning for the TSP, it is possible to find near-optimal solutions without explicitly defining the objective function or using heuristics. This reduces the computational complexity and can lead to more efficient and scalable solutions for large-scale TSP instances.

In conclusion, unsupervised learning techniques offer a new perspective on solving the Traveling Salesman Problem. By leveraging the power of artificial intelligence and machine learning, we can develop innovative approaches to solve this classic optimization problem efficiently and effectively.

Reinforcement Learning for TSP

Artificial Intelligence (AI) techniques have been widely applied to solve various real-world problems, and the Traveling Salesman Problem (TSP) is no exception. TSP is a classic optimization problem where a salesman needs to find the shortest possible route to visit a set of cities and return to the starting point.

In recent years, machine learning algorithms, particularly reinforcement learning, have shown promising results in tackling TSP. Reinforcement learning is a branch of AI that focuses on training agents to make sequential decisions based on environmental feedback. It has been successfully applied to various problems, including robotics, game playing, and now TSP.

In reinforcement learning for TSP, the salesman is treated as an agent that learns how to choose the next city to visit in order to minimize the total distance traveled. The agent receives rewards or penalties based on the choices it makes. By exploring different actions and learning from the feedback, the agent gradually improves its decision-making abilities.

One common approach to reinforcement learning for TSP is to use a policy-based method, where the agent learns a policy that maps states (current city and visited cities) to actions (next city to visit). The agent uses this learned policy to make decisions during the traversal of the cities. The policy is updated through a process called policy gradient, where the agent adjusts the probabilities assigned to each action based on the rewards received.

Another approach is to use value-based methods, where the agent learns the expected value (reward) of being in a certain state and taking a certain action. The agent then selects the action with the highest expected value at each step. This process is done iteratively, adjusting the value estimates based on the rewards received and the expected values of the next states.

Reinforcement learning for TSP is still an active area of research, and various techniques and algorithms are constantly being developed and improved. As AI techniques continue to advance, we can expect further progress in solving the traveling salesman problem and optimizing salesperson routes in the real world.

Hybrid AI Techniques for TSP

The Travelling Salesman Problem (TSP) is a classic optimization problem in artificial intelligence that involves finding the shortest possible route that a salesman can travel to visit a given set of cities and return to the starting point. Due to its computational complexity, solving the TSP is a challenging task.

To tackle the TSP, researchers have explored various artificial intelligence techniques. One approach is to combine multiple AI techniques to create hybrid algorithms that can yield better results. These hybrid AI techniques leverage the strengths of different AI algorithms to find efficient solutions for the TSP.

One popular hybrid AI technique for the TSP is the combination of machine learning and heuristic algorithms. Machine learning algorithms, such as genetic algorithms or neural networks, can be used to generate initial solutions for the TSP. These initial solutions can then be improved using heuristic algorithms, such as the 2-opt or 3-opt algorithm, which search for better solutions by iteratively swapping edges in the tour.

Another hybrid AI technique for the TSP is the combination of metaheuristic algorithms and local search algorithms. Metaheuristic algorithms, such as ant colony optimization or simulated annealing, can be used to explore the search space of the TSP and find promising solutions. These solutions can then be further refined using local search algorithms, which make small adjustments to the solutions to improve their quality.

Hybrid AI techniques offer the advantage of leveraging the complementary strengths of different AI algorithms to solve the TSP more effectively. By combining different techniques, hybrid algorithms can achieve better performance and find more optimal solutions compared to using a single AI technique alone.

In conclusion, solving the Travelling Salesman Problem (TSP) requires the use of advanced artificial intelligence techniques. Hybrid AI techniques that combine machine learning, heuristic algorithms, metaheuristic algorithms, and local search algorithms have shown great promise in solving the TSP efficiently. Further research and development in this area can lead to even more effective approaches for solving this challenging problem.

Combining Genetic Algorithms with Neural Networks for TSP

The Travelling Salesman Problem (TSP) is a classic optimization problem in which a salesperson must find the shortest possible route to visit a set of cities and return to the starting city. This problem has long captivated researchers in the field of Artificial Intelligence (AI) due to its complexity and real-world applications.

One common approach to solving the TSP is by using Genetic Algorithms (GA), which mimic the process of natural selection to find optimal solutions. GA starts with a population of candidate solutions, and through selection, reproduction, and mutation, it evolves towards finding a near-optimal solution.

Recently, researchers have started combining the power of Genetic Algorithms with Neural Networks (NN) to tackle the TSP. Neural Networks are machine learning models inspired by the structure and function of biological neural networks. They are adept at pattern recognition and can be trained to learn and make predictions based on training data.

In the context of the TSP, a Neural Network can be used to learn patterns and relationships in the problem space. The Neural Network is trained using genetic operators such as mutation and crossover, with the goal of finding a good initial solution for the TSP. The solution found by the Neural Network is then further improved using Genetic Algorithms.

This combination of Genetic Algorithms with Neural Networks leverages the strengths of both approaches. The Neural Network allows for efficient learning of patterns in the problem space, while the Genetic Algorithms provide global optimization capabilities and fine-tuning of the solution.

The use of Artificial Intelligence techniques, such as combining Genetic Algorithms with Neural Networks, has shown promising results in solving the TSP. This hybrid approach has the potential to find near-optimal solutions for the TSP, which can have significant practical applications in the field of logistics and operations research.

In conclusion, the combination of Genetic Algorithms and Neural Networks offers a powerful approach to tackle the Travelling Salesman Problem. This hybrid AI technique can efficiently learn from data and optimize the solution, providing a valuable tool for solving complex optimization problems like the TSP.

Combining Ant Colony Optimization with Reinforcement Learning for TSP

The Travelling Salesperson Problem (TSP) is a classic problem in the field of artificial intelligence (AI) and is often used as a benchmark for testing various optimization algorithms. The goal of the TSP is to find the shortest possible route that a salesperson can take to visit a set of cities and return to the starting city, while visiting each city exactly once.

Ant Colony Optimization (ACO) is a metaheuristic algorithm inspired by the behavior of ants searching for food. The idea behind ACO is to simulate the pheromone trail left by ants to guide their search. By iteratively updating the pheromone trail based on the quality of the solutions found, ACO is able to converge to a near-optimal solution to the TSP.

Reinforcement Learning (RL) is a machine learning technique that focuses on how an agent can learn from interactions with a dynamic environment. In the context of the TSP, RL can be used to train an agent to navigate the cities efficiently. The agent receives a reward signal based on the quality of the solution found, and it uses this feedback to update its policy for selecting which city to visit next.

Combining ACO with RL

One approach to solving the TSP is to combine ACO with RL. In this approach, an ant colony is used to explore the solution space and update the pheromone trail, while a reinforcement learning agent learns from the ants’ behavior to improve its policy for selecting the next city to visit.

The ant colony proceeds by iteratively constructing solutions to the TSP. Each ant starts at a random city and selects the next city to visit based on the pheromone trail and a heuristic value that estimates the desirability of visiting each city. After completing a solution, the pheromone trail is updated based on the quality of the solution found.

The reinforcement learning agent observes the ants’ behavior and receives a reward signal based on the quality of the solution found. It then updates its policy for selecting the next city to visit using techniques such as Q-learning or policy gradients. The updated policy is used by the ant colony in the next iteration to guide its search.

Benefits and Challenges

The combination of ACO with RL offers several benefits in solving the TSP. Firstly, it leverages the exploration-exploitation trade-off of ACO to explore the solution space effectively. The RL agent, on the other hand, learns from the ants’ behavior and can adapt its policy to the specific characteristics of the problem instance.

However, combining ACO with RL also poses challenges. Balancing the exploration and exploitation in the ant colony is crucial to prevent premature convergence to suboptimal solutions. The RL agent needs to explore different strategies effectively and continuously learn and update its policy based on the reward signal.

The combination of Ant Colony Optimization with Reinforcement Learning is a promising approach to solving the Travelling Salesperson Problem. By leveraging the strengths of both techniques, it is possible to achieve near-optimal solutions to this challenging problem. Further research and experimentation are needed to explore the full potential of this hybrid approach and its application to other optimization problems in the field of artificial intelligence.

Combining Simulated Annealing with Tabu Search for TSP

The Travelling Salesman Problem (TSP) is a well-known problem in the field of Artificial Intelligence (AI) and Machine Learning. It involves finding the shortest possible route for a salesman to visit a number of cities and return to the starting point.

TSP is known to be an NP-hard problem, meaning that finding the optimal solution requires an exponential amount of time as the number of cities increases. Various AI techniques have been developed to solve TSP efficiently, and two popular ones are Simulated Annealing and Tabu Search.

Simulated Annealing is a metaheuristic algorithm inspired by the annealing process in metallurgy. It starts with an initial solution and iteratively explores neighboring solutions by making random changes. The algorithm gradually decreases the probability of accepting worse solutions, allowing it to escape local optima and converge towards a global optimum.

Tabu Search, on the other hand, is a local search algorithm that maintains a short-term memory of previously visited solutions. It forbids revisiting those solutions for a certain number of iterations, preventing the algorithm from getting stuck in cycles or revisiting suboptimal solutions.

Combining Simulated Annealing with Tabu Search for TSP can lead to improved performance and better results. The simulated annealing algorithm can be used to generate initial solutions, while the tabu search algorithm can be used to further explore and refine those solutions. This combination allows for a more effective exploration of the search space and a better chance of finding the optimal solution.

In summary, combining simulated annealing with tabu search is a promising approach for solving the TSP. It combines the global exploration capability of simulated annealing with the local search and memory-based strategies of tabu search. By leveraging the strengths of both algorithms, this approach can help find high-quality solutions to the travelling salesman problem efficiently and effectively.

Comparison of AI Techniques for Solving TSP

The Travelling Salesman Problem (TSP) is a well-known problem in the field of artificial intelligence and machine learning. The TSP involves finding the shortest possible route that a salesman can take to visit a given set of cities exactly once and return to the starting city. It is a classic problem that has been studied extensively in the field of computer science.

There are several AI techniques that have been used to tackle the TSP, each with its own advantages and disadvantages. One popular approach is to use genetic algorithms, which are inspired by the process of natural selection. In this approach, a population of potential solutions is evolved over multiple generations, with the fittest individuals being selected to produce offspring. This process continues until a satisfactory solution is found.

Another popular technique for solving the TSP is the use of ant colony optimization algorithms. These algorithms are inspired by the behavior of ants, who use pheromone trails to communicate and navigate their environment. In this approach, artificial ants are used to explore the solution space, leaving pheromone trails that are reinforced based on the quality of the solutions found. Over time, a good solution is discovered based on the concentration of pheromones.

Machine learning techniques have also been applied to the TSP, with some success. In these approaches, a model is trained on a set of known TSP instances, and then used to predict the optimal solution for new instances. This can be done using techniques such as reinforcement learning or supervised learning.

Overall, each AI technique has its own strengths and weaknesses when applied to the TSP. Genetic algorithms are powerful and can find good solutions, but they can be computationally expensive. Ant colony optimization algorithms are efficient and can find near-optimal solutions, but they may struggle with larger instances of the problem. Machine learning techniques have the potential to generalize well, but they may require a large amount of training data.

In conclusion, there are various AI techniques that can be used to tackle the Travelling Salesman Problem. Each technique has its own pros and cons, and the choice of technique will depend on the specific requirements of the problem at hand. It is important to consider factors such as computational efficiency, solution quality, and the availability of training data when choosing an AI technique for solving the TSP.

Pros and Cons of AI Techniques for TSP

Artificial Intelligence (AI) techniques have shown great promise in solving the Travelling Salesman Problem (TSP). The TSP is a classic combinatorial optimization problem, where a salesperson must find the shortest possible route to visit a set of cities exactly once and return to the starting city.

Pros of Using AI Techniques for TSP

1. Improved Efficiency: AI techniques, such as machine learning, can significantly improve the efficiency of finding optimal or near-optimal solutions for TSP. These techniques can explore a large search space efficiently and provide solutions that are better than those obtained from traditional methods.

2. Global Optimization: AI techniques can help in finding global optimal solutions for TSP. Traditional optimization methods may find local optima, which are not the best possible solutions. With AI techniques, the entire search space can be explored, leading to better solutions.

3. Adaptability: AI techniques can adapt to different instances of the TSP. This means that they can learn from previous instances and apply the knowledge gained to solve new instances more efficiently. This adaptability makes AI techniques suitable for solving TSP in real-world scenarios.

Cons of Using AI Techniques for TSP

1. Computational Complexity: AI techniques for solving TSP can be computationally expensive, especially when dealing with a large number of cities. The time complexity of these techniques may hinder their practicality in real-time decision-making scenarios.

2. Problem Dependency: AI techniques for solving TSP may heavily depend on the problem instance. Different instances of the TSP may require different AI techniques or parameter tuning, which can be time-consuming and computationally expensive.

3. Interpretability: AI techniques, such as machine learning based approaches, may lack interpretability. The solutions provided by these techniques may be difficult to explain or understand, especially when compared to traditional optimization methods.

Overall, AI techniques have the potential to provide efficient solutions for the Travelling Salesman Problem. While there are challenges to overcome, such as computational complexity and interpretability, the benefits of using AI techniques outweigh the drawbacks in many cases.

Real-World Applications of AI Techniques for TSP

The Travelling Salesman Problem (TSP) is a well-known problem in artificial intelligence and machine learning. It involves finding the shortest possible route that a salesperson can take to visit a given set of cities exactly once and return to the starting city. The TSP has been extensively studied and has numerous real-world applications.

Logistics and Supply Chain Management

One of the main applications of AI techniques for TSP is in logistics and supply chain management. Companies that have multiple warehouses or distribution centers need to optimize the routes their delivery vehicles take to minimize costs and maximize efficiency. AI algorithms can be used to solve the TSP for these companies, providing them with the most optimal routes for their delivery vehicles.

Circuit Board Design

Another real-world application of AI techniques for TSP is in circuit board design. When designing a circuit board, engineers need to determine the most efficient way to connect various components on the board. This can be formulated as a TSP, with the components representing cities and the connections representing distances between them. AI algorithms can be used to solve this TSP and find the most optimal connections between the components.

These are just a few examples of the real-world applications of AI techniques for TSP. There are many other areas where TSP can be applied, such as route planning for autonomous vehicles, network routing optimization, and DNA sequencing. AI techniques are invaluable tools for solving the TSP and finding optimal solutions for a wide range of problems.

Challenges in Solving TSP with AI Techniques

The Travelling Salesman Problem (TSP) is a classic optimization problem that deals with finding the shortest possible route for a salesman to travel and visit a set of cities exactly once and return to the starting city. Solving TSP is a complex task and requires the use of AI techniques such as machine learning and artificial intelligence (AI).

One of the major challenges in solving TSP with AI techniques is the exponential growth of the problem as the number of cities increases. The number of possible routes to visit all cities grows factorially with the number of cities, making it computationally expensive to find the optimal solution.

Another challenge is the high dimensionality of the problem. TSP can be represented as a graph with cities as nodes and the distances between cities as edges. The number of edges in the graph is equal to the number of possible connections between cities, which grows quadratically with the number of cities. This high dimensionality makes it difficult to explore all possible solutions and find the optimal one.

Furthermore, TSP is an NP-hard problem, which means that it is difficult to find an exact solution in a reasonable amount of time. AI techniques provide approximate solutions that are close to the optimal solution, but these solutions may not be guaranteed to be optimal. Finding good quality solutions with AI techniques is a challenge in itself.

Moreover, the performance of AI techniques in solving TSP heavily depends on the choice of algorithms and parameters. Different AI techniques such as genetic algorithms, ant colony optimization, and reinforcement learning have been applied to TSP, but their effectiveness varies depending on the problem instance and the specific parameters used. Finding the right combination of techniques and parameters is a challenging task.

In conclusion, solving TSP with AI techniques poses several challenges such as the exponential growth and high dimensionality of the problem, the NP-hardness, and the need for selecting appropriate algorithms and parameters. Addressing these challenges is crucial for obtaining efficient and accurate solutions to the TSP.

Future Trends in AI Techniques for TSP

As the world becomes more interconnected and the need for efficient transportation grows, finding optimal solutions to the Travelling Salesperson Problem (TSP) becomes increasingly important. Artificial intelligence (AI) techniques have shown great promise in tackling this complex problem, and the future holds even more potential.

One of the most exciting trends in AI techniques for TSP is the incorporation of machine learning algorithms. By analyzing large amounts of data, these algorithms can identify patterns and make predictions about the most efficient routes for a travelling salesperson. This can greatly reduce the search space and lead to faster and more accurate solutions.

Another trend is the development of hybrid AI techniques that combine the strengths of different algorithms. For example, a combination of genetic algorithms and simulated annealing can provide a more comprehensive search strategy, improving the chances of finding the optimal solution to the TSP. These hybrid techniques have shown promising results and are expected to be further refined in the future.

In addition to machine learning and hybrid techniques, advancements in AI hardware, such as faster processors and more memory, are also expected to have a significant impact on solving the TSP. With more computing power, AI algorithms can handle larger problem instances and provide more accurate solutions. This opens up new possibilities for solving real-world TSP scenarios, where the number of cities and constraints can be very high.

Furthermore, the integration of AI techniques with other emerging technologies, such as blockchain and Internet of Things (IoT), can bring a new dimension to solving the TSP. For example, by leveraging IoT data from vehicles and traffic sensors, AI algorithms can dynamically adjust the salesperson’s route based on real-time traffic conditions, leading to more efficient and adaptive solutions.

In conclusion, the future of solving the Travelling Salesperson Problem with AI techniques looks bright. With advancements in machine learning, hybrid algorithms, hardware capabilities, and the integration of AI with other technologies, we can expect more efficient and accurate solutions for the TSP. This will not only benefit businesses and salespersons, but also contribute to the overall optimization of transportation systems.

Question-answer:

What is the traveling salesperson problem.

The Traveling Salesperson Problem, also known as TSP, is a classic algorithmic problem in computer science. It involves finding the shortest possible route that a salesperson can take to visit a set of cities and return to the starting city, while visiting each city exactly once.

Why is the Traveling Salesperson Problem important?

The Traveling Salesperson Problem is important because it has practical applications in various fields, such as logistics, transportation, and network routing. Solving this problem efficiently can lead to cost savings and improved efficiency.

How can Artificial Intelligence techniques be used to solve the Traveling Salesperson Problem?

Artificial Intelligence techniques, such as genetic algorithms, ant colony optimization, and simulated annealing, can be used to solve the Traveling Salesperson Problem. These algorithms mimic natural processes to search for optimal or near-optimal solutions.

What is the role of machine learning in solving the Traveling Salesperson Problem?

Machine learning can be used in various ways to solve the Traveling Salesperson Problem. For example, reinforcement learning algorithms can learn to find good solutions through trial and error, while supervised learning can be used to train models that predict the optimal route given a set of cities.

What are the limitations of using Artificial Intelligence techniques to solve the Traveling Salesperson Problem?

While Artificial Intelligence techniques can provide good solutions to the Traveling Salesperson Problem, they are not guaranteed to find the optimal solution. These algorithms can also be computationally expensive and may require significant computational resources to solve large-scale instances of the problem.

What is the Traveling Salesman Problem?

The Traveling Salesman Problem (TSP) is a classic combinatorial optimization problem in mathematics and computer science. It involves finding the shortest possible route that allows a salesman to visit a set of cities and return to the original city, visiting each city only once. The problem is known to be NP-hard, meaning that finding an exact solution becomes extremely time-consuming as the number of cities increases.

How can Artificial Intelligence techniques be used to solve the Traveling Salesman Problem?

Artificial Intelligence techniques, such as optimization algorithms and machine learning, can be applied to solve the Traveling Salesman Problem. Optimization algorithms like genetic algorithms, ant colony optimization, and simulated annealing can be used to find approximate solutions that are close to the optimal route. Machine learning techniques can also be used to learn patterns and heuristics from previous solutions, which can help improve the efficiency of finding good solutions.

What are the challenges in solving the Traveling Salesman Problem using AI techniques?

One of the main challenges in using AI techniques to solve the Traveling Salesman Problem is the exponential increase in the search space as the number of cities increases. This makes finding an exact solution computationally expensive and impractical for large problem instances. Additionally, finding good solutions that are close to the optimal route is still a challenging task, as it requires balancing exploration and exploitation in the search process. Finally, determining the stopping criteria for the algorithms and evaluating the quality of the solutions obtained are also challenging aspects of solving TSP using AI techniques.

Related posts:

About the author

Embrace AI-Powered CDPs: The Future of Customer Engagement

Elon musk’s vision ai, creating a powerful gpt telegram chatbot, who invented ai.

12.9 Traveling Salesperson Problem

Learning objectives.

After completing this section, you should be able to:

• Distinguish between brute force algorithms and greedy algorithms.
• List all distinct Hamilton cycles of a complete graph.
• Apply brute force method to solve traveling salesperson applications.
• Apply nearest neighbor method to solve traveling salesperson applications.

We looked at Hamilton cycles and paths in the previous sections Hamilton Cycles and Hamilton Paths . In this section, we will analyze Hamilton cycles in complete weighted graphs to find the shortest route to visit a number of locations and return to the starting point. Besides the many routing applications in which we need the shortest distance, there are also applications in which we search for the route that is least expensive or takes the least time. Here are a few less common applications that you can read about on a website set up by the mathematics department at the University of Waterloo in Ontario, Canada:

• Design of fiber optic networks
• Minimizing fuel expenses for repositioning satellites
• Development of semi-conductors for microchips
• A technique for mapping mammalian chromosomes in genome sequencing

Before we look at approaches to solving applications like these, let's discuss the two types of algorithms we will use.

Brute Force and Greedy Algorithms

An algorithm is a sequence of steps that can be used to solve a particular problem. We have solved many problems in this chapter, and the procedures that we used were different types of algorithms. In this section, we will use two common types of algorithms, a brute force algorithm and a greedy algorithm . A brute force algorithm begins by listing every possible solution and applying each one until the best solution is found. A greedy algorithm approaches a problem in stages, making the apparent best choice at each stage, then linking the choices together into an overall solution which may or may not be the best solution.

To understand the difference between these two algorithms, consider the tree diagram in Figure 12.187 . Suppose we want to find the path from left to right with the largest total sum. For example, branch A in the tree diagram has a sum of 10 + 2 + 11 + 13 = 36 10 + 2 + 11 + 13 = 36 .

To be certain that you pick the branch with greatest sum, you could list each sum from each of the different branches:

A : 10 + 2 + 11 + 13 = 36 10 + 2 + 11 + 13 = 36

B : 10 + 2 + 11 + 8 = 31 10 + 2 + 11 + 8 = 31

C : 10 + 2 + 15 + 1 = 28 10 + 2 + 15 + 1 = 28

D : 10 + 2 + 15 + 6 = 33 10 + 2 + 15 + 6 = 33

E : 10 + 7 + 3 + 20 = 40 10 + 7 + 3 + 20 = 40

F : 10 + 7 + 3 + 14 = 34 10 + 7 + 3 + 14 = 34

G : 10 + 7 + 4 + 11 = 32 10 + 7 + 4 + 11 = 32

H : 10 + 7 + 4 + 5 = 26 10 + 7 + 4 + 5 = 26

Then we know with certainty that branch E has the greatest sum.

Now suppose that you wanted to find the branch with the highest value, but you only were shown the tree diagram in phases, one step at a time.

After phase 1, you would have chosen the branch with 10 and 7. So far, you are following the same branch. Let’s look at the next phase.

After phase 2, based on the information you have, you will choose the branch with 10, 7 and 4. Now, you are following a different branch than before, but it is the best choice based on the information you have. Let’s look at the last phase.

After phase 3, you will choose branch G which has a sum of 32.

The process of adding the values on each branch and selecting the highest sum is an example of a brute force algorithm because all options were explored in detail. The process of choosing the branch in phases, based on the best choice at each phase is a greedy algorithm. Although a brute force algorithm gives us the ideal solution, it can take a very long time to implement. Imagine a tree diagram with thousands or even millions of branches. It might not be possible to check all the sums. A greedy algorithm, on the other hand, can be completed in a relatively short time, and generally leads to good solutions, but not necessarily the ideal solution.

Example 12.42

Distinguishing between brute force and greedy algorithms.

A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This leaves $ 0.37 − $ 0.25 = $ 0.12 $ 0.37 − $ 0.25 = $ 0.12 . The cashier selects the coin of highest value less than or equal to $0.12, which is a dime. This leaves $ 0.12 − $ 0.10 = $ 0.02 $ 0.12 − $ 0.10 = $ 0.02 . The cashier selects the coin of highest value less than or equal to $0.02, which is a penny. This leaves $ 0.02 − $ 0.01 = $ 0.01 $ 0.02 − $ 0.01 = $ 0.01 . The cashier selects the coin of highest value less than or equal to $0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.

• Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
• The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.
• The approach the cashier used is an example of a greedy algorithm, because the problem was approached in phases and the best choice was made at each phase. Also, it is not a brute force algorithm, because the cashier did not attempt to list out all possible combinations of coins to reach this conclusion.
• Yes, it is consistent. A greedy algorithm does not always yield the best result, but sometimes it does.

Your Turn 12.42

The traveling salesperson problem.

Now let’s focus our attention on the graph theory application known as the traveling salesperson problem (TSP) in which we must find the shortest route to visit a number of locations and return to the starting point.

Recall from Hamilton Cycles , the officer in the U.S. Air Force who is stationed at Vandenberg Air Force base and must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needed to visit each base once. We looked at the weighted graph in Figure 12.192 representing the four U.S. Air Force bases: Vandenberg, Edwards, Los Angeles, and Beal and the distances between them.

Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. If the officer wants to travel the shortest distance, this will correspond to a Hamilton cycle of lowest weight. We saw in Table 12.11 that there are six distinct Hamilton cycles (directed cycles) in a complete graph with four vertices, but some lie on the same cycle (undirected cycle) in the graph.

Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown in Figure 12.193 .

The possible distances are:

So, a Hamilton cycle of least weight is V → B → E → L → V (or the reverse direction). The officer should travel from Vandenberg to Beal to Edwards, to Los Angeles, and back to Vandenberg.

Finding Weights of All Hamilton Cycles in Complete Graphs

Notice that we listed all of the Hamilton cycles and found their weights when we solved the TSP about the officer from Vandenberg. This is a skill you will need to practice. To make sure you don't miss any, you can calculate the number of possible Hamilton cycles in a complete graph. It is also helpful to know that half of the directed cycles in a complete graph are the same cycle in reverse direction, so, you only have to calculate half the number of possible weights, and the rest are duplicates.

In a complete graph with n n vertices,

• The number of distinct Hamilton cycles is ( n − 1 ) ! ( n − 1 ) ! .
• There are at most ( n − 1 ) ! 2 ( n − 1 ) ! 2 different weights of Hamilton cycles.

TIP! When listing all the distinct Hamilton cycles in a complete graph, you can start them all at any vertex you choose. Remember, the cycle a → b → c → a is the same cycle as b → c → a → b so there is no need to list both.

Example 12.43

Calculating possible weights of hamilton cycles.

Suppose you have a complete weighted graph with vertices N, M, O , and P .

• Use the formula ( n − 1 ) ! ( n − 1 ) ! to calculate the number of distinct Hamilton cycles in the graph.
• Use the formula ( n − 1 ) ! 2 ( n − 1 ) ! 2 to calculate the greatest number of different weights possible for the Hamilton cycles.
• Are all of the distinct Hamilton cycles listed here? How do you know? Cycle 1: N → M → O → P → N Cycle 2: N → M → P → O → N Cycle 3: N → O → M → P → N Cycle 4: N → O → P → M → N Cycle 5: N → P → M → O → N Cycle 6: N → P → O → M → N
• Which pairs of cycles must have the same weights? How do you know?
• There are 4 vertices; so, n = 4 n = 4 . This means there are ( n − 1 ) ! = ( 4 − 1 ) ! = 3 ⋅ 2 ⋅ 1 = 6 ( n − 1 ) ! = ( 4 − 1 ) ! = 3 ⋅ 2 ⋅ 1 = 6 distinct Hamilton cycles beginning at any given vertex.
• Since n = 4 n = 4 , there are ( n − 1 ) ! 2 = ( 4 − 1 ) ! 2 = 6 2 = 3 ( n − 1 ) ! 2 = ( 4 − 1 ) ! 2 = 6 2 = 3 possible weights.
• Yes, they are all distinct cycles and there are 6 of them.
• Cycles 1 and 6 have the same weight, Cycles 2 and 4 have the same weight, and Cycles 3 and 5 have the same weight, because these pairs follow the same route through the graph but in reverse.

TIP! When listing the possible cycles, ignore the vertex where the cycle begins and ends and focus on the ways to arrange the letters that represent the vertices in the middle. Using a systematic approach is best; for example, if you must arrange the letters M, O, and P, first list all those arrangements beginning with M, then beginning with O, and then beginning with P, as we did in Example 12.42.

Your Turn 12.43

The brute force method.

The method we have been using to find a Hamilton cycle of least weight in a complete graph is a brute force algorithm, so it is called the brute force method . The steps in the brute force method are:

Step 1: Calculate the number of distinct Hamilton cycles and the number of possible weights.

Step 2: List all possible Hamilton cycles.

Step 3: Find the weight of each cycle.

Step 4: Identify the Hamilton cycle of lowest weight.

Example 12.44

Applying the brute force method.

On the next assignment, the air force officer must leave from Travis Air Force base, visit Beal, Edwards, and Vandenberg Air Force bases each exactly once and return to Travis Air Force base. There is no need to visit Los Angeles Air Force base. Use Figure 12.194 to find the shortest route.

Step 1: Since there are 4 vertices, there will be ( 4 − 1 ) ! = 3 ! = 6 ( 4 − 1 ) ! = 3 ! = 6 cycles, but half of them will be the reverse of the others; so, there will be ( 4 − 1 ) ! 2 = 6 2 = 3 ( 4 − 1 ) ! 2 = 6 2 = 3 possible distances.

Step 2: List all the Hamilton cycles in the subgraph of the graph in Figure 12.195 .

To find the 6 cycles, focus on the three vertices in the middle, B, E, and V . The arrangements of these vertices are BEV, BVE, EBV, EVB, VBE , and VEB . These would correspond to the 6 cycles:

1: T → B → E → V → T

2: T → B → V → E → T

3: T → E → B → V → T

4: T → E → V → B → T

5: T → V → B → E → T

6: T → V → E → B → T

Step 3: Find the weight of each path. You can reduce your work by observing the cycles that are reverses of each other.

1: 84 + 410 + 207 + 396 = 1097 84 + 410 + 207 + 396 = 1097

2: 84 + 396 + 207 + 370 = 1071 84 + 396 + 207 + 370 = 1071

3: 370 + 410 + 396 + 396 = 1572 370 + 410 + 396 + 396 = 1572

4: Reverse of cycle 2, 1071

5: Reverse of cycle 3, 1572

6: Reverse of cycle 1, 1097

Step 4: Identify a Hamilton cycle of least weight.

The second path, T → B → V → E → T , and its reverse, T → E → V → B → T , have the least weight. The solution is that the officer should travel from Travis Air Force base to Beal Air Force Base, to Vandenberg Air Force base, to Edwards Air Force base, and return to Travis Air Force base, or the same route in reverse.

Your Turn 12.44

Now suppose that the officer needed a cycle that visited all 5 of the Air Force bases in Figure 12.194 . There would be ( 5 − 1 ) ! = 4 ! = 4 × 3 × 2 × 1 = 24 ( 5 − 1 ) ! = 4 ! = 4 × 3 × 2 × 1 = 24 different arrangements of vertices and ( 5 − 1 ) ! 2 = 4 ! 2 = 24 2 = 12 ( 5 − 1 ) ! 2 = 4 ! 2 = 24 2 = 12 distances to compare using the brute force method. If you consider 10 Air Force bases, there would be ( 10 − 1 ) ! = 9 ! = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 362 , 880 ( 10 − 1 ) ! = 9 ! = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 362 , 880 different arrangements and ( 10 − 1 ) ! 2 = 9 ! 2 = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 2 = 181 , 440 ( 10 − 1 ) ! 2 = 9 ! 2 = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 2 = 181 , 440 distances to consider. There must be another way!

The Nearest Neighbor Method

When the brute force method is impractical for solving a traveling salesperson problem, an alternative is a greedy algorithm known as the nearest neighbor method , which always visit the closest or least costly place first. This method finds a Hamilton cycle of relatively low weight in a complete graph in which, at each phase, the next vertex is chosen by comparing the edges between the current vertex and the remaining vertices to find the lowest weight. Since the nearest neighbor method is a greedy algorithm, it usually doesn’t give the best solution, but it usually gives a solution that is "good enough." Most importantly, the number of steps will be the number of vertices. That’s right! A problem with 10 vertices requires 10 steps, not 362,880. Let’s look at an example to see how it works.

Suppose that a candidate for governor wants to hold rallies around the state. They plan to leave their home in city A , visit cities B, C, D, E , and F each once, and return home. The airfare between cities is indicated in the graph in Figure 12.196 .

Let’s help the candidate keep costs of travel down by applying the nearest neighbor method to find a Hamilton cycle that has a reasonably low weight. Begin by marking starting vertex as V 1 V 1 for "visited 1st." Then to compare the weights of the edges between A and vertices adjacent to A : $250, $210, $300, $200, and $100 as shown in Figure 12.197 . The lowest of these is $100, which is the edge between A and F .

Mark F as V 2 V 2 for "visited 2nd" then compare the weights of the edges between F and the remaining vertices adjacent to F : $170, $330, $150 and $350 as shown in Figure 12.198 . The lowest of these is $150, which is the edge between F and D .

Mark D as V 3 V 3 for "visited 3rd." Next, compare the weights of the edges between D and the remaining vertices adjacent to D : $120, $310, and $270 as shown in Figure 12.199 . The lowest of these is $120, which is the edge between D and B .

So, mark B as V 4 V 4 for "visited 4th." Finally, compare the weights of the edges between B and the remaining vertices adjacent to B : $160 and $220 as shown in Figure 12.200 . The lower amount is $160, which is the edge between B and E .

Now you can mark E as V 5 V 5 and mark the only remaining vertex, which is C , as V 6 V 6 . This is shown in Figure 12.201 . Make a note of the weight of the edge from E to C , which is $180, and from C back to A , which is $210.

The Hamilton cycle we found is A → F → D → B → E → C → A . The weight of the circuit is $ 100 + $ 150 + $ 120 + $ 160 + $ 180 + $ 210 = $ 920 $ 100 + $ 150 + $ 120 + $ 160 + $ 180 + $ 210 = $ 920 . This may or may not be the route with the lowest cost, but there is a good chance it is very close since the weights are most of the lowest weights on the graph and we found it in six steps instead of finding 120 different Hamilton cycles and calculating 60 weights. Let’s summarize the procedure that we used.

Step 1: Select the starting vertex and label V 1 V 1 for "visited 1st." Identify the edge of lowest weight between V 1 V 1 and the remaining vertices.

Step 2: Label the vertex at the end of the edge of lowest weight that you found in previous step as V n V n where the subscript n indicates the order the vertex is visited. Identify the edge of lowest weight between V n V n and the vertices that remain to be visited.

Step 3: If vertices remain that have not been visited, repeat Step 2. Otherwise, a Hamilton cycle of low weight is V 1 → V 2 → ⋯ → V n → V 1 V 1 → V 2 → ⋯ → V n → V 1 .

Example 12.45

Using the nearest neighbor method.

Suppose that the candidate for governor wants to hold rallies around the state but time before the election is very limited. They would like to leave their home in city A , visit cities B , C , D , E , and F each once, and return home. The airfare between cities is not as important as the time of travel, which is indicated in Figure 12.202 . Use the nearest neighbor method to find a route with relatively low travel time. What is the total travel time of the route that you found?

Step 1: Label vertex A as V 1 V 1 . The edge of lowest weight between A and the remaining vertices is 85 min between A and D .

Step 2: Label vertex D as V 2 V 2 . The edge of lowest weight between D and the vertices that remain to be visited, B, C, E , and F , is 70 min between D and F .

Repeat Step 2: Label vertex F as V 3 V 3 . The edge of lowest weight between F and the vertices that remain to be visited, B, C, and E , is 75 min between F and C .

Repeat Step 2: Label vertex C as V 4 V 4 . The edge of lowest weight between C and the vertices that remain to be visited, B and E , is 100 min between C and B .

Repeat Step 2: Label vertex B as V 5 V 5 . The only vertex that remains to be visited is E . The weight of the edge between B and E is 95 min.

Step 3: A Hamilton cycle of low weight is A → D → F → C → B → E → A . So, a route of relatively low travel time is A to D to F to C to B to E and back to A . The total travel time of this route is: 85 min + 70 min + 75 min + 100 min + 95 min + 90 min = 515 min or 8 hrs 35 min 85 min + 70 min + 75 min + 100 min + 95 min + 90 min = 515 min or 8 hrs 35 min

Your Turn 12.45

Check your understanding, section 12.9 exercises.

As an Amazon Associate we earn from qualifying purchases.

This book may not be used in the training of large language models or otherwise be ingested into large language models or generative AI offerings without OpenStax's permission.

Want to cite, share, or modify this book? This book uses the Creative Commons Attribution License and you must attribute OpenStax.

Access for free at https://openstax.org/books/contemporary-mathematics/pages/1-introduction

• Authors: Donna Kirk
• Publisher/website: OpenStax
• Book title: Contemporary Mathematics
• Publication date: Mar 22, 2023
• Location: Houston, Texas
• Book URL: https://openstax.org/books/contemporary-mathematics/pages/1-introduction
• Section URL: https://openstax.org/books/contemporary-mathematics/pages/12-9-traveling-salesperson-problem

© Dec 21, 2023 OpenStax. Textbook content produced by OpenStax is licensed under a Creative Commons Attribution License . The OpenStax name, OpenStax logo, OpenStax book covers, OpenStax CNX name, and OpenStax CNX logo are not subject to the Creative Commons license and may not be reproduced without the prior and express written consent of Rice University.

• 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 Graphs - Data Structure and Algorithm Tutorials
• 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?

To revisit this article, visit My Profile, then View saved stories .

• Backchannel
• Newsletters
• WIRED Insider
• WIRED Consulting

Duncan Geere

Film explores moral and political repercussions of proving P equals NP

What would happen if one government learnt how to bypass the world's encryption systems? That's the all-too-timely question asked by Travelling Salesman , a movie that hands the starring role to a mathematical puzzle.

Its title refers to the "travelling salesman problem" -- given a list of cities and the distances between them all, what's the most efficient way that a salesman can visit them all and return home?

It's easy to check whether a given answer satisfies the criteria, but finding the best solution without trying every single possibility may be impossible. This puzzle, and others like it, are referred to as P vs NP.

In Travelling Salesman , a quartet of mathematicians solve this problem -- they find a way to shortcut the brute-force process of trying every approach, instantaneously negating the way the world's encryption systems operates. They've been hired to do their work by the United States, but they're confronted with the moral quandary of whether to hand over their research to the government or publish it publicly for the whole world's benefit. "We wanted to make a film that felt authentic to a niche group, but also ultimately would be accessible to a wide audience," said Tim Lanzone, one of the movie's creators. "The film is science fiction, but we wanted the science part to be as accurate as possible," his brother and co-writer, Andy Lanzone, added.

It's set almost entirely around a conference table in a sleek, modern, government facility. Initially the four argue over the implications of their research, before a representative of the government arrives and their argument escalates significantly. "I wanted to see if I could contain drama in one room," says Tim Lanzone. "Film school professors always warn that the hardest and most difficult scenes to shoot occur around kitchen tables."

Of course, that makes shooting it cheap, too. The film has a definite DIY aesthetic, but it's impressive what Lanzone has managed to achieve within those constraints. He opted deliberately for a cool colour temperature to make the atmosphere intense and unsettling. "Most of the drama takes place in one room, so we looked to use any sort of additional drama we could harness to our advantage."

That atmosphere is paired with fast-paced and complex dialogue -- it's not a movie that you can put on in the background. Attempts are made to explain the mathematical ideas behind the plot, but you will get more out of it if you've done a little research beforehand. The Lanzones admit this. "Understanding P vs NP directly isn't essential to enjoying the film -- especially if you have some grasp of the implications," says Tim. "We try to simplify it as well as we can during certain scenes but the pace of the dialogue is so fast that a lot of people are just along for the ride."

The movie isn't about the maths, though. Travelling Salesman is a film about power, and how it should be distributed. The government representative's job is to convince the four to sign off their parts of the solution, but it's an uphill struggle as they grapple with the repercussions of what the knowledge would mean for the world.

The bogeyman of China is brought up repeatedly, but it's fascinating to watch the film in light of recent revelations about the extent to which the US and UK's security agencies are already violating global encryption systems through back doors created in many of the world's communication networks.

Boone Ashworth

Carlton Reid

Amanda Hoover

Reece Rogers

The script was written long before Edward Snowden's revelations came to light, but Tim Lanzone says the topic had been on his mind for some time. "I wrote the first draft of the script back in early 2009, which in cyber-time is like an eternity. Back then, articles were really starting to come out more and more highlighting issues related to cyber-security and cyber-espionage -- particularly on important defence targets. It just seemed to be the next cold war-style battleground."

Andy Lanzone adds: "I don't know anyone that foresaw the scope of what the NSA is doing, so that was entirely coincidental. But the more general topic of cyber warfare was an interesting topic that we felt would only become more relevant over time."

The film firmly fails the Bechdel Test in that every one of the characters is white and male, limiting their perspectives considerably. The Lanzones blame this lack of diversity on budget: "We shot the film for under $25,000 and had a whirlwind casting session over two days in LA -- which was all the time we could afford," says Tim. "Knowing we only had about ten days to shoot Travelling Salesman , we were just trying to narrow it down to the five people who could most ably handle the complex language."

Ultimately, you'll get the same amount out of Travelling Salesman that you put into it. It's not a casual watch, but rewards concentration and occasionally pausing the movie and opening Wikipedia to check whether you've understood something right. If you were being cruel, you'd call it an argument for an hour and a half. But the themes and issues it addresses have never been more relevant -- the power of access to private communications, and whether it's right for that power to be concentrated under the auspices of one or a few governments. If you have strong feelings on the matter, on either side, Travelling Salesman is an essential watch.

This article was originally published by WIRED UK

Angela Watercutter

Eric Ravenscraft

Meghan O'Gieblyn

Jennifer M. Wood

• Design Pattern
• Interview Q

C Control Statements

C functions, c dynamic memory, c structure union, c file handling, c preprocessor, c command line, c programming test, c interview.

• Send your Feedback to [email protected]

Help Others, Please Share

Learn Latest Tutorials

Transact-SQL

Reinforcement Learning

R Programming

React Native

Python Design Patterns

Python Pillow

Python Turtle

Preparation

Verbal Ability

Interview Questions

Company Questions

Trending Technologies

Artificial Intelligence

Cloud Computing

Data Science

Machine Learning

B.Tech / MCA

Data Structures

Operating System

Computer Network

Compiler Design

Computer Organization

Discrete Mathematics

Ethical Hacking

Computer Graphics

Software Engineering

Web Technology

Cyber Security

C Programming

Control System

Data Mining

Data Warehouse

What a lovely hat

Is it made out of tin foil , paper 2024/626, exponential quantum speedup for the traveling salesman problem.

The traveling salesman problem is the problem of finding out the shortest route in a network of cities, that a salesman needs to travel to cover all the cities, without visiting the same city more than once. This problem is known to be $NP$-hard with a brute-force complexity of $O(N^N)$ or $O(N^{2N})$ for $N$ number of cities. This problem is equivalent to finding out the shortest Hamiltonian cycle in a given graph, if at least one Hamiltonian cycle exists in it. Quantum algorithms for this problem typically provide with a quadratic speedup only, using Grover's search, thereby having a complexity of $O(N^{N/2})$ or $O(N^N)$. We present a bounded-error quantum polynomial-time (BQP) algorithm for solving the problem, providing with an exponential speedup. The overall complexity of our algorithm is $O(N^3\log(N)\kappa/\epsilon + 1/\epsilon^3)$, where the errors $\epsilon$ are $O(1/{\rm poly}(N))$, and $\kappa$ is the not-too-large condition number of the matrix encoding all Hamiltonian cycles.

Note: 6 pages, 2 figures, comments welcome.

An official website of the United States government Here's how you know

Official websites use .gov A .gov website belongs to an official government organization in the United States.

Secure .gov websites use HTTPS A lock ( Lock A locked padlock ) or https:// means you’ve safely connected to the .gov website. Share sensitive information only on official, secure websites.

Biden-Harris Administration Announces Final Rule Requiring Automatic Refunds of Airline Tickets and Ancillary Service Fees

Rule makes it easy to get money back for cancelled or significantly changed flights, significantly delayed checked bags, and additional services not provided  

WASHINGTON – The Biden-Harris Administration today announced that the U.S. Department of Transportation (DOT) has issued a final rule that requires airlines to promptly provide passengers with automatic cash refunds when owed. The new rule makes it easy for passengers to obtain refunds when airlines cancel or significantly change their flights, significantly delay their checked bags, or fail to provide the extra services they purchased.

“Passengers deserve to get their money back when an airline owes them - without headaches or haggling,” said U.S. Transportation Secretary Pete Buttigieg . “Our new rule sets a new standard to require airlines to promptly provide cash refunds to their passengers.”  

The final rule creates certainty for consumers by defining the specific circumstances in which airlines must provide refunds. Prior to this rule, airlines were permitted to set their own standards for what kind of flight changes warranted a refund. As a result, refund policies differed from airline to airline, which made it difficult for passengers to know or assert their refund rights. DOT also received complaints of some airlines revising and applying less consumer-friendly refund policies during spikes in flight cancellations and changes. 

Under the rule, passengers are entitled to a refund for:

• Canceled or significantly changed flights: Passengers will be entitled to a refund if their flight is canceled or significantly changed, and they do not accept alternative transportation or travel credits offered. For the first time, the rule defines “significant change.” Significant changes to a flight include departure or arrival times that are more than 3 hours domestically and 6 hours internationally; departures or arrivals from a different airport; increases in the number of connections; instances where passengers are downgraded to a lower class of service; or connections at different airports or flights on different planes that are less accessible or accommodating to a person with a disability.  
• Significantly delayed baggage return: Passengers who file a mishandled baggage report will be entitled to a refund of their checked bag fee if it is not delivered within 12 hours of their domestic flight arriving at the gate, or 15-30 hours of their international flight arriving at the gate, depending on the length of the flight.  
• Extra services not provided: Passengers will be entitled to a refund for the fee they paid for an extra service — such as Wi-Fi, seat selection, or inflight entertainment — if an airline fails to provide this service.

DOT’s final rule also makes it simple and straightforward for passengers to receive the money they are owed. Without this rule, consumers have to navigate a patchwork of cumbersome processes to request and receive a refund — searching through airline websites to figure out how make the request, filling out extra “digital paperwork,” or at times waiting for hours on the phone. In addition, passengers would receive a travel credit or voucher by default from some airlines instead of getting their money back, so they could not use their refund to rebook on another airline when their flight was changed or cancelled without navigating a cumbersome request process.  

The final rule improves the passenger experience by requiring refunds to be:

• Automatic: Airlines must automatically issue refunds without passengers having to explicitly request them or jump through hoops.   
• Prompt: Airlines and ticket agents must issue refunds within seven business days of refunds becoming due for credit card purchases and 20 calendar days for other payment methods.  
• Cash or original form of payment: Airlines and ticket agents must provide refunds in cash or whatever original payment method the individual used to make the purchase, such as credit card or airline miles. Airlines may not substitute vouchers, travel credits, or other forms of compensation unless the passenger affirmatively chooses to accept alternative compensation.    
• Full amount: Airlines and ticket agents must provide full refunds of the ticket purchase price, minus the value of any portion of transportation already used. The refunds must include all government-imposed taxes and fees and airline-imposed fees, regardless of whether the taxes or fees are refundable to airlines.

The final rule also requires airlines to provide prompt notifications to consumers affected by a cancelled or significantly changed flight of their right to a refund of the ticket and extra service fees, as well as any related policies.

In addition, in instances where consumers are restricted by a government or advised by a medical professional not to travel to, from, or within the United States due to a serious communicable disease, the final rule requires that airlines must provide travel credits or vouchers. Consumers may be required to provide documentary evidence to support their request. Travel vouchers or credits provided by airlines must be transferrable and valid for at least five years from the date of issuance.

The Department received a significant number of complaints against airlines and ticket agents for refusing to provide a refund or for delaying processing of refunds during and after the COVID-19 pandemic. At the height of the pandemic in 2020, refund complaints peaked at 87 percent of all air travel service complaints received by DOT. Refund problems continue to make up a substantial share of the complaints that DOT receives.

DOT’s Historic Record of Consumer Protection Under the Biden-Harris Administration

Under the Biden-Harris Administration and Secretary Buttigieg, DOT has advanced the largest expansion of airline passenger rights, issued the biggest fines against airlines for failing consumers, and returned more money to passengers in refunds and reimbursements than ever before in the Department’s history.

• Thanks to pressure from Secretary Buttigieg and DOT’s flightrights.gov dashboard, all 10 major U.S. airlines guarantee free rebooking and meals, and nine guarantee hotel accommodations when an airline issue causes a significant delay or cancellation. These are new commitments the airlines added to their customer service plans that DOT can legally ensure they adhere to and are displayed on flightrights.gov .  
• Since President Biden took office, DOT has helped return more than $3 billion in refunds and reimbursements owed to airline passengers – including over $600 million to passengers affected by the Southwest Airlines holiday meltdown in 2022.   
• Under Secretary Buttigieg, DOT has issued over $164 million in penalties against airlines for consumer protection violations. Between 1996 and 2020, DOT collectively issued less than $71 million in penalties against airlines for consumer protection violations.  
• DOT recently launched a new partnership with a bipartisan group of state attorneys general to fast-track the review of consumer complaints, hold airlines accountable, and protect the rights of the traveling public.  
• In 2023, the flight cancellation rate in the U.S. was a record low at under 1.2% — the lowest rate of flight cancellations in over 10 years despite a record amount of air travel.  
• DOT is undertaking its first ever industry-wide review of airline privacy practices and its first review of airline loyalty programs.

In addition to finalizing the rules to require automatic refunds and protect against surprise fees, DOT is also pursuing rulemakings that would:

• Propose to ban family seating junk fees and guarantee that parents can sit with their children for no extra charge when they fly. Before President Biden and Secretary Buttigieg pressed airlines last year, no airline committed to guaranteeing fee-free family seating. Now, four airlines guarantee fee-free family seating, and the Department is working on its family seating junk fee ban proposal.  
• Propose to make passenger compensation and amenities mandatory so that travelers are taken care of when airlines cause flight delays or cancellations.   
• Expand the rights for passengers who use wheelchairs and ensure that they can travel safely and with dignity . The comment period on this proposed rule closes on May 13, 2024.

The final rule on refunds can be found at https://www.transportation.gov/airconsumer/latest-news and at regulations.gov , docket number DOT-OST-2022-0089. There are different implementation periods in this final rule ranging from six months for airlines to provide automatic refunds when owed to 12 months for airlines to provide transferable travel vouchers or credits when consumers are unable to travel for reasons related to a serious communicable disease. 

Information about airline passenger rights, as well as DOT’s rules, guidance and orders, can be found at   https://www.transportation.gov/airconsumer .

Help | Advanced Search

Computer Science > Artificial Intelligence

Title: distilling privileged information for dubins traveling salesman problems with neighborhoods.

Abstract: This paper presents a novel learning approach for Dubins Traveling Salesman Problems(DTSP) with Neighborhood (DTSPN) to quickly produce a tour of a non-holonomic vehicle passing through neighborhoods of given task points. The method involves two learning phases: initially, a model-free reinforcement learning approach leverages privileged information to distill knowledge from expert trajectories generated by the LinKernighan heuristic (LKH) algorithm. Subsequently, a supervised learning phase trains an adaptation network to solve problems independently of privileged information. Before the first learning phase, a parameter initialization technique using the demonstration data was also devised to enhance training efficiency. The proposed learning method produces a solution about 50 times faster than LKH and substantially outperforms other imitation learning and RL with demonstration schemes, most of which fail to sense all the task points.

Submission history

Access paper:.

• HTML (experimental)
• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

Science | April 26, 2024

Ten Amazing Facts About Tornadoes, Explained

To prepare you for the movie “Twisters,” we’ve compiled some jaw-dropping details about the powerful phenomenon

Catherine Duncan

Staff Contributor

As looming thunderstorm clouds spit out baseball-sized hail and torrential rain, a narrow whirlwind of air stretches its way toward the ground, signaling the arrival of one of nature’s most violent phenomena: a tornado.

Also known as twisters, these violent cyclones can reach wind speeds of 300 miles per hour and blaze a path of destruction that can last from mere seconds to several hours . While most people flee or take shelter at the sight of these alarming conditions, others dive headfirst into them. Storm chasers, people who get dangerously close to extreme weather events, sometimes for scientific research, jump at the chance to pursue the ever-unpredictable tornado.

The 1996 disaster classic Twister follows a group of these daring storm chasers, a university professor and her team of students who rush toward an outbreak of severe twisters sweeping Oklahoma. Their goal: deploy a revolutionary weather alert device, aptly named “Dorothy,” within the heart of multiple tornado systems to track and possibly tame the forces of nature. After a series of disastrous attempts to deploy their invention within multiple cyclones, a final, massive tornado rips through the area. In the nick of time, the team successfully sets up their device in the twister’s center and collects crucial data.

The highly awaited sequel Twisters sees the continuation of this research nearly two decades later, with a new generation of storm chasers and technology. The story’s hesitant protagonist Kate Cooper, played by Daisy Edgar-Jones, joins forces with adrenaline junkie Tyler Owens, played by Glen Powell, as twin twisters ravage the plains of central Oklahoma. The pair races against a rival team and devastating weather conditions to conduct groundbreaking analysis. Though the film is fictionalized, its overarching circumstances—the treacherous nature of twisters and the difficulty of predicting their arrival—ring true.

In anticipation of the July 19 release of Twisters , we contacted three scientists to unravel some of the secrets wrapped within these catastrophic cyclones. Here are a few of the coolest finds we uncovered.

Supercell thunderstorms are responsible for creating tornadoes

Tornadoes are born within supercell thunderstorms , an anvil-shaped cloud with a rotating updraft called a mesocyclone. As an extremely rare weather event, only one in thousands of storms yields a supercell thunderstorm. One in five or six supercells , though, produces a tornado.

“To get a thunderstorm, we have to have an unstable atmosphere, and generally, for a tornado, we need the thunderstorms to rotate,” says William Gallus, a meteorologist at Iowa State University. “That happens if we have wind shear, which means that the wind speed and wind directions are changing as you go up.”

Warm air rises, cold air falls, rough winds whip within the storm system, and an updraft occurs. If this rotating updraft descends toward the ground, lowering itself below the storm, a tornado can emerge from the chaos.

The tornado forms as the mesocyclone accelerates from the bottom up—and the feature intensifies its rotation, in a way similar to an ice skater who pulls her arms into her body to spin faster, says Jana Houser , a supercell thunderstorm and tornado radar analysis expert at Ohio State University.

The strongest winds of the tornado are closest to the ground

In the atmosphere, the winds get stronger the higher up you go. Tornadoes reverse these conditions, with their strongest winds appearing at the lowest points. This powerful rotation starts at the ground and then floats its way upward to converge into the visible funnel cloud.

“This process happens very quickly,” says Houser, who, alongside her team and National Geographic cameras, captured the very tornadoes set to appear as background footage in the upcoming film Twisters . “In under a minute, you can go from a weak rotation to, all of a sudden, a full tornado.”

According to Gallus, computer models of tornadoes have shown that the strongest winds could lie just 15 feet above the ground—their most brutal region lining up with the height of homes and buildings.

“That’s pretty unfortunate for all of us who live on Earth, because that means that in a tornado, unlike any other weather system, the very worst winds are impacting buildings, people and trees down near the ground,” says Gallus.

Tornadoes can form anywhere, anytime

Most tornadoes are formed in the Great Plains of the United States, in an area deemed “Tornado Alley.” Flat terrain combined with unstable conditions—warm, moist air from the Gulf of Mexico collides with dry winds drifting in from the Rocky Mountains—provides the ideal breeding ground for twisters to spawn. But tornadoes can happen almost anywhere. They have been reported in all 50 states and all continents except Antarctica, and they’ve struck major urban areas , such as Dallas, Miami and Minneapolis.

But cyclones don’t follow any sort of pattern or path, contrary to popular misconceptions. “It doesn’t matter if you’re in a downtown part of the city, in a hilly area or even a mountainous area,” says Houser. She adds that some terrain may reduce or increase the probability of tornadoes, but complete protection from the twisters can’t be guaranteed.

Similarly, while peak tornado season ranges from May to July depending on location, tornadoes can hit at any month and any time, both day and night.

Tornadoes have uniquely powerful upward motion

In most weather phenomena, the most aggressive winds blow horizontally, directing their potency outward toward the north, south, east and west, rather than upward and downward. Tornadoes defy these expectations. Things resting in the tornado’s path—the roofs of homes, cars, animals—can be suddenly whisked straight up and into the whirl of debris, victim to the sheer power of the tornado’s upward winds. According to Gallus, the strength of a tornado’s upward motion is comparable to the speed at which it moves along terrain, with 100- or 200-mile-an-hour winds shooting up toward the sky.

“That’s why the damage that a tornado does to buildings is very different than if you have the exact same mile-per-hour wind from just a thunderstorm,” says Gallus. “It’s also why you hear these stories of people or things getting picked up and seeming to levitate or fly up into the air—it’s because the tornado has such strong upward motion.”

The air pressure inside a tornado can cause just as much damage as the wind itself

When visiting the site of a Missouri hospital ravaged by a tornado, Gallus recalls, a nurse he spoke with had to tilt her head a certain direction to hear. Due to the intense air pressure change caused by the tornado, her eardrum ruptured. The air pressure in the middle of a tornado can drop suddenly and strongly, as if you were riding on a plane flying up into the air extremely fast. Many people near tornadoes have reported their ears “popping” during the phenomenon. “That change in pressure is almost like nature’s way of giving you a very last warning by having your head experience this strange rapid adjustment and popping going on in your head,” says Gallus.

The change in air pressure can also create an additional force on buildings that, along with the strong winds, can intensify and quicken their destruction.

Terrain can change a tornado’s behavior

Researchers have a difficult time predicting when a tornado will form—and where it will go. Changing winds and differing terrain can make it hard for meteorologists chart the exact path of a twister.

“Tornadoes are incredibly susceptible to very small nuances in the land cover, in the environment, in the storm itself, and it’s very difficult, I would say impossible, to account for every single factor that could possibly go into changing what a tornado is doing,” says Houser. “They defy generalization.”

While predicating a storm is hard, meteorologists say that some features of terrain may enhance the conditions needed for a twister to form. For example, sprawling urban areas can affect thunderstorms, which, in turn, can affect tornadoes. Since cities have more precipitation on their downwind side because of the way water systems interact with urban structures, they produce more rain and more hail, and can be warmer, helping set up an environment that’s more likely for a tornado to form.

“Sometimes urban areas are warmer than rural areas due to the urban heat island. What happens if a tornado goes over a warmer city?” says Jason Naylor, an atmospheric scientist at the University of Louisville. “It looks like the urban heat island could potentially enhance the low-level updrafts in the storm and may help instigate tornadoes in a theoretical way.”

Tornadoes usually rotate counterclockwise, but they can switch directions

In the Northern Hemisphere, about 98 percent of tornadoes spin counterclockwise , which meteorologists label as cyclonical. However, a clockwise-swirling tornado is not out of the question—just much less common.

The counterclockwise motion of most tornadoes has long been attributed to the Coriolis effect, the force caused by the Earth’s rotation. But, according to Houser, this is merely a myth. Tornadoes exist on “too small a space scale and time scale for the Coriolis force to affect it,” she says. Rather, the counterclockwise motion results from how vertical winds change in speed and height within the storm.

Meteorologists call clockwise tornadoes anti-cyclonic. “You get an anti-cyclonic tornado when you have a very strong surge of air within the storm,” says Houser.

Storms can produce more than one tornado at a time

Twisters sees two groups of storm chasers unite as two different tornadoes converge over a small town in central Ohio. This event isn’t just movie magic: The same storm system can really eject multiple tornadoes at once. As winds change, the storm itself can begin to form a new tornado in a slightly different location from the original tornado—with the fledgling rotating updraft gaining power as the other twister slowly dies down. Or, if the original tornado is particularly violent , the level of agitation can churn out smaller whirlwinds that extend toward the ground.

And Houser says that other freak circumstances, such as extremely strong rotation along the edges of a storm, can also produce multiple tornadoes. A clockwise and counterclockwise tornado can even appear in the same storm system.

Tornadoes themselves can’t be forecast—only the conditions that produce them can

The 1996 film Twister and its 2024 companion Twisters center around the same key issue: the frustrating impossibility of forecasting tornadoes. “We don’t even really try to forecast exactly when and where a tornado would hit, because we simply cannot do that ahead of time,” says Gallus.

Warnings for tornadoes are only issued when a twister is already forming and has been sighted—or indicated by weather radar—and the alerts cover an area that may be impacted.

Scientists are able to predict, however, the conditions favorable for supporting thunderstorms that spin and would be more likely to produce tornadoes. Up to a couple of hours ahead of time, when increased weather severity is detected, local television and radio news stations issue a tornado watch.

But a tornado’s intensity can’t be determined until after its wake. Scientists determine a tornado’s level of destruction by using the Enhanced Fujita Scale . The scale assesses the damage a tornado does to trees, buildings and homes. Scientists then use that information to calculate its probable wind speed. The rating system ranges from F0, the weakest cyclone, to F5, a vicious, deadly tornado, which a character in Twister deems the “finger of God.”

Climate change is affecting tornadoes

Tornado Alley is moving eastward . In the past decade, twisters have been inching their way into the Midwest and hitting states such as Missouri in record-breaking severity . Meteorologists attribute this shift to climate change.

“Now, with climate change, places that were normally too cold in the winter are finding themselves with days warm enough that you’re starting to see tornadoes at times of year, parts of the country, where they didn’t used to happen,” says Gallus.

This is caused by climate change’s impact on weather. Gallus says that climate change is making conditions warmer and more humid near the ground, which is increasing the level of instability that leads to stronger, tornado-producing storms.

According to Gallus, we may see more days that meteorologists call tornado outbreak days, where five to ten tornadoes crop up. But climate change could also decrease the frequency of days where one or two tornadoes crop up. Essentially, the number of tornadoes could be concentrated on fewer days.

“We can’t say that tornadoes are going to become stronger. We can’t say that we’re going to have less,” says Gallus. “But what we do know is, because of how the temperature is changing, we are going to start finding them in weird times of the year and places where it always used to be too cold to have a tornado.”

Get the latest Science stories in your inbox.

Catherine Duncan | READ MORE

Catherine Duncan is an intern with  Smithsonian magazine.

• Travel Insurance

The journalists on the editorial team at Forbes Advisor Australia base their research and opinions on objective, independent information-gathering.

When covering investment and personal finance stories, we aim to inform our readers rather than recommend specific financial product or asset classes. While we may highlight certain positives of a financial product or asset class, there is no guarantee that readers will benefit from the product or investment approach and may, in fact, make a loss if they acquire the product or adopt the approach.

To the extent any recommendations or statements of opinion or fact made in a story may constitute financial advice, they constitute general information and not personal financial advice in any form. As such, any recommendations or statements do not take into account the financial circumstances, investment objectives, tax implications, or any specific requirements of readers.

Readers of our stories should not act on any recommendation without first taking appropriate steps to verify the information in the stories consulting their independent financial adviser in order to ascertain whether the recommendation (if any) is appropriate, having regard to their investment objectives, financial situation and particular needs. Providing access to our stories should not be construed as investment advice or a solicitation to buy or sell any security or product, or to engage in or refrain from engaging in any transaction by Forbes Advisor Australia. In comparing various financial products and services, we are unable to compare every provider in the market so our rankings do not constitute a comprehensive review of a particular sector. While we do go to great lengths to ensure our ranking criteria matches the concerns of consumers, we cannot guarantee that every relevant feature of a financial product will be reviewed. We make every effort to provide accurate and up-to-date information. However, Forbes Advisor Australia cannot guarantee the accuracy, completeness or timeliness of this website. Forbes Advisor Australia accepts no responsibility to update any person regarding any inaccuracy, omission or change in information in our stories or any other information made available to a person, nor any obligation to furnish the person with any further information.

Do Frequent Flyer Points Expire?

Updated: Apr 30, 2024, 1:15pm

Table of Contents

Frequent flyer expiry dates explained, bottom line, frequently asked questions (faqs).

Frequent flyer program members earn points from doing exactly that: flying frequently. Keen point earners may also invest in a frequent flyer credit card to increase their points balance with every purchase, or earn points via other means specified by their frequent flyer program.

Each program is different, and that includes whether or not your frequent flyer points have an expiration date.

This guide runs through the two primary frequent flyer memberships in Australia, Qantas and Virgin, followed by an overview of international airline programs and their frequent flyer expiry dates.

Qantas Frequent Flyer

Qantas Frequent Flyer is Australia’s largest frequent flyer membership, boasting 14.7 million members as of 2023. To join directly, you’ll be charged a joining fee of $99.50. However, there are many ways to avoid this fee, including by signing up to a Qantas Frequent Flyer Credit Card .

To keep your Qantas Frequent Flyer points active, you’ll need to earn or use your points at least once every 18 months. This 18-month period starts from the date of your last activity on your membership: for example, if the last time you had earned Qantas Points was from an eligible flight, your last date of activity would be when the flight was taken.

Featured Partners

Fast Cover Travel Insurance

On Fast Cover’s Secure Website

Medical cover

Unlimited, 24/7 Emergency Assistance

Cancellations

Unlimited, (Trip Disruption $50,000)

Key Features

25-Day Cooling Off Period, Australian Based Call Centre, 4.6 Star Product Review Rating

Cover-More Travel Insurance

On Cover-more’s secure website

Unlimited, with a $2000 limit to dental

Yes, amount chosen by customer

Southern Cross Travel Insurance

Medical Cover

Including medical treatment, doctors’ visits, prescribed medication, specialist treatment & medical transport costs

$2,500 with option to increase to unlimited

Other eligible activity includes earning or using Qantas Points with Qantas’ program partners; redeeming Qantas Points for flights; and shopping at the Qantas Points store.It does not include transferring points to or from a family member’s account, or the transfer of points from Qantas Business Rewards.

Related: What The Qantas Frequent Flyer Program Changes Mean For You

Virgin Velocity

The loyalty program of Virgin Australia is known as Velocity Frequent Flyer, with a membership base of 11 million members as of 2022. Unlike the Qantas program, membership to Velocity is free, and you can begin earning points immediately.

Virgin Velocity points expire after 24 months of account inactivity; as is the case with Qantas, this means not spending or earning any points within this period. However, you can see, Virgin Velocity gives its members an extra six months before expiry compared to Qantas Frequent Flyer.

“Essentially, every time you earn, redeem or buy points, you’re renewing your points for another two years,” the website states.

This means if you had a Velocity Rewards Credit Card that you used regularly, you’d never have to worry about your balance expiring even if you weren’t flying—as every transaction on your credit card would earn you points.

Note that receiving points via family pool transfers won’t count as account activity.

Related: Our Pick Of The Best Frequent Flyer Credit Cards

American Airlines AAdvantage

Looking at overseas frequent flyer programs with major airlines that serve Australia, we’ll start alphabetically: American Airlines. This membership program is known as AAdvantage, with points known as ‘AAdvantage miles’. It’s free to join, and can be worthwhile for Australians considering AAdvantage miles can be redeemed on Qantas flights.

American Airlines AAdvantage miles expire after 24 months of inactivity; any type of qualifying activity on your account will restart this period.

It’s worth noting that customers under the age of 21 are not subject to this expiration period; however, as soon as the customer turns 21 years old, the 24-month policy will begin—even if the AAdvantage miles were earned prior.

British Airways Executive Club

For a frequent flyer membership with British Airways, you’ll need to join their Executive Club—which is free.

The loyalty currency is known as ‘Avios’, and is the same across partner airlines Qatar, Iberia and Aer Lingus. This means you can combine Avios from an Iberia Plus, AerClub or Qatar Airways Privilege Club account and choose how (or where) you spend them.

Unused Avios will expire after 36 months of inactivity; so, as long as you collect, spend, buy or share at least one Avios every 36 months, your frequent flyer points will remain.

Cathay Pacific Asia Miles

In August 2022, Marco Polo Club and Asia Miles combined into one rewards program: Cathay Pacific’s Asia Miles. Pre-existing members were automatically enrolled in the new program, while new members can sign up via Cathay Pacific for free.

Asia Miles will remain active as long as you earn or redeem on your account at least once every 18 months.

Like other frequent flyer programs, it’s not only flying that can earn you points. Cathay Pacific’s website states it has more than 800 partners worldwide that you can spend with to earn Asia Miles, across shopping, credit cards, dining, hotels and more.

SkyMiles is Delta’s loyalty program, which is free to join and, unusually for a frequent flyer program, does not have an expiry date. Your miles will remain in your account as long as it is open.

As Delta is US-based, it may not be as enticing to join as membership programs closer to home are. Yet, with more than 20 airline partners across the globe—including the nearby China Airlines and Vietnam Airlines—it can still serve Australians looking to gain miles without the fuss of regularly earning or spending points.

Australians can also earn SkyMiles on Airbnb stays worldwide (when booking through the dedicated Delta-Airbnb site ) and choose SkyMiles as the reward of choice when staying in global hotel chains such as Marriott Bonvoy or World of Hyatt.

Emirates Skywards

Emirates Skywards is yet another free membership program, allowing frequent travelers to earn points—Skywards—through travel and more.

The expiry date for Emirates Skywards isn’t as clear-cut as other programs, however. Instead, Skywards expire at the end of your birthday month, three years after they were earned.

For example, if your last flight was in January 2023 and your birthday is September 10, your Skywards would expire on September 30, 2026.

You can’t extend the validity of your Skywards through account activity, either. Instead, you have the option to pay to extend them an additional 12 months from the aforementioned expiry date.

Etihad Guest

Being a member of the Etihad Guest loyalty program is free, and allows you to earn Etihad Airways Guest Miles.

Activities that allow you to earn these miles include earning, spending or buying them. Inactivity in your account will see your Etihad Guest Miles expire after 18 months.

To avoid this, you need to make a transaction; the first qualifying activity in a month resets the expiry date again.

For Etihad Platinum Guests, there is no expiration of miles as long as they maintain their Platinum status.

Singapore Airlines KrisFlyer

Singapore Airlines KrisFlyer is another global membership that allows Australian travellers to earn points both locally and abroad, and is also free to join.

After earning KrisFlyer Miles, members have three years to use them—regardless of whether or not there is activity within the account..

You can extend this expiration date for six months for a fee; however, Singapore Airlines notes there is no way to get KrisFlyer Miles back if they have expired.

Members of Singapore Airline’s PPS Club are exempt from the expiration rules.

United Airlines MileagePlus

Like Delta’s SkyMiles, United Airlines’ MileagePlus is a program whose miles never expire.

It’s free to join, and United is part of Star Alliance, the biggest airline alliance in the world, which includes our nearby carriers of Air New Zealand, Singapore Airlines, and Thai Airways.

Outside of Star Alliance, MileagePlus members can also earn (and redeem) miles when flying with Virgin Australia.

As you can see from our guide, all frequent flyer programs vary with their conditions on whether or not your frequent flyer points will expire. This includes how you can extend your expiration date, and how long the validity period lasts for.

Remember to read the terms and conditions of your frequent flyer membership carefully so you understand how long you have to spend your points.

Will my frequent flyer points expire if I don’t fly?

Not necessarily While the expiration of frequent flyer points is dependent on the individual frequent flyer program, it is common that points will remain valid as long as there’s activity oni your account. This doesn’t just mean flying: you can also earn, spend, and buy points through other means.

Are frequent flyer points and airline miles the same?

In short, yes. ‘Frequent flyer points’ is commonly used in Australia, whereas many overseas programs will use the term ‘miles’ as their reward currency. Some have their own names entirely, like British Airways, who use ‘Avios’.

How can I earn frequent flyer points?

Frequent flyer points can be earned through a range of means. This includes flying with the airline that your program is associated with (or an airline partner), having a credit card that earns frequent flyer points , spending points at a frequent flyer rewards store, and even buying points to top up your balance.

• Best Comprehensive Travel Insurance
• Best Seniors Travel Insurance
• Best Domestic Travel Insurance
• Best Cruise Travel Insurance
• Best Family Travel Insurance
• Travel Insurance Cost
• Pregnancy Travel Insurance Guide
• Travel Insurance Cancellation Cover
• Travel Insurance For Bali
• Travel Insurance For Fiji
• Travel Insurance For The USA
• Travel Insurance For Thailand
• Travel Insurance For New Zealand
• Travel Insurance For Japan
• Travel Insurance For Europe
• Travel Insurance For Singapore
• Travel Insurance For Indonesia
• Travel Insurance For Vietnam
• Travel Insurance For Canada
• Travel Insurance For South Africa
• Cover-More Travel Insurance Review
• Fast Cover Travel Insurance Review
• Travel Insurance Saver Review
• Allianz Comprehensive Travel Insurance Review
• 1Cover Comprehensive Travel Insurance Review
• Australia Post Comprehensive Travel Insurance Review
• Tick Travel Insurance Review

More from  

Travel insurance for canada: what you need to know before you go, travel insurance for south africa: everything you need to know, travel insurance for vietnam: everything you need to know, tick travel insurance top cover review: features, pros and cons, was discovery travel insurance review: features, pros and cons, fast cover comprehensive travel insurance review: pros and cons.

Sophie Venz is an experienced editor and features reporter, and has previously worked in the small business and start-up reporting space. Previously the Associate Editor of SmartCompany, Sophie has worked closely with finance experts and columnists around Australia and internationally.