主题：Distributed computing approaches for large-scale traffic assignment problem
主讲人：东南大学刘志远教授
主持人：工商管理学院 肖峰教授
时间：2020年11月8日（周日）15:00-16:00
直播平台及会议ID：腾讯会议，会议ID：564 165 641
主办单位：工商管理学院科研处
主讲人简介：
刘志远，东南大学交通学院教授、博导、副院长，复杂交通网络研究中心主任，东南大学网络空间安全学院博导，澳大利亚蒙纳士大学客座教授。入选国家自科基金优青、江苏省“双创人才”、江苏省“青年双创英才”、东南大学“青年首席教授”，获评东南大学“五四青年奖章”。2011年毕业于新加坡国立大学，获博士学位，并随后留校进行博士后研究一年。自2015年回到东南大学交通学院工作。归国前就职于澳大利亚蒙纳士大学土木工程系，任讲师、博导。2017年12月至2018年1月，澳大利亚墨尔本大学数学系访问学者。主要研究领域包括交通网络规划与管理、交通大数据分析与建模、公共交通、多模式物流网络等。迄今为止在这些领域中发表学术论文百余篇，其中被SCI/SSCI期刊检索70余篇。Google Scholar引用2000余次。担任交通研究领域知名SCI期刊ASCE Journal of Transportation Engineering以及IET Intelligent Transport Systems副主编，担任国际期刊Transportation Research Part E（SCI/SSCI）、Transportation Research Record（SCI）、Journal of Transport and Land Use（SSCI）编委。指导学生获得多项国内外大数据算法比赛奖项（皆为前三名），包括被誉为“大数据比赛世界杯”的KDD CUP冠军（2020年）、与第二名（2019）年，及其他同为人工智能三大国际顶级赛事的IJCAI（冠军，2019年）。此外还包括，2016年阿里巴巴天池大赛算法挑战赛冠军、2016年首届滴滴算法大赛-亚军、2017年美国TRB大会数据分析比赛优秀论文奖、2017年CCF大数据与计算智能大赛亚军、2017年Ucar Artificial Intelligence Cup冠军(IEEE computer society)、2018年阿里巴巴天池大赛冠军、2019年数字中国创新大赛大数据比赛一等奖等。
内容提要：
Traffic assignment is a fundamental tool to evaluate the flow distribution pattern in a transport network. As one of the most recognized theory for traffic assignment, user equilibrium is widely investigated and implemented. Most of the existing algorithms for the user equilibrium-based traffic assignment problem are developed and implemented sequentially. This study aims to study and investigate the parallel computing approach to utilize the widely available parallel computing resources. The Parallel Block-Coordinate Descent (PBCD) algorithm is developed based on the path-based algorithm, i.e, the improved path-based gradient projection algorithm (iGP). A parallel block-coordinate method is proposed to replace the widely used Gauss-Seidel method for the procedure of path flow adjustment. To further improve the robustness/performance of the algorithm, the iPBCD algorithm is developed based on the state-of-the-art PBCD algorithm. A different type of flow update policy is studied and investigated intensively. The block size is determined using a sensitive test, and five indices-grouping rules are compared. Besides, a greedy update order of block indexes is introduced to compare with the cyclic scheme. Moreover, a new algorithm is developed based on the alternating direction method of multipliers (ADMM). In order to take use of the ADMM, the network links should be grouped into several blocks, where the links in the same block are disconnected. This link grouping problem falls into the category of edge-coloring problem in graph theory, and it follows the Vizing theorem. Numerical examples show that the proposed algorithms perform well in convergence and efficiency and can significantly reduce the computing time.
交通分配是评估交通网络中流量分配模式的基本工具。用户均衡理论作为最公认的交通分配理论之一，已经得到了广泛的研究和应用。现有的大多数解决基于用户平衡的交通分配问题的算法都是采用串行计算的模式来开发和实现的。本研究旨在研究并行计算方法，以利用广泛可用的并行计算资源。并行分块坐标下降算法(PBCD)是基于路径算法发展起来的，比如改善的基于路径搜索的GP算法(iGP)。我们提出并行块坐标法来代替已经被广泛使用的高斯-塞德尔方法来进行路径流量调整。为了提高算法的鲁棒性和性能，基于最新的PBCD算法，进一步提出了iPBCD算法。我们针对不同类型的交通流更新策略进行了深入研究和调查。通过灵敏度测试来确定块的大小，并与五项指标分组规则进行了比较。此外，我们引入了基于贪心算法的块索引更新顺序并与循环方案进行比较，并基于交替方向乘子法(ADMM)开发了一种新算法。为了使用ADMM算法，应将网络分为几个块，其中同一块中的路径不相连。该路径分组问题属于图论中的边缘着色问题，它遵循Vizing定理。数值算例表明，所提出的算法在收敛性和效率上都表现良好，并且可以大大减少计算时间。
