Solver Principles

• Tasha is built around the ruin and recreate principle and the adaptive large Neighbourhood search.
• The ruin and recreate principle effectively breaks parts of an initial solution and tries to rebuild it. It is known to be effective in complex solutions. In a large neighbourhood search the algorithm relaxes some constraints to permit large scale changes from the initial answer. Research indicates that these solver principles are known to produce better results but are more processing intensive. There is a lot of literature on these approaches: http://www.diku.dk/~sropke/Papers/PDPTW_techRep.pdf http://www.staff.uni-mainz.de/schneidj/papers/ruinandrecreate.pdf
• It is a stimulated annealing algorithm meaning that user defined settings dictate the scope of change during solution optimisation (small changes through to large scale change). This is configurable within the solver options.
• A key feature of the algorithm is its use of random numbers whilst solving which means that it is feasible to generate different answers to the same problem when other environmental factors remain unchanged.

Solver methodology:

• The solver creates an initial solution with data that comprises of both pickup and deliveries. This initial solution is normally very poor and inefficient but it is feasible.
• 1st heuristic is the ruin. Tasha looks at the solution and randomly takes a percentage of the solution out.
• Tasha uses 4 different types of ruin: Random, Geographic removal, Shaw removal (removes “time” clusters) and Vehicle removal.
• Each type of ruin is used at different points within the solver process. If a ruin doesn’t improve the solution it is unlikely to be reused.
• After the ruin the algorithm begins to recreate, by looking at how much it costs to load each stop onto the cheapest truck, then the second cheapest. It does not automatically load each stop onto its cheapest truck.
• The second heuristic is to fill each truck one by one
• The algorithm runs the ruin and recreate process repeatedly
• It is important to understand that this doesn’t necessarily find a better solution, it just explores an alternative to establish whether or not this is cheaper than the initial solution generated.
• Simulated annealing principle: The system begins at a user defined temperature. In the beginning the most dramatic solution changes are explored as the temperature cools down the changes are more minimal and predetermined somewhat by the original solution. As the temperature cools more inefficient solutions maybe explored. Eventually the solution cools down and then we can no longer accept more inefficient solutions.
• In complex scenarios you would apply a higher starting temperature but for simpler problem you would not apply a high temperature this is computationally inefficient.