多叉树蚁群算法及在区位选址中的应用研究

doi:10.11821/xb201102013

Abstract

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

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.

References

[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.]

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

PDF (PC)

Like

Knowledge

Cited

Abstract

Cite this article

share this article

References

Related Articles 15

Metrics

Comments

[1]	AN Ning,FENG Qiuyi,ZHU Hong. The spatial imagination of Guangzhou's African community: Analysis based on newspaper discourses [J]. Acta Geographica Sinica, 2019, 74(8): 1650-1662.
[2]	Rongping LIN, Suhong ZHOU, Xiaopei YAN. Intergenerational differences of spatio-temporal characteristics and influencing factors of home-work location changes since 1978: Empirical analysis based on the micro-survey in Guangzhou, China [J]. Acta Geographica Sinica, 2019, 74(4): 753-769.
[3]	XU Zhihua,LIU Kaizhi. State rescaling of the urban development in Hong Kong after the reunification: A case study of the planning process of the Hong Kong section of the Guangzhou-Shenzhen-Hong Kong Express Rail Link [J]. Acta Geographica Sinica, 2019, 74(2): 253-265.
[4]	YANG Ying,LIN Lin,ZHONG Zhiping,OU Yingying,XU Qian,MENG Meiyun,HAO Shan. Comprehensive evaluation and spatial differentiation of community resilience in Guangzhou based on response of the city to public health hazards [J]. Acta Geographica Sinica, 2019, 74(2): 266-284.
[5]	WU Rong,HUANG Xu,LIU Ye,LI Zhigang. Place attachment of urbanites in Guangzhou: Measurement and mechanism [J]. Acta Geographica Sinica, 2019, 74(2): 379-393.
[6]	YANG Wenyue,CAO Xiaoshu. The influence mechanism of travel-related CO₂ emissions from the perspective of residential self-selection: A case study of Guangzhou [J]. Acta Geographica Sinica, 2018, 73(2): 346-361.
[7]	CHEN Chun,YUAN Zhenjie,ZHU Hong. Floating children in Guangzhou: The construction of "home" in the context of urbanization [J]. Acta Geographica Sinica, 2018, 73(12): 2440-2451.
[8]	Suhong ZHOU, Jiangyu SONG, Guangwen SONG. Examining the dual-levels impact of neighbourhood and individual variables on car use on weekdays in Guangzhou [J]. Acta Geographica Sinica, 2017, 72(8): 1444-1457.
[9]	Zhangzhi TAN, Shaoyin LI, Xia LI, Xiaoping LIU, Yimin CHEN, Weixian LI. Spatio-temporal effects of urban rail transit on complex land-use change [J]. Acta Geographica Sinica, 2017, 72(5): 850-862.
[10]	Chenhao FU, Suhong ZHOU, Xiaopei YAN, Lin LIU, Weishan CHEN. Spatio-temporal characteristics and influencing factors of consumer behavior in retailing centers: A case study of Guangzhou in Guangdong Province [J]. Acta Geographica Sinica, 2017, 72(4): 603-617.
[11]	Wei TAO, Shaoxu WANG, Hong ZHU. Scavengers' bodily practices and spatial construction in Guangzhou [J]. Acta Geographica Sinica, 2017, 72(12): 2199-2213.
[12]	Haiyan TAO, Zhongzhe PAN, Maolin PAN, Li ZHUO, Yong XU, Miao LU. Mixing spatial-temporal transmission patterns of metropolis dengue fever: A case study of Guangzhou, China [J]. Acta Geographica Sinica, 2016, 71(9): 1653-1662.
[13]	Chunshan ZHOU, Jincan HU, Xinmei TONG, Yan BIAN. The socio-spatial structure of Guangzhou and its evolution [J]. Acta Geographica Sinica, 2016, 71(6): 1010-1024.
[14]	ZHU Hong, LI Rutie, SU Binyuan. The migrants' sense of place and its influencing factors on a microcosmic perspective:A case study of the migrants in the urban villages in Guangzhou [J]. Acta Geographica Sinica, 2016, 71(4): 637-648.
[15]	Shili CHEN, Haiyan TAO, Xuliang LI, Li ZHUO. Discovering urban functional regions using latent semantic information: Spatiotemporal data mining of floating cars GPS data of Guangzhou [J]. Acta Geographica Sinica, 2016, 71(3): 471-483.