Planning methods / optimization steps (xTour1)

This forum deals with any kind of trip optimization whether it is automatic planning or manual dispatching, refering to transport orders or service planning.

Planning methods / optimization steps (xTour1)

Postby Bernd Welter » Tue Apr 07, 2015 1:54 pm

Hello xServer community,

Some days ago a customer asked me "what is th meaning of these optimization steps? How can I decide which one I should enable in my usecase?" and so I decided to gather some basic info here in the forum. Further more we will add such valuable information to our standard usecase documentation. Feel free to enable yourself for a better understanding and provide feedback to us so we can improve these texts for all users.

Here we are:

  • Some simple statements about the API itself. You can create new tour plans from scratch or provide an existing plan where we will try to optimize your goals.
  • It's all about heuristics - the complexity of tour planning requires to apply different strategies that will play with a large number of permutations to get so-called solutions that satisfy requirements and consider what is your optimum (As few vehicles as possible? Short distances? many more!) but it is not possible to guarantee the perfect optimum in 100% of the given cases.
  • update 14.5.2018 - violation handling: it's not guessing what you want. Remember a tour is called VALID if it does not violate the given constraints (timewindows, skills, capacities). A chain is called valid if all tours of the chain are valid - otherwise it is invalid. Imagine a multi-tours chain with a valid 1st, 2nd, ... tours and an invalid succeeding tour is producing an invalid chain. This is quite important to understand if you deal with input plans: invalid input chains will not be optimized because we can't determine how you want us to resolve a conflict in a tour. So if you face a result where some unscheduled orders seem to be "possible" on a first tour: this might be the cause of the chain's succeeding invalid tours.
  • It's iterative: those algorithms perform a lot of loops for the optimization and they always keep "the best known solution" in mind so from a theoretical point of view we might interrupt these loops and return what we already identified as a "solution". This is why we offer the AvailableMachineTime parameter (=AMT).
  • As interupting a loop requires a dedicated exit point in our algorithms source it might be necessary to complete at the least the existing loop. So applying an AMT of 30 seconds does not guaranty the current plan is returned after 30 seconds: if a check against AMT is positive we just decide to perform another loop which might exceed the 30seconds AMT. But more or less we prevent the algorithm to run much longer than necessary. Waiting for the algorithms to terminate might take hours or even days if the scenario is large (hundreds of vehicles, thousands of orders).
  • Within these steps we offer different algorithms with the same goals but different behaviour in performance (result quality versus computation time). It's like sorting data:
    you may use QuickSort, BubbleSort, ... If you know more about the data (is uniqueness guaranteed? How many records do you want to sort) you may be able to apply the proper algorithm (are there time windows? How many vehicles do you want to optimize?)...
  • Available steps: Depending on the current conditions of a planning scenario we offer various steps. The following chapter tries to enable you for a better understanding of these steps and should help you to decide when to apply which step in your usecase.

    • startSequencingStep (sSEQ): optimizes the sequence of given input tours. This might improve the input for the succeeding construction step. So enabling this step is only meaningful if you provide a non empty input plan.
    • constructionStep (CON): This phase is the only one that creates new tours based on the chosen algorithms strategy. This phase usually creates good starting tours within a short period of time.
    • middleSequencingStep (mSEQ): This step applies the same algorithm as startSequencing and is meaningful if you just ran a construction phase. (Personal statement: reminds me of defragmenting a disk after I performed a cleanup of files.)
    • tourReductionStep (TR): tries to resolve existing tours (by merging their stops to other tours, even different target tours). Meaningful only if the potential of "being able to resolve a tour" is high (e.g. many tours available construction phase). Definetly not meaningful if the available tours are "full" (no available "space" to accept a stop from a resolved tour). Update 19.4.2018: tourReduction does not schedule orders which haven't been scheduled so far. So if you are not happy with a plan due to unscheduled orders it is not helpful to apply tourReduction. Furthermore the tradeoff between "tour reduction algorithm time" and "benefit due to saved costs" is not very high and this is why we recommend not to apply tour reduction unless you really need it.
    • improvementStep (IMP): applies a local search (or many local searches) to improve the existing plan. Let's compare this phase with climbing on top of a mountain: while Construction only accepts "uphill" movement the improvement accepts to climb down a little bit to get to a higher neighbour summit (=even better solution). The kind of manipulations on a plan is big: While sequencing and construction consider only manipulations within each tour (add unscheduled stops, change sequence within a tour..) the improvementPhase also considers moving orders from one tour to another tour or swapping orders between tours. This enables improvement to get better results but with a strong impact on the computation time. It is not meaningful to apply this phase without an existing plan (waste of time with not that good perspective to proper results).
    • endSequencingStep (eSEQ): Same as with the other secuencing steps, just meaningful as a clean up after improvement step. Just some basic moves to improve the existing plan. But: do not expect too much gain in quality here. In most cases the benefit isn't significant though there might be some scenarios where the impact is big.
    • Basics about sequencing steps: If you want to import and sequence an existing plan it is sufficient to apply just one of the sequencing steps. The result is the same then.
    • To simplify your workflow you may enable startSequencing even if no input plan is available because in this case it doesn't waste much time.
    • Enabling TourReduction within Balancing is not meaningful: this contradicts to the definition of balanced tours
  • So now it is up to you to define your algorithm packages. While some of you may prefer to apply a "single shot" scenario (apply all steps in one method call, simplifies code but might waste time) others could play with (check)+(construction+middleSequencing)+(check)+(improvement+endSequencing). "check" means to evaluate whether the conditions mentioned above are given and the apply the next group of algorithms.
  • Also quite important: what are the Default settings for given Planning scenarios? In fact they depend on the scenario:

    Phase / StepStartSeqConstructionMiddleSeqTourReductionImprovementEndSeq

    • Standard: CON,mSEQ,TR,IMP,eSEQ
    • Overnight: CON, mSEQ,TR,IMP,eSEQ,
    • Amending: sSEQ, CON, mSEQ,TR
    • Area: CON,mSEQ,TR, IMP,eSEQ
    • Balancing: sSEQ, CON,mSEQ,IMP, eSEQ
Update 21.09.2018: From my personal perspective it is not the best preconfiguration. As explained above the usage of TourReduction only applies in rare cases and so I recommend to disable (overwrite) this step via the API. Improvement by default is ok but at least you should be aware of it's time consuming behaviour and apply an AMT from the beginning. Another approach is to disable improvement and gather experience with the other steps. If the quality is insufficient then it is meaningful to activate Imrpovement+AMT.

I'm looking forward to your feedback,
User avatar
Bernd Welter
Site Admin
Posts: 1638
Joined: Mon Apr 14, 2014 10:28 am

Re: Planning methods / optimization steps

Postby Bernd Welter » Tue Sep 29, 2015 4:25 pm

And here is a little appendix:
The planSequence-method simply executes

  • sSEQ ( = start sequencing )
  • CON ( = construction )
  • mSEQ ( = middle sequencing )

Update 3.672019:
By the way: this is also important to know: sometimes players want to override the optimization goals via API. But: as these goals are part of IMPROVEMENT phase you can't override them in planSequence. PlanSequence won't execute IMPRO...

You can't override this behaviour via API :cry:
There you go!

User avatar
Bernd Welter
Site Admin
Posts: 1638
Joined: Mon Apr 14, 2014 10:28 am

Return to PTV xTourServer