Speed tests for large scale problems

[ghost]

Hi, I am building a CVRP program with too many nodes. Currently, I am using Python and considering migrating to Rust.

I was wondering how fast this solver works? Google OR Tools solves a 1000+ node, 5 vehicle problem in around 5-6 hours with some node segmentation. Are there any benchmarks for this?

[reinterpretcat]

Hi, I would say it depends on hardware and your definition "problem solved". With my environment, laptop with Intel i7 12 cores, I have the following rough results for one of the reference problems:

• Problem from Gehring & Homberger benchmark, 1000 customers, RC1_10_1 instance. Reference results: best known solution is 90 vehicles and 45830.62 cost
• This solver results: initial solution in 500ms, 91 vehicle ~53000 cost in 5 minutes, best known cost: 90 vehicles, ~50000 cost in 2hrs (unstable, might be worse as the search is non-deterministic)

[ghost]

I mostly go for the optimal if possible since <24hrs solution time is viable for me. But these results already are way better than Python. Thanks a lot.

[thisduck]

@reinterpretcat Could you share the problem.json and other configuration for this problem? I would love to run the same problem on my machine to compare. Thanks!

[reinterpretcat]

Hi, it is not pragmatic (json) format, but solomon. You can use text file from the link above (https://www.sintef.no/globalassets/project/top/vrptw/homberger/1000/homberger_1000_customer_instances.zip). Regarding configuration, at the moment you need to use parallel options (passed either as cli argument or within config file) to enable multiple thread pools instead of one when you have more than 16 CPUs.

I would say, this is one of aspects where the project lakes of good default configuration which works for any hardware you have.

[reinterpretcat]

Here is the file:
RC1_10_1.txt

You can use it with:

./target/release/vrp-cli solve solomon RC1_10_1.txt --log --max-time=300

[thisduck]

Thank you!

[leobudima]

I have a potential situation where I would need to solve:

• 150.000 jobs across 1 month date range, where some of those jobs have 1-week time-window within that month, other can happen any time during the month

• each job has 6 potential pickup places and 1 delivery place, no other specific constraints (apart from 1month/1week date range mentioned above)

• each driver/vehicle has limit of 20 jobs per day and 8h working time

• crazy, but based on the above, I don't see any oportunity to segment work into multiple optimizations based on any criteria - (date ranges, pickup places, zones or anything else)...

I'm interested in any information or experience that would shed more light on:

• whether this is realistic / possible at all, with optimization time measured in something "reasonable", like 48 or 72h?

• any kind of approximate relation between solving time, number of cores at this scale? E.g. is 256/512 cores going to be significantly different than 128/256? Is there an upper limit, or any kind of approximate point that dictates when the diminisihing returns start?

• any specific approach (e,g, something like one configuration for initial solution to determine segmentation for subsequent optimizations with more demanding config?) that I could employ to get this done more manageably?

Thank you very much, highy appreciate any kind of advice or suggestions you can give!

[reinterpretcat]

Hi,

the strategy could be to split problem into sub-problems and solve them separately. For example, you can try to split jobs by weekly schedule, then by proximity for monthly time windowed jobs, etc.

Additionally, you can implement the logic to merge solutions back into one solution which will be an initial solution for the complete problem with all jobs. This will help to rearrange jobs to mitigate partitioning issues.

Regarding hardware configuration, I observed issues with default settings and 96 CPUs. I've introduced settings to address it, but it is far from the proper solution. Some work is needed here.

[leobudima]

Thanks a lot, @reinterpretcat - I see how segmenting the optimization and using joint calculated pieces to form the initial solution of the "whole" optimization could help. I'll experiment with it and report any findings here for the potential benefit of others. Cheers!