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.

History: Accepted by Russel Bent, Area Editor for Network Optimization: Algorithms & Applications.

Funding: This work was supported by the National Natural Science Foundation of China [Grants 62403123, 72471100, and 72122006].

Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.0416) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2023.0416). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/.