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 / Step StartSeq Construction MiddleSeq TourReduction Improvement EndSeq Standard yes yes yes yes yes Overnight yes yes yes yes yes Amending yes yes yes yes Area yes yes yes yes yes Balancing yes yes yes yes yes - 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 1.12.2020: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 17.03.2021: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!
I'm looking forward to your feedback,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
