Originally posted by **amandhaka** September 23, 2023
I've been working with the pgr_TSP function in the pgrouting library, and I noticed a change in its behavior between versions 3.1.2 and 3.2.1. Specifically, it seems that in 3.2.1, the algorithm was upgraded from using the "simulated annealing" algorithm to the "metric approximation" algorithm.
I've observed some differences in routing outcomes, including an increase in aggregated cost, when using the newer version. My understanding is that different algorithms can indeed yield different results, but I expected the newer algorithm to provide improved results.
Can someone shed light on why I might be experiencing these differences in routing results between the two versions? Shouldn't the newer algorithm generally produce better results, or are there specific factors I should consider?
I have used same data and tried the algorithms on 100 queries set on both the versions of pgr_TSP.
SA pgr_TSP performed 5% better than MA pgrTSP.
Example, the below result are using same dataset, but pgrouting version is different.
1. pgr_TSP which uses Metric approximation (3.2.1+)
seq | node | cost | agg_cost
1 | 1032 | 0 | 0
2 | 287 | 8.949999966025345 | 8.949999966025345
3 | 302 | 1.0199999999999996 | 9.969999966025345
4 | 191 | 12.219999781847001 | 22.189999747872346
5 | 960 | 18.67000019431057 | 40.85999994218292
6 | 803 | 7.349999879002565 | 48.209999821185484
7 | 778 | 1.0199999999999996 | 49.22999982118549
8 | 496 | 8.719999923109999 | 57.94999974429548
9 | 746 | 2.08999997615814 | 60.03999972045362
10 | 755 | 1.0199999999999996 | 61.05999972045362
11 | 791 | 2.059999902844421 | 63.11999962329804
12 | 229 | 17.769000121004964 | 80.888999744303
13 | 231 | 0.6799999999999997 | 81.568999744303
14 | 232 | 0.33999999999999986 | 81.908999744303
15 | 252 | 6.860000000000003 | 88.768999744303
16 | 370 | 9.349999904632572 | 98.11899964893557
17 | 467 | 10.100000025629983 | 108.21899967456555
18 | 1248 | 8.57999999821185 | 116.7989996727774
19 | 706 | 18.96000000178813 | 135.75899967456553
20 | 709 | 1.4299999725818644 | 137.1889996471474
21 | 1080 | 8.56000000000001 | 145.7489996471474
22 | 1262 | 10.506923599189609 | 156.255923246337
23 | 1032 | 37.55999989092349 | 193.81592313726048
2. pgr_TSP which uses SA (3.1.2)
seq | node | cost | agg_cost
1 1032 8.949999966025345 0
2 287 1.0199999999999996 8.949999966025345
3 302 7.379999781846999 9.969999966025345
4 252 6.860000000000003 17.349999747872346
5 232 0.33999999999999986 24.20999974787235
6 231 0.6799999999999997 24.54999974787235
7 229 15.430000194310852 25.22999974787235
8 960 7.349999879002565 40.6599999421832
9 803 1.0199999999999996 48.009999821185765
10 778 8.719999923109999 49.02999982118577
11 496 2.08999997615814 57.74999974429576
12 746 3.0799999028444205 59.8399997204539
13 791 2.059999902844421 62.919999623298324
14 755 9.989000020266197 64.97999952614275
15 191 12.189999904632574 74.96899954640895
16 370 10.100000025629983 87.15899945104152
17 467 10.380000003576281 97.2589994766715
18 706 1.4299999725818644 107.63899948024779
19 709 8.56000000000001 109.06899945282966
20 1080 17.52692357177146 117.62899945282967
21 1248 8.720000020265566 135.15592302460112
22 1262 37.55999989092349 143.87592304486668
23 1032 0 181.4359229357902
Any insights or advice would be greatly appreciated
Discussed in https://github.com/pgRouting/pgrouting/discussions/2562