feature suggestion: min-max optimization

[nielsenko]

Vroom tries to minimize the overall cost of solutions, but often it is useful to find a solution such that the most expensive route is as cheap as possible, hence the name min-max. This has interesting consequences for how jobs are initially partitioned and how jobs are moved between routes during the search phase. Such a solution will utilize all possible vehicles, and the cost of routes will be fairly balanced.

Fx. if you have 4 drivers available on a given day, you can argue that it is better to have them all working 6 hours shifts, than having 3 working 7 hours shifts, and the last driver working a 2 hour shift, since you need to pay all drivers for full work-day anyway, and your last served customer will be served faster with the balanced plan.

I think a good starting point is this article from 2007: https://web.stanford.edu/~yyye/MDVRP-JGSWY.pdf

I'm wondering if this is something you see vroom supporting down the line?

[jcoupey]

No plan for this right now but maybe worth considering at some point, so I'm flagging this to keep track of the feature request.

This is only relevant for use-cases where the fleet is oversized compared to the workload. Even then we already have ways to circumvent the problem. In your example, you could manually reduce the available working hours for all drivers to "force" a more balanced solution. A bit hacky and obviously not as flexible but does not require to mess with the optimization objective.

I'm always cautious about objective changes. First because using the overall travel time as main objective is part of the reason we enjoy a very fast convergence: during the local search phase, all gain evaluation and validity checks are performed in constant time (at least for CVRP, and not much more with time window constraints). Hence evaluating other metrics could have a huge impact on computing times. In this case, maybe we could come up with cheap ways to recompute the required end dates. But second, switching objectives would probably require to adjust the whole local search phase, to an extent that is difficult to determine without trying.

[jcoupey]

Also thanks for the reference, the region partition approach described in the paper does ring a bell with the current clustering heuristic implemented for CVRP.

[myleftshoe]

@nielsenko, agreed. If you have X drivers turning up to work and the first always gets a full 8 hr shift and the last few or zero you may have some complaints.

[nielsenko]

@myleftshoe exactly - and the increase in total cost is typically neglisable.

@jcoupey Have you considered the benefit of min-max optimization from an algorithmic perspective? Ie. that you don't have to optimize on the number of vehicles. All vehicles should be used, so the search space is greatly reduced.

But hey, this is open-source, if we need it bad enough, then we should start coding :-)

[jcoupey]

If you have X drivers turning up to work and the first always gets a full 8 hr shift and the last few or zero you may have some complaints.

Sure. But again this only happens when the fleet is oversized, and then you still have some ways to work around the problem, see e.g. #225. Probably a bit hacky but still a decent way to ensure the solution is acceptable while mitigating the overall cost increase.

Have you considered the benefit of min-max optimization from an algorithmic perspective?

I'm not sure we'd reduce the search space that way. We're currently not optimizing on the number of vehicles, just overall travel time. It just happens that leaving a vehicle aside is usually cheaper on this metric.

But hey, this is open-source, if we need it bad enough, then we should start coding :-)

Way to go ! ;-) To be honest this is not something that have been reported as critical for my own use-cases, so I'll probably spend way more time on other topics before this comes at the top of the pile.

[myleftshoe]

Was going to do it like this:

1. Get initial optimization with standard time windows for each vehicle.
2. If some vehicle routes are maxed an others under, reduce vehicle time windows by a percentage and re-optimize.
3. Possibly repeat 2 until a balanced solution is acheived

[jcoupey]

@myleftshoe yep, same idea as https://github.com/VROOM-Project/vroom/issues/225#issuecomment-481305597.

[jcoupey]

I don't see this being included as such in the current solving approach any time soon. Note that we now have more ways to get around initial concerns in this topic. For example balancing routes can happen using #421 or other similar constraints. The need to use all vehicles and minimize completion time is somehow addressed in #466 too.