Journal of Computer Applications ›› 2021, Vol. 41 ›› Issue (5): 1406-1411.DOI: 10.11772/j.issn.1001-9081.2020081183

Special Issue: 先进计算

• Advanced computing • Previous Articles     Next Articles

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

ZHENG Liping, WANG Jianqiang, ZHANG Yuzhao, DONG Zuofan   

  1. School of Traffic and Transportation, Lanzhou Jiaotong University, Lanzhou Gansu 730070, China
  • Received:2020-08-06 Revised:2020-09-14 Online:2021-05-10 Published:2020-11-05
  • Supported by:
    This work is partially supported by the National Natural Science Foundation of China (71761025), the "Chunhui Plan" Cooperative Scientific Research Project of the Ministry of Education, the Scientific Research Funded Projects of Colleges and Universities in Gansu Province (2018A-023).

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

郑李萍, 王建强, 张玉召, 董祚帆   

  1. 兰州交通大学 交通运输学院, 兰州 730070
  • 通讯作者: 王建强
  • 作者简介:郑李萍(1996-),女,四川眉山人,硕士研究生,主要研究方向:智能交通系统、无人配送车路径规划;王建强(1980-),男,山东临沂人,副教授,博士,主要研究方向:智能交通系统、复杂系统、网络科学;张玉召(1981-),男,安徽砀山人,副教授,博士,主要研究方向:轨道交通运输组织与优化、客货运技术与管理;董祚帆(1994-),男,山西运城人,硕士研究生,主要研究方向:自动驾驶车辆路径规划。
  • 基金资助:
    国家自然科学基金资助项目(71761025);教育部“春晖计划”合作科研项目;甘肃省高等学校科研资助项目(2018A-023)。

Abstract: 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.

Key words: terminal delivery, autonomous delivery vehicle, minimum fleet, spatio-temporal network, path coverage problem, maximum flow problem

摘要: 为解决快递终端配送多时空任务驱动下的最小无人车队车辆数配置问题,提出一种随机优化方法。首先,分析服务时长和等待时长对无人车队行驶路线规划的影响,从而构建最短路径模型;然后,基于二维时空网络构造服务序列网络;其次,通过网络转换将最小无人车队车辆数配置问题转化为网络最大流问题,并建立以车队车辆数最小为目标的最小车队模型;最后,针对模型特征设计一种融合Dijkstra算法和Dinic算法的Dijkstra-Dinic算法来对最小无人车队车辆数配置问题进行求解。在四种不同规模的服务网络中进行仿真实验,实验结果表明:在不同成功服务率下,最小无人车队车辆数与服务网络规模呈正相关,但随等待时长的增加而减少并趋向于稳定;所提算法中所引入的One-stop算子大大提高了搜索效率,所提模型和算法适用于大规模服务网络中的最小车队计算。

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

CLC Number: