Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs

doi:10.12005/orms.2021.0141

Operations Research and Management Science ›› 2021, Vol. 30 ›› Issue (5): 31-37.DOI: 10.12005/orms.2021.0141

• Theory Analysis and Methodology Study • Previous Articles Next Articles

Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs

WANG Xin¹, WANG Zheng², XU Wei¹

1. School of Transportation Engineering, Dalian Maritime University, Dalian 116026, China;
2. School of Maritime Economics and Management, Dalian Maritime University, Dalian 116026, China

Received:2019-08-11 Online:2021-05-25

面向多个无人机站点的车辆与无人机联合配送路径问题研究

王新¹, 王征², 徐伟¹

1.大连海事大学交通运输工程学院,辽宁大连 116026;
2.大连海事大学航运经济与管理学院,辽宁大连 116026

作者简介:王新(1995-),男,吉林松原人,硕士研究生,研究方向:物流系统优化;王征(1978-),男,辽宁大连人,教授,博士生导师,研究方向:物流系统优化。
基金资助:
国家自然科学基金项目(71971036,71971037,71571027,71531002);教育部人文社科一般项目(19YJA630084);大连市重点学科重大课题研究项目(2019J11CY002);辽宁省科技厅重点研发计划项目(2020JH2/10100042)

Abstract

Abstract: The joint distribution mode of vehicle and drone is popular in the industry. This mode effectively reduces the distribution cost, but it has great scheduling difficulty, and the solution of the problem is also very complex. In this paper, the problem is clearly defined and the model is established. According to the characteristics of the problem, an adaptive large neighborhood search (ALNS) algorithm is designed. The results show that, compared with Gurobi, ALNS algorithm has obvious advantages in running time, and the results are the same or even better; the joint distribution mode of vehicle and drone also saves the cost compared with the only truck distribution mode.

Key words: truck and drone joint distribution, dronehubs, vehicle routing problem, adaptive large neighborhood search

摘要： 车辆与无人机联合配送模式在产业界受到青睐,该模式有效地降低了配送成本,但却有极大的调度难度,问题的求解也非常复杂。本文对问题进行明确定义并建立模型,根据问题特性设计了一个自适应大规模邻域搜索(Adaptive Large Neighborhood Search, ALNS)算法,进行了大量的实验的对比和分析。研究结果表明,ALNS算法相比Gurobi在运行时间上有明显优势,结果相同甚至更优;车辆与无人机联合配送模式也较仅卡车配送模式节约了成本。

关键词: 车辆与无人机联合配送, 无人机站点, 车辆路径问题, 自适应大规模邻域搜索算法

CLC Number:

U116

WANG Xin, WANG Zheng, XU Wei. Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs[J]. Operations Research and Management Science, 2021, 30(5): 31-37.

王新, 王征, 徐伟. 面向多个无人机站点的车辆与无人机联合配送路径问题研究[J]. 运筹与管理, 2021, 30(5): 31-37.

References

[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] Kim S, Moon I. Traveling salesman problem with a drone station[J]. IEEE Transactions on Systems, Man, and Cybernetics: Systems, 2018, 49(1): 42-52.
[3] Agatz N A H, Bouman P C, Schmidt M E. Optimization approaches for the traveling salesman problem with drone[J]. Transportation Science, 2016, 52(4): 965-981.
[4] Ha Q M, Deville Y, Pham Q D, HaM H. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C: Emerging Technologies, 2018, 86: 597-621.
[5] Mathew N, Smith S L, Waslander S L. Planning paths for package delivery in heterogeneous multirobot teams[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(4): 1298-1308.
[6] Sergio M F, Timothy H, Troy W, Robert S, Robert R. Optimization of a truck-drone in tandem delivery network using k-means and genetic algorithm[J]. Journal of Industrial Engineering and Management, 2016, 9(2): 374-388.
[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] Khosiawan Y, Nielsen I. A system of UAV application in indoor environment[J]. Production & Manufacturing Research An Open Access Journal, 2016, 4(1): 2-22.
[9] 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.
[10] Chauhan D, Unnikrishnan A, Figliozzi M. Maximum coverage capacitated facility location problem with range constrained drones[J]. Transportation Research Part C: Emerging Technologies, 2019, 99: 1-18.
[11] Xia J, Wang K, Wang S. Drone scheduling to monitor vessels in emission control areas[J]. Transportation Research Part B: Methodological, 2019, 119: 174-196.
[12] Prodhon C, Prins C. A survey of recent research on location-routing problems[J]. European Journal of Operational Research, 2014, 238(1): 1-17.
[13] 李雪,何正文,王能民.不确定环境下基于时间、费用及鲁棒性权衡的多目标项目调度优化[J].运筹与管理,2019,28(1):10-20.
[14] Zhou Z, Chu F, Che A, Zhou M. Epsilon-constraint and fuzzy logic-based optimization of hazardous material transportation via lane reservation[J]. IEEE Transactions on Intelligent Transportation Systems, 2013, 14(2): 847-857.
[15] Zhang M, Wang N, He Z, Yang Z, Guan Y. Bi-objective vehicle routing for hazardous materials transportation with actual load dependent risks and considering the risk of each vehicle[J]. IEEE Transactions on Engineering Management, 2019, 66(3): 429-442.
[16] 邵路路,杨珺,杨超.电动汽车的市场需求和环境影响:功能更新与政府补贴[J].运筹与管理,2018(1):103-111.
[17] 李杰,赵旭东,王玉霞,CHU Chao-hsien.面向电商终端物流配送的电动车配置与路径集成优化[J].运筹与管理,2018(10):23-30.
[18] Ropke S, Pisinger D. An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows[J]. Transportation Science, 2006, 40(4): 455-472.
[19] Masson R, Lehuédé F, Péton O. An adaptive large neighborhood search for the pickup and delivery problem with transfers[J]. Transportation Science, 2013, 47(3): -44355.

Vehicle and Drone Joint Distribution Routing Problem with Multiple Drone Hubs

面向多个无人机站点的车辆与无人机联合配送路径问题研究

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

[1]	WANG Yu-qin, HU Hui, LIU Fu-xin, WANG Yan-hui, ZHAO Jiao, HAN Yi. Optimization of Unmanned Vehicle Distribution Path under Intelligent Network Connection [J]. Operations Research and Management Science, 2021, 30(8): 52-58.
[2]	XIANG Ting, LI Yan-feng. A Bi-objective Home Health Care Scheduling Problem: Based on Costs and Overtime [J]. Operations Research and Management Science, 2021, 30(8): 233-239.
[3]	ZHANG Xiao-nan, FAN Hou-ming. Hybrid Memetic Algorithm for Vehicle Routing Problem with Time Windows [J]. Operations Research and Management Science, 2021, 30(7): 128-135.
[4]	XUE Gui-qin, WANG Zheng. Dynamic Vehicle Routing Problem with Inventory Synergetic [J]. Operations Research and Management Science, 2021, 30(11): 19-25.
[5]	LIU Chang-shi, WANG Song, LUO Liang, DENG Sheng-qian. Open Vehicle Routing Problem Based on Joint Distribution Mode under Time-dependent Road Networks [J]. Operations Research and Management Science, 2021, 30(11): 26-33.
[6]	ZHANG Jian-tong, DING Ye. Simulated Annealing with Variable Neighborhood for Time-Dependent Vehicle Routing Problem with Time Window [J]. Operations Research and Management Science, 2019, 28(11): 77-84.
[7]	PAN Li-jun, FU Zhuo, LIU Xi-mei. Bike Sharing Rebalancing Problem and Capacity Range Length Insertion Heuristic Algorithm [J]. Operations Research and Management Science, 2019, 28(10): 26-32.
[8]	XU Guo-xun, LI Yan-feng, LI Jun, XU Guan-yu. A Multi-type Bike Repositioning Problem [J]. Operations Research and Management Science, 2019, 28(1): 116-124.
[9]	GUO Fang, YANG Jun, YANG Chao. Study on the Electric Vehicle Routing Problem and Pattery SwappingStrategy in the Presence of Cargo Category [J]. Operations Research and Management Science, 2018, 27(9): 33-44.
[10]	XU Guo-xun, LI Yan-feng, LI Jun, YANG fang. The Cash-in-transit Routing Optimization Problem with Multi-type Risks [J]. Operations Research and Management Science, 2018, 27(4): 72-82.
[11]	RAO Wei-zhen, LI Mei-yan, XUN Nan, WANG Bing-cheng, YU Hao, HOU Yan-hui. Research into the Average Loading Rate and 4-stage Algorithm of the Capacitated Vehicle Routing Problem [J]. Operations Research and Management Science, 2018, 27(12): 64-72.
[12]	MA Yan-fang, YAN Fang, KANG Kai, LI Zong-min. An Improved Particle Swarm Optimization for Simultaneous Pickup and Delivery Vehicle Routing Problems with Time [J]. Operations Research and Management Science, 2018, 27(12): 73-83.
[13]	LI Jie, ZHAO Xu-dong, WANG Yu-xia, CHU Chao-hsien. Integrated Optimization of Electric Vehicle Allocation & Routing forLarge Scale E-Commerce Terminal Logistics Distribution [J]. Operations Research and Management Science, 2018, 27(10): 23-30.
[14]	ZHANG Yuan-kai, SUN Li-jun, HU Xiang-pei. Multi-compartment Vehicle Dispatching and Routing for Product Oil Distribution [J]. Operations Research and Management Science, 2017, 26(7): 1-9.
[15]	LI Zhen-ping, ZHAO Fei, LIU Hong-wei. Intelligent Water Drops Algorithm for Vehicle Routing Problem with Multiple Time Windows [J]. Operations Research and Management Science, 2015, 24(6): 1-10.