search

torressa / cspy

A collection of algorithms for the (Resource) Constrained Shortest Path problem in Python / C++ / C#
https://torressa.github.io/cspy/
MIT License
78 stars 24 forks source link

Benchmarks against boost's r_c_shortest_paths #65

Closed torressa closed 3 years ago

torressa commented 3 years ago

Compare BiDirectional implementation against Michael Drexl's 2006 implementation in the boost library. Found here: https://www.boost.org/doc/libs/1_62_0/libs/graph/doc/r_c_shortest_paths.html

The comparison can be done using the Beasley and Christofides (1989) benchmarks, already in the repo, along with some results.

Parsing + runner can be found in a unit test.

But they're also a bunch of other benchmarks to look at e.g. Zhu and Wilhelm.

torressa commented 3 years ago

Just added a Dockerfile that runs the example from the library. Looks like it's trickier than I thought as you have to have to define the graph, resources, dominance relationships for each case. Can't really see how to do it so that it works on all instances...

torressa commented 3 years ago

Some instances fail with bounds_pruning=true (only in the forward direction interestingly). Unfair comparison as I ran the r_c_shortest_paths in docker and the others on my machine.

Both on docker see a lot worse results, but clear winner on hard instances (e.g. 5, 23 and 24).

Will be interesting to fix direction="both" to perform as it should (faster than just forward) and see

Instance r_c_shortest_paths (docker) fwd_bounds_pruning (local) Speed diff (%) fwd_bounds_pruning (docker) Speed diff (%)
1 4 3 25.00 5 -25.00
2 4 3 25.00 5 -25.00
3 3 5 -66.67 8 -166.67
4 3 5 -66.67 8 -166.67
5 125 3 97.60 5 96.00
6 81 3 96.30 5 93.83
7 53 16 69.81 31 41.51
8 16 19 -18.75 45 -181.25
9 2 2 0.00 3 -50.00
10 2 2 0.00 3 -50.00
11 7 8 -14.29 18 -157.14
12 7 8 -14.29 18 -157.14
13 7 5 28.57 10 -42.86
14 6 3 50.00 7 -16.67
15 38 28 26.32 49 -28.95
16 13 14 -7.69 21 -61.54
17 39 - - - -
18 37 - - - -
19 18 - - - -
20 18 - - - -
21 71 17 76.06 24 66.20
22 32 16 50.00 22 31.25
23 4566 28 99.39 42 99.08
24 274 84 69.34 131 52.19
    Average Speed up 26.25   -32.44
torressa commented 3 years ago

I've tried step 1 for #66 and we see some more realistic results without the bounds pruning. Faster results in both directions for the harder instances, this is more in line with what should happen.

 Instance boost both fwd best
1 6 12 7 7
2 4 12 7 7
3 2 13 8 8
4 2 11 8 8
5 121 245 116 116
6 80 195 94 94
7 51 112 98 98
8 14 71 32 32
9 1 1 1 1
10 1 1 1 1
11 5 37 19 19
12 5 36 19 19
13 3 15 8 8
14 2 13 4 4
15 35 59 79 59
16 9 29 24 24
17 35 116 70 70
18 32 112 69 69
19 14 79 45 45
20 14 70 44 44
21 61 13 132 13
22 26 6 64 6
23 4792 1872 3279 1872
24 266 446 464 446
stale[bot] commented 3 years ago

This issue has been automatically marked as stale because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.

torressa commented 3 years ago

Current version in branch patch66 seems to work as expected:

instance both fwd boost
1 9 7 5
2 9 7 4
3 11 9 3
4 9 8 2
5 158 114 122
6 134 91 79
7 83 97 51
8 34 32 14
9 1 1 1
10 1 1 1
11 22 19 5
12 22 19 5
13 9 8 3
14 7 4 1
15 52 77 34
16 23 23 9
17 79 72 37
18 78 74 33
19 50 44 14
20 47 43 14
21 12 129 63
22 7 62 22
23 1779 3447 4790
24 382 480 264
Average 125.75 202.83 232.33
torressa commented 3 years ago

Significant improvements using LEMON

instance both fwd best boost
1 6 5 5 5
2 6 5 5 4
3 6 5 5 2
4 6 5 5 2
5 119 79 79 120
6 94 63 63 79
7 57 68 57 50
8 26 22 22 14
9 1 1 1 1
10 1 1 1 1
11 14 12 12 6
12 14 11 11 6
13 6 6 6 3
14 5 3 3 1
15 35 52 35 36
16 17 16 16 10
17 52 45 45 39
18 52 45 45 33
19 32 28 28 15
20 30 27 27 13
21 6 77 6 60
22 4 39 4 23
23 1148 2268 1148 4629
24 240 291 240 330
average 82.38 132.25 77.875 228.42