欢迎访问《汽车安全与节能学报》，
汽车安全与节能学报

JASE ›› 2020, Vol. 11 ›› Issue (1): 102-110.DOI: 10.3969/j.issn.1674-8484.2020.01.011

• 汽车安全 • 上一篇    下一篇

智能移动系统中大规模分布式车辆路径规划问题研究

李 伟 1,2,4,5，郭继孚 2，  缐 凯 2*，商   攀1，杨少峰 3#br#   

  1. （1. 北京交通大学 交通运输学院，北京 100044，中国；
        2. 北京交通发展研究院，北京 100073，中国； 
        3. 中国科学院 计算技术研究所，北京 100190，中国；
        4. 城市交通运行仿真与决策支持北京实验室， 北京 100073，中国；
        5. 城市交通北京市国际科技合作基地，北京 100073，中国）
  • 收稿日期:2019-12-18 出版日期:2020-03-31 发布日期:2020-04-01
  • 通讯作者: 缐凯 (1980—)，男 ( 汉)，北京，高级工程师。E-mail: xiank@bjtrc.org.cn。
  • 作者简介:第一作者 / First author： 李伟 (1982—），男 ( 汉)，陕西，博士后。E-mail: 09111015@bjtu.edu.cn。
  • 基金资助:
     国家重点研发计划“大规模网联车辆协同服务核心技术” (2018YFB1600703)。

Large scale distributed transportation vehicle routing for smart mobility systems

LI Wei 1,2,4,5, GUO Jifu 2,  XIAN Kai 2*，SHANG Pan 1, YANG Shaofeng3   

  1. (1. School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China; 
     2. Beijing Transport Institute, Beijing 100073, China; 
     3. Institute of Computing Technology, Chinese Academy of Sciences, Beijing, 100190, China; 
     4. Beijing Municipal Key Laboratory of Urban Transport Operation Simulation and Decision Support, Beijing 100073, China; 
     5. Beijing International Technology Cooperation Base for Urban Transport, Beijing 100073, China)
  • Received:2019-12-18 Online:2020-03-31 Published:2020-04-01

PDF

318

摘要： 本文针对智能交通和主动交通管理提出了一种适用于大规模交通分配和路径规划的分布式计 算方法。讨论了通过信息传递接口（MPI）在多中央处理器（ CPU）上并行计算实现的一系列研究需求和 实现挑战；将基于时空事件的车辆路径规划模型应用于大规模的城市路网仿真；将原始车辆路径规划 模型分解为一系列计算效率较高的子问题，大幅减少了仿真耗时和通信开销。通过将子问题分发到单 独的分布式 CPU上，使 CPU 可以同时执行其任务，并保证较好的负载平衡。重点分析了将所提出的 方法应用于北京路网大规模路径规划，以及该方法在不同 CPU 核数下的计算效率。结果表明：所提 出的并行计算方法可以显著减少计算耗时，并在 512 个计算节点上实现 200 倍以上的加速比。

关键词: 交通管理 , 智能移动系统 (SMS) , 交通分配 , 基于树的算法 , 并行计算

Abstract: A new application of distributed computing for large-scale traffic vehicular assignment and routing problems was proposed for smart mobility and proactive traffic management applications. A range of research needs and realization challenges for parallel computing implementation on multi-central processing units （CPU）through multi process interface (MPI) were discussed. A space-time event-based vehicle routing model was applied in a large scale urban network simulation setting. The primal vehicle routing model was decomposed into a set of computationally efficient sub-problems, which could significantly reduce the simulation time cost and communication overhead. The sub-problems were then assigned to independent distributed CPUs that can execute their tasks simultaneously and maintain excellent load balancing. The proposed method was applied to simulate a pilot study in Beijing metropolitan area, specifically in large scale routing and scheduling cases, the computational efficiency was examined under different number of CPU cores. The results show that the proposed parallel computing method can significantly reduce the computing time and reach a speedup of more than 200 on 512 computation nodes.  

Key words: raffic management , smart mobility system (SMS) ,  traffic assignment ,  tree based algorithm , parallel computing