Skip to Main content Skip to Navigation
Journal articles

A hybrid evolutionary algorithm for the periodic location-routing problem

Abstract : The well-known vehicle routing problem (VRP) has been studied in depth over the last decades. Nowadays, generalizations of VRP have been developed for tactical or strategic decision levels of companies but not both. The tactical extension or periodic VRP (PVRP) plans a set of trips over a multiperiod horizon, subject to frequency constraints. The strategic extension is motivated by interdependent depot location and routing decisions in most distribution systems. Low-quality solutions are obtained if depots are located first, regardless of the future routes. In the location-routing problem (LRP), location and routing decisions are tackled simultaneously. Here for the first time, except for some conference papers, the goal is to combine the PVRP and LRP into an even more realistic problem covering all decision levels: the periodic LRP or PLRP. A hybrid evolutionary algorithm is proposed to solve large size instances of the PLRP. First, an individual representing an assignment of customers to combinations of visit days is randomly generated. The evolution operates through an Evolutionary Local Search (ELS) on visit day assignments. The algorithm is hybridized with a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) to create feasible solutions and stops when a given number of iterations is reached. The method is evaluated over three sets of instances, and solutions are compared to the literature on particular cases such as one-day horizon (LRP) or one depot (PVRP). This metaheuristic outperforms the previous methods for the PLRP.
Document type :
Journal articles
Complete list of metadatas

https://hal-utt.archives-ouvertes.fr/hal-02476398
Contributor : Daniel Gavrysiak <>
Submitted on : Wednesday, February 12, 2020 - 4:21:27 PM
Last modification on : Thursday, February 13, 2020 - 1:35:02 AM

Identifiers

Collections

ROSAS | UTT | CNRS

Citation

Caroline Prodhon. A hybrid evolutionary algorithm for the periodic location-routing problem. European Journal of Operational Research, Elsevier, 2011, 210 (2), pp.204-212. ⟨10.1016/j.ejor.2010.09.021⟩. ⟨hal-02476398⟩

Share

Metrics

Record views

50