无人机和车辆协同配送映射模式综述与展望

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

摘要/Abstract

摘要：

基于近年来兴起的无人机和车辆协同配送模式的研究, 主要从无人机和车辆映射关系的角度着手进行了分析, 包括单车单机映射模式、单车多机映射模式和多车多机映射模式。在单车单机映射模式中，主要总结了无人机和车辆协同配送的4种模式, 包括无人机和车辆同步配送模式、无人机和车辆并行配送模式、车辆保障无人机配送模式和无人机保障车辆配送模式。在单车多机映射模式中，主要总结了基于车辆保障无人机配送模式的相关文献; 而在多车多机映射模式中, 主要总结了基于无人机和车辆同步配送模式的相关文献。探究了3种映射模式中的相同变体和不同变体, 并归纳分析了目前无人机和车辆协同配送模式中的目标、算法、相关参数及约束条件。展望了无人机和车辆协同配送模式中需要考虑实际性能分析和异构无人机优化, 对未来研究和实际运用具有重要参考价值和指导意义。

关键词: 无人机, 协同配送, 映射模式

Abstract:

Based on the research on the coordinated delivery mode of drones and trucks that has emerged in recent years, the analysis is mainly from the perspective of the mapping relationship between drones and vehicles, including single-vehicle single-drone mapping mode (TSP-D), single-vehicle multi-drone mapping mode (TSP-mD) and multi-vehicle multi-drone mapping mode (MTSPD). In the TSP-D, four modes of coordinated delivery of drones and trucks are mainly summarized, including the flying sidekick traveling salesman problem (FSTSP), the parallel drone scheduling traveling salesman problem (PDSTSP), the vehicle guarantee drone traveling salesman problem (VGDTSP) and the drone guarantee vehicle traveling salesman problem (DGVTSP). In the TSP-mD, the relevant documents are mainly summarized based on the VGDTSP. In the multiple traveling salesman problem with drones (MTSPD), the relevant documents are mainly summarized based on the FSTSP. The same variants and different variants of the three mapping modes are explored, and the targets, algorithms, related parameters and constraints in the current coordinated delivery mode of drones and trucks are summarized and analyzed. Considering actual performance analysis and heterogeneous drone optimization in the coordinated delivery model of drones and vehicles, this research will have important reference value and guiding significance for future research and practical applications.

Key words: drone, coordinated delivery, mapping mode

中图分类号:

C939

刘正元, 王清华. 无人机和车辆协同配送映射模式综述与展望[J]. 系统工程与电子技术, 2023, 45(3): 785-796.

Zhengyuan LIU, Qinghua WANG. Review and prospect under the mapping mode of coordinated delivery of drones and vehicles[J]. Systems Engineering and Electronics, 2023, 45(3): 785-796.

图/表 10

图1

图2

图3

图4

图5

图6

图7

图8

图9

图10

参考文献 70

1	圆通研究院. 盘点无人机在物流相关领域的应用实践[J]. 中国物流与采购, 2018, (1): 48- 51.
	Yuantong Research Institute . Inventory the application practice of drones in logisticsrelated fields[J]. China Logistics and Procurement, 2018, (1): 48- 51.
2	HEATH N. The long-range drone that can keep up with a car and fly for an hour[EB/OL]. [2021-02-11]. https://www.techrepublic.com/blog/european-technology/the-long-range-drone-that-can-keep-up-with-a-car-and-fly-for-an-hour/.
3	WOHLSEN M. The next big thing you missed: Amazon's delivery drones could work--they just need trunks[EB/OL]. [2021-03-05]. https://www.wired.com/2014/06/the-next-big-thing-you-missed-delivery-drones-launched-from-trucks-are-the-future-of-shipping/.
4	PEREZ S, KOLODNY L. UPS tests show delivery drones still need work[EB/OL]. [2021-02-14]. https://techcrunch.com/2017/02/21/ups-tests-show-delivery-drones-still-need-work/.
5	任新惠, 岳一笛, 尹晓丽, 等. 无人机车辆组合物流配送路径规划探讨[J]. 飞行力学, 2020, 38 (2): 88- 94.
	REN X H , YUE Y D , YIN X L , et al. Discussion on UAV vehicle combined logistics distribution path planning[J]. Flight Mechanics, 2020, 38 (2): 88- 94.
6	MURRAY C C , CHU A G . The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery[J]. Transportation Research Part C, 2015, 54, 86- 109.
7	AGATZ N , BOUMAN P , SCHMIDT M . Optimization appro-aches for the traveling salesman problem with drone[J]. Transportation Science, 2018, 52 (4): 965- 981.
8	BOUMAN P , AGATZ N , SCHMIDT M . Dynamic programming approaches for the traveling salesman problem with drone[J]. Networks, 2018, 72 (4): 528- 542.
9	HA Q M , DEVILLE Y , PHAM Q D , et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C, 2018, 86, 597- 621.
10	ES Y E , OZMUTLU H C . A decomposition-based iterative optimization algorithm for traveling salesman problem with drone[J]. Transportation Research Part C, 2018, 91, 249- 262.
11	PEDRO L , GONZALEZ-R D C , JOSE L , et al. Truck-drone team logistics: a heuristic approach to multi-drop route planning[J]. Transportation Research Part C, 2020, 114, 657- 680.
12	HAM A M . Integrated scheduling of m-truck, m-drone, and m-depot constrained by time-window, drop-pickup, and m-visit using constraint programming[J]. Transportation Research Part C, 2018, 91, 1- 14.
13	KIM S , MOON I . Traveling salesman problem with a drone station[J]. IEEE Trans.on System, Man, Cybernetics: System, 2019, 49 (1): 42- 52.
14	CHAUHAN D , UNNIKRISHNAN A , FIGLIOZZI M . Maximum coverage capacitated facility locationproblem with range constrained drones[J]. Transportation Research Part C, 2019, 99, 1- 18.
15	MATHEW N , SMITH S L , WASLANDER S L . Planning paths for package delivery in heterogeneous multirobot teams[J]. IEEE Trans.on Automatic Science and Engineering, 2015, 12 (4): 1298- 1308.
16	SAVURAN H , KARAKAYA M . Efficient route planning for an unmanned air vehicle deployedon a moving carrier[J]. Soft Computer, 2016, 20 (7): 2905- 2920.
17	OTHMA M S B , SHURBEVSKI A , KARUNO Y , et al. Routing of carrier-vehicle systems with dedicated last-stretch deli-very vehicle and fixed carrier route[J]. Journal of Information Processing, 2017, 25, 655- 666.
18	LUO Z H , LIU Z , SHI J M , et al. A two-echelon cooperated routing problem for a ground vehicle and its carried unmanned aerial vehicle[J]. Sensors, 2017, 17 (5): 1144.
19	CARLSSON J G , SONG S Y . Coordinated logistics with a truck and a drone[J]. Management Science, 2017, 64 (9): 4052- 4069.
20	DAYARIAN I , SAVELSBERGH M , CLARKE J P . Same-day delivery with drone resupply[J]. Transportation Science, 2020, 54 (1): 229- 249.
21	MCCUNNEY B, CAUWENBERGHE K. Simulation test bed for drone-supported logistics systems[EB/OL]. [2021-03-05]. https://ctl.mit.edu/sites/ctl.mit.edu/files/theses/43823520-Brent%20%26%20Kristof%20Executive%20Summary.pdf.
22	CAMPBELL J F, SWEENEY D, ZHANG J. Strategic design for delivery with trucks and drones[EB/OL]. [2021-03-05]. https://villagereach.org/wp-content/uploads/2018/07/StrategicDesignforDeliverywithDronesandTrucks_4-17-17_SCMA-2017-0201.pdf.
23	WANG X , POIKONEN S , GOLDEN B . The vehicle routing problem with drones: several worst-case results[J]. Optimization Letter, 2017, 11 (4): 679- 697.
24	POIKONEN S , WANG X , GOLDEN B . The vehicle routing problem with drones: extended models and connections[J]. Networks, 2017, 70 (1): 34- 43.
25	DAKNAMA R, KRAUS E. Vehicle routing with drones. [EB/OL]. [2021-03-05]. https://arxiv.org/pdf/1705.06431.pdf.
26	WANG Z , SHE J B . Vehicle routing problem with drones[J]. Transportation Research Part B, 2019, 122, 350- 364.
27	SACRAMENTO D , PISINGER D , ROPKE S . An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J]. Transportation Research Part C, 2019, 102, 289- 315.
28	DANIEL S , MAHDI M , OLIVER W . A matheuristic for the vehicle routing problem with dronesand its variants[J]. Transportation Research Part C, 2019, 106, 166- 204.
29	EUCHI J , SADOK A . Hybrid genetic-sweep algorithm to solve the vehicle routing problem with drones[J]. Physical Communication, 2021, 44, 101236.
30	FELIX T , UDO B . A branch-and-cut algorithm for the vehicle routing problem with drones[J]. Transportation Research Part B, 2021, 144, 174- 203.
31	FERRANDEZ S M , HARBISON T , WEBER T , et al. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm[J]. Journal of Industrial Engineering & Management, 2016, 9 (2): 374- 388.
32	BOYSEN N , BRISKORN D , FEDTKE S , et al. Drone delivery from trucks: drone scheduling for given truck routes[J]. Networks, 2018, 72 (4): 506- 527.
33	CHANG Y S , LEE H J . Optimal delivery routing with wider drone-delivery areas along ashorter truck-route[J]. Expert System Apply, 2018, 104, 307- 317.
34	ALINE K , KHALED A . The hybrid vehicle-drone routing problem for pick-up and delivery services[J]. Transportation Research Part C, 2019, 102, 427- 449.
35	PATCHARA K , MARIO V , MOHAMMED M J , et al. Multiple traveling sales-man problem with drones: mathematical model and heuristic approach[J]. Computers & Industrial Engineering, 2019, 129, 14- 30.
36	DUKKANCI O , KARA B Y , BEKTA T . Minimizing energy and cost in range-limited drone deliveries with speed optimization[J]. Transportation Research Part C, 2021, 125, 102985.
37	胡小亮. "货车+无人机"联合配送路径规划研究[D]. 重庆: 西南交通大学, 2019.
	HU X L. Research on "Truck+UAV" joint distribution route planning[D]. Chongqing: Southwest Jiaotong University, 2019.
38	FRANÇA P M , GENDREAU M , LAPORTE G , et al. The m-traveling salesman problem with minmax objective[J]. Transportation Science, 1995, 29 (3): 267- 275.
39	PHAN A T, NGUYEN T D, PHAM Q D. Traveling salesman problem with multiple drones[C]//Proc. of the 9th International Symposium on Information and Communication Technology, 2018: 46-53.
40	KARAK A , ABDELGHANY K . The hybrid vehicledrone routing problem for pick-up and delivery services[J]. Transportation Research Part C: Emerging Technologies, 2019, 102, 427- 449.
41	LI Y S , ZHANG G Z , PANG Z B , et al. Continuum approximation models for joint delivery systems using trucks and drones[J]. Enterprise Information Systems, 2020, 14 (4): 406- 435.
42	DELL'AMICO M , MONTEMANNI R , NOVELLANI S . Drone-assisted deliveries: new formulations for the flflying sidekick traveling salesman problem[J]. Optimization Letters, 2021, 15 (5): 1617- 1648.
43	周鲜成, 周开军, 王莉, 等. 物流配送中的绿色车辆路径模型与求解算法研究综述[J]. 系统工程理论与实践, 2021, 41 (1): 213- 230.
	ZHOU X C , ZHOU K J , WANG L , et al. A surveyof green vehicle routing models and solving algorithms in logistics distribution[J]. System Engineering-Theory and Practice, 2021, 41 (1): 213- 230.
44	任璇, 黄辉, 于少伟, 等. 车辆与无人机组合配送研究综述[J]. 控制与决策, 2021, 36 (10): 2313- 2327.
	REN X , HUANG H , YU S W , et al. Overview of research on combined delivery of vehicles and UAVs[J]. Control and Decision, 2021, 36 (10): 2313- 2327.
45	林驿, 吕靖, 蒋永雷. 考虑交通时变特性的城乡快递无人机配送优化研究[J]. 计算机应用研究, 2019, 37 (10): 2984- 2989.
	LIN Y , LYU J , JIANG Y L . Research on the optimization of urban and rural express drone distribution considering the time-varying characteristics of traffic[J]. Application Research of Computers, 2019, 37 (10): 2984- 2989.
46	杨航. 车辆与无人机协同配送优化研究[D]. 浙江: 浙江理工大学, 2020.
	YANG H. Research on optimization of collaborative delivery between vehicles and drones[D]. Zhejiang: Zhejiang SciTech University, 2020.
47	BRAMEL J , SIMCHI-LEVI D . A location based heuristic for general routing problems[J]. Operations Research, 1995, 43 (4): 649- 660.
48	BEASLEY J E . Route-first cluster-second methods for vehicle routing[J]. Omega, 1983, 11 (4): 403- 408.
49	MOHAMMAD M J , LEE S , MATTHIAS W . Design and evaluation of a multi-trip delivery model with truck and drones[J]. Transportation Research Part E, 2020, 136, 101887.
50	DORLING K , HEINRICHS J , MESSIER G G , et al. Vehicle routing problems for drone delivery[J]. IEEE Trans.on Systems, Man, and Cybernetics: Systems, 2017, 47 (1): 70- 85.
51	BYUNG D S , KYUNGSU P , JONGHOE K . Persistent UAV delivery logistics: MILP formulation and efficient heuristic[J]. Computers & Industrial Engineering, 2018, 120, 418- 428.
52	彭勇, 黎元钧. 考虑疫情影响的"车辆-无人机"协同配送路径优化[J]. 中国公路学报, 2020, 33 (11): 73- 82.
	PENG Y , LI Y J . "Vehicle-UAV" collaborative delivery route optimization considering the impact of the epidemic[J]. China Journal of High-way and Transport, 2020, 33 (11): 73- 82.
53	LIU Z, SENGUPTA R, KURZHANSKIY A. A power consumption model for multi-rotor small unmanned aircraft systems[C]//Proc. of the International Conference on Unmanned Aircraft Systems, 2017: 310-315.
54	MURRAY C C , RAJ R . The multiple flying sidekicks traveling salesman problem: parcel delivery with multiple drones[J]. Transportation Research Part C, 2020, 110, 368- 398.
55	MURRAY C C , RAJ R . The multiple flying sidekicks traveling salesman problem with variable drone speeds[J]. Transportation Research Part C, 2020, 120, 102813.
56	JEONG H Y , SONG B D , LEE S . Truck-drone hybrid delivery routing: payload-energy dependency and no-fly zones[J]. International Journal of Production Economics, 2019, 214, 220- 233.
57	朱晓宁, 陈立双, 田昊彤, 等. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30 (5): 144- 155.
	ZHU X N , CHEN L S , TIAN H T , et al. Research on the path of trucks with drones considering area restrictions[J]. China Management Science, 2022, 30 (5): 144- 155.
58	DI P P L, GUERRIERO F. Last-mile deliveries by using drones and classical vehicles[C]//Proc. of the International Conference on Optimization & Decision Science, 2017.
59	KOCH H , BORTFELDT A , WASCHER G . A hybrid algorithm for the vehicle routing problem with backhauls, time windows and three-dimensional loading constraints[J]. OR Spectrum, 2018, 40 (4): 1029- 1075.
60	庞燕, 罗华丽, 邢立宁, 等. 车辆路径优化问题及求解方法研究综述[J]. 控制理论与应用, 2019, 36 (10): 1573- 1584.
	PANG Y , LUO H L , XING L N , et al. Research review of vehicle routing optimization problems and solutions[J]. Control Theory and Applications, 2019, 36 (10): 1573- 1584.
61	唐嘉诚. 多约束条件下无人机协同配送算法研究[D]. 辽宁: 沈阳航空航天大学, 2019.
	TANG J C. Research on UAV collaborative delivery algorithm under multiple constraints[D]. Liaoning: Shenyang University of Aeronautics and Astronautics, 2019.
62	丛书全, 王成军, 姜杨. 无人机航程与续航时间的实时估算方法研究[J]. 宇航计测技术, 2012, 32 (2): 62- 65.
	CONG S Q , WANG C J , JIANG Y . Research on realtime estimation method of UAV's range and endurance[J]. Aerospace Measurement Technology, 2012, 32 (2): 62- 65.
63	黄俊波. 无人机安全评估体系速度计算[J]. 云南电力技术, 2016, 44 (6): 35- 37.
	HUANG J B . Speed calculation of UAV safety assessment system[J]. Yunnan Electric Power Technology, 2016, 44 (6): 35- 37.
64	OLLERO A, MAZA I. 异构多无人机[M]. 朱永贤等, 译. 北京: 国防工业出版社, 2012.
	OLLERO A, MAZA I. Heterogeneous multi-UAV[M]. ZHU Y X, et al. trans. Beijing: National Defense Industry Press, 2012.
65	肖东. 异构多无人机自主任务规划方法研究[D]. 南京: 南京航空航天大学, 2018.
	XIAO D. Research on the autonomous mission planning me-thod of heterogeneous multi-UAVs[D]. Nanjing: Nanjing University of Aeronauticsand Astronautics, 2018.
66	严飞, 祝小平, 周洲, 等. 考虑同时攻击约束的多异构无人机实时任务分配[J]. 中国科学: 信息科学, 2019, 49 (5): 555- 569.
	YAN F , ZHU X P , ZHOU Z , et al. Realtime task allocation of multiple heterogeneous UAVs considering simultaneous attack constraints[J]. Science in China: Information Science, 2019, 49 (5): 555- 569.
67	田震, 王晓芳. 基于多基因遗传算法的异构多无人机协同任务分配[J]. 飞行力学, 2019, 37 (1): 39- 44.
	TIAN Z , WANG X F . Heterogeneous multi-UAV cooperative task allocation based on multi-genegenetic algorithm[J]. Flight Mechanics, 2019, 37 (1): 39- 44.
68	贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术, 2021, 43 (1): 99- 111.
	JIA G W , WANG J F . Summary of research on UAV cluster mission planning methods[J]. System Engineering and Electronics, 2021, 43 (1): 99- 111.
69	周晶, 赵晓哲, 许震, 等. 基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法[J]. 系统工程与电子技术, 2021, 43 (5): 1240- 1247.
	ZHOU J , ZHAO X Z , XU Z , et al. High-dimensional multi-target task allocation method for UAV swarm based on D-NSGA-Ⅲ algorithm[J]. Systems Engineering and Electronics, 2021, 43 (5): 1240- 1247.
70	汪小帆, 李翔, 陈关荣. 网络科学导论[M]. 北京: 高等教育出版社, 2012: 210- 230.
	WANG X F , LI X , CHEN G R . Introduction to network science[M]. Beijing: Higher Education Press, 2012: 210- 230.

[1]	史文卿, 王海峰, 陈海昕. 战斗机无人机编组协同系统需求捕获与验证[J]. 系统工程与电子技术, 2023, 45(1): 108-118.
[2]	方坤, 李晓辉, 樊韬. 基于随机森林权重补偿的无人机高精度定位算法[J]. 系统工程与电子技术, 2023, 45(1): 202-209.
[3]	张俊杰, 仲伟志, 张璐璐, 王俊智, 朱秋明. 基于IUPF算法的三维无人机毫米波波束跟踪[J]. 系统工程与电子技术, 2023, 45(1): 257-263.
[4]	孙田野, 孙伟, 吴建军. 改进Quatre算法的无人机编队快速集结方法[J]. 系统工程与电子技术, 2022, 44(9): 2840-2848.
[5]	余婧, 雍恩米, 陈汉洋, 郝东, 张显才. 面向多无人机协同对地攻击的双层任务规划方法[J]. 系统工程与电子技术, 2022, 44(9): 2849-2857.
[6]	徐星光, 王晓峰, 姚璐, 任章. 固定翼无人机编队构型与通信拓扑优化[J]. 系统工程与电子技术, 2022, 44(9): 2936-2946.
[7]	杨建峰, 肖和业, 李亮, 白俊强, 董维浩. 基于模糊聚类和专家评分机制的无人机多层次模块划分方法[J]. 系统工程与电子技术, 2022, 44(8): 2530-2539.
[8]	卢元杰, 刘志敏, 孙智孝, 阚东. 基于模型的无人机系统架构综合评估方法[J]. 系统工程与电子技术, 2022, 44(4): 1239-1245.
[9]	李洪瑶, 李小强, 韩心中, 谢学立, 席建祥. 基于决策融合的多无人机协同目标检测识别算法[J]. 系统工程与电子技术, 2022, 44(3): 746-754.
[10]	张源原, 高阳, 朱鹏, 刘锦涛, 谷树山. 基于着色Petri网的无人机侦察战术规划[J]. 系统工程与电子技术, 2022, 44(3): 900-907.
[11]	谷旭平, 唐大全. 基于联邦滤波算法的无人机集群分层协同导航[J]. 系统工程与电子技术, 2022, 44(3): 967-976.
[12]	余雪勇, 朱烨, 邱礼翔, 朱洪波. 基于无人机辅助边缘计算系统的节能卸载策略[J]. 系统工程与电子技术, 2022, 44(3): 1022-1029.
[13]	杨兴家, 段克清, 李想, 祁炜. 无人机集群协同探测距离解模糊方法[J]. 系统工程与电子技术, 2022, 44(2): 480-489.
[14]	符小卫, 潘静. 无人机集群规避动态障碍物的分布式队形控制[J]. 系统工程与电子技术, 2022, 44(2): 529-537.
[15]	陈都, 孟秀云. 基于自适应郊狼算法的无人机离线航迹规划[J]. 系统工程与电子技术, 2022, 44(2): 603-611.