Add benchmarks with other libraries

[Kuifje02]

Following #42, It would be great to add benchmarks with:

• [x] ~py-ga-vrptw~

  • [x] ~Solomon instances (VRPTW)~

• [ ] ortools

  • [ ] Solomon instances (VRPTW)

  • [x] Augerat instances (CVRP)

Expected format: performance profiles such as

x axis : relative gap with best known solution y axis : % of data sets solved within gap

[torressa]

@Halvaros We can probably take this one

[Kuifje02]

Perhaps we could create a separate folder dedicated to benchmarks with a script that can be run and automatically generates the performance profiles. This way, when the code evolves, we can easily update the benchmarks. I already have some code to run the tests and generate the profiles.

Also, regarding py-ga-VRPTW:

• as mentioned in their README, this was more of an experimental project and performances are poor
• everything is ready to run the Solomon instances, which is great, but I think they run the data sets with the first 26 nodes, while all the benchmarks out there use the 25 first nodes. We'll see if we can tweak their script to take the first 25 ones only.

[Kuifje02]

I have added a folder here with csv files with CVRP (Augerat) results run with Clarke&Wright, vrpy, ortools and a jupyter notebook where the performance profile is generated (for some reason the notebooks sometimes fail to load correctly on github).

• If the results are always in this format (csv with columns unchanged, the performance profile will be automatically generated when running the notebook)

• These tests were run some time ago and should be definitely be run again (the vrpy ones).

[torressa]

Cool! Thanks man I think it's not displaying properly because the output of the cell is too long, so it's not closed. It might be plotly's fault. I've reran it and used matplotlib and it looks good :ok_hand: @Halvaros is writing some code to write the csv files. It'll super useful to compare all the different solving variants (pricing strategies, subproblem solver, diving, ...) So we can update the vrpy tables soon!

[Kuifje02]

I have done some tests with py-ga-VRPTW and here is what I think :

• The coding style is not very user friendly, it is not well structured and lacks comments. This is contrasting with the quality of the README, which is very very detailed.

• I was not able to find a feasible solution for solomons instances with 25 nodes (it always violates the upper time window)

Unless we are able to find feasible solutions, I no longer think benchmarks with the library are relevant. Perhaps a little paragraph in the paper is sufficient. To be fair, the author does warn that the performances are poor.

I will continue trying to find a feasible solution just in case. I have also raised an issue, maybe they can help us out.

[Kuifje02]

Other (non python) VRP libraries that could be mentioned in the paper (#44 ) (and benchmarked if doable, or if results found in some paper ?) include:

• VRP Spreadsheet solver (Excel)

• LKH (C)

• OptaPlanner (Java)

• GraphHopper (Java)

• Vroom (C++)

• VRPSolver (Julia) -> This one I believe has the best performances out there...

Also, note that some of these libraries non open source and/or free for academic use only.

[torressa]

PR #51 is the csv writer

[Kuifje02]

Unless we are able to find feasible solutions, I no longer think benchmarks with the library are relevant. Perhaps a little paragraph in the paper is sufficient. To be fair, the author does warn that the performances are poor.

I will continue trying to find a feasible solution just in case. I have also raised an issue, maybe they can help us out.

From here : https://github.com/iRB-Lab/py-ga-VRPTW/issues/12#issuecomment-656851376 :

"You are right. I am afraid that this project is not even close to a robust solution"