TSP - Travelling Salesman Problem - for 10 Cities - Problem definition and Solution in Excel
Vložit
- čas přidán 7. 06. 2022
- TSP - Travelling Salesman Problem - for 10 Cities - Problem definition and Solution in Excel #excel #exceltricks #exceltutorial #exceltutorialforbeginners #excelfunction #exceltips #excelsolver #solver #operationalresearch #operationsresearch
#linearprogrammingproblem #linearprogramming #linearprogrammingproblems
#lp #lpprogarmming #TSP #travellingsalesmanproblem
The Traveling Salesman Problem (TSP) is one of the most well-known optimization problems in computer science and mathematics. It is a problem that is designed to find the shortest possible route that visits a set of cities and returns to the starting city, where each city is visited only once. The problem is called the traveling salesman problem because it is based on a hypothetical scenario where a salesperson must travel to a set of cities and visit each one, returning to the starting city at the end.
The TSP is an NP-hard problem, meaning that there is no known algorithm that can solve the problem in a polynomial time. This makes the TSP an interesting problem to study as it represents a challenge for computer scientists and mathematicians. In its simplest form, the TSP can be defined as follows: Given a set of n cities and the distances between each city, find the shortest possible route that visits each city once and returns to the starting city.
One of the ways to solve the TSP is through brute force, where all possible routes are evaluated and the shortest one is selected. However, this method is only feasible for small numbers of cities, as the number of possible routes grows exponentially with the number of cities. For example, if there are 5 cities, there are 120 possible routes, while if there are 10 cities, there are 3,628,800 possible routes.
Another approach is to use heuristics and approximation algorithms. Heuristics are methods that do not guarantee an optimal solution, but instead provide a solution that is close to the optimal solution. Approximation algorithms are methods that provide a solution that is guaranteed to be within a certain distance from the optimal solution. One of the most well-known heuristics for the TSP is the nearest neighbor algorithm, which starts from the starting city and selects the nearest unvisited city at each step.
There are also various optimization algorithms that can be used to solve the TSP. Some of the most popular optimization algorithms include #geneticalgorithm genetic algorithms, simulated annealing, and ant colony optimization. These #algorithms are based on the idea of using a search process to find the optimal solution. For example, a genetic algorithm starts with a population of candidate solutions, and over time, the solutions evolve and become better. The simulated annealing algorithm is based on the idea of a physical process called annealing, where a material is heated and cooled to reach its optimal state. In the case of the TSP, the algorithm starts with a random solution and changes it over time to reach the optimal solution. The ant colony optimization algorithm is based on the behavior of ants and uses the idea of swarm intelligence to find the optimal solution.
In recent years, deep learning techniques have been applied to the TSP, and there has been some success in using neural networks to solve the problem. The idea behind these techniques is to use a neural network to learn a mapping from a given city configuration to a tour that visits all cities. The neural network is trained on a large number of examples, and the weights of the network are adjusted so that the network produces the desired output.
The TSP has numerous practical applications, including vehicle routing, scheduling, and logistics planning. For example, in vehicle routing, the TSP can be used to find the shortest route for a delivery truck that must visit a set of customers and return to its starting location. In scheduling, the TSP can be used to find the shortest schedule for a set of tasks that must be performed in a given order. In logistics planning, the TSP can be used to find the most efficient route for a set of deliveries that must be made.
In conclusion, the TSP is a well-known #optimization #optimisation #optimizationtechniques
Very nice problem. This can help me minimise kilometers travel in Indian vacation trips.
OMG THIS SAVED MEE THANK YOU SO MUCHHHH
Thanks, very helpful
Glad it was helpful!
This is a really useful video for me to understand the TSP model. I have a question, if the travleller don't return to the initial city, how to list the constaint?
Thank you for the video, it was very helpful. I have a further question if I may: how does my constrain look, when my data is not the distance but the time I need between the destinations, and I have a time limit for the travel? Maybe also: I have 4 salesman who have to travel all destinations together, each have the same start and same destination.. how would my constrain look this time?
How can I solve the same Problem but not for all cities ? how would be the solution if I need to show the distance just for 5 or 6 cities from this 10 cities ?
Can you pls elaborate little bit more of your problem model. Thanks.
@@allansam I am building a matrix for the warehouse, as this matrix calculates the best routes for order pickers, I tried your plan, but it is not effective if the orders are in different locations and not in order
Ok. What I understood is that you have a set of warehouses or locations that could be used partially to find the minimum travel for pickers. For that you may need to add another set of variables for cities yes or no as 1 or 0 and add them into your constraints so that the model or your algorithm will know the exact cities you want consider every time.
Hope this helps. Thanks. GB
Your solution is correct but you are wrong to calculate the distance between cities 1 and 3 is 12, not 0.
Let me go through where is the problem and reply. thanks.
Tutto sbagliato, Nella Città 3 non da una distanza e le formule sono state inserite male, inserire nella cella M12la seguente formula =M2
Le formule nella colonna N vanno riviste:
N2 =Index(DistanceBetweenCities,M2,M3) .... N11=Index(DistanceBetweenCities,M11,M12) 🤔