A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem

Christian Prins (1) , Caroline Prodhon (1) , Roberto Wolfler Calvo (1)

1 LOSI - Laboratoire d'Optimisation des Systèmes Industriels

As shown in recent researches, in a distribution system, ignoring routes when locating depots may overestimate the overall system cost. The Location Routing Problem (LRP) overcomes this drawback dealing simultaneously with location and routing decisions. This paper presents a memetic algorithm with population management (MA|PM) to solve the LRP with capacitated routes and depots. MA|PM is a very recent form of memetic algorithm in which the diversity of a small population of solutions is controlled by accepting a new solution if its distance to the population exceeds a given threshold. The method is evaluated on three sets of instances, and compared to other heuristics and a lower bound. The preliminary results are quite promising since the MA|PM already finds the best results on several instances.

Domaines: Recherche opérationnelle [math.OC]

Christian Prins, Caroline Prodhon, Roberto Wolfler Calvo. A Memetic Algorithm with Population Management (MA|PM) for the Capacitated Location-Routing Problem. 6th Evolutionary Computation in Combinatorial Optimization European Conference, EvoCOP 2006, Apr 2006, Budapest, Hungary. pp.183-194, ⟨10.1007/11730095_16⟩. ⟨hal-02891678⟩