带时间窗的海军航空兵场站特种保障车辆调度问题

doi:10.3969/j.issn.1009-086x.2022.06.015

摘要/Abstract

摘要：

随着海军航空兵任务样式和数量的剧增，基于经验的人工编排式特种保障车辆调度方法不仅会造成保障资源的浪费，还容易因车辆派遣不及时导致战机延误。针对海军航空兵场站特种保障车辆调度问题，在时间窗和车辆载重的约束下，以出动保障车辆最少、车辆总行驶距离最短为目标建立数学模型。改进遗传算法初始种群和编码方式对模型求解，以一次多机种、大批量飞行保障任务进行仿真试验，得到特种保障车辆调度方案，验证了该模型的合理性。

关键词: 海军航空兵场站, 保障车辆调度, 路径规划, 时间窗, 载重约束, 遗传算法

Abstract:

With the dramatic increase in the style and number of naval aviation missions， the experience-based manual scheduling type of special support vehicle dispatching method will not only cause a waste of support resources， but also easily lead to delays in warplanes due to untimely dispatch of vehicles. To address the problem of dispatching special support vehicles at naval aviation station， a mathematical model is established with the objective of dispatching the least number of support vehicles and the shortest total vehicle travel distance under the constraints of time window and vehicle load. The model is solved by improving the initial population and coding method of genetic algorithm， and a simulation test is carried out with a multi-aircraft and high-volume flight protection task to obtain a special support vehicle dispatching scheme， which verifies the rationality of the model.

Key words: naval aviation station, protection vehicle dispatching, routing planning, time windows, load restraint, genetic algorithm

中图分类号:

E917

阎哲, 汪民乐, 汪江鹏, 吴丰轩, 闫少强. 带时间窗的海军航空兵场站特种保障车辆调度问题[J]. 现代防御技术, 2022, 50(6): 117-123.

Zhe YAN, Min-le WANG, Jiang-peng WANG, Feng-xuan WU, Shao-qiang YAN. Scheduling of Special Support Vehicles at Naval Aviation Station with Time Windows[J]. Modern Defense Technology, 2022, 50(6): 117-123.

图/表 8

图1 算法流程图

Fig. 1 Algorithm flow chart

表1 保障中心参数

Table 1 Parameters of support center

序号

位置横

坐标/m

位置纵

坐标/m

保障需

求量 $X i$

最早保障开始时间

$e i$ /h

最晚保障开始时间

$l i$ /h

工作持续时间

$b i$ /h

T+5

表1 保障中心参数

Table 1 Parameters of support center

序号

位置横

坐标/m

位置纵

坐标/m

保障需

求量 $X i$

最早保障开始时间

$e i$ /h

最晚保障开始时间

$l i$ /h

工作持续时间

$b i$ /h

T+5

表2 A型战机需求参数

Table 2 Demand parameters of type A fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
1	500	100	200	T	T+0.2	T+0.1
2	550	100	200	T	T+0.2	T+0.1
3	600	100	200	T	T+0.2	T+0.1
4	650	100	200	T	T+0.2	T+0.1
5	700	100	200	T	T+0.2	T+0.1
6	750	100	200	T+1	T+1.2	T+0.1
7	800	100	200	T+1	T+1.2	T+0.1
17	-1 000	100	200	T+0.5	T+0.7	T+0.1
18	-1 050	100	200	T+0.5	T+0.7	T+0.1
19	-1 100	100	200	T+0.5	T+0.7	T+0.1
20	-1 150	100	200	T+0.5	T+0.7	T+0.1
21	-1 200	100	200	T+0.5	T+0.7	T+0.1

表2 A型战机需求参数

Table 2 Demand parameters of type A fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
1	500	100	200	T	T+0.2	T+0.1
2	550	100	200	T	T+0.2	T+0.1
3	600	100	200	T	T+0.2	T+0.1
4	650	100	200	T	T+0.2	T+0.1
5	700	100	200	T	T+0.2	T+0.1
6	750	100	200	T+1	T+1.2	T+0.1
7	800	100	200	T+1	T+1.2	T+0.1
17	-1 000	100	200	T+0.5	T+0.7	T+0.1
18	-1 050	100	200	T+0.5	T+0.7	T+0.1
19	-1 100	100	200	T+0.5	T+0.7	T+0.1
20	-1 150	100	200	T+0.5	T+0.7	T+0.1
21	-1 200	100	200	T+0.5	T+0.7	T+0.1

表3 B型战机需求参数

Table 3 Demand parameters of type B fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
8	1 000	100	300	T+1	T+1.2	T+0.1
9	1 050	100	300	T+1	T+1.2	T+0.1
10	1 100	100	300	T+1	T+1.2	T+0.1
11	1 150	100	300	T+1	T+1.2	T+0.1
22	-1 250	100	300	T+1	T+1.2	T+0.1
23	-1 800	100	300	T+1	T+1.2	T+0.1
24	-1 850	100	300	T+1	T+1.2	T+0.1
25	-1 900	100	300	T+1	T+1.2	T+0.1
26	-1 950	100	300	T+1	T+1.2	T+0.1

表3 B型战机需求参数

Table 3 Demand parameters of type B fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
8	1 000	100	300	T+1	T+1.2	T+0.1
9	1 050	100	300	T+1	T+1.2	T+0.1
10	1 100	100	300	T+1	T+1.2	T+0.1
11	1 150	100	300	T+1	T+1.2	T+0.1
22	-1 250	100	300	T+1	T+1.2	T+0.1
23	-1 800	100	300	T+1	T+1.2	T+0.1
24	-1 850	100	300	T+1	T+1.2	T+0.1
25	-1 900	100	300	T+1	T+1.2	T+0.1
26	-1 950	100	300	T+1	T+1.2	T+0.1

表4 C型战机需求参数

Table 4 Demand parameters of type C fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
12	1 300	300	400	T+1.5	T+1.8	T+0.15
13	1 300	350	400	T+1.5	T+1.8	T+0.15
14	1 300	400	400	T+1.5	T+1.8	T+0.15
15	1 300	450	400	T+1.5	T+1.8	T+0.15
16	1 300	500	400	T+1.5	T+1.8	T+0.15
27	-2 000	250	400	T+2	T+2.3	T+0.15
28	-2 050	300	400	T+2	T+2.3	T+0.15
29	-2 050	350	400	T+2	T+2.3	T+0.15
30	-2050	400	400	T+2	T+2.3	T+0.15
31	-2050	450	400	T+2	T+2.3	T+0.15

表4 C型战机需求参数

Table 4 Demand parameters of type C fighter

战机序号	位置横坐标/m	位置纵坐标/m	保障需求量 $X i$	最早保障开始时间 $e i$ /h	最晚保障开始时间 $l i$ /h	工作持续时间 $b i$ /h
12	1 300	300	400	T+1.5	T+1.8	T+0.15
13	1 300	350	400	T+1.5	T+1.8	T+0.15
14	1 300	400	400	T+1.5	T+1.8	T+0.15
15	1 300	450	400	T+1.5	T+1.8	T+0.15
16	1 300	500	400	T+1.5	T+1.8	T+0.15
27	-2 000	250	400	T+2	T+2.3	T+0.15
28	-2 050	300	400	T+2	T+2.3	T+0.15
29	-2 050	350	400	T+2	T+2.3	T+0.15
30	-2050	400	400	T+2	T+2.3	T+0.15
31	-2050	450	400	T+2	T+2.3	T+0.15

表5 配送路线

Table 5 Distribution routes

配送路线序号	具体路线
1	0→3→4→0
2	0→19→21→20→18→0
3	0→6→7→11→10→0
4	0→2→8→9→12→0
5	0→17→30→31→0
6	0→1→13→14→0
7	0→25→26→27→0
8	0→29→28→0
9	0→5→16→15→0
10	0→22→24→23→0

图2 最优配送路线图

Fig. 2 Map of optimal distribution route

图3 优化过程图

Fig. 3 Diagram of optimization process

参考文献 15

1	DANTZIG G B， RAMSER J H.The Rruck-Dispatching Problem ［J］.Management Science，1959（6）：80-91.
2	CALVETE H I， GALE C， OLIVEROS M J.A Goal Programming Approach to Vehicle Routing Problems with Soft Time Windows［J］. European Journal of Operational Researeh， 2007，177（1）：1720-1733.
3	KUHN K， LOTH S. Airport Service Vehicle Scheduling［J］.Air Traffic Control Quarterly， 2010， 18（1）： 63-83.
4	PADRON S， GUIMARANS D， JOSE RAMOS J， et al.A Bi-objective Approach for Scheduling Ground-Handling Vehicles in Airports［J］. Computers & Operations Research，2016， 71（7）：34-53.
5	贾丽琦.应用于机场保障的资源调度算法研究［D］.西安：西安科技大学，2020.
	JIA Li-qi. Research on Resource Scheduling Algorithm Applied to Airport Support［D］. Xi'an：Xi'an University of Science and Technology， 2020.
6	樊琳琳.大型机场地勤服务中的车辆调度问题的初步研究［D］.沈阳：东北大学，2009.
	FAN Lin-lin. Preliminary Study on Vehicle Scheduling in Ground Service of Large Airports ［D］. Shenyang： Northeastern University， 2009.
7	杨珏.基于遗传算法的机场特种车辆调度应用研究［J］.计算机技术与发展，2019，29（3）：164-168.
	YANG Jue. Application Research on Airport Special Vehicle Scheduling Based on Genetic Algorithm ［J］. Computer Technology and Development， 2019，29 （3）： 164-168.
8	魏明，高成修，胡润洲.一种带时间窗和容量约束的车辆路线问题及其Tabu Search算法［J］.运筹与管理，2002，11（3）： 49- 54.
	WEI Ming， GAO Cheng-xiu， HU Run-zhou. A Vehicle Routing Problem with Time Window and Capacity Constraints and Its Tabu Search Algorithm ［J］.Operations Research and Management， 2002，11（3）： 49- 54.
9	王正武，刘杰，邹文竹.多车场响应型接驳公交运行线路与调度的协调研究［J］.铁道科学与工程学报（自然科学版），2020， 17（7）：1849-1856.
	WANG Zheng-wu， LIU Jie， ZOU Wen-zhu. Research on the Coordination of Multi Depot Responsive Feeder Bus Operation Lines and Scheduling ［J］. Journal of Railway Science and Engineering （Natural Science Edition）， 2020， 17 （7）： 1849-1856.
10	马洪坤，杨伟，赵佳，等.基于遗传蚁群算法的带时间窗多车场车辆调度问题［J］.西华大学学报（自然科学版）， 2016， 35（3）：31-35.
	MA Hong-kun， YANG Wei， ZHAO Jia， et al. Multi Depot Vehicle Scheduling Problem with Time Window Based on Genetic Ant Colony Algorithm ［J］. Journal of Xihua University （Natural Science Edition）， 2016， 35 （3）： 31-35.
11	HOLLAND J. Adaptation in Natural and Artificial Systems［M］.MI：University of Michigan Press，Ann Arbor， 1975.
12	GOLDBERG D E.Genetic Algorithm in Search， Optimization，and Machine Learning［J］.Addision Wisely， 1989（102）：36.
13	汪民乐，高晓光，范阳涛.先进遗传算法及其工程应用［M］.西安：西北工业大学出版社，2019.
	WANG Min-le， GAO Xiao-guang， FAN Yang-tao. Advanced Genetic Algorithm and Its Engineering Applic- Ation［M］. Xi'an： Northwest Polytechnical University Press，2019.
14	毕义明，李景文.遗传算法及其军事应用［M］.北京：解放军出版社，1998.
	BI Yi-ming， LI Jing-wen. Genetic Algorithm and Its Military Applications ［M］. Beijing： PLA press， 1998.
15	王小平.遗传算法理论、应用与软件实现［M］.西安：西安交通大学出版社，2002.
	WANG Xiao-ping. Genetic Algorithm Theory， Application and Software Implementation ［M］. Xi'an： Xi'an Jiaotong University Press， 2002.

[1]	唐明南, 张承龙, 赵强, 李林林. 任务场景驱动的防空资源部署方案智能生成与优化方法[J]. 现代防御技术, 2023, 51(3): 1-9.
[2]	陈小卫, 杨超, 季自力. 基于粗糙集和遗传算法的作战试验指标集优化方法[J]. 现代防御技术, 2022, 50(3): 90-96.
[3]	孙丰础, 甘旭升. 无人机双机空战对抗侧向机动路径规划[J]. 现代防御技术, 2022, 50(3): 109-118.
[4]	赵黎兴, 侯兴明, 徐兆文, 和林子. 基于GA-小波-BP神经网络的装备维修能力评估[J]. 现代防御技术, 2022, 50(2): 84-95.
[5]	施端阳, 林强, 胡冰, 陈嘉勋. 遗传算法优化神经网络的雷达杂波抑制方法[J]. 现代防御技术, 2021, 49(6): 74-83.
[6]	宋卫星, 武婧婧, 董志鹏, 张君, 周凯. 基于成本分析的装备维修调度优化模型[J]. 现代防御技术, 2021, 49(5): 88-94.
[7]	马小梦, 何岷, 张长革. 递进型优化算法对相控阵天线阵列的波束优化[J]. 现代防御技术, 2021, 49(2): 72-77.
[8]	郭泽, 焦倩倩. 一种面向自动化标检的文本分类方法[J]. 现代防御技术, 2020, 48(5): 97-104.
[9]	王睦深, 谭湘霞. 基于自适应遗传算法的弹道性能优化设计[J]. 现代防御技术, 2020, 48(2): 35-39.
[10]	马特, 刘刚, 何兵. 弹载小卫星应急发射入轨方法设计与优化[J]. 现代防御技术, 2018, 46(3): 177-183.