基于混合遗传算法的海军航空兵场站物资配送车辆调度智能优化

doi:10.12305/j.issn.1001-506X.2023.12.20

摘要/Abstract

摘要：

为提升海军航空兵场站物资配送车辆调度效率, 根据海军航空兵场站物资配送任务特点, 建立了物资配送车辆调度优化模型, 提出了混合遗传算法(hybrid genetic algorithm, HGA)对模型进行了求解。在HGA中引入了模拟退火(simulated annealing, SA)操作对经典遗传算法(genetic algorithm, GA)进行了改进: 选择适合模型的编码方式和交叉算子; 使用类似路径构造的方法构建初始种群; 在遗传操作产生子种群之后, 通过SA操作寻找子种群邻域中的潜在优秀个体, 提升算法局部搜索能力。最后, 通过与经典GA的对比实验, 验证了所提算法的有效性和可靠性。

关键词: 混合遗传算法, 海军航空兵场站, 物资配送, 智能优化

Abstract:

In order to improve the scheduling efficiency of material distribution vehicles in naval aviation stations, an optimization model for material distribution vehicle scheduling is established based on the characteristics of material distribution tasks in naval aviation stations, and a hybrid genetic algorithm (HGA) is proposed to solve the model. The HGA introduces the simulated annealing (SA) algorithm operation to improve the classical genetic algorithm (GA): choosing the coding method and crossover operator suitable for the model; using a method similar to path construction to construct the initial population; after the genetic operation generating the sub-population, the SA operation is used to find the potential outstanding individuals in the sub-population neighbourhood to improve the local search ability of the algorithm. Finally, the effectiveness and reliability of the proposed algorithm are verified by comparing the experiments with the classical GA.

Key words: hybrid genetic algorithm (HGA), naval aviation station, material distribution, intelligent optimization

中图分类号:

E917

阎哲, 汪民乐, 汪江鹏, 闫少强, 吴丰轩. 基于混合遗传算法的海军航空兵场站物资配送车辆调度智能优化[J]. 系统工程与电子技术, 2023, 45(12): 3908-3914.

Zhe YAN, Minle WANG, Jiangpeng WANG, Shaoqiang YAN, Fengxuan WU. Intelligent optimization of vehicle scheduling for material distribution in naval aviation station based on hybrid genetic algorithm[J]. Systems Engineering and Electronics, 2023, 45(12): 3908-3914.

图/表 12

图1

图2

图3

图4

图5

图6

表1

表2

图7

图8

图9

图10

参考文献 29

1	NORIN A , YUAN D , GRANBERG T A , et al. Scheduling deicing vehicles within airport logistics: a heuristic algorithm and performance evaluation[J]. Palgrave Macmillan, 2012, 63 (8): 47- 49.
2	FENG L , MILLER-HOOKS E , SCHONFELD P , et al. Optimizing ridesharing services for airport access[J]. Transportation Research Record: Journal of the Transportation Research Board, 2014, 2467 (1): 157- 167. doi: 10.3141/2467-17
3	PADRON S , GUIMARANS D , JOSE R J , et al. A bi-objective approach for scheduling ground-handling vehicles in airports[J]. Computers & Operations Research, 2016, 71, 34- 53.
4	张积洪, 孟庆寿. 基于改进FCM和磷虾群算法的机场特种车辆调度优化[J]. 机床与液压, 2018, 46 (18): 112- 117.
	ZHANG J H , MENG Q S . Airport special vehicle scheduling optimization based on improved FCM and krill swarm algorithm[J]. Machine Tool and Hydraulic, 2018, 46 (18): 112- 117.
5	PADRON S , GUIMARANS D , JOSE R J , et al. A bi-objective approach for scheduling ground-handling vehicles in airports[J]. Computers & Operations Research, 2016, 71 (6): 34- 53.
6	JIA Y D , JENS O , BRUNNER R K . Planning towing processes at airports more efficiently[J]. Transportation Research, Part E: Logistics and Transportation Review, 2014, 70 (10): 293- 304.
7	XU X M , YE Z R , LI J , et al. Solving a large-scale multi-depot vehicle scheduling problem in urban bus systems[J]. Mathema-tical Problems in Engineering, 2018, (10): 4868906.
8	衡红军, 晏晓东. 实现多目标优化的机场特种车辆调度算法[J]. 计算机应用与软件, 2016, 33 (10): 238- 242. doi: 10.3969/j.issn.1000-386x.2016.10.053
	HENG H J , YAN X D . Airport special vehicle scheduling algorithm for multiobjective optimization[J]. Computer Applications and Software, 2016, 33 (10): 238- 242. doi: 10.3969/j.issn.1000-386x.2016.10.053
9	徐刚, 张磊, 贠永刚, 等. 多机种大机群再次出动保障资源配置仿真与优化[J]. 系统仿真学, 2021, 33 (4): 892- 899.
	XU G , ZHANG L , YUN Y G , et al. Simulation and optimization of support resource allocation for large multi aircraft clusters[J]. Journal of System Simulation, 2021, 33 (4): 892- 899.
10	赵红梦, 姜志侠, 曾坤. 一种用于公共自行车调度的改进GA-SA算法[J]. 计算机技术与发展, 2021, 31 (10): 184- 189.
	ZHAO H M , JIANG Z X , ZENG K . An improved GA-SA algorithm for public bicycle scheduling[J]. Computer Technology and Development, 2021, 31 (10): 184- 189.
11	段丽妮, 阚龙营. 基于蚁群算法的多车型物流车辆调度研究[J]. 物流科技, 2022, 45 (4): 14- 17.
	DUAN L N , KAN L Y . Research on multi vehicle logistics vehicle scheduling based on ant colony algorithm[J]. Logistics Technology, 2022, 45 (4): 14- 17.
12	曾胜, 戴贤君, 胡徐胜, 等. 基于蚁群算法对调度车辆进行路径最优化设计[J]. 自动化与仪表, 2022, 37 (4): 89-93, 98.
	ZENG S , DAI X J , HU X S , et al. Route optimization design of dispatching vehicles based on ant colony algorithm[J]. Automation and Instrumentation, 2022, 37 (4): 89-93, 98.
13	赵小瑾, 张开宇, 冯冬涵, 等. 基于强化学习的电动汽车集群实时优化调度策略[J]. 智慧电力, 2022, 50 (1): 53-59, 81.
	ZHAO X J , ZHANG K Y , FENG D H , et al. Real time optimal scheduling strategy for electric vehicle cluster based on reinforcement learning[J]. Smart Power, 2022, 50 (1): 53-59, 81.
14	赵法强, 袁汉凯, 宋泽均, 等. 基于Map Reduce的车辆移动云任务调度算法研究[J]. 自动化技术与应用, 2021, 40 (11): 89- 93.
	ZHAO F Q , YUAN H K , SONG Z J , et al. Research on vehicle mobile cloud task scheduling algorithm based on map reduce[J]. Automation Technology and Application, 2021, 40 (11): 89- 93.
15	冯明端, 肖雪, 周航. 机场地面保障多车型车辆联合调度模型研究[J]. 武汉理工大学学报(交通科学与工程版), 2023, 47 (1): 67- 72.
	FENG M D , XIAO X , ZHOU H . Research on joint dispatching model of multi vehicle types for airport ground support[J]. Journal of Wuhan University of Technology (Traffic Science and Engineering Edition), 2023, 47 (1): 67- 72.
16	曾强, 林凯, 王科峰. 基于B/S架构的物流配送车辆精细化调度[J]. 物流工程与管理, 2022, 44 (3): 101- 103.
	ZENG Q , LIN K , WANG K F . Refined scheduling of logistics distribution vehicles based on B/S architecture[J]. Logistics Engineering and Management, 2022, 44 (3): 101- 103.
17	汪民乐, 高晓光, 范阳涛. 先进遗传算法及其工程应用[M]. 西安: 西北工业大学出版社, 2019.
	WANG M L , GAO X G , FAN Y T . Advanced genetic algorithm and its engineering application[M]. Xi'an: Press of Northwestern Polytechnical University, 2019.
18	王文鹏, 邹刚, 张玎, 等. 基于自适应遗传算法的舰载机保障调度[J]. 兵工自动化, 2021, 40 (1): 37- 42.
	WANG W P , ZOU G , ZHANG D , et al. Shipborne aircraft support scheduling based on adaptive genetic algorithm[J]. Ordnance Industry Automation, 2021, 40 (1): 37- 42.
19	杨山亮, 黄健, 刘洋, 等. 基于遗传算法的联合火力WTA问题研究[J]. 计算机仿真, 2012, 29 (3): 61-63, 136.
	YANG S L , HUANG J , LIU Y , et al. Research on joint fire WTA problem based on genetic algorithm[J]. Computer Simulation, 2012, 29 (3): 61-63, 136.
20	高伟, 王俊义. 机场特种服务保障车辆优化调度研究[J]. 计算机仿真, 2019, 36 (4): 17- 23.
	GAO W , WANG J Y . Research on optimal scheduling of airport special service support vehicles[J]. Computer Simulation, 2019, 36 (4): 17- 23.
21	杨珏. 基于遗传算法的机场特种车辆调度应用研究[J]. 计算机技术与发展, 2019, 29 (3): 164- 168.
	YANG Y . Application research on airport special vehicle sche-duling based on genetic algorithm[J]. Computer Technology and Development, 2019, 29 (3): 164- 168.
22	吴凡, 杨冰, 洪思. 基于改进遗传算法的应急车辆调度研究[J]. 数学的实践与认识, 2021, 51 (18): 10- 23.
	WU F , YANG B , HONG S . Research on emergency vehicle scheduling based on improved genetic algorithm[J]. Practice and Understanding of Mathematics, 2021, 51 (18): 10- 23.
23	HOLLAND J. Adaptation in natural and artificial systems[D]. Ann Arbor: University of Michigan, 1975.
24	GOLDBERG D E . Genetic algorithm in search, optimization, and machine learning[M]. Massachusetts: Addision-Wisely, 1989.
25	KATOCH S , CHAUHAN S S , KUMAR V . A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80 (5): 8091- 8126.
26	岳晓鹏, 全启圳, 何月华. 基于模拟退火算法的公共自行车调度优化问题[J]. 科学技术创新, 2021, (36): 19- 21.
	YUE X P , QUAN Q Z , HE Y H . Public bicycle scheduling optimization problem based on simulated annealing algorithm[J]. Science and Technology Innovation, 2021, (36): 19- 21.
27	杨真真, 方秀男. 模拟退火算法及实例应用[J]. 中国科技信息, 2021, (15): 65- 66.
	YANG Z Z , FANG X N . Simulated annealing algorithm and its application[J]. China Science and Technology Information, 2021, (15): 65- 66.
28	李朝迁, 裴建朝. 新型模拟退火遗传算法在路径优化的应用[J]. 组合机床与自动化加工技术, 2022, (3): 52- 55.
	LI C Q , PEI J C . Application of new simulated annealing genetic algorithm in path optimization[J]. Modular Machine Tools and Automatic Machining Technology, 2022, (3): 52- 55.
29	毕义明, 李景文. 遗传算法及其军事应用[M]. 北京: 解放军出版社, 1998.
	BI Y M , LI J W . Genetic algorithm and its military application[M]. Beijing: PLA Publishing House, 1998.

序号	坐标/m	物资需求/t	物资接收最早/最晚时间/h	卸载时间/h
1	(1 500, 1 500)	0	0/20	0
2	(1 000, 300)	0.5	0/1	0.2
3	(1 050, 300)	0.3	0/1	0.2
4	(1 100, 300)	0.4	1/2	0.2
5	(1 150, 300)	0.4	0/1	0.2
				
40	(300, 850)	1.4	0/2	0.4
41	(300, 900)	2.3	8/9.5	0.3
42	(300, 950)	1.3	0/2	0.2
43	(300, 1 000)	1.5	3/5	0.3
				
70	(3 100, 1 900)	0.4	3/5	0.3
71	(3 150, 1 850)	0.7	10/11	0.3
72	(3 200, 1 800)	0.6	2/3.5	0.3
73	(3 250, 1 750)	0.9	9/10.5	0.2
				
98	(1 350, 3 250)	2.3	2/3	0.2
99	(1 400, 3 300)	1.2	5/7	0.3
100	(1 500, 3 400)	3.3	8/10	0.4

战机数量	使用算法	使用车辆数	总行驶距离	运算时间/s	运行时间倍数	车辆减少比例/%	距离减少比例/%
30	GA	10	35 310.88	42.32	4.94	10	1.78
30	HGA	9	34 682.44	209.19	4.94	10	1.78
50	GA	17	61 768.68	51.45	4.92	11.8	15.69
50	HGA	15	52 074.53	253.29	4.92	11.8	15.69
100	GA	24	101 320.22	77.16	4.21	16.7	17.51
100	HGA	20	83 578.43	325.03	4.21	16.7	17.51

[1]	张佳唯, 钱凤臣, 杨俊强, 赵骞, 张峥嵘. 弹性光网络中路由与频谱分配算法综述[J]. 系统工程与电子技术, 2022, 44(6): 2001-2010.
[2]	孙剑炜, 王超, 施庆展, 任文博, 尧泽昆, 袁乃昌. 基于遗传算法的相位调制波形智能优化[J]. 系统工程与电子技术, 2022, 44(3): 722-729.
[3]	高昂, 董志明, 李亮, 段莉, 郭齐胜. 面向LVC训练的蓝方虚拟实体近距空战决策建模[J]. 系统工程与电子技术, 2021, 43(6): 1606-1617.
[4]	杨永建, 禚真福, 黄柏儒, 樊晓光, 邓有为, 王彪. 物种生灭算法[J]. 系统工程与电子技术, 2018, 40(4): 941-947.
[5]	夏维, 刘新学, 范阳涛, 范金龙. 基于混合遗传BP神经网络的城市系统作战能力评估[J]. 系统工程与电子技术, 2017, 39(1): 107-113.
[6]	欧阳高翔, 王小丽, 孙成明, 杨新. 基于隐式基因混合遗传算法的多脉冲交会导引[J]. 系统工程与电子技术, 2015, 37(12): 2810-2816.
[7]	王连锋，宋建社，王正元，曹继平. 带硬时间窗的战场物资配送车辆路径优化[J]. Journal of Systems Engineering and Electronics, 2013, 35(4): 770-776.
[8]	吴宝林１，２，田也壮１. 航天复杂产品系统智能优化协调方法及其应用[J]. 系统工程与电子技术, 2013, 35(11): 2342-2346.
[9]	叶玉玲. 模糊粗糙神经网络的结构与参数优化[J]. Journal of Systems Engineering and Electronics, 2009, 31(12): 2988-2993.