A genetic algorithm integrated with the initial solution procedure and parameter tuning for capacitated P-median problem

The capacitated p-median problem is a well-known location-allocation problem that is NP-hard. We proposed an advanced Genetic Algorithm (GA) integrated with an Initial Solution Procedure for this problem to solve the medium and large-size instances. A 3(3) Full Factorial Design was performed where three levels were selected for the probability of mutation, population size, and the number of iterations. Parameter tuning was performed to reach better performance at each instance. MANOVA and Post-Hoc tests were performed to identify significant parameter levels, considering both computational time and optimality gap percentage. Real data of Lorena and Senne (2003) and the data set presented by Stefanello et al. (2015) were used to test the proposed algorithm, and the results were compared with those of the other heuristics existing in the literature. The proposed GA was able to reach the optimal solution for some of the instances in contrast to other metaheuristics and the Mat-heuristic, and it reached a solution better than the best known for the largest instance and found near-optimal solutions for the other cases. The results show that the proposed GA has the potential to enhance the solutions for large-scale instances. Besides, it was also shown that the parameter tuning process might improve the solution quality in terms of the objective function and the CPU time of the proposed GA, but the magnitude of improvement may vary among different instances.