IEEE Trans Cybern. 2018 Apr;48(4):1304-1315. doi: 10.1109/TCYB.2017.2691666. Epub 2017 Apr 14.
Finding an equilibrium state of the traffic assignment plays a significant role in the design of transportation networks. We adapt the path finding mathematical model of slime mold Physarum polycephalum to solve the traffic equilibrium assignment problem. We make three contributions in this paper. First, we propose a generalized Physarum model to solve the shortest path problem in directed and asymmetric graphs. Second, we extend it further to resolve the network design problem with multiple source nodes and sink nodes. At last, we demonstrate that the Physarum solver converges to the user-optimized (Wardrop) equilibrium by dynamically updating the costs of links in the network. In addition, convergence of the developed algorithm is proved. Numerical examples are used to demonstrate the efficiency of the proposed algorithm. The superiority of the proposed algorithm is demonstrated in comparison with several other algorithms, including the Frank-Wolfe algorithm, conjugate Frank-Wolfe algorithm, biconjugate Frank-Wolfe algorithm, and gradient projection algorithm.
交通分配的平衡状态在交通网络设计中起着重要作用。我们采用多头绒泡菌 Physarum polycephalum 的路径发现数学模型来解决交通均衡分配问题。本文主要有三个贡献。首先，我们提出了一种广义 Physarum 模型来解决有向非对称图中的最短路径问题。其次，我们进一步将其扩展到解决具有多个源节点和汇节点的网络设计问题。最后，我们证明 Physarum 求解器通过动态更新网络中链路的成本，收敛到用户优化的（Wardrop）均衡。此外，还证明了所开发算法的收敛性。通过数值示例验证了所提算法的有效性。与 Frank-Wolfe 算法、共轭 Frank-Wolfe 算法、双共轭 Frank-Wolfe 算法和梯度投影算法等其他几种算法相比，所提出算法的优越性得到了验证。
