2

I am trying to get my head around a TSP program for college, I have to admit I'm finding it very difficult.

Basically I have an array of Lat values and an array of Lng values, using haversine's, I have transferred the distances into a matrix.
Now where to go from here?
I have to find the shortest distance, visiting all 80 towns. I am trying to think of the best way to do it. Should I make a nearest neighbor algorithm? Should I just store the permutations and total the distance. or is there a better way? I have to admit, I think this is a little difficult for a 1st year student! Anyway here's my code, it's awful, the applet etc was given to us.

public class Brain { //These are the names of the 80 towns and their north and west GPS co-ordinates static double north[] = {53.855,52.794,54.350,53.433,52.992,54.117,53.328,54.800,54.863,55.071,54.502,54.343,51.746,54.660,51.680,54.597,53.091,53.175,55.136,52.831,53.976,53.944,53.861,53.991,51.622,52.354,51.897,54.996,54.322,53.714,53.348,54.009,54.500,52.085,53.345,52.846,52.502,54.345,53.272,52.677,53.728,53.106,52.648,52.059,51.708,53.783,54.851,54.957,55.053,52.665,52.447,53.727,53.197,51.904,54.750,52.131,53.382,52.266,54.248,53.116,53.522,52.863,52.396,54.210,52.451,54.590,53.633,52.714,54.267,53.245,54.830,52.679,52.474,52.268,53.515,53.267,52.257,53.800,52.334,51.952}; static double west[] = {-6.538,-6.165,-6.655,-7.950,-6.987,-9.167,-8.219,-7.790,-6.284,-6.508,-8.190,-6.260,-8.735,-5.670,-9.453,-5.930,-7.913,-6.525,-7.456,-6.932,-6.719,-8.095,-9.299,-7.360,-8.886,-7.712,-8.470,-7.307,-5.703,-6.350,-6.260,-6.405,-6.770,-7.640,-7.051,-8.981,-6.566,-7.640,-9.049,-6.292,-6.878,-6.065,-7.256,-9.507,-8.531,-8.917,-5.811,-7.720,-6.946,-8.624,-9.486,-7.800,-8.567,-8.957,-6.610,-8.642,-6.591,-8.270,-6.971,-7.324,-7.338,-8.200,-6.945,-5.882,-9.055,-7.290,-8.183,-8.869,-8.483,-9.306,-7.470,-7.814,-8.162,-9.696,-8.851,-7.500,-7.129,-9.533,-6.458,-7.846}; String names[] = {"Ardee","Arklow","Armagh","Athlone","Athy","Ballina","Ballinasloe","Ballybofe","Ballymena","Ballymoney","Ballyshannon","Banbridge","Bandon","Bangor","Bantry","Belfast","Birr","Blessington","Buncrana","Carlow","Carrickmacross","Carrick-On-Shannon","Castlebar","Cavan","Clonakilty","Clonmel","Cork","Derry","Downpatrick","Drogheda","Dublin","Dundalk","Dungannon","Dungarvan","Edenderry","Ennis","Enniscorthy","Enniskillen","Galway","Gorey","Kells","Kilcoole","Kilkenny","Killarney","Kinsale","Knock","Larne","Letterkenny","Limavady","Limerick","Listowel","Longford","Loughrea","Macroom","Magherafelt","Mallow","Maynooth","Mitchelstown","Monaghan","Mountmellick","Mullingar","Nenagh","New-Ross","Newcastle","Newcastle-West","Omagh","Roscommon","Shannon","Sligo","Spiddal","Strabane","Thurles","Tipperary","Tralee","Tuam","Tullamore","Waterford","Westport","Wexford","Youghal"}; static double[][] matrix = new double[80][80]; boolean visit[]=new boolean[80]; boolean valid = true; public static void fillmatrix (){ double tote = 0; for(int i=1;i<80;i++){ for(int j=1;j<80;j++){ matrix[i][j]=getDistance(north[i],west[j],north[j],west[j]); } } } public String compute () { String solution =""; for (int i=0;i<80;i++){ solution+=(char)(i+40); } solution+="Anything you add on after the 80 characters will be " + "printed in the textbox (e.g. you can compute the distance)"; return solution; } public static double getDistance(double lat1, double lon1, double lat2, double lon2){ double R = 6371; double dLat = Math.toRadians((lat2-lat1)); double dLon = Math.toRadians((lon2-lon1)); double a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(Math.toRadians(lat1)) * Math.cos(Math.toRadians(lat2)) * Math.sin(dLon/2) * Math.sin(dLon/2); double c = 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); double d = R * c; return d; } }
Improve this question
1
  • if there are 80 cities that means there are approximately 80! (10^ 118) permutations! Commented May 3, 2012 at 17:17

3 Answers 3

Reset to default
1

The best way to tackle the nearest neighbor heuristic is to break down the algorithm into sub-problems.

  1. Select a random city.
  2. Find the nearest unvisited city and go there.
  3. Are there any unvisitied cities left? If yes, repeat step 2.
  4. Return to the first city.

Next, solve each sub-problem.

  1. Pick a random value in the names array
  2. Check all of the cities for distance to the random city by iterating through the north and west array and calculating distance. Store visited cities in an array.
  3. Repeat 2
  4. Return to first city

Then, think about the pseudo code and try to write the Java code.

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

1

Checking all permutations will be prohibitively expensive for anything but the tiniest instances.

Fortunately, there's a whole bunch of well-known heuristic algorithms for the TSP. Take your pick.

Improve this answer

2 Comments

Yeah I was thinking about nearest neighbour, have no idea how to implementhits books
Link is dead, care to elaborate?
0

About SourceCode

At first, I might advise you to change the definition of a cities coordinates to class City, and, as you're cities are pre-defined, you might want to 'export' it in external file and load it at file beggining. For example,

public class City{ public double North; public double West; public String Name; public double getDistanceToCity(City target){ double R = 6371; double dLat = Math.toRadians((target.North-this.North)); double dLon = Math.toRadians((target.West-this.West)); double a = Math.sin(dLat/2) * Math.sin(dLat/2) + Math.cos(Math.toRadians(this.North)) * Math.cos(Math.toRadians(this.West)) * Math.sin(dLon/2) * Math.sin(dLon/2); double d = R * 2 * Math.atan2(Math.sqrt(a), Math.sqrt(1-a)); return d;}}

Then, for example, after reading your file into "ArrayList Cities" you'll bild your matrix by:

double[][] distances = new double[Cities.size()][Cities.size()]; int i=0; int j=0; for(City start:Cities){ for(City end:Cities){ distances[i][j]=start.getDistanceToCity(end); j++;} i++;}

And get the same matrix. In this case, you'll can change input data size, for example testing Correctness of your algo with 10 cities, and after all works fine run with 80. Besides, in this case you'll see by yourself hardness of this problem - simply run it on 40 and 41 city...

Next, about algo...

This is NP-hard problem, so your permutations will work VERY long time. I'll suggest Held–Karp algorithm, which is much faster but pretty hard for realization and needs a lot of memory. ( For example, suggested method if (n*n*2^n), which is 10^27 for n=80, and permutations are n!, which 10^121 for n=80 - i mean operations required for solving task).

In any way, afaic the best exact solution for now is linear programming (can't remember exact method, but...). May you'll find some algo considering to use graph methods.

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.