Title :
Applying Genetic Algorithm and Hilbert Curve to Capacitated Location Allocation of Facilities
Author :
Li, Xiang ; Liu, Zhengjun ; Zhang, Xihui
Author_Institution :
Key Lab. of Geogr. Inf. Sci., East China Normal Univ., Shanghai, China
Abstract :
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.
Keywords :
Hilbert transforms; curve fitting; facility location; genetic algorithms; Hilbert curve; chromosomes reproduction process; facilities capacitated location allocation; gene groups independency; genetic algorithm; unique-value operator; Artificial intelligence; Biological cells; Computational intelligence; Costs; Encoding; Genetic algorithms; Genetic mutations; Geography; Laboratories; Portable media players; GIS; Genetic Algorithm; Hilbert Curve; Location Allocation;
Conference_Titel :
Artificial Intelligence and Computational Intelligence, 2009. AICI '09. International Conference on
Conference_Location :
Shanghai
Print_ISBN :
978-1-4244-3835-8
Electronic_ISBN :
978-0-7695-3816-7
DOI :
10.1109/AICI.2009.11