search

Kuifje02 / vrpy

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

fixed number of vehicles #93

Closed piaulous closed 3 years ago

piaulous commented 3 years ago

Having an option to force the number of vehicles is something I would be interested in. This could be done by extending the num_vehicles command with something like use_all, or setting up min / max values for the number of vehicles.

Kuifje02 commented 3 years ago

The feature has been added. The argument is called use_all_vehicles (example in the docs here). Will make new relase by tomorow.

piaulous commented 3 years ago

Thank your very much!

piaulous commented 3 years ago

in some cases I now get an 'empty' route: ['Source', 'Sink']

Kuifje02 commented 3 years ago

Aha, this is interesting...re opening.

Kuifje02 commented 3 years ago

Ortools users have ran into this problem already : https://github.com/google/or-tools/issues/1351 :

This is generally a bad idea to add min values to cumul vars (e.g., number of used vehicles). You can easily run into infeasible problems. It would be better to constraint the max number of visits per vehicle.

If you want to model fairness, it should be reflected in the objective, not in hard constraints.

So @lperron basically suggests 3 options:

  1. Constrain the number of stops per routes in order to force the required number of vehicles. It can be tricky to find this value (the good number of stops).
  2. Use "fairness": minimize the maximum difference of duration between two routes. You can do this with the minimize_global_span argument: https://github.com/Kuifje02/vrpy/blob/96cc5501d05c341cc50f4377d15f27fbf422584a/vrpy/vrp.py#L74 But this changes the formulation and may lead to slower convergence.
  3. Add an "empty route" cost. I think this option may be the best (easy to implement, and not a hard constraint).
Kuifje02 commented 3 years ago

We can hard code the use_all option to enforce at least one visit with a warning that it is probably a bad approach and may lead to infeasible configurations. Or add an empty route cost, I think this is the way to go.

Kuifje02 commented 3 years ago

@piaulous routes ["Source","Sink"] how have a very high cost and should not be part of the solution. I am closing the issue for now. Feel free to re open it if the next release is not satisfactory.