Cyclic flows, Markov process and stochastic traffic assignment
DOI: 10.1016/0191-2615(96)00003-3
archive: archived pipeline: cataloged verified
Get this paper ↗ (DOI — opens at the source; we link to it, we don't host it)
Summary
This paper addresses a significant limitation in Dial’s (1971) stochastic traffic assignment algorithm, which restricts path selection to "efficient paths" that strictly increase distance from the origin. This restriction often yields unrealistic flow patterns by excluding paths that are frequently used in reality, particularly those involving cyclic flows or apparent loops. To resolve this, the author proposes a LOGIT-type stochastic assignment model that does not restrict the assignment path set, allowing for the inclusion of infinite cycles. This approach ensures computational feasibility for large-scale networks and avoids oscillatory behavior in iterative equilibrium assignments by maintaining a constant path set regardless of link cost changes. The study establishes the theoretical foundation for this unrestricted model by linking it to Sasaki’s assignment model through the theory of Absorbing Markov Processes (MPA). The author demonstrates that the proposed LOGIT model is equivalent to an MPA where transition probabilities between nodes are defined by link costs and dispersion parameters. This equivalence allows the model to be solved using matrix operations rather than explicit path enumeration. Specifically, the paper derives that the calculation of link flows can be achieved by evaluating the inverse of a matrix related to link costs, satisfying the Hawkins-Simon condition for convergence. Furthermore, the paper develops an efficient algorithm that avoids the heavy computational burden of full matrix inversions or path enumeration. By utilizing an entropy decomposition derived from the Markov property of the LOGIT model, the author constructs an equivalent mathematical program. This method requires only a single inverse matrix calculation for the traversal nodes, significantly reducing computational complexity compared to previous approaches. The analysis confirms that this algorithm correctly calculates link flows, including those on cyclic paths, by summing infinite path flows weighted by their LOGIT probabilities. The significance of this work lies in providing a robust, computationally efficient method for stochastic traffic assignment that overcomes the structural limitations of Dial’s algorithm. By validating the equivalence between the unrestricted LOGIT model and the Absorbing Markov Process, the paper offers a rigorous theoretical basis for handling cyclic flows. Additionally, the proposed algorithm’s efficiency makes it suitable for large-scale networks, and its stability facilitates extension to flow-dependent stochastic equilibrium assignments, thereby enhancing the practical applicability of stochastic assignment models in transportation planning.
Provenance
The full processing record for this entry. Every stage of this paper's journey through the pipeline is logged — what ran, with which tool and model, how many attempts it took, and when it last completed.
| Stage | Outcome | Tool | Model | Prompt | Attempts | Completed |
|---|---|---|---|---|---|---|
| discover | success | Crossref | — | — | 1 | 2026-06-19 |
| archive | success | semantic_scholar | — | — | 6 | 2026-06-26 |
| extract | success | pdftotext | — | — | 2 | 2026-06-26 |
| clean | success | clean | — | — | 1 | 2026-06-26 |
| chunk | success | chunk | — | — | 1 | 2026-06-26 |
| embed | success | embed | Qwen/Qwen3-Embedding-8B | — | 1 | 2026-06-26 |
| enrich | failed | — | — | — | 4 | 2026-06-26 |
| promote | success | — | — | — | 1 | 2026-06-19 |
| summarize | success | llm | qwen3.6-27b-prismaquant | summ-v5 | 1 | 2026-06-26 |
| tag | success | vector_similarity | — | — | 6 | 2026-06-26 |
| verify | success | — | — | — | 1 | 2026-06-26 |
Summary generated by qwen3.6-27b-prismaquant on 2026-06-26; verification: verified.
Topics
Ranked by relevance to this paper. Hover a topic for its definition.