AvailableMachineTime = AMT (xTour1)

[Bernd Welter]

Hello guys,

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

Step 2 of 2: The optimization itself

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

The Available Machine Time = AMT

• 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 checkpoints
The frequenzy within the steps is based on

• ConstructionPhase: after every move (+)
• SequencingPhase: after every move (+)
• PostOptimization: after every iteration (-)

Depending on the used methods there might be some more checkpoints.In other words: the highest level of accuracy is available for sequencing and construction. The post optimization has the lowest flexibility.

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.

I hope this description enlights you and helps you to understand our optimization,

Kind regards Bernd

[a.henniger]

Hi Bernd,

it is possible to seperate the AMTs for
Constructionphase and Improvementphase?

the "Construction step" should theoretically run until it is finished.
without finishing this step the job is unusable.

so i think it is useful to seperate the different phases:
ATM Constructionphase = 86400 (maybe max 1 day)
ATM Improvementphase = 300

What do you think?

best regards André

[Joost]

Hello André,

This is not possible in a single call. However you can do this in 2 calls.

First call with "start sequencing", construction and "middle sequencing" steps enable and no available machine time set.
Second call (if needed) tour reduction, improvement and end sequencing enabled and a available machine time towards your liking.

You can pass the result plan of the first call with the second call as the input plan.

If you make sure that you do not delete the dima's between the 2 calls there will not be a notable change in performance. To do this make sure that the deleteAfterUsageattribute of you DistanceMatrixByRoad are set to false in the first call, and the deleteBeforeUsage to false in the second call.

With regards,
Joost