The goal of IJTTE is to broaden the knowledge of traffic and transport experts and academicians by promoting free access and provide valuable insight to transport related information, research and ideas. IJTTE will serve as a great resource for researchers and students across the globe.
Volume List  / Volume 4 (3)

Article

SLOPE-BASED PATH SHIFT PROPENSITY ALGORITHM FOR THE STATIC TRAFFIC ASSIGNMENT PROBLEM

DOI: 10.7708/ijtte.2014.4(3).05


4 / 3 / 297-319 Pages

Author(s)

Amit Kumar - NEXTRANS Center, Purdue University, West Lafayette, IN, USA -

Srinivas Peeta - School of Civil Engineering, Purdue University, West Lafayette, IN, USA -


Abstract

This paper presents a path-based traffic assignment algorithm for solving the static deterministic user equilibrium traffic assignment problem. It uses the concepts of the path shift-propensity factor and the sensitivity of path costs with respect to path flows in the flow update process, and is labeled as the slope-based path shift-propensity algorithm (SPSA). It seeks to enable faster convergence, incorporates behavioral realism in the flow update process, and maintains simplicity of execution for easy deployment in practice. The behavioral rationale behind the proposed algorithm is explained. The mathematical exposition of the algorithm and its proof of convergence are articulated. Numerical experiments are conducted using test networks to benchmark the performance of SPSA. The computational performance of the SPSA is compared with those of two versions of the recently developed path-based algorithm labeled slope-based multipath algorithm (SMPA), the widely-used Frank-Wolfe (F-W) algorithm, and a variant of the F-W algorithm labeled the social pressure algorithm (SPA). They illustrate that the rate of convergence of the SPSA is very close to that of the SMPA and significantly better than those of the F-W algorithm and the SPA. One version of the SMPA performs better than the SPSA in terms of convergence, though the latter is easier to implement and hence a potential substitute for SMPA in practice. Further, the results vindicate the notion that the SPSA is a feasible deployment option under the computational capabilities available today.


Download Article

Number of downloads: 2244

Keywords:
traffic assignment; user equilibrium; path flows; path shift-propensity;


Acknowledgements:

This study was partly funded by a project through the NEXTRANS Center at Purdue University, USA. We would like to acknowledge valuable comments from researchers at NEXTRANS Center during the algorithm development and coding process.


References:

Bar-Gera, H. 1999. Origin-Based Algorithms for Transportation Network Modeling. PhD Dissertation, University of Illinois at Chicago. Technical report, No.103.

 

Bar-Gera, H. 2010. Traffic assignment by paired alternative segments, Transportation Research Part B: Methodological. DOI: http://dx.doi.org/10.1016/j.trb.2009.11.004, 44(8-9): 1022-1046.

 

Bertsekas, D.P. 1976. On the Goldstein-Levitin-Poljak gradient projection method, IEEE Transactions on Automatic Control, 21(2): 174-184.

 

Bertsekas, D.P.; Gallager, R.G. 1987. Data Networks. Englewood Cliffs, Prentice-Hall, NJ, USA.

 

Bruynooghe, M.; Gilbert, A.; Sakarovitch, M. 1969. Une methode d’affectation du traffic. In Proceedings of the 4th International Symposium on the Theory of Road Traffic. Bundesminister fur Verkehr, Abt. Strassenbau, Bonn, Germany.

 

Beckmann, M.; McGuire, C.B.; Winsten, C.B. 1956. Studies in the Economics of Transportation. Yale University Press, New Haven.

 

Dafermos, S. 1968. Traffic Assignment and Resource Allocation in Transportation Networks. PhD Dissertation, Johns Hopkins University, Baltimore, MD, USA.

 

Dafermos, S.; Sparrow, R. 1969. The traffic assignment problem for a general network, Journal of Research of the National Bureau of Standards, 73(B): 91-118.

 

Dial, R.B. 2006. A path-based user-equilibrium traffic assignment algorithm that obviates path storage and enumeration, Transportation Research Part B: Methodological. DOI: http://dx.doi.org/10.1016/j.trb.2006.02.008, 40(10): 917-936.

 

Dow, P.; Van Vliet, D. 1979. Capacity restrained road assignment, Traffic Engineering and Control, 20(6): 261-273.

 

Florian, M.; Nguyen, S. 1976. An application and validation of equilibrium trip assignment methods, Transportation Science, 10(4): 374-390.

 

Florian, M.; Constantin, I.; Florian, D. 2009. A new look at the projected gradient method for equilibrium assignment, Transportation Research Record. DOI: http://dx.doi.org/10.3141/2090-02, 2090: 10-16.

 

Florian, M.; Guelat, J.; Spiess, H. 1987. An efficient implementation of the “PARTAN” variant of the linear approximation method for the network equilibrium problem, Networks. DOI: http://dx.doi.org/10.1002/net.3230170307, 17(3): 319-339.

 

Fukushima, M. 1984. A modified Frank-Wolfe algorithm for solving the traffic assignment problem, Transportation Research Part B: Methodological. DOI: http://dx.doi.org/10.1016/0191-2615(84)90029-8, 18(2): 169-177.

 

Gallager, R.G. 1977. A minimum delay routing algorithm using distributed computation, IEEE Transactions on Communications. DOI: http://dx.doi.org/10.1109/TCOM.1977.1093711, 25(1): 73-85.

 

Jayakrishnan, R .; Tsai, W.K.; Prashker, J.; Rajadhyaksha, S. 1994. A faster path-based algorithm for traffic assignment, Transportation Research Record, 1443: 75-83.

 

Knight, F.H. 1924. Some fallacies in the interpretation of social cost, Quarterly Journal of Economics. DOI: http://dx.doi.org/10.2307/1884592, 38(4): 582-606.

 

Kumar, A.; Peeta, S. 2010. Slope-based multipath flow update algorithm for the static user equilibrium traffic assignment problem, Transportation Research Record. DOI: http://dx.doi.org/10.3141/2196-01, 2196(1): 1-10.

 

Kumar, A.; Peeta, S. 2013. A post-processing technique for the four-step travel demand modeling executed through a feedback loop, Procedia – Social and Behavioral Sciences. DOI: http://dx.doi.org/10.1016/j.sbspro.2013.11.155, 104(2): 611-620.

 

Kumar, A.; Peeta, S.; Nie, Y.M. 2012. Update strategies for restricted master problem for the user equilibrium traffic assignment problem: a computational study, Transportation Research Record. DOI: http://dx.doi.org/10.3141/2283-14, 2283(1): 131-142.

 

Kupiszewska, D.; Van Vliet, D. 1998. Incremental traffic assignment: a perturbation approach. In Proceedings of the 3rd IMA International Conference on Mathematics in Transportation Planning and Control. 155-165.

 

Larsson, T.; Pat r iksson, M. 1992. Simplicial decomposition with disaggregate representation for the traffic assignment problem, Transportation Science. DOI: http://dx.doi.org/10.1287/trsc.26.1.4, 26(1): 4-17.

 

LeBlanc, L.J. 1973. Mathematical Programming Algorithms for Large Scale Network Equilibrium and Network Design Problems. PhD Dissertation, Department of Industrial Engineering and Management Science, Northwestern University, USA.

 

LeBlanc, L.J.; Helgason, R.V.; Boyce, D.E. 1985. Improved efficiency of the Frank-Wolfe algorithm for convex network problems, Transportation Science. DOI: http://dx.doi.org/10.1287/trsc.19.4.445, 19(4): 445-462.

 

LeBlanc, L.J.; Morlok, E.K.; Pierskalla, W.P. 1975. An efficient approach to solving the road network equilibrium traffic assignment problem, Transportation Research. DOI: http://dx.doi.org/10.1016/0041-1647(75)90030-1, 9(5): 309-318.

 

Lee, D.H.; Nie, Y.M. 2001. Accelerating strategies and computational studies of the Frank-Wolfe algorithm for the traffic assignment problem, Transportation Research Record. DOI: http://dx.doi.org/10.3141/1771-13, 1771: 97-105.

 

Lu, S.; Nie, Y.M. 2010. Stability of user-equilibrium route flow solutions for the traffic assignment problem, Transportation Research Part B: Methodological. DOI: http://dx.doi.org/10.1016/j.trb.2009.09.003, 44(4): 609-617.

 

Luenberger, D.G. 1973. Introduction to Linear and Nonlinear Programming. Addison-Wesley, Reading, Massachusetts. Meyer, G. 1974. Accelerated Frank-Wolfe algorithms, SIAM Journal on Control. DOI: http://dx.doi.org/10.1137/0312050, 12(4): 655-663.

 

Nguyen, S. 1974. An algorithm for the traffic assignment problem, Transportation Science. DOI: http://dx.doi.org/10.1002/net.3230100303, 8(3): 203-216.

 

Rosen, B. 1960. The gradient projection method fornonlinear programming, part I linear constraints, Journal of the Society for Industrial and Applied Mathematics, 8(1):181-217.

 

Rossi, T.F.; McNeil, S.; Hendrickson, C. 1989. Entropy model for consistent impact-fee assessment, Journal of Urban Planning and Development, ASCE. DOI: http://dx.doi.org/10.1061/(ASCE)0733-9488(1989)115:2(51), 115(2): 51-63.

 

Sheffi, Y. 1985. Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc., Englewood Cliffs, New Jersey.

 

Wardrop, J. 1952. Some theoretical aspects of road traffic research. In Proceedings of the Institution of Civil Engineers, 2: 325-378.

 

Weintraub, A; Ortiz, C.; Gonzales, J. 1985. Accelerating convergence of the Frank-Wolfe algorithm, Transportation Research Part B: Methodological. DOI: http://dx.doi.org/10.1016/0191-2615(85)90018-9, 19(2): 113-122.

 

Wolfe, P. 1970. Convergence Theory in Nonlinear Programming. In: Abadie J (ed) Integer and Nonlinear Programming, Nor th-Hol land, Amsterdam, Netherlands. 1-36.


Quoted IJTTE Works

There is no quoted studies.



Related Keywords

EVALUATION OF NIGHT ROUTE NETWORK ON FLIGHT EFFICIENCY IN EUROPE