Valery's Travelling Salesman Problem

Forum|Forum|15 years ago
August 29, 2010
4 replies
6332 views

Apologies for starting a new thread, but I couldn't see how to upload a Mathcad file near Valery's video.

The attached file is rather simplistic and very inefficient, but it would be interesting to see how it compares with Valery's method. There is plenty of scope for improving the efficiency, including, possibly, incorporating a Metropolis-style algorithm (in which there is a small probability of accepting a worsening rather than an improvement from time to time).

I've saved the file in M11 format, but I've not tested it in M11.

Alan

Note: I've edited this - the current attachment calculates the total distance correctly, which the original didn't!

Also made it somewhat faster.

1_Luxembourg2-mcd.zip

Other

J

jeanGiraud

1-Visitor

Thanks Alan,

It computes in reasonable time [5 ... 10 mn ?] Mathcad 11.

Steven Finch [Mathsoft] had a work sheet,,, in lost worlds !

Jean

J

jeanGiraud

1-Visitor

The traveling salesman was included in Mathcad numerical recipes pack [version 5 /6 ?]. Still advertised to Mathsoft but it ends to a "girls zooooooo"

V

ValeryOchkov

24-Ruby IV

>The traveling salesman was included in Mathcad numerical recipes pack

Yes - see the function anneal here

V

ValeryOchkov

24-Ruby IV

Thanks, Alan, for the interest on my task!

Bur sorry - the optimal tour in Luxemburg is here http://www.tsp.gatech.edu/world/lutour.html

A

AlanStevens

Author

19-Tanzanite

"...Bur sorry - the optimal tour in Luxemburg is here http://www.tsp.gatech.edu/world/lutour.html"

Yes! I've increased the speed of the program considerably from the one I posted earlier, but the best it finds in a reasonable time is a distance of about 25000 as against the actual best of 11000+. Clearly the logic would need to be modified (completely altered!) to improve further. I don't intend to take it any further myself, there are lots of programs out there that do this (mainly Matlab and Maple it seems; not Mathcad unfortunately!). It was an interesting Sunday afternoon excercise though!

Alan

V

ValeryOchkov

24-Ruby IV

My hobby (beiside Mathcad of couse) is unordinary clocks and watchs.

An unordinary clock for the land of clocks & travelers (Switzerland) - see the video in attach!