Planning methods / optimization steps

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

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.
  • 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).
    • 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 string 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 (I'd love to have a table here but I still have to find out how this works in PHPBB ;-) )
    • 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
I'm looking forward to your feedback,
Bernd
User avatar
Bernd Welter
Site Admin
 
Posts: 932
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 ( = iddle sequencing )

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

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


Return to PTV xTourServer

cron