Kuifje02 / vrpy

A python framework for solving the VRP and its variants with column generation.
MIT License
173 stars 42 forks source link

Non elementary routes #126

Closed torressa closed 2 years ago

torressa commented 2 years ago

@Kuifje02 Hey Romain! I think this is ready for a review now. I'm using black (the formatter) so hopefully won't be looking at much useless diff after this. It would be cool if you could test a little bit too. The unit test for issue 99 is the only one that doesn't pass (but this works fine with the new version of cspy). Same for some of the examples (failing with cspy-v101, working with the new version). I think this may be a source of new issues (missing nodes and such), so I've included an option for people to turn this off elementary (and removed the exact option).

I've been running mostly regression tests wrt cspy-v101 and vrpy-v051 (previous releases). Results on the Solomon instances (benchmarks/tests/test_cvrptw_solomon_range.py) and it looks pretty good (times per subproblem averaged over 10 runs) (x-axis should start at 7-69 as it's the number of nodes): image

The grey (fwd_new) and orange lines (both_new) are the new unreleased version of cspy (which I'm planning on releasing soon) with this new non-elementary route stuff. Performance is more stable (fwd_new being slightly better most of the time). I've also included the previous release of vrpy with cspy (vrpy_051_cspy_101), which is flailing about all over the place (also giving me some memory issues but I think that's cause of pytest).

I think this also contains fixes #101 and related.

torressa commented 2 years ago

Tell a lie, #101 not sure if fixed. Do we have to check upper TW for departure times? I don't we can as it is not enforced at the subproblem level.

Kuifje02 commented 2 years ago

Great job @torressa ! Thanks for all the work.

There is a test regarding issue #99 with non elementary routes that still fails. Not sure whats going on, needs more investigation.

torressa commented 2 years ago

Thanks man! #99 is on cspy side, the next release works!