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

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

Abstract

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

CLC Number:

C939

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Fig.8

Fig.9

Fig.10

References 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]	Wenqing SHI, Haifeng WANG, Haixin CHEN. Fighter-drone teaming system requirements elicitation and verification [J]. Systems Engineering and Electronics, 2023, 45(1): 108-118.
[2]	JIANG Liang, ZHANG Qingpu, HAN Song, LOU Yanfeng. Dual-polarized antenna space coding method based on micro drone [J]. Systems Engineering and Electronics, 2019, 41(3): 651-658.
[3]	CHEN Wu, FAN Mingkai, LI Zehong, JIN Xin, HONG Liang. Design of network robustness for drone swarm system [J]. Systems Engineering and Electronics, 2019, 41(11): 2633-2640.

Review and prospect under the mapping mode of coordinated delivery of drones and vehicles

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 10

References 70

Related Articles 3

Recommended Articles

Metrics

Comments