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

Abstract

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