Acta Geographica Sinica ›› 2011, Vol. 66 ›› Issue (2): 279-286.doi: 10.11821/xb201102013

Previous Articles    

An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location

ZHAO Yuan, ZHANG Xinchang, KANG Tingjun   

  1. School of Geography and Planning, Sun Yat-sen University, Guangzhou 510275, China
  • Received:2010-02-24 Revised:2010-05-30 Online:2011-02-20 Published:2011-03-31
  • Supported by:

    National Natural Science Foundation of China, No.40971216;41071246

Abstract: Site location by brute-force method is difficult for optimization due to massive spatial data and huge solution space under the constraint condition of multi-objective and large spatial resolutions. In this study, an improved ant colony optimization (ACO) based on multi-way tree is introduced to solve site location problem. Better solutions can be obtained swiftly according to the density of pheromone the ants leave on the search paths constructed in nested subspaces divided by means of the multi-way tree algorithm. First, the algorithm derived from ACO is aiming to search for an optimal path in space regardless of initial distribution, based on the behavior of ants seeking a path at a specific probability. Second, the multi-way tree algorithm's growth rate between search size and spatial scale is logarithmic, so the cost of searching increases slowly as the size of its input grows. The study area, located in Guangzhou city, is a densely populated region. The raster layers have a resolution of 92 m× 92 m with a size of 512 × 512 pixels. This optimization problem consists of two factors: population distribution and spatial distance. Comparison experiment between ACO based on multi-way tree and the simple search algorithm indicates that this method can produce closely related results with a greater convergence rate and spend less computing time. In conclusion, the proposed algorithm is important and suitable for solving site search problems.

Key words: site location, multi-way tree, ant colony optimization, Guangzhou