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

[amandhaka]

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]

Yes indeed, we stopped using the simulated annealing developed by a GSoC student and started using the solution given by Boost/Graph

Making sure that the acronyms for non English speaking
SA = Simulated Annealing
MA = matrix approximation

About signature simplification:

Simulated annealing
used many parameters

pgr_TSP(Matrix SQL,
    [start_id], [end_id],
    [max_processing_time],
    [tries_per_temperature], [max_changes_per_temperature], [max_consecutive_non_changes],
    [initial_temperature], [final_temperature], [cooling_factor],
    [randomize])

Matrix approximation:

pgr_TSP([Matrix SQL](matrix_sql, [start_id, end_id])

About performance

Yes, it is the case that the results of simulated annealing are more accurate, than the matrix approximation, but the time to get the results is too slow.

Simulated annealing
From the performance files,

select test_performance(1.1);  # for Djibouti
select test_performance(1.4); # for Katar
select test_performance(1.065); # for Western Sahara

The files were there, but we could not use them as part of our test framework because of the time they took to execute.
Please be my guest of running those files on v3.1.2.

Matrix approximation
From University of Waterloo benchmark test data
and from the statement Boost's documentation:
"This implementation generates solutions that are twice as long as the optimal tour in the worst case."

pgRouting has the following test function is here

And been used as:

SELECT tsp_performance('dj38', 38, 6656.0, 2);
SELECT tsp_performance('qa194', 5, 9352, 2); 
SELECT tsp_performance('wi29', 29, 95345, 2);

For (Djibouti)[https://www.math.uwaterloo.ca/tsp/world/djpoints.html)

pgtap/tsp/TSPeuclidean/performance/dj38.pg .. ok     
All tests successful.
Files=1, Tests=38,  0 wallclock secs ( 0.00 usr  0.01 sys +  0.01 cusr  0.00 csys =  0.02 CPU)
Result: PASS

real	0m0.579s
user	0m0.043s
sys	0m0.018s

For Qatar

pgtap/tsp/TSPeuclidean/performance/qa194.pg .. ok   
All tests successful.
Files=1, Tests=5, 18 wallclock secs ( 0.01 usr  0.00 sys +  0.01 cusr  0.00 csys =  0.02 CPU)
Result: PASS

real	0m18.007s
user	0m0.037s
sys	0m0.025s

FOR Western Sahara

pgtap/tsp/TSPeuclidean/performance/wi29.pg .. ok     
All tests successful.
Files=1, Tests=29,  0 wallclock secs ( 0.00 usr  0.00 sys +  0.01 cusr  0.00 csys =  0.01 CPU)
Result: PASS

real	0m0.251s
user	0m0.057s
sys	0m0.004s

Conclusion

The solution that we had of Simulated annealing had that problem execution time when the problem was big, and the developer of that function was a Google Summer of Code student that moved on, and we had a very difficult time trying to improve that code.
We opted then to use Boost's solution with matrix approximation. for pgr_TSP.

There are many more algorithms, that give more precise solutions, like this one that used a network of 110 processors the total computer time used in the computation was 22.6 years, for 15K+ cities in Germany
Germanny

[DettmerAL]

Hi there.

Isn't it possible to keep both algorithms?

[amandhaka]

It makes sense, thank you for detailed answer.