The optimization of multi-UAVs patrol path with hybrid genetic algorithm

doi:10.3785/j.issn.1008-9497.2024.01.004

Journal of Zhejiang University (Science Edition)

2024, Vol. 51

Issue (1): 21-28 DOI: 10.3785/j.issn.1008-9497.2024.01.004

Mathematics and Computer Science

The optimization of multi-UAVs patrol path with hybrid genetic algorithm

Guojun LI¹,Ziwan ZHENG²(

),Yingsheng FAN¹,Tiantian LU¹,Zhijiang XU³

^1.Basic Courses Department，Zhejiang Police College，Hangzhou 310053，China
^2.School of Big-Data and Network Security，Zhejiang Police College，Hangzhou 310053，China
^3.School of Automation，Zhejiang Institute of Mechanical & Electrical Engineering，Hangzhou 310053，China

Download:

HTML( 4 )

PDF(940KB)
Export: BibTeX | EndNote (RIS)

Abstract

Aiming at the optimization of multi-UAVs patrol path, a patrol model of multi-UAVs based on hybrid genetic algorithm is proposed. When constructing the patrol model, each UAV must start from the police station and return to the police station at the end of the patrol. The algorithm is designed by combining traditional genetic algorithm and hill-climbing algorithm. In order to achieve a better optimization effect, the roulette wheel method is employed to select the excellent individuals with higher probability when selecting individuals of the population. In the application of genetic algorithm, the rules of gene crossover and mutation adapted to path optimization are defined. The simulation results show that the proposed hybrid genetic algorithm is significantly better than the traditional genetic algorithm on the optimization effect.

Key words： genetic algorithm hill-climbing algorithm patrol path optimization

Received: 01 February 2023 Published: 10 January 2024

CLC:

O 224

Corresponding Authors: Ziwan ZHENG E-mail: zhengziwan@zjjcxy.cn

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Guojun LI
	Ziwan ZHENG
	Yingsheng FAN
	Tiantian LU
	Zhijiang XU

Cite this article:

Guojun LI,Ziwan ZHENG,Yingsheng FAN,Tiantian LU,Zhijiang XU. The optimization of multi-UAVs patrol path with hybrid genetic algorithm. Journal of Zhejiang University (Science Edition), 2024, 51(1): 21-28.

URL:

https://www.zjujournals.com/sci/EN/Y2024/V51/I1/21

基于混合遗传算法的多无人机巡逻路径优化

假设无人机巡逻的起、终点均为派出所，提出了一种融合传统遗传算法和爬山算法的警用无人机巡逻路径优化模型——混合遗传算法。按照轮盘赌法则，进行种群个体的选择，以增大优秀种群个体被选中的概率，达到较好的优化效果。同时定义了与路径优化相适应的基因交叉和变异规则。仿真结果表明，提出的混合遗传算法在寻优效果上明显优于传统遗传算法。

关键词： 遗传算法, 爬山算法, 巡逻, 路径优化

Fig.1 Flow of path planning algorithm

Fig.2 Schematic diagram of the relative positions of some patrol points under the jurisdiction of Changhe Police Station

Table 1 Relative coordinate information of patrol points and cruise time of patrol points

Fig.3 Patrol path of the best individual in the first generation population

Fig.4 Optimal patrol path after 200 iterations

Fig.5 Shortest path changes during iteration process

Table 2 Results of 20 runs when population size is 80

Table 3 Results of 20 runs when population size is 200


[1]	卢文忠，杨俊峰. 抗疫精神融入公安院校治安学专业课程的教学实践探索［J］. 铁道警察学院学报， 2022， 32（6）： 120-124. DOI：10.19536/j.cnki.411439. 2022.06.020 LU W Z， YANG J F. Exploring the teaching practice of integrating the spirit of anti epidemic into the public security course in public colleges and universities［J］. Journal of Railway Police College， 2022， 32（6）： 120-124. DOI：10.19536/j.cnki.411439. 2022.06.020 doi: 10.19536/j.cnki.411439. 2022.06.020

[2]	邹青，刘小丽. 屯警街面全天候巡逻：潜江市推出警务综合服务新模式［J］. 领导科学论文（下）， 2015（4）： 37-38. DOI：10.3969/j.issn.2095-5103.2015. 04.015 ZOU Ｑ， LIU X L. Police patrol on the street all day ： Qianjiang city launched a new model of comprehensive police service［J］. Leadership Science Thesis （Volume II）， 2015（4）： 37-38. DOI：10.3969/j.issn.2095-5103.2015.04.015 doi: 10.3969/j.issn.2095-5103.2015.04.015

[3]	董晓霖. 大数据在社会治安防控中的应用探索［J］. 中国新通信， 2021， 23（13）： 147-148. DOI：10.3969/j.issn.1673-4866.2021.13.075 DONG X L. Application of big data in social security prevention and control［J］. China New Communications， 2021， 23（13）： 147-148. DOI：10.3969/j.issn.1673-4866.2021.13.075 doi: 10.3969/j.issn.1673-4866.2021.13.075

[4]	张叶彤. 社区警务网格化管理的优化研究：以南京市G区J派出所为例［D］. 南京：南京大学， 2019. ZHANG Y T. Research on Optimizing Grid Management of Community Policing： J Police Station in G District， Nanjing City is Taken as an Case［D］. Nanjing： Nanjing University， 2019.

[5]	沈建十，叶宏杰. 关于深化完善社会治安巡逻防控体系建设的实践与思考：以宁波市社会治安四级巡逻防控体系建设为例［J］. 公安研究， 2012（12）：22-27. SHEN J S， YE H J. Practice and thinking on perfecting the construction of social security patrol prevention and control system： Take the construction of the four-level patrol prevention and control system of social security in Ningbo as an example［J］. Policing Studies， 2012（12）：22-27.

[6]	李路，王行愚，江开忠. 基于k阶不可逆邻接矩阵的警车巡逻［J］. 电气自动化， 2010， 32（4）： 32-34.DOI：10.3969/j.issn.1000-3886.2010.04.012 LI L， WANG X Y， JIANG K Z. Police cars patrol based on k-order irreversible adjacency matrix［J］. Electrical Automation， 2010， 32（4）： 32-34. DOI：10.3969/j.issn.1000-3886.2010.04.012 doi: 10.3969/j.issn.1000-3886.2010.04.012

[7]	吴思远. 全局最优警车巡逻区域最大覆盖调度策略［J］. 广西师范大学学报（自然科学版）， 2010（1）：96-99. DOI：10.3969/j.issn.1001-6600.2010.01.022 WU S Y. Global optimum maximal coverage scheduling strategy for police cars deployment［J］. Journal of Guangxi Normal University （Natural Science Edition） 2010（1）： 96-99. DOI：10.3969/j.issn.1001-6600.2010.01.022 doi: 10.3969/j.issn.1001-6600.2010.01.022

[8]	FRAZIER A E， BAGCHI-SEN S， KNIGHT J. The Spatio-temporal impacts of demolition land use policy and crime in a Shrinking city［J］. Applied Geography， 2013， 41：55-64. DOI：10.1016/j.apgeog.2013.02.014 doi: 10.1016/j.apgeog.2013.02.014

[9]	LERMAN Y， ROFE Y， OMER I. Using space syntax to model pedestrian movement in urban transportation planning［J］. Geographical Analysis， 2014， 46（4）：392-410. DOI：10.1111/gean.12063 doi: 10.1111/gean.12063

[10]	JIANG B， OKABE A. Different ways of thinking about street networks and spatial analysis［J］. Geographical Analysis， 2014， 46（4）： 341-344. DOI：10.1111/gean.12060 doi: 10.1111/gean.12060

[11]	SHIODE S， SHIODE N. Network-based space- time search-window technique for hotspot detection of street-level crime incidents［J］. International Journal of Geographical Information Science， 2013， 27（5）： 866-882. DOI：10.1080/13658816. 2012.724175 doi: 10.1080/13658816. 2012.724175

[12]	SHIODE S， SHIODE N， BLOCK R， et al. Space- time characteristics of micro-scale crime occurrences： An application of a network-based space-time search window technique for crime incidents in Chicago［J］. International Journal of Geographical Information Science， 2015， 29（5）： 697-719. DOI：10.1080/13658816.2014.968782 doi: 10.1080/13658816.2014.968782

[13]	WEISSBURD D L， GROFF E R， YANG S. The Criminology of Place： Street Segments and Our Understanding of the Crime Problem［M］. New York：Oxford University Press， 2012. DOI：10.1093/acprof：oso/9780195369083.001.0001 doi: 10.1093/acprof：oso/9780195369083.001.0001

[14]	DINC S， DINC I. Evaluation of unsupervised classification on police patrol zone design problem［C］// IEEE SoutheastCon 2018. St Petersburg： IEEE， 2018： 1-7. DOI：10.1109/secon.2018.8478908 doi: 10.1109/secon.2018.8478908

[15]	ALLEN B. Case study： Using crime data and open source data to design a police patrol area［J］. SMU Data Science Review， 2018， 1（1）： 1-22.

[16]	MUKHOPADHYAY A， CHAO Z， VOROBEYCHIK Y， et al. Optimal allocation of police patrol resources using a continuous-time crime model［C］// International Conference on Decision and Game Theory for Security. New York ： GameSec， 2016： 139-158. DOI：10.1007/978-3-319-47413-7_9 doi: 10.1007/978-3-319-47413-7_9

[17]	SAINT-GUILLAIN M， PAQUAY C， LIMBOURG S. Time-dependent stochastic vehicle routing problem with random requests： Application to online police patrol management in Brussels［J］. European Journal of Operational Research， 2020， 292（3）： 869-885. DOI：10.1016/j.ejor.2020.11.007 doi: 10.1016/j.ejor.2020.11.007

[18]	HUTT O K， BOWERS K， JOHNSON S D. The Effect of GPS refresh rate on measuring police patrol in microplaces［J］. Crime Science， 2021， 10（1）：1-14. DOI：10.1186 /s40163-021-00140-1 . doi: 10.1186 /s40163-021-00140-1

[19]	PIZA E L， GILCHRIST A M， CAPLAN J M， et al. The financial implications of merging proactive CCTV monitoring and directed police patrol： A cost-benefit analysis［J］. Journal of Experimental Criminology， 2016， 12（3）： 403-429. DOI：10.1007/s11292-016-9267-x doi: 10.1007/s11292-016-9267-x

[20]	RYDBERG J， MCGARRELL E F， NORRIS A， et al. A Quasi-experimental synthetic control evaluation of a place-based police-directed patrol intervention on violent crime［J］. Journal of Experimental Criminology， 2018， 14（1）： 83-109. DOI：10.1007/s11292-018-9324-8 doi: 10.1007/s11292-018-9324-8

[21]	CHEN X. Fast patrol route planning in dynamic environments［J］. IEEE Transactions on Systems Man and Cybernetics， Part A： Systems and Humans， 2012， 42（4）： 894-904. DOI：10.1109/tsmca.2012.2183361 doi: 10.1109/tsmca.2012.2183361

[22]	CHEN X. Police patrol optimization with security level functions ［J］. IEEE Transactions on Systems Man and Cybernetics Systems， 2013， 43（5）： 1042-1051. DOI：10.1109/tsmca.2012.2226025 doi: 10.1109/tsmca.2012.2226025

[23]	ZHU S， BUKHARIN A W， LU L， et al. Data-driven optimization for police beat design in South Fulton， Georgia［Z］. （2021-08-24）. https：//doi.org/10.48550/ arXiv.2004.09660.

[24]	ZHU S， WANG H， XIE Y. Data-driven optimization for police zone design［Z］. （2021-11-02）. https：//doi.org/10.48550/arXiv.2104.00535.

[25]	杨旭，王锐，张涛. 面向无人机集群路径规划的智能优化算法综述［J］. 控制理论与应用， 2020， 37（11）： 2291-2302. DOI：10.7641/cta.2020.00157 YANG X， WANG R， ZHANG T. Review of unmanned aerial vehicle swarm path planning based on intelligent optimization［J］. Control Theory & Applications， 2020， 37（11）： 2291-2302. DOI：10. 7641/cta.2020.00157 doi: 10. 7641/cta.2020.00157

[26]	郎茂祥，胡思继. 用混合遗传算法求解物流配送路径优化问题的研究［J］. 中国管理科学， 2002， 10（5）： 51-56. DOI：10.3321/j.issn：1003-207x.2002.05.011 LANG M X HU S J. Study on the optimization of physical distribution routing problem by using hybrid genetic algorithm［J］. Chinese Journal of Management Science， 2002， 10（5）： 51-56. DOI：10. 3321/j.issn：1003-207x.2002.05.011 doi: 10. 3321/j.issn：1003-207x.2002.05.011

[27]	胡小建，杨智. 基于混合遗传算法的多拣货小车路径规划研究［J］. 合肥工业大学学报（自然科学版）， 2022， 45（12）： 1715-1722. DOI：10.3969/j.issn.1003-5060.2022.12.019 HU X J， YANG Z. Research on path planning of multi-picking car based on hybrid genetic algorithm［J］. Journal of Hefei University of Technology（Natural Science）， 2022， 45（12）： 1715-1722. DOI：10.3969/j.issn.1003-5060.2022.12.019 doi: 10.3969/j.issn.1003-5060.2022.12.019

[28]	丛玉良，孙闻晞，薛科，等. 基于改进的混合遗传算法的车联网任务卸载策略研究［J］. 通信学报， 2022， 43（10）： 77-85. DOI：10.11959/j.issn.1000-436x.2022188 CONG Y L， SUN W X， XUE K， et al. Research on task offloading strategy of internet of vehicles based on improved hybrid genetic algorithm［J］. Journal on Communications， 2022， 43（10）： 77-85. DOI：10. 11959/j.issn.1000-436x.2022188 doi: 10. 11959/j.issn.1000-436x.2022188

[29]	张铁，胡亮亮，邹焱飚. 基于混合遗传算法的机器人改进摩擦模型辨识［J］. 浙江大学学报（工学版）， 2021， 55（5）： 801-810. DOI：10.3785/j.issn.1008-973X.2021.05.001 ZHANG T， HU L L， ZOU Y B. Identification of improved friction model for robot based on hybrid genetic algorithm［J］. Journal of Zhejiang University（Engineering Science）， 2021， 55（5）： 801-810. DOI：10.3785/j.issn.1008-973X.2021.05.001 doi: 10.3785/j.issn.1008-973X.2021.05.001

[30]	张玉州，徐廷政，郑军帅. 基于混合遗传算法的紧急程度不确定应急物流问题求解［J］. 系统科学与数学， 2020， 40（4）： 714-728. DOI：10.12341/jssms13847 ZHANG Y Z， XU T Z， ZHENG J S. Solving emergency logistics problem with uncertain urgency based on a hybrid genetic algorithm［J］. Journal of Systems Science and Mathematical Sciences， 2020， 40（4）： 714-728. DOI：10.12341/jssms13847 doi: 10.12341/jssms13847

[1]	Ran XIAO, Xinlei AN, Huimin QI, Shuai QIAO. Bifurcation analysis and parameter identification of HR neurons under electric field[J]. Journal of Zhejiang University (Science Edition), 2022, 49(6): 691-697.

[2]	LI Kangping, WANG Pengjun, ZHANG Huihong. The search of the best power polarity of ternary FPRM circuit based on simulated annealing genetic algorithm[J]. Journal of Zhejiang University (Science Edition), 2016, 43(2): 190-194.

[3]	BU Dengli. Hybrid genetic algorithm for MPRM minimization[J]. Journal of Zhejiang University (Science Edition), 2016, 43(2): 184-189.

[4]	HE Jiang -ping 1,TANG Jing -chang 1,TONG S Y 2. The application of genetic algorithms in LEED.[J]. Journal of Zhejiang University (Science Edition), 2000, 27(5): 503-507.

[5]	Deng Mingrong　Bao Yongguang　Shen Zuzhi. Genetic Algorithm for Optimization of Running a Thermal Power Plant [J]. Journal of Zhejiang University (Science Edition), 1998, 25(4): 24-27.

Viewed

Full text

Abstract

Cited

Shared

Discussed