Skip to Main content Skip to Navigation
Journal articles

Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking

Abstract : As shown in recent researches, the costs in distribution systems may be excessive if routes are ignored when locating depots. The location routing problem (LRP) overcomes this drawback by simultaneously tackling location and routing decisions. This paper presents a new metaheuristic to solve the LRP with capacitated routes and depots. A first phase executes a GRASP, based on an extended and randomized version of Clarke and Wright algorithm. This phase is implemented with a learning process on the choice of depots. In a second phase, new solutions are generated by a post-optimization using a path relinking. The method is evaluated on sets of randomly generated instances, and compared to other heuristics and a lower bound. Solutions are obtained in a reasonable amount of time for such a strategic problem. Furthermore, the algorithm is competitive with a metaheuristic published for the case of uncapacitated depots.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02507805
Contributor : Daniel Gavrysiak <>
Submitted on : Friday, March 13, 2020 - 3:25:45 PM
Last modification on : Wednesday, May 20, 2020 - 11:58:04 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Christian Prins, Caroline Prodhon, Roberto Wolfler Calvo. Solving the capacitated location-routing problem by a GRASP complemented by a learning process and a path relinking. 4OR: A Quarterly Journal of Operations Research, Springer Verlag, 2006, 4 (3), pp.221-238. ⟨10.1007/s10288-006-0001-9⟩. ⟨hal-02507805⟩

Share

Metrics

Record views

73