PyVRP: BrokenPairsDistance for different problem variants.
For VRPTW, routes are directed so the current brokenPairsDistance implementation compares directed routes (through directed neighbours).
- For CVRP, we should probably implement a a version that considers undirected routes (undirected neighbours) as in HGS-CVRP.
- For heterogeneous vehicle capacities (#203), we should probably take into account vehicle assignments in the distance computation, but then the name
brokenPairsDistanceis no longer accurate.
We could implement different versions (directed, undirected, heterogeneous) but that would put a responsibility for the user to pick the right version for the right problem/variant. I suggest we implement something to make picking the right option the default.
Note that always considering vehicle assignments (in something named more generally like solution_distance) will not change behavior for the homogeneous case (may just be a bit slower), so we only need to distinguish directed vs undirected which could be done based on a property of ProblemData (like ProblemData.is_undirected which holds true for CVRP/TSP with symmetric distances), then using that to select the right distance function when initializing Population.
Out of the box: do we need this function to be on the c++ side? If we bind the Individual::neighbours (/assignments) as numpy arrays we can compute the distance efficiently through numpy (but we should avoid repeated copying of the neighbours, so maybe wrap the individual object in Python). Not sure though.
About this issue
- Original URL
- State: open
- Created a year ago
- Comments: 18 (15 by maintainers)
This might be worth repeating for 0.7.0. If the improvement is large enough (say, >0.05%?) we could consider implementing undirected BPD. It’s easy enough to do so, and could be worthwhile for users solving problem variants where this matters.
Is that student currently working on undirected BPD? I think Thibaut’s version can be adapted pretty easily to fit our function signature, so it need not be too hard to do. We could implement an undirected variant of BPD if the performance difference between the two is really significant on their benchmark, alongside the current directed implementation.
If the difference matters we should probably include some of their benchmark instances into our benchmark set going forward, because they then have properties our current instances do not yet test for.