TSPRoadTrip/Tsp.java at master · Bennerman/TSPRoadTrip · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
import java.util.ArrayList;

class Tsp{


    /**
     * Calculates the distance between two coordinates currently.
     * @param points - an array of coordinates
     * @param i
     * @param j
     * @return
     */

    public static double calcDistance(Location loc1, Location loc2){
        final double AVERAGE_RADIUS_OF_EARTH_KM = 6371;
        double distance;
        double distLon1 = loc1.getLongitude();
        double distLon2 = loc2.getLongitude();
        double distLat1 = loc1.getLatitude();
        double distLat2 = loc2.getLatitude();
        double distLon;
        double distLat;
        double a;
        double c;

        distLon = Math.abs((distLon2 - distLon1)) * Math.PI/180;
        distLat = Math.abs((distLat2 - distLat1)) * Math.PI/180;

        distLat1 = distLat1 * Math.PI/180;
        distLat2 = distLat2 * Math.PI/180;

        //System.out.println("distLon =" + distLon);
        //System.out.println("distLat =" + distLat);


        a = Math.pow(Math.sin(distLat / 2), 2) + Math.pow(Math.sin(distLon / 2), 2) * Math.cos(distLat1) * Math.cos(distLat2);
        //System.out.println("a =" + a);
        c = 2 * Math.asin(Math.sqrt(a));

        distance = AVERAGE_RADIUS_OF_EARTH_KM * c;


        return distance;
    }


    public static Route findShortestPath(Route routeInit){
        int iterations = 0;
        int improve = 0;
        Route bestRoute = routeInit;

        while(improve < 800) {


            for(int i = 1; i < bestRoute.size - 1; i++) {
                for(int k = i + 1; k < routeInit.size; k++) {
                    iterations++;
                    Route newRoute = bestRoute.swap(i, k);


                    double newRouteDist = newRoute.routeDistance();
                    double bestRouteDist = bestRoute.routeDistance();

                    //RESET
                    if( newRouteDist < bestRouteDist ) {
                        improve = 0;
                        bestRoute = newRoute;
                    }
                    //System.out.println(bestRouteDist);
                }
            }


            improve++;
            //System.out.println("Iteration: " + iterations);
            //System.out.println("Improve: " + improve);

        }


        return bestRoute;
    }

}