需求可拆分的无人机与卡车协同路径优化问题

doi:10.3969/j.issn.1007-7375.2022.01.007

工业工程 ›› 2022, Vol. 25 ›› Issue (1): 54-63,143.doi: 10.3969/j.issn.1007-7375.2022.01.007

需求可拆分的无人机与卡车协同路径优化问题

李妍峰^1,2, 李佳¹, 向婷¹

1. 西南交通大学经济管理学院;
2. 服务科学与创新四川省重点实验室，四川成都 610031

收稿日期:2020-10-20 发布日期:2022-03-02
作者简介:李妍峰(1980—)，女，四川省人，副教授，博士，主要研究方向为物流优化、交通优化
基金资助:
国家自然科学基金面上资助项目(72071161,71571150)；四川省科技厅应用基础研究资助项目(2020YJ0220)；西南交通大学智慧物流与供应链管理研究生导师团队资助项目(YJSY-DSTD201918)

Split-delivery Vehicle Routing Problem with Drone

LI Yanfeng^1,2, LI Jia¹, XIANG Ting¹

1. School of Economics and Management;
2. Service Science and Innovation Key Laboratory of Sichuan Province, Southwest Jiaotong University, Chengdu 610031, China

Received:2020-10-20 Published:2022-03-02

摘要/Abstract

摘要： 基于无人机配送优势，提出一类无人机与卡车分区域协同配送问题。考虑需求稀疏地区由无人机配送，需求密集地区由卡车与无人机协同配送的情形。由于无人机的载重能力较小，无人机访问的顾客需求允许被拆分。结合无人机与卡车的访问路径关系，以最小化运输成本和使用卡车的人力成本为目标建立混合整数规划模型，并设计一种改进变邻域搜索算法对问题进行求解。小规模算例的特性分析表明，运输成本对无人机的载重能力及单位运输成本敏感性较高。多个不同规模的算例测试表明，改进变邻域搜索算法能在较短时间内有效求解各规模算例，且算法稳定性较好。

关键词: 无人机, 车辆路径问题, 需求可拆分, 协同配送, 改进变邻域搜索算法

Abstract: Based on the advantages of drone distribution, a regional collaborative distribution problem between drone and truck is proposed. Considering the situation that drone is used to distribute in sparse area and truck and drone cooperate in demand intensive area, due to the small load capacity of drone, the customer demand of drone access is allowed to be split. Combined with the access path relationship between drone and truck, a mixed integer programming model is established to minimize the transportation cost and the labor cost of using truck, and an improved variable neighborhood search algorithm is designed to solve the problem. The characteristic analysis of small-scale calculation shows that the transportation cost is sensitive to the load capacity and unit transportation cost of drone. The test results of several different scale examples show that the improved variable neighborhood search algorithm can effectively solve the cases of various scales in a short time, and the algorithm has a good stability.

Key words: drone, vehicle routing problem, split-delivery, collaborative distribution, improved variable neighborhood search

中图分类号:

F253.4

李妍峰, 李佳, 向婷. 需求可拆分的无人机与卡车协同路径优化问题[J]. 工业工程, 2022, 25(1): 54-63,143.

LI Yanfeng, LI Jia, XIANG Ting. Split-delivery Vehicle Routing Problem with Drone[J]. Industrial Engineering Journal, 2022, 25(1): 54-63,143.

参考文献

[1] MURRAY C C, CHU A G. The flying sidekick traveling salesman problem: optimization of drone-assisted parcel delivery[J]. Transportation Research Part C:Emerging Technologies, 2015, 54: 86-109
[2] HA Q M, DEVILLE Y, PHAM Q D, et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C:Emerging Technologies, 2018, 86: 597-621
[3] YUREK E E, OZMUTLU H C. A decomposition-based iterative optimization algorithm for traveling salesman problem with drone[J]. Transportation Research Part C:Emerging Technologies, 2018, 91: 249-262
[4] PONZA A. Optimization of drone-assisted parcel delivery[D]. Padova: University of Padova, 2016.
[5] CARLSSON J G, SONG S. Coordinated logistics with a truck and a drone[J]. Management Science, 2017, 64(9): 4052-4069
[6] 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
[7] CHANG Y S, LEE H J. Optimal delivery routing with wider drone-delivery areas along a shorter truck-route[J]. Expert Systems with Applications, 2018, 104: 307-317
[8] WANG Z, SHEU J B. Vehicle routing problem with drones[J]. Transportation Research Part B: Methodological, 2019, 122: 350-364
[9] KITJACHAROENCHAI P, VENTRESCA M, MOSHREF-JAVADI M, et al. Multiple traveling salesman problem with drones: mathematical model and heuristic approach[J]. Computers & Industrial Engineering, 2019, 129: 14-30
[10] SCHERMER D, MOEINI M, WENDT O. A matheuristic for the vehicle routing problem with drones and its variants[J]. Transportation Research Part C: Emerging Technologies, 2019, 106: 166-204.
[11] SCHERMER D, MOEINI M, WENDT O. A hybrid VNS/Tabu search algorithm for solving the vehicle routing problem with drones and en route operations[J]. Computers & Operations Research, 2019, 109: 134-158
[12] SACRAMENTO D, PISINGER D, ROPKE S. An adaptive large neighborhood search metaheuristic for the vehicle routing problem with drones[J]. Transportation Research Part C:Emerging Technologies, 2019, 102: 289-315
[13] PUGLIESE L D P, GUERRIERO F. Last-mile deliveries by using drones and classical vehicles[C]//International Conference on Optimization and Decision Science. Switzerland: Springer, Cham, 2017: 557-565.
[14] 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:Emerging Technologies, 2018, 91: 1-14
[15] 魏京婷. 京东无人机送出试运营第一单智慧物流实现乡村落地 [DB/OL]. (2016-06-08). http://finance.ce.cn/rolling/201606/08/t20160608_12654261.shtml.
[16] BOUZID M C, HADDADENE H A, SALHI S. An integration of Lagrangian split and VNS: the case of the capacitated vehicle routing problem[J]. Computers & Operations Research, 2017, 78: 513-525
[17] DHAHRI A, MJIRDA A, ZIDI K, et al. A VNS-based heuristic for solving the vehicle routing problem with time windows and vehicle preventive maintenance constraints[J]. Procedia Computer Science, 2016, 80: 1212-1222
[18] DE FREITAS J C, PENNA P H V. A variable neighborhood search for flying sidekick traveling salesman problem[J]. International Transactions in Operational Research, 2020, 27(1): 267-290
[19] DE FREITAS J C, PENNA P H V. A randomized variable neighborhood descent heuristic to solve the flying sidekick traveling salesman problem[J]. Electronic Notes in Discrete Mathematics, 2018, 66: 95-102

需求可拆分的无人机与卡车协同路径优化问题

Split-delivery Vehicle Routing Problem with Drone

RichHTML

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

本文评价

[1]	闫军, 常乐, 王璐璐, 赵彤. 带时间窗的同时取送货车辆路径问题求解算法[J]. 工业工程, 2021, 24(5): 72-76.
[2]	李博威, 户佐安, 贾叶子, 唐诗韵. 带软时间窗的同时取送货车辆路径问题研究[J]. 工业工程, 2020, 23(5): 75-81.
[3]	芦娟, 夏扬坤, 邹安全, 符卓, 王松, 魏占国, 符瑛. 带装载能力的需求依背包拆分车辆路径问题[J]. 工业工程, 2019, 22(6): 67-73.
[4]	江海, 陈峰. 面向快递同城运输的车辆路径问题研究[J]. 工业工程, 2019, 22(4): 58-63.
[5]	冯春, 秦冰芳, 叶露. 共享电动车电池配送问题研究[J]. 工业工程, 2019, 22(3): 52-56.
[6]	户佐安, 贾叶子, 李博威, 刘陆. 考虑客户满意度的车辆路径优化研究[J]. 工业工程, 2019, 22(1): 100-107.
[7]	贺政纲，刘沙. 考虑均衡负载的车辆路径问题及算法设计[J]. 工业工程, 2015, 18(4): 140-145.
[8]	陈震1，徐丽萍2. 碳政策下货运企业运营成本比较分析[J]. 工业工程, 2015, 18(3): 55-62.
[9]	谢天保1，张晓雯1，仵凯博2，胡丹1. 电子商务下基于协同配送的配送中心选址研究[J]. 工业工程, 2015, 18(3): 75-81.
[10]	侯玲娟1, 周泓2. 基于离散差分进化算法的随机车辆路径问题[J]. 工业工程, 2014, 17(3): 101-107.
[11]	方卫国，蔡伟宁. 基于Gram'Schmidt回归的军用无人机研制费用预测[J]. 工业工程, 2013, 16(6): 29-33.
[12]	寇明顺，叶春明，陈子皓. 应用蜜蜂繁殖进化型粒子群算法求解车辆路径问题[J]. 工业工程, 2012, 15(1): 23-27.
[13]	彭碧涛1,2，周永务1. 三维装载约束的车辆路径问题的模拟退火算法[J]. 工业工程, 2011, 14(5): 71-74.