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

https://nap.nationalacademies.org/catalog/27432/critical-issues-in-transportation-for-2024-and-beyond

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

ORCID

  • 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

Earlier Faculty Research banner

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

  1. Traffic Assignment Problem

    path based traffic assignment problem

  2. Mod 6, Part 2: Traffic Assignment (Path Finding)

    path based traffic assignment problem

  3. The dynamic traffic assignment problem can be solved using iterations

    path based traffic assignment problem

  4. The Traffic Assignment Problem: Models and Methods

    path based traffic assignment problem

  5. Solved Question 2 (40 points): Solve the traffic assignment

    path based traffic assignment problem

  6. (PDF) Path-Constrained Traffic Assignment: Model and Algorithm

    path based traffic assignment problem

VIDEO

  1. “AI Based Traffic Management” Project by Atishay, Raghav, Uday ; MRIS14

  2. Density Based Traffic Control System

  3. NPTEL Problem Solving Through Programming In C || Week 3 || Assignment 3 Solution || Swayam || JAN24

  4. TRAFFIC PROBLEM 1

  5. Segment Routing Traffic Engineering

  6. Traffic Assignment 1

COMMENTS

  1. Range-constrained traffic assignment for electric vehicles under heterogeneous range anxiety

    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.

  2. A path-based flow formulation for the traffic assignment problem

    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

  3. A parallel computing approach to solve traffic assignment using path

    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.

  4. Path-based system optimal dynamic traffic assignment: A subgradient

    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.

  5. Strategies to Enhance the Performance of Path‐Based Static Traffic

    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...

  6. A Greedy Path-Based Algorithm for Traffic Assignment

    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.

  7. Path-Constrained Traffic Assignment: Model and Algorithm

    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 ...

  8. Efficient Algorithm for the Traffic Assignment Problem with Side

    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: ...

  9. Computational study of state-of-the-art path-based traffic assignment

    {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.

  10. A Path-Based Solution Algorithm for Dynamic Traffic Assignment

    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.

  11. A 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...

  12. A path-based flow formulation for the traffic assignment problem

    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 ...

  13. Computational study of state-of-the-art path-based traffic assignment

    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.

  14. Traffic Assignment: A Survey of Mathematical Models and Techniques

    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 ...

  15. PDF Path-based algorithms for solving traffic assignment

    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

  16. A Faster Path-based Algorithm for Traffic Assignment

    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

  17. A Greedy Path-Based Algorithm for Traffic Assignment

    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.

  18. A Greedy Path-Based Algorithm for Traffic Assignment

    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

  19. PDF Faster Path-Based Algorithm for Traffic Assignment

    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.

  20. Linear Programming Formulation for Strategic Dynamic Traffic Assignment

    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 ...

  21. A path-based traffic assignment algorithm based on the TRANSYT traffic

    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...

  22. Faster Path-based Algorithm for Traffic Assignment

    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 ...

  23. A Faster Path-Based Algorithm for Traffic Assignment

    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 ...