Non optimal tour

[vsrdharca]

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

[vsrdharca]

@RodolfoPichardo = If you could please look into this cursorily and advice.

[vsrdharca]

Hi @RodolfoPichardo

Would appreciate your thoughts on this. Thank you.

[RodolfoPichardo]

Good question. I will test this and let you know

[vsrdharca]

Thanks Rodolfo. I really appreciate it. I can provide you more data in the way you need it to make your life easier.

My email id is vikram{dot}sridharan{at}gmail{dot}com

I am happy to talk on the phone to explain the situation as well.

Let me know

Best

Vikram

On Jan 25, 2018 3:24 PM, "RodolfoPichardo" notifications@github.com wrote:

Good question. I will test this and let you know

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/RodolfoPichardo/LinKernighanTSP/issues/8#issuecomment-360634520, or mute the thread https://github.com/notifications/unsubscribe-auth/AYEEadbc9QLDy6nVsx9K1UT7z8LsbG22ks5tOQ0ogaJpZM4RscWp .

[RodolfoPichardo]

Hey Vikram,

There seems to be number of issues with the code:

1. The program looses precision when dealing with really small numbers; such as the difference between some of the coordinates you provided.
2. It is misreporting the total distance.

I modified the file you provided by subtracting 4847 to the x coordinates, and 3003 to the y coordinates; since the distance will remain the same; furthermore, I multiplied the x and y by 100,000 to get a larger number.

This was the result:

0 | 70537.2803715363 | 93634.2507138761
1 | 76891.910312952 | 89717.3909793764
2 | 70980.4791756142 | 93969.1886461787
3 | 42895.5004372256 | 74381.1154188734
4 | 123976.248136842 | 66917.0033394494
5 | 103377.109779922 | 74121.227386604
6 | 87057.6937414626 | 59511.4087927868
7 | 87250.5230905517 | 60201.6981891666
8 | 91385.8063947373 | 60698.8877657841
9 | 90959.7574439431 | 60567.0888776785

After multiple runs I got the following routes: 2 => 1 => 5 => 4 => 8 => 9 => 7 => 6 => 3 => 0 2 => 0 => 3 => 4 => 5 => 8 => 9 => 6 => 7 => 1 3 => 0 => 2 => 1 => 5 => 4 => 8 => 9 => 7 => 6 6 => 3 => 0 => 2 => 1 => 4 => 5 => 8 => 9 => 7

Where they are all smaller than the nearest neighbour algorithm.

So, I will fix it either tomorrow or on the weekend.

[vsrdharca]

Thank you so much Rodolfo. I really really appreciate you trouble shooting.

I'll wait for your fix.

Best Regards

Vikram

On Jan 25, 2018 5:18 PM, "RodolfoPichardo" notifications@github.com wrote:

Hey Vikram,

There seems to be number of issues with the code:

1. The program looses precision when dealing with really small numbers; such as the difference between some of the coordinates you provided.
2. It is misreporting the total distance.

I modified the file you provided by subtracting 4847 to the x coordinates, and 3003 to the y coordinates; since the distance will remain the same; furthermore, I multiplied the x and y by 100,000 to get a larger number.

This was the result:

0 | 70537.2803715363 | 93634.2507138761 <(250)%20713-8761> 1 | 76891.910312952 | 89717.3909793764 2 | 70980.4791756142 | 93969.1886461787 3 | 42895.5004372256 | 74381.1154188734 4 | 123976.248136842 | 66917.0033394494 5 | 103377.109779922 | 74121.227386604 6 | 87057.6937414626 | 59511.4087927868 7 | 87250.5230905517 | 60201.6981891666 8 | 91385.8063947373 | 60698.8877657841 9 | 90959.7574439431 | 60567.0888776785

After multiple runs I got the following routes: 2 => 1 => 5 => 4 => 8 => 9 => 7 => 6 => 3 => 0 2 => 0 => 3 => 4 => 5 => 8 => 9 => 6 => 7 => 1 3 => 0 => 2 => 1 => 5 => 4 => 8 => 9 => 7 => 6 6 => 3 => 0 => 2 => 1 => 4 => 5 => 8 => 9 => 7

Where they are all smaller than the nearest neighbour algorithm.

So, I will fix it either tomorrow or on the weekend.

— You are receiving this because you authored the thread. Reply to this email directly, view it on GitHub https://github.com/RodolfoPichardo/LinKernighanTSP/issues/8#issuecomment-360655275, or mute the thread https://github.com/notifications/unsubscribe-auth/AYEEaegNQebs7UiQBrN-yrehxoD1to_Uks5tOSfvgaJpZM4RscWp .

[vsrdharca]

Hi @RodolfoPichardo

Hope your weekend is going well. Just touching base to see if you had a chance to fix the issues. Thanks again for taking the time.

Best Regards

Vikram

[vsrdharca]

Hi @RodolfoPichardo

Hope your week is going well. Just touching base to see if you might have some time to fix the issues. Sorry for the bother.

Thanks!

Best

Vikram

[vsrdharca]

Hi @RodolfoPichardo

Just checking to see if you might have any time to make the code changes near term?

Thank you for your help.

Best

Vikram