Solving Travelling Salesman Problem(TSP) using Excel Solver
Vložit
- čas přidán 2. 05. 2015
- Given a distance matrix, the optimal path for TSP is found using evolutionary solver module available with Microsoft Excel.
Notebook of an Industrial Engineer- nboaie.blogspot.in/
Video made using Screencast-o-Matic free version.
No useless explanations, straight to the point! Great work!
Thank you so much Jeffy Joseph. I am sure you have made the lives of many of us a lot easier by this simple TSP algorithm. Cheers!
It's a long time that I try to use excel to solve TSP. You give me for the easy step to use. thank you very much.
Hey Jeffy, nice video. I found it interesting that you showed how to solve the TSP using the evolutionary algorithm on Solver. I`ve always solved it as an exact method, and I found it very simple to apply with GA. Thanks for this!
Thank you for sharing this. It's clear and straight to the point!
Thanks very useful. Just a minor tweak for my start point and it works well. One thing I noted if re-running it the constraints have to be edited to include 'dif' again as that was lost.
You save my life with this video... many thanks!!
Dear Jeffy, Thank you so much for your help! this video is a life saver for me
!!!!If you have a issue read this!!!! Set your starting point = to the final point. In this example the cell I11 should read; =B11. What you will see initially is a 1 after deselecting the I11
Think you're right!
Literally life-changer information!!!!!!! Thanks a lot
Interesting and Informative! Thank you Jeffy!
YOOO Mr Joseph, shout out to youuuuuuu. Thanks to you, I can get my Assignment done.
HELLO MR SILVAM
Does it work the INDEX function if I have instead 1 to 7, a reference for each city or even a letter? it returns me a REF result.
What if I have a triangular inequality in my matrix with fixed starting and ending point
Very good, very simple, thank you.
Thank you for making a smart video! I did my task of TSP using this video!
I am glad it was helpful!
Thanks! I am going to use this for actually planning my trip, like the salesman. I'm on a holiday in Australia, and wanted to find out the shortest, (possibly cheapest), route between destinations.
That's HILARIOUS lol you're doing this cause you need it, and I'm doing it cause I'm being forced to do it by my lecturer.
I'm looking to find an exact solution of the travelling salesman problem for 9 cities but I am not the tech savvy type and my interest in the subject was recreational. Is there a user friendly tsp solver online that you can recommend?
SO SIMPLE. I LOVE YOU . YOU SAVED MY ASSIGNMENT.
pro tip : you can watch movies at Kaldrostream. Been using them for watching all kinds of movies recently.
@Cruz Jayson Definitely, I've been watching on kaldroStream for since december myself :)
Which method is used in this video to solve TSP? I tried the same problem using zero- one programming in excel solver (simplex algorithm) and it gives the same result but involves many constraints..
hello, it's really helpful but how can i do, if i want to know the best combination between 1,3,and 4 for example not all of them ??? i really need to know how to do that please !!! and thank you very much
Does someone know how is the algorithm behind working and how to put it in mathematical terms?
It was really helful ...Thanks a lot.
what a nice video, thanks Jeffy
Gracias, me sirvió mucho!!!
thank you brother, the method is well explained, can you please show us how to solve maximum flow (ford fulkerson diagram on solver ) and thanks alot for your help
Thanks a ton for sharing this!
Can I solve this problem with the method you presented? "I have a source of products and 5 destinations, each trailer can hold up to 8 units and I need to satisfy demand". Would this be the model I'm looking for?
Should we add the distance from the last node to initial node to the objective?
buenos dias, una pregunta si me puede colaborar, numero de variables que se pueden resolver con solver, gracias
Thank you, your video help me. Bless u
Thanks for uploading this ✨
hi Joseph i need to go back to city 1 ? how ah ?
Good video Jeffy, thank you.
What if I need to fix the starting to to be number 1? What are more conditions I need to add there
Thanks by share the solution, I suggest in the solver add the constraint I11=B11
hi Joseph how to go back to City 1?
So useful and simple, But how can i set a starting point, supposing that 1 is the centre of distrubution where the trucks or vehicles are supposed to come back again?
Hi Joseph, Can i also use simplex for tsp using solver.
Do you know how to save solver model in LibreOffice exporting to Excel?
Exactly what I'm looking for! But, since I'm hearing impaired, I find it impossible to follow because of the bad sound quality (background noise, etc). Any chance of re-recording the sound track, or can I find the 'recipe' in writing somewhere??
Thanks, Bill.
+WilliamBlaky Sorry about the sound quality. No, I dont have any 'recipe'.. :) But i will try to re-record as soon as possible
Very nice, thank you!
Please help - using excel 2007 and did not have a choice "Diff " in "add contraint" - how else can I solve this?
Thank you for help.
Most of these options are available from 2010 only. If you dont have access to 2010 then you can try installing OpenSolver. Its less that 5 MB.
You are the best
how to make a distance table with excel?? Please help me
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 3 or 4 cities from this 7 cities ?
why is the evolutionary solver preferredm in this problem
Thank you for this video. Is the evolutionary solver based on genetic algorithm (GA)?
yes, excel solver window says so
Thank you for the TSP solution! I have a question. Let's say that I wanted optimal routes for 2 different vehicles from a large set of locations (20+), could I do that using this method? This method works really well, but only if you have a single vehicle. I need the program to find optimal solutions if the set of data were to split into two routes (the program decides how to split the data).
+Akshay Sutrave Thats vehicle routing problem. Ofcourse it could be done with coding. But if you want to do with just excel functions and solver, then it could be a little tricky. Because the number of locations to be covered by a particular vehicle is not fixed. Hence the dif option cannot be used directly. Slightly tricky, but doable. As for the accuracy, you may not obtain an optimal solution but one that is very close. I would definitely give it a try.
How would I be able to program excel to plan two optimal routes for me? What constraints should I add? I'm guessing that is the tricky part.
+Akshay Sutrave It wasn't as tricky as I thought. It took only a couple of minutes to formulate it. You just want to minimize the distance with multiple vehicles, right? Thats not VRP but mTSP. Sorry for misinterpreting the problem. I will try to record a video and post it.
+jeffy joseph Thank you so much! It will really help me in the analysis I want to do. I attempted to formulate it but it would not run correctly the way I was doing it. Let me know when you upload the video, I really appreciate the help!
+Akshay Sutrave This video has really helped me on my project, and I want to give you credit for helping me. If you can email me that would be great!
very nice indeed..i am looking for shortest path problem applying genetic Algorithm in Matlab..if you or anyone knows any good source or tutorial video about it..kindly share
I'm using excel 2007.There's no diff option.so i downloaded open solver but there this problem can't be solved.What can i do?
hi that was a worthy information u have shown...could you also please solve the same in MATLAB?
Aravind kamalesh I will try..
What if the starting point and ending point are two different locations and fixed?
Looking for a quick reply.
That means it not a travelling salesman problem. It has to be a Hamiltonian circuit for it to be a travelling salesman problem. What you’re looking for is not called a travelling salesman problem.
hey i think something went wrong, the first city should be city 1 right, but after you solve it then it became city 6 ?? please explain??
Its giving a circular route starting at 6 and ending at six. If you start at one and follow the sequence generated, you will come back to 1.
thanks so much :)
How du you solve this if the start and end location has to be the same? Solver will not let you do this..
The one I solve in this video starts and ends at the same location. See @4:03
Hello Mr. Jeffy Joseph. First of all I want to thank you for give this solving method of the TSP to the internet. Secondly, i want to ask you a question: does this method still work in matrixes where the upper triangle is not exactly like the oppostite of the triangle at the bottom.
+Wil Ospino yes it will work for both symmetric and asymmetric matrices
jeffy joseph Thanks a lot, this is really useful for me. This is one of the topics of my Grade Project so I can get my degree as Engineer.
how to find which route has the salesperson followed?
Aravind kamalesh The 11th row in the video gives the route followed.
Can you tell me how did you add "All different " in the constraints , cause i don't have it ? thank you
Are you using excel 2010 or above? The older versions have a different solver with lesser number of features. If you are using 2007 try installing Opensolver (~5MB). It's an excel plugin/addon. If i remember correctly, it has alldifferent.
no no it's fine now i have the ''all different '' but my problem is that my project is to defin the minimize the time of cleaning between different production, i have a matrix with all the time needed to go from a formulation to another , and i need to give as an input for example just 4 formulation and the solver has to give me the which formulation should start first, second ... to have the min time of cleaning , and it's working like in your video but i don't want to choose the 7 cities for example just 4 or 3 ... Thank you so much for answering
Soukaina Sadqi Im willing to help you. you can email me. jeff_go12@yahoo.com
Right Now :p , i really need help thank you so much :)
weon eres la mejor wea que me ha pasado en la vida
Hi, what if I want:
1. to have a defined starting point that does not change?
2. to have a defined ending point that does not change?
How could I apply this solution for these 2 problems?
yes you could.
But how exactly?
In this example B11 to I11 represent the solution. For a fixed staring point add a constraint as B11={desired starting city}. If there is a desired ending city, we dont need I11. Delete I11 and add another constraint H11 = {desired ending city}. That should work.
could you please explain more sir ?
Can you send me details about this formula? I really need it please
thanks a lot
Thank you very much, however when applying it on my excel the excel solver does not change the last number after the decision variable.. in the video this is (I11) meaning that the total distance does not take into account the length from the last to the first. How is this solved?
Once again thank you for the video
+Tatyana Pellan i11 is equated to b11 so that when b11 changes i11 also changes. It does consider that distance from last to first. After solving, the last location is 7 and the distance from last to first appear as 19 in h12
Thanks!
I Wonder how to make this work if you only want to determine the most optimal route between 2 - 3 - 5- 7, in other terms not using the whole list of destinations in the matrix, just some of them. The solver seems to alway bring back values from 1 and up. In my example, the solution will give me a sequence from 1 to 4, instead of using the inputs 2 - 3 - 5 or 7 and rearranging them.
you need to redo the distance matrix to include only those cities/locations.
Yuan Li is right. Since you want only the route through some cities, whats the point in having the whole distance matrix.
I have the same problem , i want to have the whole matrix but every time choose different cities ! i have an undustriel problem which looks like this , how can i do it please ?
I think your problem is vehicle routing problem (where you want to find the shortest route between two points) and not TSP. I have uploaded an other video on mTSP. You could use the same methodology. Just add one more constraint like 'cities 2,4 and 5' should be covered by the same salesman'. It should work. Here is the link : czcams.com/video/owHq3Mbniqo/video.html
Thank you i will try that, i'm really bad in excel :( and i have to finish this project alone to have my degree and finish my internship, thank you so much
Bagaimana cara membuat tabel jarak menggunakan excel bro??
Thanks for the video, its really helpful. Do you think its also possible to solve a TSP with 79 cities with excel?
Thanks in advance!!
Sorry for the late reply. I haven't tried. But solver has a limit of around 100 variables. 79 should be ok. But again I dont know.
Thanks
Hi Joseph....i got furthur less using the same data and same technique as advised by you...126
whta if i have to start in 1 and to finish in 1 again?
change data to be used in solver = make them a constant
@@alexanderschmidt75 hi alex i dont understanf how to make them constant ?
Pls help I have a question which I have been using at work which is very time consuming.
Kindly help by providing mail or number
Thanks in Advance
Where is route? You got distance but how about path?
Hey, this is Pixy and I am looking for Corp on Wartune. If this is you, please check in with us. You are missed!! Got this name from Papa. Hope you are well!!
in your calculation you did not return to pint 1 which you started from.
Hallo, can I have your Email? I need your help to fix a Travelling Problem but for a Warehouse
Este we sabe cosas
thanks a lot but another time when you try to record a lesson plz record in quite a place, not in the street
I am getting 123
My answer is 126
The only mistake which i can see that for 1-1 should be defined high value
Hi Jeffy,
could you explain how to solve it, but with starting/ending point as 1?
I need to calculate route starting on point 1 and then going back to this city.
It didnt work
If you limit the solver to 20 seconds, it will only find the best one it was able to get to in 20 seconds. While it is _a_ solution, it is not guaranteed to be the best solution.
i dont think thats right