KMG:考虑逆向物流的无人机路径规划策略研究

裴颂文, 沈天马, 宁钟, 谢雨鸣

系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (12) : 3111-3119.

PDF(1223 KB)
PDF(1223 KB)
系统工程理论与实践 ›› 2019, Vol. 39 ›› Issue (12) : 3111-3119. DOI: 10.12011/1000-6788-2018-0679-09
论文

KMG:考虑逆向物流的无人机路径规划策略研究

    裴颂文1,2, 沈天马2, 宁钟1, 谢雨鸣1
作者信息 +

KMG: Study on UAV path planning strategy by considering reverse logistics

    PEI Songwen1,2, SHEN Tianma2, NING Zhong1, XIE Yuming1
Author information +
文章历史 +

摘要

物流领域无人机派送正成为一种快捷高效的派件方式和应用热点.针对于正向、逆向的物流数据,无人机派送是国内外大型物流企业实施高效物流派送的重要手段.本文提出了一种融合拓展性K-Means++算法和遗传算法的路径动态规划模型(KMG),实现包含逆向物流的无人机调度策略.KMG模型将逆向物流路径融入正向物流路径之中,采用加权聚类算法确定不同属性包裹所需派送无人机的最小数量.在每一簇坐标数据的连通图中,采用遗传算法求解TSP问题,并对可行解进行编码,最终求解出最小欧拉回路.在仿真实验中,KMG模型比独立逆向物流派送的成本减少20.08%,使用拓展性K-Means++聚类计算的时间比传统K-Means算法缩短了298.85%.

Abstract

Delivery by UAV in the logistics field is becoming a fast and efficient dispatch method and application hotspot. For forward and reverse logistics data, drone dispatch is an important means for large-scale logistics enterprises at home and abroad to implement efficient logistics delivery. A path dynamic programming model (KMG) that integrates the scalable K-Means++ algorithm and genetic algorithm to implement a UAV scheduling strategy including reverse logistics. The KMG model integrates the reverse logistics path into the forward logistics path, using weighted clustering. The algorithm determines the minimum number of dispatched drones required for different attribute packages. For each connected graph of coordinate data, the genetic algorithm is used to solve the TSP problem and the feasible solution is coded, and finally the minimum Euler loop is solved. The simulation results show that the cost of the KMG model is 20.08% lower than that of the independent reverse logistics. The time of using the scalable K-Means++ clustering calculation is 298.85% shorter than the traditional K-Means algorithm.

关键词

无人机 / 逆向物流 / 拓展性K-Means++ / 遗传算法 / 路径规划

Key words

UAV / reverse logistics / scalable K-Means++ / genetic algorithm / path planning

引用本文

导出引用
裴颂文 , 沈天马 , 宁钟 , 谢雨鸣. KMG:考虑逆向物流的无人机路径规划策略研究. 系统工程理论与实践, 2019, 39(12): 3111-3119 https://doi.org/10.12011/1000-6788-2018-0679-09
PEI Songwen , SHEN Tianma , NING Zhong , XIE Yuming. KMG: Study on UAV path planning strategy by considering reverse logistics. Systems Engineering - Theory & Practice, 2019, 39(12): 3111-3119 https://doi.org/10.12011/1000-6788-2018-0679-09
中图分类号: O221.3   

参考文献

[1] Lin C E, Dimpudus K K, Hsu Y C. Airspace risk assessment in logistic path planning for UAV[C]//Integrated Communications, Navigation and Surveillance Conference (ICNS), 2017:1-9.
[2] Doherty P, Rudol P. A UAV search and rescue scenario with human body detection and geolocalization[C]//Australian Conference on Artificial Intelligence, 2007:1-13.
[3] Remy M A, de Macedo K A C, Moreira J R. The first UAV-based P-and X-band interferometric SAR system[C]//2012 IEEE International Geoscience and Remote Sensing Symposium. IEEE, 2012:5041-5044.
[4] Kim J, Morrison J R. On the concerted design and scheduling of multiple resources for persistent UAV operations[J]. Journal of Intelligent Robotic Systems, 2014, 74:479-498.
[5] Song B D, Kim J, Morrison J R. Towards real time scheduling for persistent UAV service:A rolling horizon MILP approach, RHTA and the STAH heuristic[J]. Unmanned Aircraft Systems, 2014:506-515.
[6] Song B D, Kim J, Kim J, et al. Persistent UAV service:An improved scheduling formulation and prototypes of system components[J]. Journal of Intelligent & Robotic Systems, 2013, 74(1-2):221-232.
[7] El-Sayed M, Afia N, El-Kharbotly A. A stochastic model for forward-reverse logistics network design under risk[J]. Computers & Industrial Engineering, 2010, 58(3):423-431.
[8] Kannan D, Diabat A, Alrefaei M, et al. A carbon footprint based reverse logistics network design model[J]. Resources Conservation and Recycling, 2012, 67:75-79.
[9] Alumur S A, Nickel S, Saldanha-Da-Gama F, et al. Multi-period reverse logistics network design[J]. European Journal of Operational Research, 2012, 220(1):67-78.
[10] Yu H, Solvang W D. Improving the decision-making of reverse logistics network design part I:A MILP model under stochastic environment[J]. Advanced Manufacturing and Automation VII, February 2018:431-438.
[11] Zokaee S, Jabbarzadeh A, Fahimnia B, et al. Robust supply chain network design:An optimization model with real world application[J]. Annals of Operations Research, 2014, 257(1-2):15-44.
[12] Eskandarpour M, Dejax P, Pè ton O. A large neighborhood search heuristic for supply chain network design[J]. Computers & Operations Research, 2017, 80:23-37.
[13] Govindan K, Paam P, Abtahi A R. fuzzy multi-objective optimization model for sustainable reverse logistics network design[J]. Ecological Indicators, 2016, 67:753-768.
[14] Sun X, Wu C C, Chen L R. Analysis and design of the logistics system for rope manufacturing plant[C]//MATEC Web of Conferences, 2017, 139.
[15] Choi S G, Jung W J, Choi J H. 3D-based UAV path-planning algorithm considering altitude and reconnaissance areas[J]. International Journal of Transportation and Logistics Management, 2017, 1(1):9-16.
[16] Yang J F, Zeng Z Y, Fang Z. Traffic detection system based on unmanned aerial vehicle integrated analysis (UAVIA) in e-business logistics[C]//IEEE International Conference on E-business Engineering, IEEE Computer Society, 2015.
[17] Rana K, Praharaj S, Nanda T. Unmanned aerial vehicles (UAVs):An emerging technology for logistics[J]. International Journal of Business and Management Invention, 2016, 5(5):86-92.
[18] Bahmani B, Moseley B, Vattani A, et al. Scalable k-means++[J]. Proceedings of the VLDB Endowment, 2012, 5(7):622-633.
[19] Jain A K. Data clustering:50 years beyond K-means[J]. Pattern Recognition Letters, 2010, 31(8):651-666.
[20] Cui X L, Zhu P F, Yang X, et al. Optimized big data K-means clustering using MapReduce[J]. The Journal of Supercomputing, 2014, 70(3):1249-1259.
[21] Archer A, Bateni M H, Hajiaghayi M T, et al. Improved approximation algorithms for prize-collecting Steiner tree and TSP[J]. SIAM Journal on Computing, 2011, 40(2):309-332.
[22] Mo Y. The Advantage of Intelligent Algorithms for TSP[M]//Traveling Salesman Problem, Theory and Applications. Rijeka:InTech, 2010:25-40.
[23] 侯玉梅, 贾震环, 田歆, 等. 带软时间窗整车物流配送路径优化研究[J]. 系统工程学报, 2015, 30(2):240-250.Hou Y M, Jia Z H, Tian X, et al. Research on the optimization on the vehicle logistics distribution with soft time windows[J]. Journal of Systems Engineering, 2015, 30(2):240-250.
[24] Razali N M, Geraghty J. Genetic algorithm performance with different selection strategies in solving TSP[C]//Pro-ceedings of the world congress on engineering, 2011, 2(1):1-6.
[25] 黄凯明,卢才武,连民杰. 三层级设施选址-路径规划问题建模及算法研究[J].系统工程理论与实践, 2018, 38(3):743-754.Huang K M, Lu C W, Lian M J. Research on modeling and algorithm for three-echelon location-routing problem[J]. Systems Engineering-Theory & Practice, 2018, 38(3):743-754.
[26] An H C, Kleinberg R, Shmoys D B. Improving Christofides' algorithm for the s-t path TSP[J]. Journal of the ACM (JACM), 2015, 62(5):article34, 28 pages. doi:http://dx.doi.org/10.1145/2818310.
[27] Karpinski M, Lampis M, Schmied R. New inapproximability bounds for TSP[J]. Journal of Computer and System Sciences, 2015, 81(8):1665-1677.

基金

上海市浦江人才(16PJ1407600);中国博士后科学基金(2017M610230);国家自然科学基金重点项目(61332009);国家自然科学基金面上项目(61775139);上海市自然科学基金(15ZR1428600)
PDF(1223 KB)

871

Accesses

0

Citation

Detail

段落导航
相关文章

/