城市低空物流无人机飞行计划预先调配

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

摘要/Abstract

摘要：

针对城市环境下物流无人机(unmanned aerial vehicle, UAV)飞行计划调配问题, 以UAV运输成本和延误成本最小为目标, 建立多约束物流UAV飞行计划预先调配模型。考虑货物类型优先级、物流公司优先级和配送时间优先级提出综合优先级, 设计了基于综合优先级的飞行计划预先调配算法求解。以校园配送为仿真环境进行验证, 模型和算法能够生成无冲突的飞行时刻表, 实现飞行计划预先差异化调配。实验结果表明, 综合优先级调配与传统任务优先调配、先到先服务调配相比, 每条飞行计划的成本分别降低了21.69%和26.58%;当综合优先级权重组合为0.2、0.4和0.4时, 每条飞行计划的成本最低为5.42元, 调配结果最佳。

关键词: 航空运输, 飞行计划调配, 综合优先级, 物流无人机

Abstract:

In view of the problem of logistics unmanned aerial vehicle (UAV) flight plan allocation in urban environment, with the goal of minimizing UAV transportation cost and delay cost, a multi-constraint logistics UAV flight plan pre-allocation model is established. Considering the priority of cargo type, the priority of logistics company and the priority of delivery time, a comprehensive priority is proposed. A flight plan pre-allocation algorithm based on the comprehensive priority is designed. Using campus distribution as a simulation environment for verification, the model and algorithm can generate conflict-free flight schedules and realize pre-differentiated flight plan allocation. The experimental results show that the cost of each flight plan is reduced by 21.69% and 26.58% respectively compared with the task priority allocation and the first come first service allocation. When the comprehensive priority weight combination is 0.2, 0.4, and 0.4, the lowest cost of each flight plan is 5.42 yuan, and the allocation result is the best.

Key words: air transportation, flight plan allocation, comprehensive priority, logistics unmanned aerial vehicle (UAV)

中图分类号:

张洪海, 任真苹, 冯讴歌, 王非, 刘皞. 城市低空物流无人机飞行计划预先调配[J]. 系统工程与电子技术, 2023, 45(9): 2802-2811.

Honghai ZHANG, Zhenping REN, Ouge FENG, Fei WANG, Hao LIU. Logistics unmanned aerial vehicle flight plan pre-allocation in urban low-altitude airspace[J]. Systems Engineering and Electronics, 2023, 45(9): 2802-2811.

图/表 12

图1

图2

表1

图3

表2

表3

表4

表5

表6

图4

图5

图6

参考文献 31

1	CONSULTING P. The future of vertical mobility: sizing the market for passenger, inspection, and goods services until 2035[EB/OL]. [2022-04-15]. https://www.porsche consulting.com/fileadmin/docs/04_Medien/Pub likationen/TT1371_The_Future_ of_Vertical_Mobility/The_Future_of_Vertical_Mobility_A_Porsche_Consulting_study__C_2018.pdf.
2	STANLEY M. Urban air mobility flying cars: Investment implications of autonomous urban air mobility[EB/OL]. [2022-04-15]. https://www.morganstanley.com/ideas/autonomous-aircraft.
3	GOYAL R. Urban air mobility(UAM) market study[EB/OL]. [2022-04-15]. https://ntrs.nasa.gov/archive/nasa/casi.ntrs.nasa.gov/20190001472.pdf.
4	SWADESIR L, BIL C. Urban air transportation for Melbourne metropolitan area[C]//Proc. of the AIAA Aviation 2019 Forum, 2019.
5	RABTAB,WANKMVLLERC,REINERG.A drone fleet model for last-mile distribution in disaster relief operations[J].International Journal of Disaster Risk Reduction,2018,28,107-112. doi: 10.1016/j.ijdrr.2018.02.020
6	SCOTT J, SCOTT C. Drone delivery models for healthcare[C]// Proc. of the Hawaii International Conference on System Sciences, 2017.
7	SONGB D,PARKK,KIMJ.Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J].Computers & Industrial Engineering,2018,120,418-428.
8	CHEN A Z J, MO J P T. Modelling of unmanned aerial vehicle deliveries in populated urban areas for risk management[C]//Proc. of the International Conference on Software, Knowledge, Information Management & Applications, 2017: 61-66.
9	DUAN F L, LI X H, ZHAO Y. Express UAV swarm path planning with VND enhanced memetic algorithm[C]//Proc. of the International Conference on Computing and Data Engineering, 2018: 93-97.
10	JIANG X W, ZHOU Q, YE Y. Method of task assignment for UAV based on particle swarm optimization in logistics[C]//Proc. of the International Conference on Intelligent Systems, 2017: 113-117.
11	ZHAOY Q,LIUK,LUG H,et al.Path planning of UAV delivery based on improved APF-RRT^* algorithm[J].Journal of Physics Conference Series,2020,1624,042004. doi: 10.1088/1742-6596/1624/4/042004
12	LINC E,SHAOP C.Failure analysis for an unmanned aerial vehicle using safe path planning[J].Journal of Aerospace Information Systems,2020,17(7):358-369. doi: 10.2514/1.I010795
13	傅辰涛, 王宏伟. 飞行冲突探测与调配辅助决策过程研究[C]// 第一届空中交通管理系统技术学术年会论文集, 2018: 74-77.
	FU C T, WANG H W. Research on flight conflict detection and deployment assistant decision-making process[C]//Proc. of the Annual Conference on Air Traffic Management System Technology, 2018: 74-77.
14	TAN Q Y, WANG Z K, ONG Y S, et al. Evolutionary optimization-based mission planning for UAS traffic management(UTM)[C]//Proc. of the International Conference on Unmanned Aircraft Systems, 2019: 952-958.
15	田宇,张洪海,钱晓鹏,等.低空通航飞行计划预先调配方法研究[J].武汉理工大学学报(交通科学与工程版),2020,44(3):444-449.
	TIANY,ZHANGH H,QIANX P,et al.Research on pre-allocation method of low-altitude general aviation flight plan[J].Journal of Wuhan University of Technology (Transportation Science and Engineering Edition),2020,44(3):444-449.
16	高虎,褚映红,杨明,等.通用航空飞行计划处理系统的设计与实现[J].现代导航,2019,10(3):187-190. doi: 10.3969/j.issn.1674-7976.2019.03.007
	GAOH,CHUY H,YANGM,et al.Design and realization of general aviation flight plan system[J].Modern Navigation,2019,10(3):187-190. doi: 10.3969/j.issn.1674-7976.2019.03.007
17	向征,丁钰童.基于飞行计划集中处理的预战术航路飞行流量预测[J].科学技术与工程,2021,21(24):10525-10530. doi: 10.3969/j.issn.1671-1815.2021.24.058
	XIANGZ,DINGY T.Flight flow prediction of pre-tactical routes based on centralized processing of flight plan[J].Science Technology and Engineering,2021,21(24):10525-10530. doi: 10.3969/j.issn.1671-1815.2021.24.058
18	TAKEICHIN.Nominal flight time optimization for arrival time scheduling through estimation/resolution of delay accumulation[J].Transportation Research Part C: Emerging Techno-logies,2017,77,433-443. doi: 10.1016/j.trc.2017.01.025
19	ZHANGY C,RONGS,LIQ,et al.Distributed flight routing and scheduling for air traffic flow management[J].IEEE Trans.on Intelligent Transportation Systems,2017,18(10):2681-2692. doi: 10.1109/TITS.2017.2657550
20	LIANGZ,CHAOVALITWONGSEW A,ELSAYEDE A.Sequence assignment model for the flight conflict resolution problem[J].Transportation Science,2014,48(3):334-350. doi: 10.1287/trsc.2013.0480
21	BENLICU.Heuristic search for allocation of slots at network level[J].Transportation Research Part C: Emerging Technologies,2018,86(1):488-509.
22	ZHONGH,GUANW,ZHANGW Y,et al.A bi-objective integer programming model for partly-restricted flight departure scheduling[J].PloS One,2018,13(5):e0196146. doi: 10.1371/journal.pone.0196146
23	ANDROUTSOPOULOSK N,MANOUSAKISE G,MADASM A.Modeling and solving a bi-objective airport slot scheduling problem[J].European Journal of Operational Research,2020,284(1):135-151. doi: 10.1016/j.ejor.2019.12.008
24	JORGED,RIBEIRON A,ANTUNESA P.Towards a decision-support tool for airport slot allocation: application to Guarulhos (Sao Paulo, Brazil)[J].Journal of Air Transport Ma-nagement,2021,93(2):102048.
25	FAIRBROTHERJ,ZOGRAFOSK G.Optimal scheduling of slots with season segmentation[J].European Journal of Operational Research,2020,291(3):961-982.
26	ZOGRAFOSK G,JIANGY.A bi-objective efficiency-fairness model for scheduling slots at congested airports[J].Transportation Research Part C: Emerging Technologies,2019,102(5):336-350.
27	FAIRBROTHERJ,ZOGRAFOSK G,GLAZEBROOKK D.A slot-scheduling mechanism at congested airports that incorporates efficiency, fairness, and airline preferences[J].Transportation Science,2020,54(1):115-138. doi: 10.1287/trsc.2019.0926
28	PELLEGRINIAP,BOLIĆBT,CASTELLIL,et al.SOSTA: an effective model for the simultaneous optimization of airport slot allocation[J].Transportation research Part E: Logistics and Transportation Review,2017,99C(5):34-53.
29	RIBEIRON A,JACQUILLATA,ANTUNESA P,et al.Improving slot allocation at level 3 airports[J].Transportation Research Part A: Policy and Practice,2019,127(9):32-54.
30	国家邮政局. 国家邮政局关于2021年快递服务满意度调查和时限准时率测试结果的通告[EB/OL]. [2022-04-15]. http://www.spb.gov.cn/gjyzj/c100009/c100010/202201/0ce493fa7228415e9a1e6e81998c4bbb.shtml.
	State Post Bureau. Announcement of the state post bureau on the 2021 express service satisfaction survey and time-limi- ted on-time rate test results[EB/OL]. [2022-04-15]. http://www.spb.gov.cn/gjyzj/c100009/c100010/202201/0ce493fa7228415e9a1e6e81998c4bbb.shtml.
31	李翰,张洪海,张连东,等.城市区域多物流无人机协同任务分配[J].系统工程与电子技术,2021,43(12):3594-3602.
	LIH,ZHANGH H,ZHANGL D,et al.Multiple logistics unmanned aerial vehicle collaborative task allocation in urban areas[J].Systems Engineering and Electronics,2021,43(12):3594-3602.

参数	取值
飞行速度v/(m·s^-1)	8
单位运输成本C_d/(元·kg^-1·km^-1)	0.24
单位延误成本C_p/(元·s^-1)	0.17
最长等待时间T_m/s	120
无人机最远航程d_max/m	2 865
无人机最大载重q_max/kg	6
最长飞行时间T_fly^max/min	16
最小起飞时间间隔ΔT_dep/s	10
最小到达时间间隔ΔT_arr/s	10
最小交叉点时间间隔ΔT_safe/s	10
R1航路距离/m	1 008.53
R2航路距离/m	1 104.94
R3航路距离/m	885.84
R4航路距离/m	1 258.99
R5航路距离/m	872.99
R6航路距离/m	1 392.31

序号	起飞时间	送达时间	返程时间	交叉时间	返回时间
1	08:00:00	08:01:07	08:01:16	08:01:45	08:02:15
2	08:00:40	08:01:47	08:01:56	08:02:25	08:02:55
3	08:01:20	08:02:27	08:02:36	08:03:05	08:03:35
4	08:02:00	08:03:07	08:03:16	08:03:45	08:04:15
5	08:02:40	08:03:47	08:03:56	08:04:25	08:04:55
6	08:03:20	08:04:27	08:04:36	08:05:05	08:05:35
⋮	⋮	⋮	⋮	⋮	⋮
169	09:53:00	09:54:07	09:54:16	09:54:45	09:55:15
170	09:53:40	09:54:47	09:54:56	09:55:25	09:55:55
171	09:54:20	09:55:27	09:55:36	09:56:05	09:56:35
172	09:55:00	09:56:07	09:56:16	09:56:45	09:57:15
173	09:55:40	09:56:47	09:56:56	09:57:25	09:57:55
174	09:56:20	09:57:27	09:57:36	09:58:05	09:58:35
175	09:57:00	09:58:07	09:58:16	09:58:45	09:59:15

序号	起飞时间	送达时间	返程时间	交叉时间	返回时间
1	08:00:10	08:01:28	08:01:35	08:02:05	08:02:35
2	08:00:50	08:02:08	08:02:15	08:02:45	08:03:15
3	08:01:30	08:02:48	08:02:55	08:03:25	08:03:55
4	08:02:10	08:03:28	08:03:35	08:04:05	08:04:35
5	08:02:50	08:04:08	08:04:15	08:04:45	08:05:15
6	08:03:30	08:04:48	08:04:55	08:05:25	08:05:55
⋮	⋮	⋮	⋮	⋮	⋮
169	09:53:10	09:54:28	09:54:35	09:55:05	09:55:35
170	09:53:50	09:55:08	09:55:15	09:55:45	09:56:15
171	09:54:30	09:55:48	09:55:55	09:56:25	09:56:55
172	09:55:10	09:56:28	09:56:35	09:57:05	09:57:35
173	09:55:50	09:57:08	09:57:15	09:57:45	09:58:15
174	09:56:30	09:57:48	09:57:55	09:58:25	09:58:55

序号	起飞时间	送达时间	返程时间	返回时间
1	08:00:20	08:01:09	08:01:25	08:02:25
2	08:01:00	08:01:49	08:02:05	08:03:05
3	08:01:40	08:02:29	08:02:45	08:03:45
4	08:02:20	08:03:09	08:03:25	08:04:25
5	08:03:00	08:03:49	08:04:05	08:05:05
6	08:03:40	08:04:29	08:04:45	08:05:45
⋮	⋮	⋮	⋮	⋮
171	09:54:00	09:54:49	09:55:05	09:56:05
172	09:54:40	09:55:29	09:55:45	09:56:45
173	09:55:20	09:56:09	09:56:25	09:57:25
174	09:56:00	09:56:49	09:57:05	09:58:05
175	09:56:40	09:57:29	09:57:45	09:58:45

序号	起飞时间	送达时间	返程时间	返回时间
1	08:00:30	08:01:52	08:02:33	08:04:05
2	08:01:10	08:02:32	08:03:13	08:04:45
3	08:01:50	08:03:12	08:03:53	08:05:25
4	08:02:30	08:03:52	08:04:33	08:06:05
5	08:03:10	08:04:32	08:05:13	08:06:45
6	08:03:50	08:05:12	08:05:53	08:07:25
⋮	⋮	⋮	⋮	⋮
170	09:53:30	09:54:52	09:55:33	09:57:05
171	09:54:10	09:55:32	09:56:13	09:57:45
172	09:54:50	09:56:12	09:56:53	09:58:25
173	09:55:30	09:56:52	09:57:33	09:59:05
174	09:56:10	09:57:32	09:58:13	09:59:45