from time to time customers are asking me at what moment in the tour planning call we compare the given maximum optimization time (also known as AMT = AvailableMachineTime) with the current computation time. So here are some simple facts that explain how to understand this approach - staring with some basics:
TourPlanning Flow
Step 1 of 2: Distance Matrix preparation
- Before we start the optimization itself we have to make sure that the required distance matrices are available - depending on the number of participating stops (pairwise non-equal coordinates) this might take a remarkable time as well.
- Within this initial step the distances may be computed based on simple airlines or on routing (map data required).
- Hint: ensure to use High Performance Routing if possible. For xServer INTERNET users this means to use one of the HPR-profiles.
- Hint: try to avoid recomputing distance matrices. If you want to play with the same orders (locations) by simply manipulating some of the planning constraints you should evaluate to re-use an existing distance matrix (set DistanceMatrixByRoad.deleteBefore=false, DistanceMatrixByRoad.deleteAfter=false).
- Optimization is based on heuristics (some of them with iterative loops, e.g. GTS), i.e. after an initial phase we have a first solution that satisfies the requirements
- By applying further more or less complicated algorithms to this first solution we improve the quality of the "best known solution for now"
- Hint: Depending on the used planning scenario (StandardParams, BalancingParams, ...) the preset of the available steps is set to true/false. The schema is described here: https://xserver.ptvgroup.com/forum/view ... ?f=6&t=143 For example you should at least be aware that Improvement is activated by default in Standard, Balancing and Overnight (the three most important approaches). So if your API call doesn't set them to FALSE they will be set to TRUE by the server.
- Those algorithms try to improve solutions by applying several classes of so-called moves like
- swapping two stops within a given tour to reduce time/period
- concatenating two tours to reduce number of tours and vehicles
- merging two tours to reduce number of tours and vehicles (only during construction phase)
- moving stops from one tour to another tour
- and many more
- Some of these algorithms will "roll back" once a move creates a degradation (still without violations but with worse cost value...) while others accept local declination as long as it doesn't exceed a certain level of degradation or produce violations.
- As we always have an existing "best known solution for now" we may interrupt the optimization process at various checkpoints and return this solution.
- This is the moment when AMT is considered:
At each checkpoint we compare the AMT value with the time already spent for processing the optimization. If the AMT value is exceeded we exit the step and return the “best known solution for now”. - The AMT refers to the step 2 only - the distance matrix computation is excluded!
- Even if the matrices are available in advance: The AMT does not guarantee a response within this time: if a single post optimization iteration requires 50 seconds and the AMT is set to 60 seconds, the response time is about 100 seconds and exceeds the AMT by 40 seconds.
The frequenzy within the steps is based on
- ConstructionPhase: after every move (+)
- SequencingPhase: after every move (+)
- PostOptimization: after every iteration (-)
Nice thread about AMT: https://xserver.ptvgroup.com/forum/view ... ?f=6&t=536
Hint
- Since we offer the asynchronus protocol that enables you to check KPIs of the "best known solution for now" during a planning you are enabled to interrupt an optimization ion progress if the KPIs are acceptable for you.
- A good distinction between different planning scenarios is
- IMPATIENT: Apply Construction, disable Improvement and TourReduction (and maybe apply an AMT). This will typically provide fast results but maybe not the global optimum
- PATIENT: Apply each and every available step and no AMT: might take quite a long time but provides the best quality (well, TourReduction is still a candidate for disabling
)
- THE TRUTH - is somewhere in between: Activate both Construction and Improvement (disable TourReduction) and set a meaningful AMT which reflects your macimum tolerance for waiting. Good compromise between performance and quality.
Kind regards Bernd