1 July 2016 in Transportation Research Part C: Emerging Technologies
24 May 2018 in Transportation Research Record: Journal of the Transportation Research Board
This paper presents a new path-based algorithm for the static user equilibrium traffic assignment problem. Path-based algorithms are generally considered less efficient than bush-based counterparts, such as Algorithm B, traffic assignment by paired alternative segments (TAPAS), and iTAPAS, an improved version of TAPAS, because explicitly storing and manipulating paths appears wasteful. However, our numerical experiments indicate that the proposed path-based algorithm can outperform TAPAS or iTAPAS by a wide margin. The proposed algorithm, sharing the same Gauss-Seidel decomposition scheme with existing path-based algorithms, delivered a surprising performance, most likely due to its two main features. First, it adopts a greedy method to solve the restricted subproblem defined on each origin–destination (O-D) pair. Second, instead of sequentially visiting every O-D pair in each iteration, it introduces an intelligent scheme to determine which O-D pairs need more or less work. The proposed algorithm is also more straightforward to implement than bush-based algorithms.
1 March 2019 in Transportation Science
This paper proposes a novel algorithm to determine the path flow solution that satisfies the proportionality condition from a given origin-based user equilibrium (UE) link flow solution. The algorithm iteratively refines the origin-based bush representation of the UE solution through constructing a list of “node-based arrival bushes” and solving the entropy maximization subproblems defined on them. Thanks to the special structure of bushes, these subproblems can be solved efficiently. The proposed algorithm thus obviates the known hurdles to efficient implementation, such as enumerating all UE paths or collecting a set of paired alternative segments to cover them. We prove that the algorithm ensures convergence to a solution that perfectly satisfies the proportionality condition in general networks. Numerical experiments indicate that the proposed algorithm converges much faster than the known alternative, with a three- to eightfold speed-up on large networks. The online appendices are available at https://doi.org/10.1287/trsc.2018.0845 .
1 September 2020 in Transportation Research Part C: Emerging Technologies
1 July 2022 in Transportation Science
Strategy-based equilibrium traffic assignment (SETA) problems define travel choice broadly as a strategy rather than a simple path. Travelers navigating through a network based on a strategy end up following a hyperpath. SETA is well suited to represent a rich set of travel choices that take place en route at nodes, such as transit passengers’ transfer decisions, truckers’ bidding decisions, and taxi drivers’ reposition decisions. This paper recognizes and highlights the commonalities among classical and emerging SETA problems and proposes to unify them within the same modeling framework, built on the concept of a hypergraph. A generic hyperbush algorithm (HBA) is developed by decomposing a hypergraph into destination-based hyperbushes. By constructing hyperbushes and limiting traffic assignments to them, HBA promises to obtain more precise solutions to larger instances of SETA problems at a lower computational cost, both in terms of CPU time and memory consumption. To demonstrate its generality and efficiency, we tailor HBA to solve two SETA problems. The results confirm that HBA consistently outperforms the benchmark algorithms in the literature, including two state-of-the-art hyperpath-based algorithms. To obtain high-quality equilibrium solutions for SETA instances of practical size, HBA runs up to five times faster than the best competitor with a fraction of its memory consumption.
1 January 2015 in Transportation Research Record: Journal of the Transportation Research Board
This paper presents an extensive analytical and numerical investigation of a class of origin-based algorithms for the user equilibrium–based traffic assignment problem. Nine known algorithms in this class are first clustered into four algorithmic structures on the basis of their structural differences and similarities in algorithm design. A complexity analysis of these algorithmic structures is conducted by calculating the frequency of executing node and link operations; this approach provides a simple analytical way to estimate their per iteration computation costs. To deliver a comprehensive and fair comparison of their convergence performance, all nine algorithms are implemented on the same programming platform and run to solve a few representative large-scale traffic networks by sizes and congestion levels. A close look at the convergence performance statistics further justifies the consistency of the complexity analysis and numerical evaluation results of the computational efficiency of these algorithms. Discussions on the degeneration of algorithm convergence efficiency with respect to network size and congestion level provide useful insights for the potential improvement of current origin-based algorithms or the proposition of new algorithms.