A Hybrid Genetic Algorithm with Multi-Population for Capacitated Location Routing

The capacitated location-routing problem involves determining the depots from a set of candidate-capacitated depot locations and finding the required routes for a fleet of vehicles starting from and ending at the selected depots to serve a set of customers such that the solution minimizes a cost function that includes the cost of opening the selected depots, the fixed utilization cost per vehicle used, and the total cost (distance) of the routes. This paper presents a hybrid genetic algorithm with multi-population, which includes an effective multi-depot edge assembly crossover to generate promising offspring from the perspective of both depot location and route edge assembly, a neighborhood-based local search to optimize the routes of each offspring solution, and a diversification-oriented mutation. Of particular interest is the multi-population scheme that organizes the population into multiple subpopulations according to the depot configurations being explored. Extensive experiments on four sets of 281 benchmark instances from the literature show that the algorithm performs remarkably well. Additional experiments are presented to gain insight into the role of the key elements of the algorithm.