多时空配送任务驱动的无人车队车辆数优化方法  

Vehicle number optimization approach of autonomous vehicle fleet driven by multi-spatio-temporal distribution task

作　　者：郑李萍 王建强[1] 张玉召[1] 董祚帆 ZHENG Liping;WANG Jianqiang;ZHANG Yuzhao;DONG Zuofan(School of Traffic and Transportation,Lanzhou Jiaotong University,Lanzhou Gansu 730070,China)

机构地区：[1]兰州交通大学交通运输学院,兰州730070

出　　处：《计算机应用》2021年第5期1406-1411,共6页journal of Computer Applications

基　　金：国家自然科学基金资助项目(71761025);教育部“春晖计划”合作科研项目;甘肃省高等学校科研资助项目(2018A-023)。

摘　　要：为解决快递终端配送多时空任务驱动下的最小无人车队车辆数配置问题,提出一种随机优化方法。首先,分析服务时长和等待时长对无人车队行驶路线规划的影响,从而构建最短路径模型;然后,基于二维时空网络构造服务序列网络;其次,通过网络转换将最小无人车队车辆数配置问题转化为网络最大流问题,并建立以车队车辆数最小为目标的最小车队模型;最后,针对模型特征设计一种融合Dijkstra算法和Dinic算法的Dijkstra-Dinic算法来对最小无人车队车辆数配置问题进行求解。在四种不同规模的服务网络中进行仿真实验,实验结果表明:在不同成功服务率下,最小无人车队车辆数与服务网络规模呈正相关,但随等待时长的增加而减少并趋向于稳定;所提算法中所引入的One-stop算子大大提高了搜索效率,所提模型和算法适用于大规模服务网络中的最小车队计算。A stochastic optimization method was proposed in order to solve the vehicle number allocation problem of the minimum autonomous vehicle fleet driven by spatio-temporal multi-tasks of terminal delivery.Firstly,the influence of service time and waiting time on the route planning of autonomous vehicle fleet was analyzed to build the shortest route model,and the service sequence network was constructed based on the two-dimensional spatio-temporal network.Then,the vehicle number allocation problem of the minimum autonomous vehicle fleet was converted into a network maximum flow problem through the network transformation,and a minimum fleet model was established with the goal of minimizing the vehicle number of the fleet.Finally,the Dijkstra-Dinic algorithm combining Dijkstra algorithm and Dinic algorithm was designed according to the model features in order to solve the vehicle number allocation problem of the minimum autonomous vehicle fleet.Simulation experiments were carried out in four different scales of service networks,the results show that:under different successful service rates,the minimum size of autonomous vehicle fleet is positively correlated with the scale of service network,and it decreases with the increase of waiting time and gradually tends to be stable,the One-stop operator introduced into the proposed algorithm greatly improves the search efficiency,and the proposed model and algorithm are suitable for the calculation of the minimum vehicle fleet in large-scale service network.

关 键 词：终端配送 无人配送车 最小车队 时空网络 路径覆盖问题 最大流问题 

分 类 号：TP242.6[自动化与计算机技术—检测技术与自动化装置] U492[自动化与计算机技术—控制科学与工程]