Matrixrequest

[dooley]

I've sometimes fairly large problems (up ~ 20000 jobs, ~120 vehicles). Getting the matrices (duration, distance) from osrm via http-request requires a lot of time and resources. Getting the matrix from osrm ~ 9 minutes, changing format to vrp (rounding floats to ints) ~ 10 minutes (with php).

I think it would a nice to have if vrp-cli could request the matrices itself from libosrm, like vroom does. Maybe by using https://lib.rs/crates/rsc_osrm

[reinterpretcat]

I agree, it would be nice to support osrm matrix format directly. This would require to write some parser internally - not so complicated, but need to check their docs to see what is the difference.

Regarding integrating request logic, I don't think it is responsibility of the project. It is more for a commercial product.

Btw, how fast/good is the solver for your use case (20k jobs)? I would expect that you need to change default settings a bit to gain more performance (e.g. reduce exploration ratio of the algorithm)

[dooley]

Performance is not that bad, compared to vroom. I let it only run 5 hours and vrp could get a valid result (> all jobs delivered). vroom finishes the very same problem in 9-10 hours. With vrp i got larger overall distance, but - surprise- lesser tours. vrp with no objectives set and default settings. Maybe if i let vrp also run 9 hours, results would be comparable.

I'm trying vrp, because one can set a max distance for vehicles (in vroom we cannot and have to workaround that with timewindows) and we can set parameter to end after some time > think of a company which get the jobs and cannot wait 12 hours to get their tours.

[reinterpretcat]

Cool! Thanks for feedback!

You're getting less tours as default objective is hierarchical: first minimize amount of unassigned jobs, then - amount of tours, and last one - cost (which is implicitly affects the distance). You can play with different objectives, e.g. :

"objectives": [
    [
      {
        "type": "minimize-unassigned"
      }
    ],
    [
      {
        "type": "minimize-distance"
      }
    ],
    [
      {
        "type": "minimize-tours"
      }
    ],
    [
      {
        "type": "minimize-cost"
      }
    ],
  ]

(at the moment minimize-cost is required to be present). See documentation:

https://reinterpretcat.github.io/vrp/concepts/pragmatic/problem/objectives.html
https://reinterpretcat.github.io/vrp/examples/pragmatic/objectives/index.html

Important notes regarding big problems:

• if you have more than 16 CPUs, then you have to define parallelism settings. Otherwise, performance might degradate. Alternative would be to specify RAYON_NUM_THREADS=16 as environment variable which will limit data parallelism.
• you can limit amount of initial solutions to be built with init-size=1 (useful if building initial solutions takes time. Default is 7 initial solutions with 5% time quota)
• you can try to use --search-mode=deep which will make search more exploitative by avoiding default meta-heuristic algorithm (rosomaxa) and faster in terms of generations
• you can try ti use --heuristic=static which will trigger static selective hyper-heuristic. Theoretically it is faster, but might be less explorative in long runs

[dooley]

Currently i run the 20k-Job with 6 hours , but with maxDistance set and objectives

"objectives": [ [ { "type": "minimize-tours" } ], [ { "type": "minimize-unassigned" } ], [ { "type": "minimize-cost" } ], [ { "type": "balance-distance", "options": { "threshold": 0.01 } } ] ]

In fact my machine is a AMD Ryzen 9 3950x w/ 24 Threads. I'll try one by one the tips.

Thank you!

[reinterpretcat]

I would suggest to define minimize-unassigned objective before any other except maximize-value to make sure all jobs are assigned. Balancing objective has also some impact: maybe try to remove it if you care mostly about the total distance. Otherwise you can also try to assign it on the same level as a cost objective: they are conflicting and algorithm will try to balance them together using threshold parameter (see example here: https://reinterpretcat.github.io/vrp/examples/pragmatic/objectives/objective-balance-distance.html)

Regarding multiple CPUs, you can try to play with parallelism settings (can be set from json config or command line). I've used 16 threadpools with 8 thread per pool on 96 CPUs. Limiting to 16 when you have more cpus and big problem (I tested mostly on 1k) maybe a bit counterproductive.