2
$\begingroup$

I'm trying to write my own code to find the shortest route but I'm lost on how or where to start. Does anyone have any idea how the FindShortestTour function works? What type of algorithm or structure should I have in my code?

Thanks

THANKS FOR ALL THE HELP. I figured it out. 

tour = FindShortestTour[GeoPosition[{12.3, 76.6}],
        GeoPosition[{13.21, 75.99}], GeoPosition[{9.61, 77.15}],
        GeoPosition[{10.08, 77.0597}], GeoPosition[{15.33, 76.46}],
        GeoPosition[{12.62, 80.1994}], GeoPosition[{26.35, 92.67}],
        GeoPosition[{11.58, 75.59}]][[2]]

This is the error I get:

FindShortestTour::nonopt: Options expected (instead of GeoPosition[{11.58,75.59}]) beyond position 1 in FindShortestTour[GeoPosition[{12.3,76.6}],GeoPosition[{13.21,75.99}],GeoPosition[{9.61,77.15}],GeoPosition[{10.08,77.0597}],GeoPosition[{15.33,76.46}],GeoPosition[{12.62,80.1994}],GeoPosition[{26.35,92.67}],GeoPosition[{11.58,75.59}]]. An option must be a rule or a list of rules. >>

NEW INFO- these are my 50 points 

{Entity["City", {"Bombay", "Maharashtra", "India"}], 
 Entity["City", {"Bengaluru", "Karnataka", "India"}], 
 Entity["City", {"Agra", "UttarPradesh", "India"}], 
 Entity["City", {"Aurangabad", "Maharashtra", "India"}], 
 Entity["City", {"Khajuraho", "MadhyaPradesh", "India"}], 
 Entity["City", {"Jammu", "JammuAndKashmir", "India"}], 
 Entity["City", {"Mormugao", "Goa", "India"}], 
 Entity["City", {"Jaipur", "Rajasthan", "India"}], 
 Entity["City", {"Udaipur", "Rajasthan", "India"}], 
 Entity["City", {"Jaisalmer", "Rajasthan", "India"}], 
 Entity["City", {"Leh", "JammuAndKashmir", "India"}], 
 Entity["City", {"Manali", "HimachalPradesh", "India"}], 
 Entity["City", {"Shimla", "HimachalPradesh", "India"}], 
 Entity["City", {"Gangtok", "Sikkim", "India"}], 
 Entity["City", {"Darjiling", "WestBengal", "India"}], 
 Entity["City", {"Kanyakumari", "TamilNadu", "India"}], 
 Entity["City", {"Haridwar", "Uttaranchal", "India"}], 
 Entity["City", {"NainiTal", "Uttaranchal", "India"}], 
 Entity["City", {"NewDelhi", "Delhi", "India"}], 
 Entity["City", {"DehraDun", "Uttaranchal", "India"}], 
 Entity["City", {"Amritsar", "Punjab", "India"}], 
 Entity["City", {"FatehpurSikri", "UttarPradesh", "India"}], 
 Entity["City", {"Hyderabad", "Telangana", "India"}], 
 Entity["City", {"Mangaluru", "Karnataka", "India"}], 
 Entity["City", {"Shillong", "Meghalaya", "India"}], 
 Entity["City", {"Visakhapatnam", "AndhraPradesh", "India"}], 
 Entity["City", {"Kedarnath", "Uttaranchal", "India"}], 
 Entity["City", {"Tirupati", "AndhraPradesh", "India"}], 
 Entity["City", {"Kodaikanal", "TamilNadu", "India"}], 
 Entity["City", {"Calcutta", "WestBengal", "India"}], 
 Entity["City", {"Matheran", "Maharashtra", "India"}], 
 Entity["City", {"Varanasi", "UttarPradesh", "India"}], 
 Entity["City", {"Mahabaleshwar", "Maharashtra", "India"}], 
 Entity["City", {"BodhGaya", "Bihar", "India"}], 
 Entity["City", {"Lucknow", "UttarPradesh", "India"}], 
 Entity["City", {"Madurai", "TamilNadu", "India"}], 
 Entity["City", {"Jabalpur", "MadhyaPradesh", "India"}], 
 Entity["City", {"MountAbu", "Rajasthan", "India"}], 
 Entity["City", {"Ramnagar", "Uttaranchal", "India"}], 
 Entity["City", {"Ootacamund", "TamilNadu", "India"}], 
 Entity["City", {"Thiruvananthapuram", "Kerala", "India"}], 
 Entity["City", {"Madras", "TamilNadu", "India"}], 
 GeoPosition[{12.3, 76.6}], GeoPosition[{13.21, 75.99}], 
 GeoPosition[{9.61, 77.15}], GeoPosition[{10.08, 77.0597}], 
 GeoPosition[{15.33, 76.46}], GeoPosition[{12.62, 80.1994}], 
 GeoPosition[{26.35, 92.67}], GeoPosition[{11.58, 75.59}]
Improve this question
$\endgroup$
4
  • $\begingroup$ Once you completely understand examples in documentation (reference.wolfram.com/language/ref/FindShortestTour.html), youll get much better idea about application to traveling salesman problem... $\endgroup$
    – VividD
    Commented Apr 17, 2015 at 16:18
  • $\begingroup$ I understand the traveling salesman problem however I'm trying to figure out the beginning of it. Just to get a start on the code. Do you know how to get the FindShortestTour function to work for 50 cities that you have already chosen? $\endgroup$
    – Sarah
    Commented Apr 17, 2015 at 16:32
  • $\begingroup$ There are many ways to solve it. Simulated Annealing (See the book Numerical Recipes) is the one I first encountered (this may not be how Mathematica attacks it). It can be solved exactly for a small(ish) number of cities, after that its a matter of finding a short(ish) route rather than THE shortest. $\endgroup$
    – Ymareth
    Commented Apr 17, 2015 at 16:37
  • $\begingroup$ I have 50 cities that I want to find the shortest route for. Do you think Mathematica can do that? $\endgroup$
    – Sarah
    Commented Apr 17, 2015 at 16:56

2 Answers 2

Reset to default
4
$\begingroup$

This code from this Wolfram guide uses RandomReal[] to get 100 random points in a plane, than solves traveling salesman problem using FindShortestTour[], and in turn renders suitable drawing:

With[{p = RandomReal[10, {100, 2}]}, 
 Graphics[{Line[p[[Last[FindShortestTour[p]]]]], PointSize[Large], 
   Red, Point[p]}]]

Tho output should look like this:

enter image description here

From this sample, you should be able to figure out how to organize your data in order to pass it to FindShortestTour[].

The internal algorithm should work the same way, and actually much faster, for your sample of 50 points.

Disclaimer: I am not sure if this solution is strict in mathematical (combinatorial optimization) sense, or it is just an aproximation. However, it is certainly a good starting point for solving your problem.

You may also find useful following questiions and answers from this site:

Solving the Travelling Salesman Problem

Travelling salesman with start and end points for 30 points

Edge Labels with distance between vertices

Random number generation with specific distribution

Graph Creation in Mathematica: TSP

Improve this answer
$\endgroup$
2
  • $\begingroup$ The only problem is that the FindingShortestTour function only works in a certain format. I tried to define all the locations of cities to a variable however it does not allow me to do that. Therefore, I am unable to use the function. $\endgroup$
    – Sarah
    Commented Apr 17, 2015 at 18:22
  • $\begingroup$ You must manipulate the data so that it is in the format that FindShortestTour[] requires. There is no other way. :) @Sarah $\endgroup$
    – VividD
    Commented Apr 17, 2015 at 18:23
2
$\begingroup$

Here's something very similar to the Neat example found in the Documentation for FindShortestTour.

Is this what you're asking for, or are you asking how FindShortestTour was implemented?

(* grab random cities and their GeoPositions *)
cities = SemanticInterpretation["US state capitals"];
locs = EntityValue[cities, "Position"];

(* find the shortest tour *)
tour = FindShortestTour[locs][[2]];

(* plot it *)
GeoGraphics[GeoPath[cities[[tour]]], GeoRange -> "Country"]

enter image description here

Improve this answer
$\endgroup$
2
  • $\begingroup$ Yes this is what I want to do. However, I already have my 50 cities picked out. I have them in these forms: Entity["City", {"NewDelhi", "Delhi", "India"}] GeoPosition[{15.33, 76.46} I'm just not sure how to make FindShortestTour to recognize all the cities $\endgroup$
    – Sarah
    Commented Apr 20, 2015 at 14:24
  • $\begingroup$ Your problem is that you have a mix of Entity objects and GeoPosition objects in your list. So run the above code with cities containing only the Entity objects; this turns them into GeoPositions. Then Join that list with the last 8 GeoPositions. This should give you something that you can feed into FindShortestTour. Finally, you'll need to plot GeoPath[locs[[tour]]], rather than GeoPath[cities[[tour]]]. $\endgroup$
    – Michael Seifert
    Commented Apr 20, 2015 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.