Discrepancy in Routing Results Between pgr_TSP Versions (3.1.2 vs. 3.2.1)

[amandhaka]

Discussed in #2562

^{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

[cvvergara]

The documentation mentions

Implementation generates solutions that are twice as long as the optimal tour in the worst case

Processing queries docqueries/tsp/doc-pgr_TSPeuclidean	 PASS
    test run time: 0.060995
Processing queries docqueries/tsp/doc-pgr_TSP	 PASS
    test run time: 0.052729
$stats = {
           'docqueries/tsp/test.conf' => [
                                           {
                                             'comment' => 'TSP tests',
                                             'docqueries/tsp/doc-pgr_TSP.test.sql' => 'Passed',
                                             'docqueries/tsp/doc-pgr_TSPeuclidean.test.sql' => 'Passed'
                                           }
                                         ],
           'z_crash' => 0,
           'z_fail' => 0,
           'z_pass' => 2

If I remember correctly, these tests used to take minutes to solve with the simulated annealing algorithm.
We opted for faster response + less optimal vs slower response + more optimal results.

We are not going back to the simulated annealing.