Skip to Main content Skip to Navigation
Journal articles

A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem

Abstract : The two-echelon location-routing problem (LRP-2E) is raised by the design of transportation networks with two types of trips: first-level trips serving from one main depot a set of satellite depots, to be located, and second-level trips supplying customers from these satellites. In the proposed multi-start iterated local search (MS-ILS), three greedy randomized heuristics are used cyclically to get initial solutions. Each ILS run alternates between two search spaces: LRP-2E solutions, and travelling salesman (TSP) tours covering the main depot and the customers. The number of iterations allotted to a run is reduced whenever a known solution (stored in a tabu list) is revisited. MS-ILS can be reinforced by a path-relinking procedure (PR), used internally for intensification, as post-optimization, or both. On two sets with 24 and 30 LRP-2E instances, MS-ILS outperforms on average two GRASP algorithms and adding PR brings a further improvement. Our metaheuristic also surpasses a tabu search on 30 instances for a more general problem with several main depots. It is still effective on a particular case, the capacitated location-routing problem (CLRP): In a comparison with four published metaheuristics, only one (LRGTS, Prins et al., 2007) does better.
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02478139
Contributor : Daniel Gavrysiak <>
Submitted on : Thursday, February 13, 2020 - 5:23:11 PM
Last modification on : Friday, February 14, 2020 - 1:36:34 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Viet-Phuong Nguyen, Christian Prins, Caroline Prodhon. A multi-start iterated local search with tabu list and path relinking for the two-echelon location-routing problem. Engineering Applications of Artificial Intelligence, Elsevier, 2012, 25 (1), pp.56-71. ⟨10.1016/j.engappai.2011.09.012⟩. ⟨hal-02478139⟩

Share

Metrics

Record views

37