考虑动态能耗的无人机配送选址路径规划研究

doi:10.3778/j.issn.1002-8331.2203-0489

摘要/Abstract

摘要： 随着无人机在城市配送的兴起，在联合配送模式下，配送中心的选址规划及与全自动机场之间的路径规划成为亟待解决的问题之一。根据无人机运营成本、电池能耗和配送中心管理成本构建以最佳综合运营成本和最小能耗为目标的选址-路径模型；基于K-means算法寻找最佳配送中心选址，运用遗传算法对配送路径进行求解；以天津市主城区为例进行模型应用及结果分析。结果表明天津市主城区共需40个配送中心，随着需求点增多，无人机数量和成本增加，总能耗呈波动式上升；分析发现使用载荷3.5~5.0?kg的无人机机型，覆盖范围在3~4?km内的配送中心使得配送效果更优。研究结果为城市无人机配送中心选址、路径规划以及机型选择、服务范围等提供了建设性建议。

关键词: 选址-路径规划, 物流无人机配送, 动态能耗, 无人机全自动机场, 配送中心

Abstract: With the rise of drones in urban distribution, under the joint distribution mode, the location planning of distribution centre and the path planning between distribution centre and automatic airport have become one of the urgent problems to be solved under the joint distribution. Firstly, a location-path model aiming at the best comprehensive operating cost and minimum energy consumption is constructed according to the UAV operating cost, battery energy consumption and distribution centre management cost. Secondly, the optimal location of distribution centre is found based on K-means algorithm, and the genetic algorithm is used to solve the distribution route. Finally, the main urban area of Tianjin is taken as an example to apply the model and analyze the results. The results show that a total of 40 distribution centres are needed in the main urban area of Tianjin. As demand points increase, the number and cost of drones increase, and total energy consumption increases in a fluctuating manner. It is found that the distribution effect is better with the use of drones with 3.5~5.0?kg payload and distribution centres with coverage within 3~4?km. The research results provide constructive suggestions for urban UAV distribution centre location, path planning, aircraft type selection, service range and so on.

Key words: location-path planning, distribution of logistic drones, dynamic energy consumption, unmanned automatic vertiport, distribution centre

任新惠, 王佳雪, 王梦琦. 考虑动态能耗的无人机配送选址路径规划研究[J]. 计算机工程与应用, 2023, 59(13): 273-280.

REN Xinhui, WANG Jiaxue, WANG Mengqi. Research on Drone Distribution Location-Path Planning Considering Dynamic Energy Consumption[J]. Computer Engineering and Applications, 2023, 59(13): 273-280.

参考文献

[1] WEBER A，FRIEDRICH C J.Alfred Weber’s theory of the location of industries[J].Journal of Political Economy，1929，38（2）：232-234.
[2] HAMERS H，BORM P，LEENSEL R，et al.Cost allocation in the Chinese postman problem[J].European Journal of Operational Research，1999，118（1）：153-163.
[3] CHU T C，LAI M T.Selecting distribution center location using an improved fuzzy MCDM approach[J].International Journal of Advanced Manufacturing Technology，2005，26（3）：293-299.
[4] 陈绍洵.电子商务模式下生鲜自提柜节点选址研究[D].北京：北京交通大学，2018.
CHEN S X.Location of fresh product self-collection cabinet in ecommerce[D].Beijing：Beijing Jiaotong University，2018.
[5] GAO X.A location driven approach for warehouse location problem[J].Journal of the Operational Research Society，2021，72（12）：2735-2754.
[6] 韩珣.考虑顾客需求异质性的自提服务网络优化研究[D].成都：西南交通大学，2019.
HAN X.Optimization of pickup service network under customer demand heterogeneity[D].Chengdu：Southwest Jiaotong University，2019.
[7] 曾若兰.基于共同配送的城市快递末端服务站选址优化研究[D].北京：北京邮电大学，2020.
ZENG R L.Research on location optimization of urban express terminal service station based on joint distribution[D].Beijing：Beijing University of Posts and Telecommunications，2020.
[8] ZHANG S Z，LEE C K M.Optimization of facility location problem in reverse logistics network using artificial bee colony algorithm[C]//Proceedings of IEEE International Conference on Industrial Engineering and Engineering Management，Bangkok，Thailand，Dec 10-13，2013：1348-1352.
[9] 赵世安，屈池文.改进的布谷鸟算法求解物流配送中心选址问题[J].数学的实践与认识，2017，47（3）：206-213.
ZHAO S A，QU C W.An improve cuckoo algorithm for solving the problem of logistics distribution center location[J].Journal of Mathematics in Practice and Theory，2017，47（3）：206-213.
[10] GUERREIRO N M，HAGEN G E，MADDALON J M，et al.Capacity and throughput of urban air mobility vertiports with a first-come，first-served vertiport scheduling algorithm[C]//Proceedings of AIAA Aviation 2020 Forum，Virtual Event，June 15-19，2020：2903.
[11] VASCIK P D，HANSMAN R J.Development of vertiport capacity envelopes and analysis of their sensitivity to topological and operational factors[C]//Proceedings of AIAA Scitech 2019 Forum，San Diego，California，Jan 7-11，2019.
[12] VENKATESH N，PAYAN A P，JUSTIN C，et al.Optimal siting of sub-urban air mobility（sUAM） ground architectures using network flow formulation[C]//Proceedings of AIAA Aviation 2020 Forum，Virtual Event，June 15-19，2020：2921.
[13] JEONG J，SO M，HWANG H Y.Selection of vertiports using k-means algorithm and noise analyses for urban air mobility（UAM） in the Seoul metropolitan area[J].Applied Sciences，2021，11（12）：5729.
[14] 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（2）：1-18.
[15] 陈刚，付江月.军民融合背景下无人机配送中心选址问题研究[J].计算机工程与应用，2019，55（8）：226-231.
CHEN G，FU J Y.Drone distribution center location problem under military-civilian integration strategy[J].Computer Engineering and Applications，2019，55（8）：226-231.
[16] 金垚炜.基于二层规划的无人机城市即时配送定位-路径优化研究[D].杭州：浙江工商大学，2018.
JIN Y W.Research on the drones real-time urban distribution location-path optimization based on bl-level programming[D].Hangzhou：Zhejiang Gongshang University，2018.
[17] 钱欣悦，张洪海，张芳，等.末端配送物流无人机起降点选址分配问题研究[J].武汉理工大学学报（交通科学与工程版），2021，45（4）：682-687.
QIAN X Y，ZHANG H H，ZHANG F，et al.Research on location allocation of UAV landing points for terminal distribution logistics[J].Journal of Wuhan University of Technology（Transportation Science & Engineering），2021，45（4）：682-687.
[18] MUFALLI F，BATTA R，NAGI R.Simultaneous sensor selection and routing of unmanned aerial vehicles for complex mission plans[J].Computers & Operations Research，2012，39（11）：2787-2799.
[19] 张启钱，许卫卫，张洪海，等.复杂低空物流无人机路径规划[J].北京航空航天大学学报，2020，46（7）：1275-1286.
ZHANG Q Q，XU W W，ZHANG H H，et al.Path planning for logistics UAV in complex low-altitude airspace[J].Journal of Beijing University of Aeronautics and Astronautics，2020，46（7）：1275-1286.
[20] MURRAY C C，RAJ R.The multiple flying sidekicks traveling salesman problem：parcel delivery with multiple drones[J].Transportation Research Part C：Emerging Technologies，2020，110（1）：368-398.
[21] LIU Y，LIU Z，SHI J，et al.Two-echelon routing problem for parcel delivery by cooperated truck and drone[J].IEEE Transactions on Systems，Man，and Cybernetics：Systems，2020，51（12）：7450-7465.