Initialization strategies to enhancing the performance of genetic algorithms for the p-median problem

Finding solutions to the p-median problem is an important research topic in location science. A number of meta-heuristic methods have been developed in the literature to find optimal or near optimal solutions to large-scale p-median problems within an acceptable computational time. Among these methods, the recent literature has demonstrated the effectiveness of genetic algorithms (GAs) and hybrid GAs. In this paper, we focus on the strategies of generating the initial population of a genetic algorithm and examine the impact of such strategies on the overall GA performance in terms of solution quality and computational time. Our initialization approach first produces a near optimal solution with low computational complexity, and then uses this solution as a seed to generate a set of solutions as the initial GA population, which is then used in an existing hybrid GA to test the performance of the proposed approach. Experiments based on the forty p-median problems in the OR Library are conducted. Results demonstrate that the proposed approach can significantly reduce computational time without compromising the quality of resulting solutions in almost all cases, and the excellence of the proposed approach increases with the problem scale. Furthermore, a geo-referenced dataset is also tested and the resulting solution maps visualize and validate the principle of the proposed approach.

► We initialize population of a genetic algorithm (GA) from a spatial perspective. ► Optimal medians cluster at most cases for p-median problem. ► Well-organized initial population outperforms a random one in a genetic algorithm.