基于深度学习算法的城市路网交通分配算法设计文献综述

 2022-10-22 04:10
{title}{title}

文献综述（或调研报告）：

自1962年四阶段模型被提出以来，交通分配作为其最后一步成为交通领域研究的热点题目[1]。虽然传统的、基于数学的交通分配算法已经各成体系、发展成熟，但是由于其固有的缺陷而不能适应新时代智能交通系统的预测需要。因此，数据驱动的交通分配算法成为了相关研究的新热门；机器学习，尤其是深度学习模型，以其处理大数据的优异性能被融合入传统的算法之中。

  1. 传统的交通分配算法

自上世纪以来，交通分配作为交通网络流研究中的重要问题，已提出大量基于数学的传统算法，其中本研究基于的Frank-Wolfe算法[2]是第一个被广泛采用的可收敛的算法。作为一个基于路段（link-based）的方法，该方法在每次迭代中进行一维线性搜索和最短路搜索，并适应当时节省计算机内存的需要。但该方法迭代次数多、效率低，不适用于实际的大规模城市网络，因此涌现了诸多改进手段，例如Conjugate direction Frank-Wolfe (CFW)算法, Bi-conjugate Frank-Wolfe (BFW)算法, Parallel Tangent (PARTAN)算法[3, 4]等；其中，后续研究表明，CFW和BFW算法优于原始的Frank-Wolfe及PARTAN算法[5]，而基于PARTAN算法也有可加快收敛速度的启发式算法[6]。

除Frank-Wolfe算法外，Bar-Gera[7]于2002年提出的基于起点（Origin-based）的算法也是广泛应用的著名交通分配算法之一。尽管其收敛速率相比之前算法得到显著提升，但该算法仍需要穷举其中限制性子网络的所有路径。另一大类交通分配算法即为基于路径（path-based）的算法，该算法通过分开研究子网络，简化交通分配问题，但仍需要穷举网络中的大部分甚至全部路径[8]；主要包括Defermos-Sparrow算法[9]，聚集单纯形分解法（DSD）及梯度投影法（GP）[10]等。Defermos-Sparrow算法在部分研究中被证明优于Frank-Wolfe算法[11]。

  1. 深度学习及其交通分配算法

深度学习是一种新兴的、含多隐层的机器学习方法，源于人工神经网络的研究，并已被应用于图像分类、自然语言处理、目标探测等多个领域。在城市道路网流量估计问题研究中，深度学习已涌现大量研究成果，而基于机器学习的相关研究更是层出不穷。

仅严格就交通分配这一问题而言，目前已有的研究主要基于其他机器学习和强化学习方法，尚无深度学习有关研究。例如，Grunitzki等[12]于2018年对比了基于路段和基于路径的两种多代理强化学习算法Q-learning，以解决基于系统最优（System Optimization，SO）原则下的静态交通分配问题；Ding[13]与2007年提出了基于人工神经网络（Artificial Neural Network，ANN）的整体交通分配算法，但神经网络模型用于求解交叉口的延误，而不是用于流量分配本身。

因此，总体而言，基于机器学习的交通分配算法较少；相关的路段流量估计方法更为多样（这一问题与交通分配问题有着相同的求解目标）。尽管神经网络模型在交通研究中常常被当作“黑箱”使用，但随着近年来对算法精度和速度要求的提升，精心设计的深度学习模型或混合模型[14]才有可能满足城市大路网的使用需要。相关研究如Lv等[15]于2015年提出基于非监督自编码器、贪婪逐层训练的神经网络模型，并由Yang等[16]于2017年以英国真实高速公路数据进行实验；Polson和Sokolov[17]于2017年提出的深度神经网络则着眼于分析交通流的时间-空间关系，有效预测特殊事件或意外发生时的交通流量状况；Huang等[18]于2014年提出基于无监督Deep Belief Network（DBN）的多任务学习算法，以有效提取交通流量特征进行预测；另外，Chen等[19]于2017年提出基于时间序列分析的深度学习模型，以有效跟踪路段流量变化。值得一提的是，尽管解决交通分配或流量估计问题的方法各不相同，但基于深度学习（或机器学习）的算法多着眼于实现路段流量的实时、精确预测，以弥补传统算法中普遍存在的效率低下缺陷。

  1. 传统的最短路算法

最短路问题不仅是交通分配的重要子问题，在无线通信[20]、图像识别[21]等领域也有重要应用。最短路问题的模型首先由Bellman建立，亦称为动态规划的基本方程；对应的传统最短路算法自上世纪中叶以来发展迅速，主要包括标号设定（label-setting）与标号修正（label-correcting）算法两类。

最早的最短路算法为Bellman-Ford算法，由Shimbel[22]，Ford[23]，Moore[24]及Bellman[25]分别提出。该算法为标号修正法的特殊形式，相较于标号设定法能够应用于更多场景（如存在负权重的图），但计算效率较低，计算复杂度为O(MN)，其中M和N分别为边数和节点数；其他标号修正算法包括Floyd-Warshall[26][27]算法、Drsquo;Esopo-Pape算法[28]等，以实现不同程度的计算效率改进或使用范围扩展。而标号设定法中，最为著名的即为Dijkstra算法[29]，对应时间复杂度O(N2)，但无法处理带有负权或环的图；其他基于Dijkstra算法的方法包括Johnson算法[30]、A*算法[31]等，其中A*算法进一步结合了启发式算法的理念和广度优先搜索（Broad First Search，BFS）的优势，以大幅提升计算效率。

值得一提的是，标号设定法与标号修正法的最大区别在于，前者采用了贪婪算法的理念，每次迭代生成的标号在后续计算中固定；而后者在算法迭代结束后才停止所有标号的更新。因此，标号设定法也可视为标号修正法的一种特殊形式。

  1. 总结

传统的交通分配算法虽然在过去的六十多年中作用巨大，但均具有收敛速度慢、效率低的问题，不能适用于城市现状的大规模路网，也不能满足智能交通系统下的实时路段流量预测需求；因此，寻找新的方法迫在眉睫。今年来，虽然有大量数据驱动、基于机器学习（或深度学习）的路段流量预测算法的提出，但据本人的了解，尚无基于深度学习框架的交通分配算法研究。为了填补这一空缺，本课题拟提出一崭新的算法，直接进行交通分配计算。

另外，虽然最短路算法已有丰硕的研究成果，基于神经网络（尤其是深度学习）的最短路算法仍然缺少有效性和实用性，具有广阔的研究空间和一定的研究需要。因此，本研究具有一定的理论和实验支撑，能够较好地填补前人研究的空缺，开展有价值的探索工作。

四、方案（设计方案、或研究方案、研制方案）论证：

研究方案：

本研究拟设计下述两种算法，致力于实现基于城市道路网络的高效交通分配计算。其中，算法1基于整体的交通分配算法进行设计，算法2则着眼于交通分配的重要子问题——最短路问题；通过对两种方法的讨论，本研究希望能够对新兴的、数据驱动的网络流估计算法和四阶段需求预测有较为深入的理解和学习。

设计算法1:

  1. 基于Frank-Wolfe的交通分配算法设计
    对于设计算法1，本研究拟基于对传统UE模型及Frank-Wolfe求解算法的理解，重新设计基于深度学习模型的交通分配算法，以达到替代传统算法、显著提升计算效率的目标。同时，该算法应考虑路网变化的情况，具有一定的工程实用性。
  2. 训练及测试数据生成
    由于深度学习模型需要大量的数据用于训练，且训练数据的优劣一定程度上决定了模型的使用效果，因此数据的生成尤为重要。考虑到现实数据难以获取，在算法1中随机生成OD需求和路段参数，基于传统的Frank-Wolfe算法生成达到UE的路段流量数据，以满足模型训练的要求。

设计算法2:

  1. 基于全连接神经网络的最短路算法设计
    算法2中，采用全连接的基础神经网络（naiuml;ve neural network）进行最短路预测；通过巧妙选取其输入（input）与输出（output），提升算法预测精度，并在不同大小的方格网上实验验证。
  2. 数据生成与算法评估
    与算法1类似的是，算法2同样采用传统的Dijkstra算法生成符合神经网络输入、输出格式的随机数据，用于网络训练和预测。同时，结合交通网络本身的特性，提出基于路径总长预测精确度的算法评估方法，面向工程实用性进行算法有效性分析。

五、进度安排：

3.1-3.10 初步阅读文献，明确工作任务，完成开题报告

3.11-3.20 设计基于深度学习的城市路网交通分配算法

3.21-4.1设计基于神经网络的最短路算法，同时生成交通分配算法训练数据

4.2-4.22 同时生成两种算法的数据，并根据其效果进行代码调整

4.23-5.5 两种算法的检验和实例分析

5.6-5.15 撰写报告

参考文献

  1. Patriksson, M. The traffic assignment problems: models and methods [M]. VSP, Utrecht, the Netherlands, 1994.
  2. Frank, M., and P. Wolfe. An algorithm for quadratic programming [J]. Naval Research Logistics Quarterly, 1956, 3: 95.
  3. Leblanc, L. J., R. V. Helgason, and D. E. Boyce. Improved efficiency of the frank-wolfe algorithm for convex network programs [J]. Transportation Science, 1985, 19(4): 445-462.
  4. Arezki, Y., and D. V Vliet. A full analytical implementation of the partan/frank--wolfe algorithm for equilibrium assignment [J]. Transportation Science, 1990, 24(1): 58-62.
  5. Mitradjieva, M., and P. O. Lindberg. The stiff is moving--conjugate direction frank-wolfe methods with applications to traffic assignment [J]. Transportation Science, 2016, 47(2): 280-293.
  6. Florian, M., J. Guálat, and H. Spiess. An efficient implementation of the “partan” variant of the linear approximation method for the network equilibrium problem [J]. Networks, 2010, 17(3): 319-339.
  7. Bar-Gera, H. Origin-based algorithm for the traffic assignment problem [J]. Transportation Science, 2002, 36(4): 398-417.
  8. 李峰, 王书宁. 基于终点的路径交通量求解方法[J]. 清华大学学报(自然科学版), 2006, 46(1):149-152.
  9. Dafermos, S. C., and F. T. Sparrow. The traffic assignment problem for a general network [J]. National Bureau of Standards, 1969, 73(2): 91-118.
  10. Chen, A., D. H. Lee, and R. Jayakrishnan. Computational study of state-of-the-art path- based traffic assignment algorithms [J]. Mathematics amp; Computers in Simulation, 2002, 59(6): 509-518.
  11. Nagurney, A. B. Comparative tests of multimodal traffic equilibrium methods [J]. Transportation Research Part B, 1984, 18(6): 469-485.
  12. Grunitzki, R. and Bazzan, A. L. C.. Comparing Two Multiagent Reinforcement Learning Approaches for the Traffic Assignment Problem [J]. Paper presented at the Intelligent Systems, 2018.
  13. Ding Z . A Static Traffic Assignment Model Combined with an Artificial Neural Network Delay Model[J]. Dissertations amp; Theses - Gradworks, 2007.
  14. Wu Y., H. Tan, L. Qin, B. Ran, and Z. Jiang. A hybrid deep learning based traffic flow prediction method and its understanding [J]. Transportation Research Part C: Emerging Technologies, 2018, 90: 166-180.
  15. Lv, Y., Duan, Y., Kang, W., Li, Z., and Wang. Traffic Flow Prediction With Big Data: A Deep Learning Approach [J]. IEEE Transactions on Intelligent Transportation Systems, 2015, 16(2): 1-9.
  16. Yang, H. F., Dillon, T. S., and Chen, Y. P. Optimized Structure of the Traffic Flow Forecasting Model With a Deep Learning Approach [J]. IEEE Transactions on Neural Networks Learning Systems, 2016, 28(10): 2371-2381.
  17. Polson, N. G., and Sokolov, V. O. Deep learning for short-term traffic flow prediction [J]. Transportation Research Part C Emerging Technologies, 2017, 79: 1-17.
  18. Huang, W., Song, G., Hong, H., and Xie, K. Deep Architecture for Traffic Flow Prediction: Deep Belief Networks With Multitask Learning [J]. IEEE Transactions on Intelligent Transportation Systems, 2014, 15(5), 2191-2201.
  19. Chen Y , L. Shu, and L. Wang. Poster abstract: Traffic flow prediction with big data: A deep learning based time series model[C]. IEEE Conference on Computer Communications Workshops (INFOCOM WKSHPS). IEEE, 2017.
  20. Kato, N., Fadlullah, Z. M., Mao, B., Tang, F., Akashi, O., Inoue, T., amp; Mizutani, K. The deep learning vision for heterogeneous network traffic control: Proposal, challenges, and future perspective [J]. IEEE wireless communications, 2017, 24(3), 146-153.
  21. Hermansson, L., Johansson, F. D., amp; Watanabe, O. Generalized Shortest Path Kernel on Graphs [C]. Paper presented at the International Conference on Discovery Science, 2015.
  22. Shimbel, A. Structure in communication nets. Proceedings of the Symposium on Information Networks [J]. New York, NY: Polytechnic Press of the Polytechnic Institute of Brooklyn, 1955, 199–203.
  23. Ford Jr, L. R. Network flow theory [J]. 1956.
  24. Moore, E. F. The shortest path through a maze [J]. Proceedings of an International Symposium on the Theory of Switching (Cambridge, Massachusetts, 2–5 April 1957). Cambridge: Harvard University Press, 1959, 285–292.
  25. Bellman, B. R. On a routing problem. Quarterly of Applied Mathematics [J]. 1958, 16(1), 87-90.
  26. Floyd, R. W. Algorithm 97: Shortest path. Commun. ACM [J]. 1962, 5(6), 345. doi:10.1145/367766.368168
  27. Warshall, S. A Theorem on Boolean Matrices. J. ACM [J]. 1962, 9(1), 11-12. doi:10.1145/321105.321107
  28. Pape, U. Implementation and Efficiency of Moore-Algorithms for the Shortest Route Problem [J]. Mathematical Programming, 1974, 7, 212-222.
  29. Dijkstra, E. W. A note on two problems in connexion with graphs [J]. Numerische mathematic, 1959, 1(1), 269-271.
  30. Johnson, D. B. Efficient algorithms for shortest paths in sparse networks [J]. ACM, 1977.
  31. Hart, P. E., Nilsson, N. J., amp; Raphael, B. A formal basis for the heuristic determination of minimum cost paths [J]. IEEE Transactions on Systems Science amp; Cybernetics, 1968, 4(2), 100-107.

以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章