Applying Genetic Algorithm and Hilbert Curve to Capacitated Location Allocation of Facilities

This paper introduces a Hilbert-curve-based genetic algorithm to solve capacitated location allocation facilities. Different from most existing approaches that target uncapacitated location-allocation problems, the proposed algorithm considers capacity constraints during the searching of facility sites. Genetic algorithm is employed and Hilbert curve is used to index demand points or spatial units and encode solutions as chromosomes of genetic algorithm. Compared with existing encoding strategies, the Hilbert-curve-based encoding strategy facilitates increasing the independency of gene groups in chromosomes. A fast method is developed to evaluate solutions or chromosomes and accelerate the reproduction process of chromosomes. A novel genetic operator, named unique-value operator, is proposed to fulfill the reproduction process. This operator makes full use of the advantages of Hilbert curve and combines both crossover and mutation operations. A series of experiments are conducted to validate the proposed approach in an application of locating shelters in Memphis, Tennessee.