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.
- 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 |
- 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 |