考虑区域限制的卡车搭载无人机车辆路径问题研究

doi:10.16381/j.cnki.issn1003-207x.2020.0755

中国管理科学 ›› 2022, Vol. 30 ›› Issue (5): 144-155.doi: 10.16381/j.cnki.issn1003-207x.2020.0755

• 论文 • 上一篇

考虑区域限制的卡车搭载无人机车辆路径问题研究

颜瑞, 陈立双, 朱晓宁, 田昊彤, 温雅, 张群

北京科技大学经济管理学院，北京100083

收稿日期:2020-04-26 修回日期:2020-09-01 发布日期:2022-06-01
通讯作者: 颜瑞（1986-），男（汉族），江苏连云港人，北京科技大学经济管理学院，副教授，博士，研究方向：供应链与物流管理、能源与环境政策、系统优化建模，Email：yanrui@ustb.edu.cn. E-mail:yanrui@ustb.edu.cn
基金资助:
国家自然科学基金资助项目(71802021，71801013，71803029)；北京社科基金资助重点项目(18GLA009)；北京市自然科学基金资助项目(9184023)；北京市哲学社会科学规划项目(18GLB022)；中央高校基本科研业务费资助项目(FRF-BD-20-15A)

Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction

YAN Rui, CHEN Li-shuang, ZHU Xiao-ning, TIAN Hao-tong, WEN Ya, ZHANG Qun

School of Economics and Management, University of Science and Technology Beijing, Beijing 100083, China

Received:2020-04-26 Revised:2020-09-01 Published:2022-06-01
Contact: 颜瑞 E-mail:yanrui@ustb.edu.cn

摘要/Abstract

摘要： 无人机参与配送是解决末端物流难题的重要途径之一。卡车搭载无人机协同配送模式，克服了无人机载重量小、续航时间短的弊端，成为无人机参与末端物流配送的重要形式之一。在疫区、灾区进行应急配送时，经常遇到由于道路毁坏或封锁、区域污染，导致部分路段车辆或无人机无法通行的情况。在非应急配送中，也可能存在车辆限行和空域禁飞等区域限制措施。区域限制给卡车搭载无人机物流配送路径优化问题带来了很大挑战。论文构建了区域限制条件下卡车搭载无人机车辆路径问题的混合整数线性规划模型，提出了一种结合最短路算法和禁忌搜索算法的混合算法，基于标准算例库设计测试集并进行测试实验，实验结果表明混合算法具有较好的计算性能。

关键词: 车辆路径问题；无人机；区域限制；禁忌搜索；最短路

Abstract: As the new force of modern transportation system, drone has many irreplaceable advantages, such as its high efficiency and flexibility, easy control, low energy consumption, and no occupation of road resources. But it is also restricted by many factors, such as the flight distance, complex flight environment and the law and policy barriers, which leads to the failure of drone to carry out the large-scale logistics distribution tasks. Therefore, the logistics operation mode of collaborating with truck has become the inevitable choice for the large-scale application of drone in terminal logistics distribution, emergency items distribution, military air transportation and other fields. This new logistics operation mode brings great challenges to the theory and practice of vehicle routing problem. In recent three years, scholars begin to pay more attention to this issue.

Key words: vehicle routing problem; drone; region restriction; tabu search; shortest path

中图分类号:

O221.4

颜瑞, 陈立双, 朱晓宁, 田昊彤, 温雅, 张群. 考虑区域限制的卡车搭载无人机车辆路径问题研究[J]. 中国管理科学, 2022, 30(5): 144-155.

YAN Rui, CHEN Li-shuang, ZHU Xiao-ning, TIAN Hao-tong, WEN Ya, ZHANG Qun. Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction[J]. Chinese Journal of Management Science, 2022, 30(5): 144-155.

参考文献

［1］ Jenkins D, Vasigh B, Oster C, et al. Forecast of the commercial UAS package delivery market. 2017.
［2］ Wang Dan. The economics of drone delivery. IEEE Spectrum, 2016.
［3］ Colomina I, Molina P. Unmanned aerial systems for photogrammetry and remote sensing: A review［J］. Journal of Photogrammetry & Remote Sensing, 2014, 92(2): 79-97.
［4］ Turner I L, Harley M D, Drummond C D. UAVs for coastal surveying［J］. Coastal Engineering, 2016, 114: 19-24.
［5］邓荣军, 王斌, 熊典, 等. 基于遗传算法的输电线路无人机巡检路径规划［J］. 计算机测量与控制, 2015, 23(4): 1299-1301.Deng Rongjun, Wang Bin, Xiong Dian, et al. A path planning for power transmission lines inspection with unmanned aerial vehicle based on genetic-pattern searching algorithm［J］. Computer Measurement & Control, 2015, 23(4): 1299-1301.
［6］李绍斌, 姜大立, 付高阳, 等. 战场物资无人机配送研究［J］. 国防科技, 2019, 40(3): 98-104.Li Shaobin, Jiang Dali, Fu Gaoyang, et al. Review and prospect of research on UAV delivery of battlefield materials［J］. National Defense Technology, 2019, 40(3): 98-104.
［7］陈刚, 付江月. 军民融合背景下无人机配送中心选址问题研究［J］. 计算机工程与应用, 2019, 55(8): 226-231, 237.Chen Gang, Fu Jiangyue. Drone distribution center location problem under military-civilian integration strategy［J］. Computer Engineering and Applications, 2019, 55(8): 226-231, 237.
［8］魏法杰, 卢珊, 张羽. 某实际型号无人机试飞风险评估案例［J］. 中国管理科学, 2014(S1): 199-204.Wei Fajie, Lu Shan, Zhang Yu. Case study on a UAV test flight risk evaluation［J］. Chinese Journal of Management Science, 2014(S1): 199-204.
［9］刘子齐, 牛新源. 无人机配送的血液供应链管理探讨［J］. 管理观察, 2018(1): 190-192.Liu Ziqi, Niu Xinyuan. Discussion on blood supply chain management of drone delivery［J］. Management Observer, 2018(1): 190-192.
［10］ 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.
［11］ Paul B, Niels A, Marie S. Dynamic programming approaches for the traveling salesman problem with drone［J］. SSRN Electronic Journal, 2017.
［12］ Wang X, Poikonen S, Golden B. The vehicle routing problem with drones: Several worst-case results［J］. Optimization Letters, 2017, 11(4): 679-697.
［13］罗志浩. 车载无人机双层协同路径规划问题研究［D］. 湖南: 国防科技大学, 2017.Luo Zhihao. Research on two-echelon ground vehicle and its mounted unmanned aerial vehicle cooperated routing problem［D］.Hunan: National University of Defense Technology, 2017.
［14］熊传明. 基于无人机和货车协同送货的调度与路径规划算法研究［D］. 湖北: 华中科技大学, 2018.Xiong Chuanming. A thesis submitted in partial fulfillment of the requirements for the degree for the master of engineering［D］.Hubei: Huazhong University of Science & Technology, 2018.
［15］ Carlsson J G, Song S. Coordinated logistics with a truck and a drone［J］. Management Science, 2018(1): 18-26.
［16］ Drexl M. On some generalized routing problems［D］. Aachen: RWTH Aachen University, 2007.
［17］ Drexl M. Synchronization in vehicle routing—A survey of VRPs with multiple synchronization constraints［J］. Transportation Science, 2012, 46(3): 297-316.
［18］ Chao I M. A tabu search method for the truck and trailer routing problem［J］. Computers & Operations Research, 2002, 29(1): 33-51.
［19］ Villegas J G, Prins C, Prodhon C, et al. A GRASP with evolutionary path relinking for the truck and trailer routing problem［J］. Computers & Operations Research, 2011, 38(9): 1319-1334.
［20］ Lin S W, Yu V F, Chou S Y. Solving the truck and trailer routing problem based on a simulated annealing heuristic［J］. Computers & Operations Research, 2009, 36(5): 1683-1692.
［21］葛显龙, 徐玖平, 王伟鑫. 交通限行条件下基于车辆协作的城市物流换乘联运问题研究［J］. 中国管理科学, 2017, 25(10): 130-139.Ge Xianlong, Xu Jiuping, Wang Weixin. The vehiclecoordination strategy and transfer combined transport to urban distribution problem under traffic restrictions［J］. Chinese Journal of Management Science, 2017, 25(10): 130-139.
［22］李阳, 范厚明, 张晓楠, 等. 求解模糊需求车辆路径问题的两阶段变邻域禁忌搜索算法［J］. 系统工程理论与实践, 2018, 38(2): 522-531.Li Yang, Fan Houming, Zhang Xiaonan, et al. Two-phase variable neighborhood tabu search for the capacitated vehicle routing problem with fuzzy demand［J］. Systems Engineering-Theory & Practice, 2018, 38(2): 522-531.
［23］ Solomon M M. Algorithms for the vehicle routing and scheduling problems with time window constraints［J］. Operations Research, 1987, 35(2): 254-265.
［24］ Iori M, Juan J S G, Vigo D. An exact approach for the vehicle routing problem with two-dimensional loading constraints［J］. Transportation Science, 2007, 41(2):253-264.

[1]	李珍萍, 贾顺顺, 卜晓奇, 吴凌云, 张国维. 无人仓系统储位分配问题的优化模型与算法[J]. 中国管理科学, 2022, 30(1): 124-135.
[2]	邓婕, 池宏, 许保光. 基于有向图相似的应急响应程序模块化问题研究[J]. 中国管理科学, 2017, 25(4): 115-123.
[3]	赵宇哲, 周晶淼, 匡海波. 竞争环境下基于服务约束的轴-辐式海运网络优化研究[J]. 中国管理科学, 2016, 24(11): 47-57.
[4]	赵宇哲. 竞争环境下的轴-辐式集装箱海运网络设计问题[J]. 中国管理科学, 2015, 23(7): 103-112.
[5]	余鹏, 隽志才. 服务水平保证下应急抢修点选址模型及求解算法研究[J]. 中国管理科学, 2014, 22(3): 34-41.

考虑区域限制的卡车搭载无人机车辆路径问题研究

Research on Vehicle Routing Problem with Truck and Drone Considering Regional Restriction

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 5

Metrics

本文评价

推荐阅读 0