An ELSxPath Relinking Hybrid for the Periodic Location-Routing Problem
Résumé
The well-known Vehicle Routing Problem (VRP) has been deeply studied over the last decades. Nowadays, generalizations of VRP are developed toward tactical or strategic decision levels of companies. The tactical extension plans a set of trips over a multiperiod horizon, subject to frequency constraints. The related problem is called the Periodic VRP (PVRP). On the other hand, 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 the future routes. In the Location-Routing Problem (LRP), location and routing decisions are simultaneously tackled. The goal here 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. Then, a heuristic based on the Randomized Extended Clarke and Wright Algorithm (RECWA) creates feasible solutions. The evolution operates through an Evolutionary Local Search (ELS) on visit days assignments. The algorithm is hybridized with a Path Relinking between individuals from an elite list. The method is evaluated on 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.