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

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

Large scale distributed transportation vehicle routing for smart mobility systems

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.