rodolfopichardo / linkernighantsp Goto Github PK

Hi Rodolfo,

Hope this finds you well. Happy new year.

I have been playing around with some sample data.

I ran the attached TSP file through your program and through a simple kd tree. For the kd tree I seeded the first node as the start point from your TSP output. The kd tree produces a route that is almost half the distance. Do you know what might be happening?
osm_x_y_run_debug_kdtree.zip = the tsp file
route_tsp.zip = csv with tsp route generated by your code
route_kdtree.zip = route seeded to kd tree with start node from tsp and then output of route

route_tsp.zip

route_kdtree.zip

osm_x_y_run_debug_kdtree.zip

The array ids is not used in the code.

This small modification returns the tour with the actual ids.

/**
 * This function returns a string with the current tour and its distance
 *
 * @return String with the representation of the tour
 */
public String toString() {
    StringBuilder str = new StringBuilder("[" + this.getDistance() + "] : ");
    boolean add = false;
    for (int cityIdx : this.tour) {
        int city = ids.get(cityIdx);
        if (add) {
            str.append(" => ").append(city); // .append("(" + cityIdx + ")");
        } else {
            str.append(city);
            add = true;
        }
    }
    return str.toString();
}

additionally the tour can be returned:

/** returns the tour as list of their Ids */
public List<Integer> getTourIds() {
    List<Integer> t = new ArrayList<>(size);
    for (int i : tour) {
        t.add(ids.get(i));
    }
    return t;
}

Hello Rodolfo

Just another quick question - is your algorithm implementation Chained Lin Kernighan? (https://pdfs.semanticscholar.org/c4ed/86c06e92dab39db4414297c2055abcaf6590.pdf)

Thank you for your patience in answering my barrage of questions!

Best

Vikram

Currently, when we get a new ti, we construct a new tour and check whether that tour is actually valid, however, this is very costly and this operation is done continuously (a recipe for disaster). So, I propose to device a mechanism to make this operation more effective.

In the original paper by S. Lin and B. W. Kernighan, they describe a limited backtracking approach (at step 6). This should be implemented for the sake of completeness.

Currently, the data format is a non-standardised form of TSPLIB that does not have any headers or end-of-file markers; however, it would be nice for this program to accept standard TSPLIB compliant data,

@RodolfoPichardo

Hello - Thank you for this implementation. I am evaluating using this on a large list (50,000) of building structures to determine the shortest route order. I have lat and longitude coordinate list.
1.) Could I use GEO for EDGE WEIGHT TYPE and provide the lat & long values?
2.) If I use EUC_2D how would I convert the lat long to the x, y coordinate system - what would I use as a base ref to compute x, c?
3.) Do you have any metrics on run time for such large lists?

I appreciate your help. Thank you for your time.

I think this is a bug, because getDistance returns double precision and somehow the java compiler doesn't complain about gain += getDistance(t2, t3) - getDistance(t1,t2); even though here is a loss of precision. For example, with wi29.tsp I get a slightly better path when changing to double.

Show the results even if the user decides to terminate early

There should be a prompt that asks the user which dataset to test.

I propose the prompt appears right after running the code, and its format shall be:

[1] Tanzania.tsp
[2] Bolivia.tsp
[3] Span.tsp
Select the dataset to test: 

This is a test of the algorithm.

The optimal tour is shorter. This result deviates also from the Concorde Lin-Kernighan implementation result, which finds the optimal tour.

TSP and optimal tour attached.
tsp16-7_test_lin_kernighan.zip