A quantum evolutionary algorithm for spatial optimization of facility allocation

doi:10.11947/j.AGCS.2023.20210295

Abstract

Abstract: Spatial optimization of facility allocation that aims to form the spatial layout and dispatch plan of facilities is a typical high-dimensional multi-peak NP-Hard combinatorial optimization problem based on geographic information, operational research modeling, and urban planning. It is essential to improve the plan's quality to design and enhance the spatial optimization algorithm of facility allocation. This paper analyzes the critical characteristics in service facility allocation spatial optimization, introduces a real coding quantum evolution algorithm, and mainly establishes tetraploid quantum chromosome coding operator and capacity constraint operator for formulating the quantum evolution algorithm for spatial optimization of facility allocation (QEA-SOFA). Based on the emergency facility spatial optimization experiment, the QEA-SOFA algorithm can effectively improve the equality of the relocation optimization of emergency facilities by 66% compared with the real-coding genetic algorithm. The result demonstrates that the QEA-SOFA algorithm has better global search capability for high-dimensional multi-peak spatial optimization problems and has a more extensive search scale for local search of heterogeneous spatial regions, which reveals that the quantum evolution mechanism has a great deal of potential in solving geospatial optimization problems.

Key words: quantum evolution, spatial optimization, service facilities, location, spatial intelligence

CLC Number:

P209

ZHOU Xinxin, YUAN Linwang, WU Changbin, HAN Peipei, HUANG Jing, YU Zhaoyuan. A quantum evolutionary algorithm for spatial optimization of facility allocation[J]. Acta Geodaetica et Cartographica Sinica, 2023, 52(1): 142-154.

References

[1] LI Wenwen, CAO Kai, CHURCH R L. Cyberinfrastructure, GIS, and spatial optimization: opportunities and challenges[J]. International Journal of Geographical Information Science, 2016, 30(3): 427-431.
[2] 赵翔. 土地利用优化配置的多目标人工免疫优化模型研究[D]. 武汉: 武汉大学, 2013. ZHAO Xiang. Land use allocation optimization models based on multi-objective artificial immune systems[D].Wuhan: Wuhan University, 2013.
[3] 黎夏,李丹,刘小平.地理模拟优化系统(GeoSOS)及其在地理国情分析中的应用[J]. 测绘学报, 2017,46(10): 1598-1608.DOI: 10.11947/j.AGCS.2017.20170355. LI Xia, LI Dan, LIU Xiaoping. Geographical simulation and optimization system (GeoSOS) and its application in the analysis of geographic national conditions[J]. Acta Geodaetica et Cartographica Sinica, 2017,46(10): 1598-1608.DOI: 10.11947/j.AGCS.2017.20170355.
[4] 王楠, 吴巍, 胡细英, 等. 大型交通设施对房地产价格影响研究进展与评述[J]. 城市发展研究, 2018, 25(5): 13-18. WANG Nan, WU Wei, HU Xiying, et al. Research progress on the impacts of great traffic facilities on housing price[J]. Urban Development Studies, 2018, 25(5): 13-18.
[5] MCCORMACK R, COATES G. A simulation model to enable the optimization of ambulance fleet allocation and base station location for increased patient survival[J]. European Journal of Operational Research, 2015, 247(1): 294-309.
[6] TONG Daoqin, MURRAY A T. Spatial optimization in geography[J]. Annals of the Association of American Geographers, 2012, 102(6): 1290-1309.
[7] SHAREEFH, ISLAMM M, MOHAMEDA. A review of the stage-of-the-art charging technologies, placement methodologies, and impacts of electric vehicles[J]. Renewable and Sustainable Energy Reviews, 2016, 64: 403-420.
[8] 崔建鑫, 赵海霞. 城镇污水处理设施空间优化配置研究[J]. 中国环境科学, 2016, 36(3): 943-952. CUI Jianxin, ZHAO Haixia. Method for spatial optimal allocation of urban sewage treatment facilities[J]. China Environmental Science, 2016, 36(3): 943-952.
[9] 戴特奇, 廖聪, 胡科, 等. 公平导向的学校分配空间优化: 以北京石景山区为例[J]. 地理学报, 2017, 72(8): 1476-1485. DAI Teqi, LIAO Cong, HU Ke, et al. Secondary school allocation optimization towards equal access: a case study on Shijingshan District, Beijing[J]. Acta Geographica Sinica, 2017, 72(8): 1476-1485.
[10] DASKIN M S. Network and discrete location: models, algorithms, and applications[M]. 2nd ed Hoboken, New Jersey: John Wiley& Sons, Inc., 2013.
[11] DASKIN M S. What you should know about location modeling[J]. Naval Research Logistics, 2008, 55(4): 283-294.
[12] 谢顺平, 冯学智, 都金康. 基于网络Voronoi图启发式和群智能的最大覆盖空间优化[J]. 测绘学报, 2011,40(6): 778-784. XIE Shunping, FENG Xuezhi, DU Jinkang. Maximal covering spatial optimization based on network Voronoi diagrams heuristic and swarm intelligence[J]. Acta Geodaetica et Cartographica Sinica, 2011,40(6): 778-784.
[13] 程敏, 崔晓. 基于多目标改进免疫算法和GIS的养老机构空间配置优化研究: 以上海市虹口区为例[J]. 地理科学, 2018, 38(12): 2049-2057. CHENG Min, CUI Xiao. Spatial optimization configuration of the residential care homes based on the multi-objective improved immune algorithm and GIS:a case study of Hongkou District in Shanghai[J]. Scientia Geographica Sinica, 2018, 38(12): 2049-2057.
[14] 王海鹰, 秦奋, 张新长, 等. 基于蚁群优化算法的城市生态用地空间规划模型[J]. 地理科学, 2017, 37(3): 426-436. WANG Haiying, QIN Fen, ZHANG Xinchang, et al. The spatial planning model of urban ecological land based on ant colony optimization algorithm[J]. Scientia Geographica Sinica, 2017, 37(3): 426-436.
[15] FARAHANI R Z, FALLAH S, RUIZ R, et al. OR models in urban service facility location: a critical review of applications and future developments[J]. European Journal of Operational Research, 2019, 276(1): 1-27.
[16] 朱阿兴, 闾国年, 周成虎, 等. 地理相似性:地理学的第三定律?[J]. 地球信息科学学报, 2020, 22(4): 673-679. ZHU Axing, LÜ Guonian, ZHOU Chenghu, et al. Geographic similarity: third law of geography?[J]. Journal of Geo-Information Science, 2020, 22(4): 673-679.
[17] 王宝楠, 水恒华, 王苏敏, 等. 量子退火理论及其应用综述[J]. 中国科学: 物理学力学天文学, 2021, 51(8): 5-17. WANG Baonan, SHUI Henghua, WANG Sumin, et al. Theories and applications of quantum annealing: a literature survey[J]. Scientia Sinica(Physica,Mechanica & Astronomica), 2021, 51(8): 5-17.
[18] 范桁. 量子计算与量子模拟[J]. 物理学报, 2018, 67(12): 16-25. FAN Heng. Quantum computation and quantum simulation[J]. Acta Physica Sinica, 2018, 67(12): 16-25.
[19] 焦李成, 李阳阳,刘芳,等. 量子计算、优化与学习[M]北京:科学出版社. 2017. JIAO Licheng, LI Yangyang,LIU Fang,et al. Quantum computation, optimization and learning[M].Beijing:Science Press,2017.
[20] HAN K H, KIM J H. Genetic quantum algorithm and its application to combinatorial optimization problem[C]//Proceedings of the 2000 Congress on Evolutionary Computation.La Jolla, CA, USA:IEEE, 2002: 1354-1360.
[21] 钱洁, 王保华, 郑建国, 等. 多重二次背包问题的量子进化求解算法[J]. 计算机学报, 2015, 38(8): 1518-1529. QIAN Jie, WANG Baohua, ZHENG Jianguo, et al. A quantum evolutionary algorithm for quadratic multiple knapsack problem[J]. Chinese Journal of Computers, 2015, 38(8): 1518-1529.
[22] 吴伟彬, 刘哲, 杨昊, 等. 后量子密码算法的侧信道攻击与防御综述[J]. 软件学报, 2021, 32(4): 1165-1185. WU Weibin, LIU Zhe, YANG Hao, et al. Survey of side-channel attacks and countermeasures on post-quantum cryptography[J]. Journal of Software, 2021, 32(4): 1165-1185.
[23] 宋慧超, 刘晓楠, 王洪, 等. 基于Grover搜索算法的整数分解[J]. 计算机科学, 2021, 48(4): 20-25. SONG Huichao, LIU Xiaonan, WANG Hong, et al. Integer decomposition based on Grover search algorithm full text replacement[J]. Computer Science, 2021, 48(4): 20-25.
[24] SMITH-MILES K, LOPES L. Measuring instance difficulty for combinatorial optimization problems[J]. Computers& Operations Research, 2012, 39(5): 875-889.
[25] 周亮. 实数编码量子进化算法及在投资组合中的应用[D]. 上海: 东华大学, 2012. ZHOU Liang. Real-coded quantum evolutionary algorithm and its application in portfolio selection[D].Shanghai: Donghua University, 2012.
[26] HAN K H, KIM J H. Quantum-inspired evolutionary algorithm for a class of combinatorial optimization[J]. IEEE Transactions on Evolutionary Computation, 2002, 6(6): 580-593.
[27] 杨淑媛, 焦李成, 刘芳. 量子进化算法[J]. 工程数学学报, 2006,23(2): 235-246. YANG Shuyuan, JIAO Licheng, LIU Fang. The quantum evolutionary algorithm[J]. Chinese Journal of Engineering Mathematics, 2006,23(2): 235-246.
[28] 赵新泉, 彭勇行. 管理决策分析[M]. 2版. 北京: 科学出版社, 2000. ZHAO Xinquan, PENG (Yong)(Hang|Xing). Management decision analysis[M]. 2nd ed. Beijing: Science Press, 2000.
[29] 高辉, 张锐. 改进实数编码量子进化算法及其在参数估计中的应用[J]. 控制与决策, 2011, 26(3): 418-422. GAO Hui, ZHANG Rui. Improved real-coded quantum evolutionary algorithms and its application on parameter estimation[J]. Control and Decision, 2011, 26(3): 418-422.
[30] 李昆仑, 关立伟. 实数编码量子共生演算法及其在云任务调度中的应用[J]. 计算机应用研究, 2019, 36(3): 786-791. LI Kunlun, GUAN Liwei. Real-coded quantum SOS algorithm and its application in cloud task scheduling[J]. Application Research of Computers, 2019, 36(3): 786-791.
[31] 覃朝勇, 郑建国, 朱佳俊. 一种实数编码量子进化算法及其收敛性[J]. 控制与决策, 2009, 24(6): 854-858, 863. QIN Chaoyong, ZHENG Jianguo, ZHU Jiajun. Real-coded quantum-inspired evolutionary algorithm and its convergence[J]. Control and Decision, 2009, 24(6): 854-858, 863.
[32] 张宇献, 钱小毅, 彭辉灯, 等. 基于等位基因的实数编码量子进化算法[J]. 仪器仪表学报, 2015, 36(9): 2129-2137. ZHANG Yuxian, QIAN Xiaoyi, PENG Huideng, et al. Real-coded quantum evolutionary algorithm based on allele[J]. Chinese Journal of Scientific Instrument, 2015, 36(9): 2129-2137.
[33] 钱小毅. 基于等位基因量子进化算法的经纱断头率优化研究[D]. 沈阳: 沈阳工业大学, 2016. QIAN Xiaoyi. Study on the end breakage rate optimization for warp based on allele quantum evolutionary algorithm[D].Shenyang: Shenyang University of Technology, 2016.
[34] 高辉, 徐光辉, 张锐, 等. 实数编码量子进化算法[J]. 控制与决策, 2008,23(1): 87-90. GAO Hui, XU Guanghui, ZHANG Rui, et al. Real-coded quantum evolutionary algorithm[J]. Control and Decision, 2008,23(1): 87-90.
[35] BROTCORNE L, LAPORTE G, SEMET F. Ambulance location and relocation models[J]. European Journal of Operational Research, 2003, 147(3): 451-463.
[36] WANG Fahui. Measurement, optimization, and impact of healthcare accessibility: amethodological review[J]. Annals of the Association of American Geographers, 2012, 102(5): 1104-1112.
[37] 张宇山. 进化算法的收敛性与时间复杂度分析的若干研究[D]. 广州: 华南理工大学, 2013. ZHANG Yushan. Some studies on the convergence and time complexity analysis of evolutionary algorithms[D].Guangzhou: South China University of Technology, 2013.
[38] 何键浩, 李绿周. 量子优化算法综述[J]. 计算机研究与发展, 2021, 58(9): 1823-1834. HE Jianhao, LI Lüzhou. An overview of quantum optimization[J]. Journal of Computer Research and Development, 2021, 58(9): 1823-1834.
[39] JIA Jingyuan, WANG Bo. The development of intelligent operation method of urban public infrastructure driven by accurate spatio-temporal information[J].Journal of Geodesy and Geoinformation Science, 2021, 4(2): 27-35.
[40] GUO Mengyu, WANG Shaowen. Quantum computing for solving spatial optimization problems[M]. Cham: Springer International Publishing, 2020: 97-113.