Linear Programming Formulation for Strategic Dynamic Traffic Assignment
- Published: 18 May 2013
- Volume 13 , pages 427–443, ( 2013 )
Cite this article
- S. Travis Waller 1 , 2 ,
- David Fajardo 1 ,
- Melissa Duell 1 , 2 &
- Vinayak Dixit 1
930 Accesses
24 Citations
Explore all metrics
This work introduces a novel formulation of system optimal dynamic traffic assignment that captures strategic route choice in users under demand uncertainty. We define strategic route choice to be that users choose a path prior to knowing the true travel demand which will be experienced (therefore users consider the full set of possible demand scenarios). The problem is formulated based on previous work by Ziliaskopoulos (Transp Sci 34(1):37–49, 2000 ). The resulting novel formulation requires substantial enhancement to account for path-based flows and scenario-based stochastic demands. Further, a numerical demonstration is presented on a network with different demand loading profiles. Finally, model complexity, implications on scalability and future research directions are discussed.
This is a preview of subscription content, log in via an institution to check access.
Access this article
Price includes VAT (Russian Federation)
Instant access to the full article PDF.
Rent this article via DeepDyve
Institutional subscriptions
Andreatta G, Romeo L (1988) Stochastic shortest paths with recourse. Networks 18:193–204
Article Google Scholar
Asakura Y, Kashiwadani M (1991) Road network reliability caused by daily fluctuation of traffic flow. In: Proceedings of the 19th PTRC Summer Annual Meeting, Brighton, Seminar G, pp 73–84
Boyles S, Waller ST (2007) A stochastic delay prediction model for real-time incident management. ITE Journal 77:18–24
Google Scholar
Cantarella GE, Cascetta E (1995) Dynamic process and equilibrium in transportation networks: toward a unifying theory. Transp Sci 29:305–329
Carey M, Subrahmanian E (2000) An approach to modeling time-varying flows on congested networks. Transp Res 34B(3):157–183
Chriqui C, Robillard P (1975) Common bus line. Transp Sci 9:115–121
Clark SD, Watling DP (2005) Modelling network travel time reliability under stochastic demand. Transp Res B Methodol 39(2):119–140
Daganzo CF (1994) The cell transmission model: a simple dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res 28B(4):269–287
Daganzo CF (1995) The cell transmission model, part II: network traffic. Transp Res 29B(2):79–93
Daganzo CF, Sheffi Y (1977) On stochastic models of traffic assignment. Transp Sci 11(3):253–273
Fan Y, Nie Y (2006) Optimal routing for maximizing the travel time reliability. Netw Spat Econ 6(3–4):333–344
Gao S, Chabini I (2006) Optimal routing policy problems in stochastic time dependent networks. Transp Res B Methodol 40(2):93–122
Hamdouch Y, Marcotte P, Nguyen S (2004) A strategic model for dynamic traffic assignment. Netw Spat Econ 4(3):291–315
Horowitz JL (1984) The stability of stochastic equilibrium in a two-link transportation network. Transp Res B 18(1):13–28
Li Y, Ziliakopoulos AK, Waller ST (1999) Linear programming formulations for system optimum dynamic traffic assignment with arrival time based and departure time based demands. Transp Res Rec 1667:52–59
Li Y, Waller ST, Ziliaskopoulos AK (2003) A decomposition scheme for system optimal dynamic traffic assignment models. Netw Spat Econ 3:441–455
Maher MJ, Hughes PC (1997) A probit-based stochastic user equilibrium assignment model. Transp Res B 31(4)
Marcotte P, Nguyen S (1998) Hyperpath formulations of traffic assignment problems. In: Marcotte P, Nguyen S (eds) Equilibrium and advanced transportation modelling. Kluwer Academic Publishers, pp 175–199
Marcotte P, Nguyen S, Schoeb A (2004) A strategic flow model of traffic assignment in static networks. Oper Res 52(2):191–212
Merchant DK, Nemhauser GI (1978a) A model and an algorithm for dynamic traffic assignment problems. Transp Sci 12(3):183–199
Merchant DK, Nemhauser GI (1978b) Optimality conditions for a dynamic traffic assignment model. Transp Sci 12(3):200–207
Miller-Hooks E, Mahmassani HS (2000) Least expected time paths in stochastic, time-varying transportation networks. Transp Sci 34:198–215
Peeta S, Ziliaskopoulos AK (2001) Foundations of dynamic traffic assignment: the past, the present and the future. Netw Spat Econ 1(3–4):233–265
Polychronopoulos GH, Tsitsiklis JN (1996) Stochastic shortest path problems with recourse. Networks 27:133–143
Psaraftis HN, Tsitsiklis JN (1993) Dynamic shortest paths in acyclic networks with Markovian arc costs. Oper Res 41(1):91–101
Sheffi Y, Powell WB (1982) An algorithm for the equilibrium assignment problem with random link times. Networks 12(2):191–207
Unnikrishnan A, Waller ST (2009) User equilibrium with recourse. Netw Spat Econ 9(4):575–593
Waller ST, Ziliaskopoulos AK (2002) On the online shortest path problem with limited arc cost dependencies. Networks 40:216–227
Waller ST, Ziliaskopoulos AK (2006) A chance-constrained based stochastic dynamic traffic assignment model: analysis, formulation and solution algorithms. Transp Res C Emerg Technol 14(6):418–427
Watling DP (1999) Stability of the stochastic assignment problem: a dynamical systems approach. Transp Res B 33:281–312
Watling D, Hazelton ML (2003) The dynamics and equilibria of day-to-day assignment models. Netw Spat Econ 3:349–370
Ziliaskopoulos AK (2000) A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transp Sci 34(1):37–49
Download references
Acknowledgments
This research has been made possible by support from the National Science Foundation under CMMI grant #0927315, the 2012 UNSW Gold Star grant, and NICTA. NICTA is funded by the Australian Government as represented by the Department of Broadband, Communications and the Digital Economy and the Australian Research Council through the ICT Centre of Excellence program.
Author information
Authors and affiliations.
School of Civil and Environmental Engineering, The University of New South Wales, Sydney, Australia
S. Travis Waller, David Fajardo, Melissa Duell & Vinayak Dixit
NICTA: National ICT Australia, Sydney, NSW, Australia
S. Travis Waller & Melissa Duell
You can also search for this author in PubMed Google Scholar
Corresponding author
Correspondence to S. Travis Waller .
Rights and permissions
Reprints and permissions
About this article
Waller, S.T., Fajardo, D., Duell, M. et al. Linear Programming Formulation for Strategic Dynamic Traffic Assignment. Netw Spat Econ 13 , 427–443 (2013). https://doi.org/10.1007/s11067-013-9187-5
Download citation
Published : 18 May 2013
Issue Date : December 2013
DOI : https://doi.org/10.1007/s11067-013-9187-5
Share this article
Anyone you share the following link with will be able to read this content:
Sorry, a shareable link is not currently available for this article.
Provided by the Springer Nature SharedIt content-sharing initiative
- Dynamic traffic assignment
- Demand uncertainty
- Linear programming
- Find a journal
- Publish with us
- Track your research
- View Record
TRID the TRIS and ITRD database
FASTER PATH-BASED ALGORITHM FOR TRAFFIC ASSIGNMENT
A fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem is taken, and the results of a gradient projection method are provided. The motivation behind the research is the orders of magnitude improvement in the availability of computer storage over the last decade. Faster assignment algorithms are necessary for real-time traffic assignment under several of the proposed advanced traffic management system strategies, and path-based solutions are preferred. The results show that gradient projection converges in one-tenth of the iterations of the conventional Frank-Wolfe algorithm. The computation time improvement is of the same order for small networks but is reduced as the network size increases. The computer implementation issues are discussed carefully, and schemes to achieve a 10-fold speedup for larger networks are also provided. The algorithm was used for networks of up to 2,000 nodes on a typical computer workstation, and certain data structures that save storage and solve the assignment problem for even a 5,000-node network are discussed.
- Record URL: http://onlinepubs.trb.org/Onlinepubs/trr/1994/1443/1443-009.pdf
- Record URL: https://scholar.google.com/scholar_lookup?title=FASTER+PATH-BASED+ALGORITHM+FOR+TRAFFIC+ASSIGNMENT&author=R.+Jayakrishnan&author=W.+Tsai&author=J.+Prashker&author=S.+Rajadyaksha&publication_year=1994
- Find a library where document is available. Order URL: http://worldcat.org/isbn/0309055245
- This paper appears in Transportation Research Record No. 1443, Travel Demand Modeling and Network Assignment Models. Distribution, posting, or copying of this PDF is strictly prohibited without written permission of the Transportation Research Board of the National Academy of Sciences. Unless otherwise indicated, all materials in this PDF are copyrighted by the National Academy of Sciences. Copyright © National Academy of Sciences. All rights reserved
- Jayakrishnan, R
- Tsai, Wei K
- Prashker, Joseph N
- Rajadyaksha, Subodh
- Publication Date: 1994
- Features: Figures; References; Tables;
- Pagination: p. 75-83
- Monograph Title: Travel demand modeling and network assignment models
- Transportation Research Record
- Issue Number: 1443
- Publisher: Transportation Research Board
- ISSN: 0361-1981
Subject/Index Terms
- TRT Terms: Algorithms ; Highway traffic control ; Real time control ; Real time data processing ; Traffic assignment
- Subject Areas: Highways; Operations and Traffic Management; Planning and Forecasting; I72: Traffic and Transport Planning;
Filing Info
- Accession Number: 00670486
- Record Type: Publication
- ISBN: 0309055245
- Files: TRIS, TRB
- Created Date: Dec 23 1994 12:00AM
University of California Transportation Center
A Faster Path-Based Algorithm for Traffic Assignment
- Jayakrishnan, R. ;
- Tsai, Wei T. ;
- Prashker, Joseph N. ;
- Rajadhyaksha, Subodh
This paper takes a fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem and provides the results of a gradient projection method. The motivation behind the research is the orders of magnitude improvement in the availability of computer storage over the last decade. Faster assignment algorithms are necessary for real-time traffic assignment under several of the proposed Advanced Traffic Management System (ATMS) strategies, and path-based solutions are preferred. Our results show that gradient projection converges in 1/10 iterations than the conventional Frank-Wolfe algorithm. The computation time improvement is of the same order for small networks, but reduces as the network size increases. We discuss the computer implementation issues carefully, and provide schemes to achieve a 10-fold speed-up for larger networks also. We have used the algorithm for networks of up to 2000 nodes on a typical computer work station, and we discuss certain data structures to save storage and solve the assignment problem for even a 5000 node network.
Enter the password to open this PDF file:
IMAGES
VIDEO
COMMENTS
Abstract This paper studied the range-constrained traffic assignment problem (RTAP), where heterogeneous range anxiety is considered among the driving population by electric vehicles (EVs). In order not to get stranded en-route, each EV driver is assumed to have his/her own driving range limit for being able to complete the trip.
A path-based flow formulation for the traffic assignment problem Caixia Li , Sreenatha Gopalarao & Tapabrata Ray Pages 597-611 | Received 10 Apr 2015, Accepted 16 Mar 2016, Published online: 31 May 2016 Cite this article https://doi.org/10.1080/03081060.2016.1187810 Full Article Figures & data References Citations Metrics Reprints & Permissions
Traffic assignment is a fundamental tool to evaluate the flow distribution pattern in a transport network. As one of the most recognized theories for traffic assignment, user equilibrium (UE) is widely investigated and implemented.
The system-optimal dynamic traffic assignment (SO-DTA) problem aims at solving the time-dependent traffic flows of a network that yield minimal total system cost provided with the Origin-Destination (O-D) demand.
There are three important stages of path-based algorithms (PBAs) for solving the static user equilibrium traffic assignment problem (STA): finding shortest paths between various origins and destinati...
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.
This paper presents a mathematical programming model and solution method for the path-constrained traffic assignment problem, ... but the resulting model and solution method can be applied to various conditions with similar path-based constraints. The equilibrium conditions of the problem reveal that any path cost in the network is the sum of ...
The standard traffic assignment problem (TAP) is often augmented with additional constraints to address non-standard applications. These models are called TAP with side constraints (TAPSC). ... A Path-Based User-eq46 Traffic Assignment Algorithm that Obviates Path Storage and Enumeration. Transportation Research Part B: ...
{7} T. Larsson, M. Patriksson, Simplicial decomposition with disaggregated representation for the traffic assignment problem, Transport. Sci. 26 (1992) 4-17. Google Scholar Digital Library {8} C. Sun, R. Jayakrishnan, W.K. Tsai, Computational study of a path-based algorithm and its variants for static traffic assignment, Transport. Res.
In this paper, a path based traffic assignment model combining the generalized expansion method in M/G/c/c model with the point queue model is proposed to extend the link traversal cost to the travel cost along the path.
A fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem is taken, and the results of a gradient projection method are provided. The motivation...
In this paper, Stackelberg game theory is introduced to the traffic assignment problem, which can achieve the trade-off process between traffic management and travelers. Since traditional traffic ...
The path-formulated traffic assignment problem Consider an urban traffic network represented as a graph G = ( N, A ), where N and A are the sets of nodes and links, respectively. Let R and S be subsets of N and qrs be the steady-state demand generated from origin r ∈ R to destination s ∈ S.
The traditional transportation planning process [1, 2] has the following four stages, having traffic assignment as one of the four stages:1. Trip Generation: Trip generation involves estimating the number of trips generated at each origin node and/or the number of trips attracted to each destination node.This estimation is performed based on surveys conducted and generally uses a model that ...
Three major reasons: FW adjusts all OD pairs by the same amount , even if some are closer to equilibrium than others. Geometrically, the FW target is always a corner of the feasible region. It is unable to erase cyclic ows. Uniform treatment of OD pairs
A fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem and the results of a gradient projection method are provided, showing that gradient projection converges in 1/10 iterations than the conventional Frank-Wolfe algorithm. Expand cloudfront.escholarship.org Save to Library Create Alert Cite Topics
A new path-based algorithm for the static user equilibrium traffic assignment problem that adopts a greedy method to solve the restricted subproblem defined on each origin-destination (O-D) pair and introduces an intelligent scheme to determine which O-D pairs need more or less work. This paper presents a new path-based algorithm for the static user equilibrium traffic assignment problem.
A Greedy Path-Based Algorithm for Traffic Assignment Jun Xie1, Yu (Marco) Nie2, and Xiaobo Liu1 Abstract This paper presents a new path-based algorithm for the static user equilibrium traffic assignment problem. Path-based algo-rithms are generally considered less efficient than bush-based counterparts, such as Algorithm B, traffic assignment by
Faster Path-Based Algorithm for Traffic Assignment R. ]AYAKRISHNAN, WEIK. TSAI, JOSEPH N. PRASHKER, AND SUBODH RAJADHYAKSHA A fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem is taken, and the results of a gradient projection method are provided.
This work introduces a novel formulation of system optimal dynamic traffic assignment that captures strategic route choice in users under demand uncertainty. We define strategic route choice to be that users choose a path prior to knowing the true travel demand which will be experienced (therefore users consider the full set of possible demand scenarios). The problem is formulated based on ...
This paper presents a path-based traffic assignment formulation and its solution algorithm for solving an asymmetric traffic assignment problem based on the TRANSYT traffic model, a well-known procedure to determine the queues and delays in a signal-controlled network with explicit considerations of the signal co-ordination effects and platoon d...
FASTER PATH-BASED ALGORITHM FOR TRAFFIC ASSIGNMENT. A fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem is taken, and the results of a gradient projection method are provided. The motivation behind the research is the orders of magnitude improvement in the availability of computer storage over ...
A Faster Path-Based Algorithm for Traffic Assignment. This paper takes a fresh look at the arguments against path-enumeration algorithms for the traffic assignment problem and provides the results of a gradient projection method. The motivation behind the research is the orders of magnitude improvement in the availability of computer storage ...