Balancing: GuidedSavings for dummies...

This forum deals with any kind of trip optimization whether it is automatic planning or manual dispatching, refering to transport orders or service planning.
Post Reply
User avatar
Bernd Welter
Site Admin
Posts: 2564
Joined: Mon Apr 14, 2014 10:28 am
Contact:

Balancing: GuidedSavings for dummies...

Post by 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.
    guidedsavings.PNG
  • 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
Technical Partner Manager Developer Components
PTV Logistics - Germany

Bernd at... The Forum,LinkedIn, Youtube, StackOverflow
I like the smell of PTV Developer in the morning... :twisted:
Post Reply