Balancing: GuidedSavings for dummies...

[Bernd Welter]

Hi there,

today my tour optimization guru and I had to explain a result to a player and as the description might be helpful for others as well my buddy wrote the following text. Feel free to gather it for your own purpose - feedback is welcome!:

• Suppose you have 10 vehicles and want each driver to work equally long.
  When you use StandardParams (not BalancingParams), you may find that only 9 vehicles are used.
  Challenge: How can you enforce that 10 vehicles are used?
• GuidedSavings (balancingConstructionMethod) does what many dispatchers would do manually: Play around with the maxPeriod tour restriction.
  Let’s say the 9 drivers work for 90 hours in total.
  When we restrict the working time per driver (means maxPeriod tour restriction) to less than 10 hours, the algorithm will (most likely) have to use 10 vehicles!
• In general, we do the following:
  We decrease the maxPeriod parameter as long as not all vehicles are used (and the working time balance is not good enough).
• We increase the parameter again if some orders remain unscheduled.
  That is all the magic.
  Plain and simple.

  

• In some cases, there may not be a parameter setting in which all vehicles are used and all orders remain scheduled.
  Scheduled orders have a higher priority so we return the best solution with all orders scheduled even if that means that not all vehicles are used.
• The balancing quality of this approach varies: It may happen that, in our case, 9 tours are close to the maximum (with respect to the maxPeriod restriction) and therefore considered as “balanced”.
  And then there is one tour which is a lot shorter.
  This is certainly not perfect but the best that this approach can achieve.
• If you are not satisfied with the result, try the BalancedInsertion approach.
• In general, there is no “one click” solution for the balancing use case.
  It needs some manual interaction!

Thanks to the anonymous developer,

Bernd

PS: from my perspective the BalancingConstruction is some kind of a meta heuristic that iterates via changing the tour length and applies the standard planning under the roof.
PS2: check this German video for some more infos

[Bernd Welter]

Here's some little brain teaser for the story...

Some alternative representation of the approach

The setting for this ficticious example is based on

• 100 orders
• 10 vehicles

Now here are the changes through the iterations where I play with the maximum tour distance:

• Initial result based on 9 hours:
  • Only 7 vehicles used: BAD
  • all orders scheduled: good
  • ratio between shortest (0 km) and longest tour): 0 = BAD
  • Consecquence: reduce max tour period
• Iteration 2 : maximum tour period set to 7 hours
  • All vehicles scheduled : good
  • not all orders scheduled: BAD
  • Ratio : 0.95 : good
  • consequence: relax
• Iteration 3 : maximum tour period set to 8 hours
  • not all vehicles used: BAD
  • all orders scheduled: good
  • ratio : bad
  • consequence: reduce
• Iteration 4 : maximum tour period set to 7.5 hours
  • all vehicles scheduled : good
  • all orders scheduled: good
  • ratio : still not sufficient
  • consequence: reduce
• Iteration 5 : maximum tour period set to 7.25 hours
  • All vehicles scheduled
  • all orders scheduled
  • ratio within desired range
  • consequence: DONE