BiDirectional in forward direction is faster than both directions
torressa opened this issue · 2 comments
Describe the bug
For some reason, the forward direction tends to be faster than the bidirectional version.
This can be the case for some problems, but I've experienced it across several problems (Beasley and Christofides, Solomon and Augerat).
To Reproduce
Run any of the Beasley and Christofides, Solomon or Augerat instances with direction="forward"
and then with direction="both"
and see.
The first can be ran
cd tools/dev/
./build -b -s
The Solomon + Augerat can be ran by using vrpy
(changing directions in subproblem_cspy.py
) and running
python3 -m pytest -k cspy -s -v benchmarks/
Suggestions
Starter
- Merge the
Search
functionality (src/cc/search.h
) intoBiDirectional
. I'm not entirely sure this would work, but I had the same issue when I had this structure in Python. - Revise joining procedure
Further
- Use a proper graph implementation (#63, unrelated, but can't hurt).
- Come up with a way of stopping the search early using the threshold (it is easy in the forward direction as paths are fully formed, whereas in both directions, labels have to merged then checked)
- Valgrind
Finally working as expected. On a solomon instance (for Beasley bencharchmarks, see #65 (comment))
The number of stops is the primary resource. I suspect changing this to match the most restrictive one (e.g. time), will see further improvements.
Table of time in seconds until optimal solution (using vrpy
)
# of nodes | both | fwd |
---|---|---|
2 | 0.03 | 0.03 |
3 | 0.05 | 0.05 |
4 | 0.05 | 0.06 |
5 | 0.07 | 0.06 |
6 | 0.07 | 0.07 |
7 | 0.15 | 0.15 |
8 | 0.17 | 0.17 |
9 | 0.20 | 0.24 |
10 | 0.35 | 0.52 |
11 | 0.44 | 0.51 |
12 | 0.63 | 1.07 |
13 | 1.60 | 1.04 |
14 | 1.46 | 1.57 |
15 | 1.88 | 1.95 |
16 | 2.27 | 2.25 |
17 | 2.17 | 2.39 |
18 | 1.37 | 1.64 |
19 | 3.43 | 3.46 |
20 | 4.45 | 4.36 |
21 | 4.18 | 3.70 |
22 | 4.16 | 4.36 |
23 | 6.29 | 5.63 |
24 | 5.44 | 6.92 |
25 | 7.27 | 8.87 |
average | 2.01 | 2.13 |