search

VROOM-Project / vroom-scripts

BSD 2-Clause "Simplified" License
34 stars 20 forks source link

Iterative solving to minimize completion time #31

Closed jcoupey closed 2 years ago

jcoupey commented 2 years ago

I'd like to try a (somehow brutal) way to answer https://github.com/VROOM-Project/vroom/issues/466 without changing the default optimization objective in the core solving approach. The idea would be to solve the same problem iteratively with various planning horizons to come up with a set of trade-offs between completion time and overall cost.

Of course this means solving several times (variants of) the same problem so the impact on computing times may be far from negligible but this may do the job for some use-cases. Also this would highly depend on how we adjust the planning horizon. A simplistic approach of reducing iteratively might result in lots of calls but a dichotomic search of the sweet spot may be all we need in the end.

Another interest of this is that instead of delivering a single "minimum completion" solution, we could actually provide a set of different trade-offs between computing time and cost in the form of a Pareto front. There are indeed situations where the actual smallest completion time may not be the desirable outcome if it means a huge increase in cost.

jcoupey commented 2 years ago

A few notes on the implementation I have done in #32.

Finding the sweet spot for completion time minimization

Dichotomic search

Using dichotomy on the planning horizon end, we're able to quickly reach a good solution with regard to completion time that still has all tasks assigned. Below is an example of the Pareto front obtained on a sample instance. pareto-front

Backward search

A more naïve approach is to slightly reduce planning horizon end upon each iteration. It results in many more steps (actual intermediate solving with vroom) so it's longer but it also has the advantage of reaching out to many more trade-offs if one is interested in evaluating intermediate options. Blue dots are the front of solutions obtained this way, overlayed with the "dichotomy" solutions (only the different ones). pareto-front-more-solutions

Making the script easy to use

Run python3 asap.py -h for full options.

  1. The asap.py script can ingest the same command-line flags that vroom does, and will forward them upon each solve step. By default it returns the solution found with smallest completion time so it can be used out-of-the-box as a drop-in replacement for vroom, e.g. in vroom-express or in any workflow. Obviously computing times are longer.
  2. In order to avoid unnecessary recomputing of the matrix across several solve steps, the script takes care of populating the instance with the relevant matrices (using utils/matrix.py) so they are computed once and for all. This includes using OSRM (default and -r osrm option) or Openrouteservice (-r ors) via #33.
  3. Additionally --pareto-plot-file my_file allows to plot the Pareto front to my_file (see pictures above).
  4. Users that want to retrieve the full list of solutions should use the --pareto-front flag: it will break the usual vroom output schema, returning an array of solutions, instead of just one solution.
  5. By default, only the dichotomic search is performed for faster result, the full search with access to more intermediate solutions is available under --pareto-front-more-solutions.