Path-based system optimal dynamic traffic assignment: A subgradient approach

The system-optimal dynamic traffic assignment (SO-DTA) problem aims at solving for the time-dependent link and path flow of a network that yields the minimal total system cost, provided with the Origin-Destination (O-D) demand. The key to solving the path-based formulation of SO-DTA is to efficiently compute the path marginal cost (PMC). Existing studies implicitly assume that the total system cost (TC) is always differentiable with respect to the path flow when computing PMC. We show that the TC could be non-differentiable with respect to the link/path flow in some cases, especially when the flow is close or under the SO conditions. Overlooking this fact can lead to convergence failure or incorrect solutions while numerically solving the SO-DTA problem. In this paper we demonstrate when the TC would be indifferentiable and how to compute the subgradients, namely the lower and upper limit of path marginal costs. We examine the relations between the discontinuity of PMC and the SO conditions, develop PMC-based necessary conditions for SO solutions, and finally design heuristic solution algorithms for solving SO in general networks with multi-origin-multi-destination OD demands. Those algorithms are tested and compared to existing algorithms in four numerical experiments, two toy networks where we compare analytical solutions with numerical solutions, one small network and one sizable real-world network. We show that the proposed heuristic algorithms outperform existing ones, in terms of both the total TC, convergence, and the resultant path/link flow.