Planning and Optimization Methods for Advanced Urban Logistics Systems at Tactical Level - Sustainable Urban Logistics: Concepts, Methods and Information Systems - page 153

optima (10-25 % in average for medium size instances), they have the interest to
be easy to understand and implement and be applied to very large instances
(Jacobsen and Madsen 1980 ). The most used algorithms are the savings algorithm
of Clarke and Wright ( 1964 ), often combined with allocation algorithms (Madsen
1983 ), cluster-first route second algorithms, mainly using greedy or semi-greedy
algorithms (Gonzalez-Feliu et al. 2010 ; Gonzalez-Feliu and Salanova 2012 ). In the
two last cases, multi-depot multi-stakeholder problems were solved, the first with
homogeneous fleets per stakeholder, the second involving heterogeneous fleets.
Local Search (LS) algorithms are procedures that, starting from an initial
solution (mainly found using a construction heuristic method), iteratively analyze
a neighborhood surrounding S' in the solution search space (Aarts and Lenstra
1997 ). The neighborhood's exploration can be exhaustively carried out then the
best solution in the neighborhood is taken as current best and the algorithm is
restarted (Best Improvement) or the exploration can be interrupted immediately
after an improving solution is found and immediately restarted from the new
current best (First Improvement). Although LS is not directly used in many works,
it is broadly and usefully applied as an intensification tool into a metaheuristic
framework as Multi Start heuristics (Crainic et al. 2011 ) or combined with Evo-
lutionary Algorithms in hybrid or mimetic heuristics (Xu et al. 2013 ).
The Greedy Randomized Adaptive Search Procedure (GRASP) is a multistart
two-phase metaheuristic algorithm based on adapted greedy procedures (Resende
and Ribeiro 2010 ). In a first phase, an initial solution is obtained using a greedy
randomized procedure, whose randomness allows solutions in different areas of the
solution space to be obtained. The second phase is a local search phase that
improves these solutions. This algorithm is often hybridated with path-relinking
post-optimization (Nguyen et al. 2012 ; Crainic et al. 2013 ).
Alternate Large Neighborhood Search (ALNS) is an iterative post-optimization
algorithm (i.e. that needs an initial solution as input) that at every iteration, a
number customers are removed by a destroy operator, put in a customer pool and
then re-inserted by a repair operator (Hemmelmayr et al. 2012 ). Several local
search operators are used, selected by a roulette wheel mechanism based on their
past success. ALNS was first developed by Ropke and Pisinger ( 2006 ) for the
pickup and delivery problem and adapted to two-stage transport systems by
Hemmelmayr et al. ( 2012 ).
Last but not least, classical metaheuristic methods, like tabu search (Boccia
et al. 2010 ) or simulated annealing (Zegordi and Nikbakhsh 2009 ; Wang et al.
2011 ) or variable neighborhood search (Schwengerer et al. 2012 ) are also used.
For a more in-depth description of such methods applied to two-stage systems, see
Mancini ( 2013b ).