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.
ZHAO Yuan, ZHANG Xinchang, KANG Tingjun
. An Ant Colony Algorithm Based on Multi-way Tree for Optimal Site Location[J]. Acta Geographica Sinica, 2011
, 66(2)
: 279
-286
.
DOI: 10.11821/xb201102013
[1] Kariv O, Hakimi S L. An algorithmic approach to network location problems (I): The p-centers. SIAM Journal AppliedMathematics, 1979, 37(3): 513-538.
[2] Kariv O, Hakimi S L. An algorithmic approach to network location problems (II): The p-medians. SIAM JournalApplied Mathematics, 1979, 37(3): 539-560.
[3] Cooper L. Location-allocation problems. Operations Research, 1963, 11: 331-343.
[4] Cooper L. Solutions of generalized location equilibrium problems. Journal of Research Science, 1967, 7: 1-18.
[5] Li Xia, Yeh A G O. Optimal spatial search using genetic algorithms and GIS. Acta Geographica Sinica, 2004, 59(5):745-753. [黎夏, 叶嘉安. 遗传算法和GIS结合进行空间优化决策的研究. 地理学报, 2004, 59(5): 745-753.]
[6] Yang Fengmei, Hua Guowei, Deng Meng et al. Some advances of the researches on location problems. OperationsResearch and Management Science, 2005, 14(6): 1-7. [杨丰梅, 华国伟, 邓猛等. 选址问题研究的若干进展. 运筹与管理, 2005, 14(6): 1-7.]
[7] Tabari M, Kaboli A, Aryanezhad M B et al. A new method for location selection: A hybrid analysis. AppliedMathematics and Computation, 2008, 206(2): 598-606.
[8] Mladenovi? N, Brimberg J, Hansen P et al. The p-median problem: A survey of metaheuristic approaches. EuropeanJournal of Operational Research, 2007, 179(3): 927-939.
[9] Fathali J. A genetic algorithm for the p-median problem with pos/neg weights. Applied Mathematics and Computation,2006, 183(2): 1071-1083.
[10] Brookes C J. A genetic algorithm for designing optimal patch configurations in GIS. International Journal ofGeographical Information Science, 2001, 15(6): 539-559.
[11] Aerts C J H, Heuvelink G B M. Using simulated annealing for resource allocation. International Journal ofGeographical Information Science, 2002, 16(6): 571-587.
[12] Lockwood C, Moore T. Harvest scheduling with spatial constraints: A simulated annealing approach. Canadian Journalof Forest Research, 1993, 23(3): 468-478.
[13] Bettinger P, Sessions J, Boston K. Using tabu search to schedule timber harvests subject to spatial wildlife goals forbig game. Ecological Modelling, 1997, 94(2): 111-123.
[14] Brumelle S, Granot D, Halme M et al. A tabu search algorithm for finding good forest harvest schedules satisfyinggreenup constraints. European Journal of Operational Research, 1998, 106(2): 408-424.
[15] Dorigo M, Stützle T. Ant Colony Optimization. London: The MIT Press, 2004: 65-67.
[16] Dorigo M, Gambardella L M. Ant colony system: A cooperative learning approach to the traveling salesman problem.IEEE Transaction on Evolutionary Computation, 1997, 1(1): 53-56.
[17] Dorigo M, Maniezzo V, Colorni A. Ant system: Optimization by colony of cooperating agents. IEEE Transactions onSystems, Man, and Cybernetics Part B, 1996, 26(1): 29-41.
[18] Dorigo M, Di C G, Gambardella L M. Ant algorithms for discrete optimization. Artificial Life, 1999, 5(3): 137-172.
[19] He Jinqiang, Li Xia, Liu Xiaoping et al. Ant colony algorithms for optimal site selection in large regions. Journal ofRemote Sensing, 2009, 13(2): 246-255. [何晋强, 黎夏, 刘小平等. 蚁群智能及其在大区域基础设施选址中的应用.遥感学报, 2009, 13(2): 246-255.]
[20] Raphael F, Bentley J L. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 1974, 4(1): 1-9.
[21] Zhao Wenji, Hu Zhuowei, Chen Yongliang et al. Quadtree-based three-dimensional visualization for thegeomorphologic data in multiple resolutions. Journal of Image and Graphics, 2007, 12(8): 1457-1462. [赵文吉, 胡卓玮, 陈永良等. 基于四叉树的多分辨率地形数据3 维可视化. 中国图象图形学报, 2007, 12(8): 1457-1462.]
[22] Chen Ye. Ant colony optimization algorithm for continuous function. Journal of Sichuan University: EngineeringScience Edition, 2004, 36(6): 117-120. [陈烨. 用于连续函数优化的蚁群算法. 四川大学学报: 工程科学版, 2004, 36(6): 117-120.]
