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). Update 24.2.2021: One additional element of the improvement phase is the object GoalImportance which applies only in the improvement phase. With these settings you can prioritize the local goals of the improvement steps known as VehicleCount, TourCount, ChainPeriod, TourPeriod, TourDrivingPeriod, TourDistance and UnplannedOrders.
    • 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
    Standardyesyesyesyesyes
    Overnightyesyesyesyesyes
    Amendingyesyesyesyes
    Areayesyesyesyesyes
    Balancingyesyesyesyesyes

    • 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.

Update 1.12.2020:
Though the following info does not refer to a "optimization" of a plan it can be relevant (as I encountered during a ticket today): There's an option to perform a post-processing of unscheduled orders (so-called UnscheduledOrderAnalysis). This additional task does not improve the quality of a plan at all - it just enables a user to gather information which triggers decisions. Depending on the number of orders in total this additional task could spend time on a significant level (whatever that means). I had a customer who asked for up to several hundred orders to be analysed and it took minutes to perform the analysis. In his case the reason for unscheduled orders was obvious: input workload is way more than the ressources could handle. In other words: be aware whether such an analysis is necessary or not!

Update 17.03.2021:
Just had a discussion about the algorithms of which you can choose during construction, improvement and sequencing steps. Here are his recommendations
- construction: always use cBasicCMAuto (this will choose between Savings and MergeSavings. Don't use cBasicCMInsertion as long as you haven't been told by DEV!
- improvement: always use cmIMGTS
- sequencing: use cSMAuto. Only use other algos such as StandardOpt or ThoroughOpt if really needed (require more time).


I'm looking forward to your feedback,
Bernd
Last edited by Bernd Welter on Wed Mar 17, 2021 5:08 pm, edited 6 times in total.
Reason: added a comment about UnscheduledOrderAnalysis
User avatar
Bernd Welter
Site Admin
 
Posts: 1803
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!

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

Re: Planning methods / optimization steps (xTour1)

Postby jmamy » Thu Sep 03, 2020 7:18 am

Hi Bernd,

• If improvementStep set to false, what is the objective function that the algorithm considers as by default?

• If the improvementStep is the one that takes the goalImportance into account. It is not necessary to pass a definition of goalImportance. What is the default if we don't define this goalImportance?

Thanks
Julien Mamy
Logistics Software Sales Engineer
PTV AMERICA
User avatar
jmamy
 
Posts: 31
Joined: Wed Jul 02, 2014 7:21 am

Re: Planning methods / optimization steps (xTour1)

Postby Bernd Welter » Thu Sep 03, 2020 8:39 am

Hello Julien,

here are the answers to your questions - if they are not sufficient I would need Alex/Frank to add their feedback:

Question 1: Objective function
This is described in the section "main objective" within this article: viewtopic.php?f=6&t=1085&p=3200#p3200 And of course you still have to be aware of the planning scenarios.

Question 2: Default goal importance for IMPROVEMENT
The default values of the planning scenarios are maintained in the famous TourOpt.INI which should not be changed without prior consultation of DEV. You don't have access to that file in the cloud anyway. Here's an extract of my TourOpt.ini (v1.30) - [DoBasicTourPlanning.Improvement]:
CostFactors.ImportanceRankCount = 4
CostFactors.VehicleCount = 50000,0,50000,100000
CostFactors.TourCount = 50000,0,50000,100000
CostFactors.ChainPeriod = 0,0,0,0
CostFactors.TourPeriod = 2,1,2,3
CostFactors.TourDrivingPeriod = 1,0,1,2
CostFactors.TourDistance = 0,0,1,2
CostFactors.UnplannedStops = 200000,200000,400000,800000
// Kostenwert eines Unplannend Stop wird genommen (entprechend dem eingestellten Rank) : value
// der Kostenwert entsprechend der Priorität ergibt sich value_i := value_(i-1) * UnplannedStopsByPrioFactor + value_0 * UnplannedStopsByPrioAddConstant
// Beispiel: Rank ist 2, Prio ist 3 -> value_0 = 200000
// value_1 := 200000 * 2.0 + 200000 * 1.0 = 500000
// value_2 = 500000 * 2.0 + 200000 * 1.0 = 1200000
CostFactors.UnplannedStopsByPrioFactor=2.0
CostFactors.UnplannedStopsByPrioAddConstant=1.0

Each one of the keys appears in the file multiple times and they can differ within each section...
[DoBasicTourPlanning.Improvement]
[DoTourBalancing.Improvement]
[DoTourAmending.Improvement]
[DoAreaTourPlanning.Improvement]


Best regards,
Bernd
Bernd Welter
Senior Technical Consultant Developer Components
PTV GROUP - Germany

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

Re: Planning methods / optimization steps (xTour1)

Postby Bernd Welter » Tue Dec 01, 2020 5:07 pm

added the following info to the core post...
Though the following info does not refer to a "optimization" of a plan it can be relevant (as I encountered during a ticket today): There's an option to perform a post-processing of unscheduled orders (so-called UnscheduledOrderAnalysis). This additional task does not improve the quality of a plan at all - it just enables a user to gather information which triggers decisions. Depending on the number of orders in total this additional task could spend time on a significant level (whatever that means). I had a customer who asked for up to several hundred orders to be analysed and it took minutes to perform the analysis. In his case the reason for unscheduled orders was obvious: input workload is way more than the ressources could handle. In other words: be aware whether such an analysis is necessary or not!
Bernd Welter
Senior Technical Consultant Developer Components
PTV GROUP - Germany

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

Re: Planning methods / optimization steps (xTour1)

Postby Bernd Welter » Wed Feb 24, 2021 9:14 am

added this to the original post:

Update 24.2.2021: One additional element of the improvement phase is the object GoalImportance which applies only in the improvement phase. With these settings you can prioritize the local goals of the improvement steps known as VehicleCount, TourCount, ChainPeriod, TourPeriod, TourDrivingPeriod, TourDistance and UnplannedOrders.
Bernd Welter
Senior Technical Consultant Developer Components
PTV GROUP - Germany

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

Re: Planning methods / optimization steps (xTour1)

Postby Bernd Welter » Wed Mar 17, 2021 5:09 pm

Update 17.03.2021:
Just had a discussion about the algorithms of which you can choose during construction, improvement and sequencing steps. Here are his recommendations
- construction: always use cBasicCMAuto (this will choose between Savings and MergeSavings. Don't use cBasicCMInsertion as long as you haven't been told by DEV!
- improvement: always use cmIMGTS
- sequencing: use cSMAuto. Only use other algos such as StandardOpt or ThoroughOpt if really needed (require more time).
Bernd Welter
Senior Technical Consultant Developer Components
PTV GROUP - Germany

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


Return to PTV xTourServer

cron