Combinatorial Approach for Multiple-Destination User Optimal Dynamic Traffic Assignment
Abstract
An algorithm that can be used to solve the user optimal dynamic traffic assignment problem for multiple destinations is proposed. The algorithm uses the cell transmission model, which can account for traffic realities, such as dynamic queuing and spillover. The approach selects a destination for equilibration, fixes the paths of the vehicles assigned to the other destinations, and finds an optimal dynamic traffic assignment for the destination of interest via an extension to a previously introduced combinatorial algorithm. The spatial path set obtained for this destination is then fixed, and another destination is relaxed. The process is repeated iteratively among the destinations. The approach is guaranteed to find the user optimal solution for a single destination given any number of other fixed-path vehicles, but the approach is a heuristic for finding the multiple-destination user optimal path set. The algorithm is implemented and computationally tested for an example network, and solution properties are explored.
Get full access to this article
View all access and purchase options for this article.
References
1. Merchant D. K., and Nemhauser G. L. A Model and an Algorithm for the Dynamic Assignment Problem. Transportation Science, Vol. 12, 1978, pp. 183–199.
2. Carey M. Optimal Time-Varying Flows on Congested Networks. Operations Research, Vol. 35, 1987, pp. 58–69.
3. Carey M. Nonconvexity of the Dynamic Traffic Assignment Problem. Transportation Research, Part B, Vol. 26, 1992, pp. 127–133.
4. Friesz T. L., Luque F. J., Tobin R. L., and Wie B. W. Dynamic Network Traffic Assignment Considered as a Continuous Time Optimal Control Problem. Operations Research, Vol. 37, 1989, pp. 893–901.
5. Janson B. N. Dynamic Traffic Assignment for Urban Networks. Transportation Research, Part B, Vol. 25, 1992, pp. 143–161.
6. Friesz T. L., Bernstein D., Smith T. E., Tobin R. L., and Wie B. W. A Variational Inequality Formulation of the Dynamic Network User Equilibrium Problem. Operations Research, Vol. 41, 1993, pp. 179–191.
7. Smith M. J. A New Dynamic Traffic Model and the Existence and Calculation of Dynamic User Equilibria on Congested Capacity-Constrained Road Networks. Transportation Research, Part B, Vol. 27, 1993, pp. 49–63.
8. Wie B. W., Tobin R. L., Friesz T. L., and Bernstein D. Discrete Time, Nested Cost Operator Approach to the Dynamic Network User Equilibrium Problem. Transportation Science, Vol. 28, 1995, pp. 79–92.
9. Boyce D. E., Lee D. H., and Janson B. N. A Variational Inequality Model of an Ideal Dynamic User-Optimal Route Choice Problem. Presented at 4th Meeting of the EURO Working Group on Transportation, Newcastle, United Kingdom, 1996.
10. Mahmassani H. S., and Peeta S. Network Performance Under System Optimal and User Equilibrium Dynamic Assignments: Implications for Advanced Traveler Information System. In Transportation Research Record 1408, TRB, National Research Council, Washington, D.C., 1993, pp. 83–93.
11. Ghali M. O., and Smith M. J. A Dynamic Traffic Assignment Model. Presented at 71st Annual Meeting of the Transportation Research Board, Washington, D.C., 1992.
12. Ben-Akiva M., Bierlaire M., Koutsopoulos H. N., and Mishalani R. DynaMIT: A Simulation-Based System for Traffic Prediction and Guidance Generation. Proc., 3rd Triennial Symposium on Transportation Systems, San Juan, Puerto Rico, 1998.
13. Ziliaskopoulos A. K., and Waller S. T. An Internet-Based Geographic Information System that Integrates Data, Models, and Users for Transportation Applications. Transportation Research, Part C, Vol. 8, No. 1, 2000, pp. 427–444.
14. Waller S. T., and Ziliaskopoulos A. K. A Combinatorial Algorithm for the User Optimal Dynamic Traffic Assignment Problem. Proc., Tristan IV, São Miguel, Portugal, 2002.
15. Daganzo C. F. The Cell Transmission Model: A Simple Dynamic Representation of Highway Traffic Consistent with the Hydrodynamic Theory. Transportation Research, Part B, Vol. 28, No. 4, 1994, pp. 269–287.
16. Daganzo C. F. The Cell Transmission Model. Part II. Network Traffic. Transportation Research, Part B, Vol. 29, No. 2, 1995, pp. 79–93.
17. Golani H. A Combinatorial Approach for Multiple-Destination User Optimal Dynamic Traffic Assignment. M.S. thesis. Department of Civil Engineering, University of Illinois, Urbana-Champaign, 2003.
18. Sheffi Y. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Englewood Cliffs, N.J., 1985.
Cite article
Cite article
Cite article
OR
Download to reference manager
If you have citation software installed, you can download article citation data to the citation manager of your choice
Information, rights and permissions
Information
Published In
Article first published: January 2004
Issue published: January 2004
Authors
Metrics and citations
Metrics
Journals metrics
This article was published in Transportation Research Record: Journal of the Transportation Research Board.
VIEW ALL JOURNAL METRICSArticle usage*
Total views and downloads: 15
*Article usage tracking started in December 2016
Altmetric
See the impact this article is making through the number of times it’s been read, and the Altmetric Score.
Learn more about the Altmetric Scores
Articles citing this one
Receive email alerts when this article is cited
Web of Science: 0
Crossref: 8
- An Excess-Demand Dynamic Traffic Assignment Approach for Inferring Ori...
- An intersection-movement-based stochastic dynamic user optimal route c...
- A Dual Variable Approximation-Based Descent Method for a Bi-level Cont...
- A combinatorial algorithm and warm start method for dynamic traffic as...
- Stochastic and Dynamic Shipper Carrier Network Design Problem
- A Dantzig-Wolfe Decomposition-Based Heuristic for Off-line Capacity Ca...
- Linear Programming Models for the User and System Optimal Dynamic Netw...
- Improvement and Evaluation of Cell-Transmission Model for Operational ...
Figures and tables
Figures & Media
Tables
View Options
Get access
Access options
If you have access to journal content via a personal subscription, university, library, employer or society, select from the options below:
loading institutional access options
Alternatively, view purchase options below:
Purchase 24 hour online access to view and download content.
Access journal content via a DeepDyve subscription or find out more about this option.
