IDEAS home Printed from https://ideas.repec.org/a/eee/transb/v41y2007i1p4-31.html
   My bibliography  Save this article

Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design

Author

Listed:
  • Josefsson, Magnus
  • Patriksson, Michael

Abstract

We provide a sensitivity analysis of separable traffic equilibrium models with travel cost and demand parameters. We establish that while equilibrium link flows may not always be directionally differentiable (even when the link travel costs are strictly increasing), travel demands and link costs are; this improves the general results of Patriksson [Patriksson, M., 2004. Sensitivity analysis of traffic equilibria. Transportation Science 37, 258-281]. The new results contradict common belief that equilibrium cost and demand sensitivities hinge on that of equilibrium flows. The paper by Tobin and Friesz [Tobin, R.L., Friesz, T.L., 1988. Sensitivity analysis for equilibrium network flow. Transportation Science 22, 242-250] brought the classic non-linear programming subject of sensitivity analysis to transportation science. Theirs is still the most widely used device by which "gradients" of traffic equilibrium solutions are calculated, for use in bilevel transportation planning applications such as network design, origin-destination (OD) matrix estimation and problems where link tolls are imposed on the users in order to reach a traffic management objective. However, it is not widely understood that the regularity conditions proposed by them are stronger than necessary. Also, users of their method sometimes misunderstand its limitations and are not aware of the computational advantages offered by more recent methods. In fact, a more often applicable formula was proposed already by Qiu and Magnanti [Qiu, Y., Magnanti, T.L., 1989. Sensitivity analysis for variational inequalities defined on polyhedral sets. Mathematics of Operations Research 14, 410-432], and Bell and Iida [Bell, M.G.H., Iida, Y., 1997. Transportation Network Analysis. John Wiley & Sons, Chichester, UK] describe one of the cases in practice in which the formula by Tobin and Friesz would not be able to generate sensitivity information, because one of their regularity conditions fails to hold. This paper provides an overview of this formula, and illustrates by means of examples that there are several cases where it is not applicable. Our findings are illustrated with small numerical examples, as are our own analysis. The findings of this paper are hoped to motivate replacing the previous approach with the more often applicable one, not only because of this fact but equally importantly because it is intuitive and also can be much more efficiently utilized: the sensitivity problem that provides the directional derivative is a linearized traffic equilibrium problem, and the sensitivity information can be generated efficiently by only slightly modifying a state-of-the-art traffic equilibrium solver. This is essential for bringing the use of sensitivity analysis in transportation planning beyond the solution of only toy problems. We finally utilize a new sensitivity solver in the preliminary testing of a simple heuristic for bilevel optimization in continuous traffic network design, and compare it favourably to previous heuristics on known small-scale problems.

Suggested Citation

  • Josefsson, Magnus & Patriksson, Michael, 2007. "Sensitivity analysis of separable traffic equilibrium equilibria with application to bilevel optimization in network design," Transportation Research Part B: Methodological, Elsevier, vol. 41(1), pages 4-31, January.
  • Handle: RePEc:eee:transb:v:41:y:2007:i:1:p:4-31
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0191-2615(06)00025-7
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Yang, Hai & Yagar, Sam & Iida, Yasunori & Asakura, Yasuo, 1994. "An algorithm for the inflow control problem on urban freeway networks with user-optimal flows," Transportation Research Part B: Methodological, Elsevier, vol. 28(2), pages 123-139, April.
    2. Chiou, Suh-Wen, 2003. "TRANSYT derivatives for area traffic control optimisation with network equilibrium flows," Transportation Research Part B: Methodological, Elsevier, vol. 37(3), pages 263-290, March.
    3. Yang, Hai & Yagar, Sam, 1995. "Traffic assignment and signal control in saturated road networks," Transportation Research Part A: Policy and Practice, Elsevier, vol. 29(2), pages 125-139, March.
    4. Chen, Anthony & Yang, Hai & Lo, Hong K. & Tang, Wilson H., 2002. "Capacity reliability of a road network: an assessment methodology and numerical results," Transportation Research Part B: Methodological, Elsevier, vol. 36(3), pages 225-252, March.
    5. Nathan H. Gartner, 1980. "Optimal Traffic Assignment with Elastic Demands: A Review Part II. Algorithmic Approaches," Transportation Science, INFORMS, vol. 14(2), pages 192-208, May.
    6. Stephen M. Robinson, 1980. "Strongly Regular Generalized Equations," Mathematics of Operations Research, INFORMS, vol. 5(1), pages 43-62, February.
    7. Wong, S. C. & Yang, Hai, 1997. "Reserve capacity of a signal-controlled road network," Transportation Research Part B: Methodological, Elsevier, vol. 31(5), pages 397-402, October.
    8. Yan, Hai & Lam, William H. K., 1996. "Optimal road tolls under conditions of queueing and congestion," Transportation Research Part A: Policy and Practice, Elsevier, vol. 30(5), pages 319-332, September.
    9. Yang, Hai & Yagar, Sam, 1994. "Traffic assignment and traffic control in general freeway-arterial corridor systems," Transportation Research Part B: Methodological, Elsevier, vol. 28(6), pages 463-486, December.
    10. Yang, Hai & Bell, Michael G. H. & Meng, Qiang, 2000. "Modeling the capacity and level of service of urban transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 34(4), pages 255-275, May.
    11. Yang, Hai & Meng, Qiang, 2000. "Highway pricing and capacity choice in a road network under a build-operate-transfer scheme," Transportation Research Part A: Policy and Practice, Elsevier, vol. 34(3), pages 207-222, April.
    12. Chaisak Suwansirikul & Terry L. Friesz & Roger L. Tobin, 1987. "Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem," Transportation Science, INFORMS, vol. 21(4), pages 254-263, November.
    13. Tam, M. L. & Lam, William H. K., 2000. "Maximum car ownership under constraints of road capacity and parking space," Transportation Research Part A: Policy and Practice, Elsevier, vol. 34(3), pages 145-170, April.
    14. Terry L. Friesz & Hsun-Jung Cho & Nihal J. Mehta & Roger L. Tobin & G. Anandalingam, 1992. "A Simulated Annealing Approach to the Network Design Problem with Variational Inequality Constraints," Transportation Science, INFORMS, vol. 26(1), pages 18-26, February.
    15. Suh-Wen Chiou, 1999. "Optimization of Area Traffic Control for Equilibrium Network Flows," Transportation Science, INFORMS, vol. 33(3), pages 279-289, August.
    16. Yang, Hai, 1995. "Heuristic algorithms for the bilevel origin-destination matrix estimation problem," Transportation Research Part B: Methodological, Elsevier, vol. 29(4), pages 231-242, August.
    17. Michael Patriksson & R. Tyrrell Rockafellar, 2002. "A Mathematical Model and Descent Algorithm for Bilevel Traffic Management," Transportation Science, INFORMS, vol. 36(3), pages 271-291, August.
    18. Roger L. Tobin & Terry L. Friesz, 1988. "Sensitivity Analysis for Equilibrium Network Flow," Transportation Science, INFORMS, vol. 22(4), pages 242-250, November.
    19. Torbjörn Larsson & Michael Patriksson, 1992. "Simplicial Decomposition with Disaggregated Representation for the Traffic Assignment Problem," Transportation Science, INFORMS, vol. 26(1), pages 4-17, February.
    20. Chan, K. S. & Lam, William H. K., 2002. "Optimal speed detector density for the network with travel time information," Transportation Research Part A: Policy and Practice, Elsevier, vol. 36(3), pages 203-223, March.
    21. N. D. Yen, 1995. "Lipschitz Continuity of Solutions of Variational Inequalities with a Parametric Polyhedral Constraint," Mathematics of Operations Research, INFORMS, vol. 20(3), pages 695-708, August.
    22. Clark, Stephen D. & Watling, David P., 2002. "Sensitivity analysis of the probit-based stochastic user equilibrium assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 36(7), pages 617-635, August.
    23. Cho, Hsun-Jung & Smith, Tony E. & Friesz, Terry L., 2000. "A reduction method for local sensitivity analyses of network equilibrium arc flows," Transportation Research Part B: Methodological, Elsevier, vol. 34(1), pages 31-51, January.
    24. Nathan H. Gartner, 1980. "Optimal Traffic Assignment with Elastic Demands: A Review Part I. Analysis Framework," Transportation Science, INFORMS, vol. 14(2), pages 174-191, May.
    25. Leurent, F., 1998. "Sensitivity and error analysis of the dual criteria traffic assignment model," Transportation Research Part B: Methodological, Elsevier, vol. 32(3), pages 189-204, April.
    26. Gao, Ziyou & Sun, Huijun & Shan, Lian Long, 2004. "A continuous equilibrium network design model and algorithm for transit systems," Transportation Research Part B: Methodological, Elsevier, vol. 38(3), pages 235-250, March.
    27. Yang, Hai, 1997. "Sensitivity analysis for the elastic-demand network equilibrium problem with applications," Transportation Research Part B: Methodological, Elsevier, vol. 31(1), pages 55-70, February.
    28. Yuping Qiu & Thomas L. Magnanti, 1989. "Sensitivity Analysis for Variational Inequalities Defined on Polyhedral Sets," Mathematics of Operations Research, INFORMS, vol. 14(3), pages 410-432, August.
    29. Michael Patriksson & R. Tyrrell Rockafellar, 2003. "Sensitivity Analysis of Aggregated Variational Inequality Problems, with Application to Traffic Equilibria," Transportation Science, INFORMS, vol. 37(1), pages 56-68, February.
    30. Michael Patriksson, 2004. "Sensitivity Analysis of Traffic Equilibria," Transportation Science, INFORMS, vol. 38(3), pages 258-281, August.
    31. Yang, Hai & Sasaki, Tsuna & Iida, Yasunori & Asakura, Yasuo, 1992. "Estimation of origin-destination matrices from link traffic counts on congested networks," Transportation Research Part B: Methodological, Elsevier, vol. 26(6), pages 417-434, December.
    32. Wong, S. C. & Yang, Chao & Lo, Hong K., 2001. "A path-based traffic assignment algorithm based on the TRANSYT traffic model," Transportation Research Part B: Methodological, Elsevier, vol. 35(2), pages 163-181, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Du, Muqing & Chen, Anthony, 2022. "Sensitivity analysis for transit equilibrium assignment and applications to uncertainty analysis," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 175-202.
    2. Patriksson, Michael, 2008. "On the applicability and solution of bilevel optimization models in transportation science: A study on the existence, stability and computation of optimal solutions to stochastic mathematical programs," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 843-860, December.
    3. Jafari, Ehsan & Pandey, Venktesh & Boyles, Stephen D., 2017. "A decomposition approach to the static traffic assignment problem," Transportation Research Part B: Methodological, Elsevier, vol. 105(C), pages 270-296.
    4. Eikenbroek, Oskar A.L. & Still, Georg J. & van Berkum, Eric C., 2022. "Improving the performance of a traffic system by fair rerouting of travelers," European Journal of Operational Research, Elsevier, vol. 299(1), pages 195-207.
    5. Prateek Bansal & Rohan Shah & Stephen D. Boyles, 2018. "Robust network pricing and system optimization under combined long-term stochasticity and elasticity of travel demand," Transportation, Springer, vol. 45(5), pages 1389-1418, September.
    6. Hsueh, Che-Fu, 2015. "A bilevel programming model for corporate social responsibility collaboration in sustainable supply chain management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 73(C), pages 84-95.
    7. Frédéric Babonneau & Jean-Philippe Vial, 2008. "An Efficient Method to Compute Traffic Assignment Problems with Elastic Demands," Transportation Science, INFORMS, vol. 42(2), pages 249-260, May.
    8. Jafari, Ehsan & Boyles, Stephen D., 2016. "Improved bush-based methods for network contraction," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 298-313.
    9. Cominetti, Roberto & Dose, Valerio & Scarsini, Marco, 2024. "Phase transitions of the price-of-anarchy function in multi-commodity routing games," Transportation Research Part B: Methodological, Elsevier, vol. 182(C).
    10. Lederman, Roger & Wynter, Laura, 2011. "Real-time traffic estimation using data expansion," Transportation Research Part B: Methodological, Elsevier, vol. 45(7), pages 1062-1079, August.
    11. Shu Lu, 2008. "Sensitivity of Static Traffic User Equilibria with Perturbations in Arc Cost Function and Travel Demand," Transportation Science, INFORMS, vol. 42(1), pages 105-123, February.
    12. Shen, Wei & Wynter, Laura, 2012. "A new one-level convex optimization approach for estimating origin–destination demand," Transportation Research Part B: Methodological, Elsevier, vol. 46(10), pages 1535-1555.
    13. Sander Van Cranenburgh & Caspar Chorus & Bert Van Wee, 2012. "Substantial Changes and Their Impact on Mobility: A Typology and an Overview of the Literature," Transport Reviews, Taylor & Francis Journals, vol. 32(5), pages 569-597, June.
    14. Bar-Gera, Hillel & Hellman, Fredrik & Patriksson, Michael, 2013. "Computational precision of traffic equilibria sensitivities in automatic network design and road pricing," Transportation Research Part B: Methodological, Elsevier, vol. 57(C), pages 485-500.
    15. Dung-Ying Lin & Avinash Unnikrishnan & S. Waller, 2011. "A Dual Variable Approximation Based Heuristic for Dynamic Congestion Pricing," Networks and Spatial Economics, Springer, vol. 11(2), pages 271-293, June.
    16. Byung Chung & Hsun-Jung Cho & Terry Friesz & Henh Huang & Tao Yao, 2014. "Sensitivity Analysis of User Equilibrium Flows Revisited," Networks and Spatial Economics, Springer, vol. 14(2), pages 183-207, June.
    17. S. Dempe & A. Zemkoho, 2012. "Bilevel road pricing: theoretical analysis and optimality conditions," Annals of Operations Research, Springer, vol. 196(1), pages 223-240, July.
    18. Diana P. Moreno-Palacio & Carlos A. Gonzalez-Calderon & John Jairo Posada-Henao & Hector Lopez-Ospina & Jhan Kevin Gil-Marin, 2022. "Entropy-Based Transit Tour Synthesis Using Fuzzy Logic," Sustainability, MDPI, vol. 14(21), pages 1-25, November.
    19. O'Hare, Steven J. & Connors, Richard D. & Watling, David P., 2016. "Mechanisms that govern how the Price of Anarchy varies with travel demand," Transportation Research Part B: Methodological, Elsevier, vol. 84(C), pages 55-80.
    20. Wei Nai & Zan Yang & Dan Li & Lu Liu & Yuting Fu & Yuao Guo, 2024. "Urban Day-to-Day Travel and Its Development in an Information Environment: A Review," Sustainability, MDPI, vol. 16(6), pages 1-29, March.
    21. Eikenbroek, Oskar A.L. & Still, Georg J. & van Berkum, Eric C. & Kern, Walter, 2018. "The Boundedly Rational User Equilibrium: A parametric analysis with application to the Network Design Problem," Transportation Research Part B: Methodological, Elsevier, vol. 107(C), pages 1-17.
    22. Chiou, Suh-Wen, 2015. "A cutting plane projection method for bi-level area traffic control optimization with uncertain travel demand," Applied Mathematics and Computation, Elsevier, vol. 266(C), pages 390-403.
    23. Cominetti, Roberto & Dose, Valerio & Scarsini, Marco, 2024. "Monotonicity of equilibria in nonatomic congestion games," European Journal of Operational Research, Elsevier, vol. 316(2), pages 754-766.
    24. Connors, Richard D. & Sumalee, Agachai & Watling, David P., 2007. "Sensitivity analysis of the variable demand probit stochastic user equilibrium with multiple user-classes," Transportation Research Part B: Methodological, Elsevier, vol. 41(6), pages 593-615, July.
    25. Wang, Jian & He, Xiaozheng & Peeta, Srinivas, 2016. "Sensitivity analysis based approximation models for day-to-day link flow evolution process," Transportation Research Part B: Methodological, Elsevier, vol. 92(PA), pages 35-53.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Michael Patriksson, 2004. "Sensitivity Analysis of Traffic Equilibria," Transportation Science, INFORMS, vol. 38(3), pages 258-281, August.
    2. Du, Muqing & Chen, Anthony, 2022. "Sensitivity analysis for transit equilibrium assignment and applications to uncertainty analysis," Transportation Research Part B: Methodological, Elsevier, vol. 157(C), pages 175-202.
    3. Connors, Richard D. & Sumalee, Agachai & Watling, David P., 2007. "Sensitivity analysis of the variable demand probit stochastic user equilibrium with multiple user-classes," Transportation Research Part B: Methodological, Elsevier, vol. 41(6), pages 593-615, July.
    4. Patriksson, Michael, 2008. "On the applicability and solution of bilevel optimization models in transportation science: A study on the existence, stability and computation of optimal solutions to stochastic mathematical programs," Transportation Research Part B: Methodological, Elsevier, vol. 42(10), pages 843-860, December.
    5. Yang, Hai, 1997. "Sensitivity analysis for the elastic-demand network equilibrium problem with applications," Transportation Research Part B: Methodological, Elsevier, vol. 31(1), pages 55-70, February.
    6. Shu Lu, 2008. "Sensitivity of Static Traffic User Equilibria with Perturbations in Arc Cost Function and Travel Demand," Transportation Science, INFORMS, vol. 42(1), pages 105-123, February.
    7. Clark, Stephen D. & Watling, David P., 2006. "Applications of sensitivity analysis for probit stochastic network equilibrium," European Journal of Operational Research, Elsevier, vol. 175(2), pages 894-911, December.
    8. Michael Patriksson & R. Tyrrell Rockafellar, 2002. "A Mathematical Model and Descent Algorithm for Bilevel Traffic Management," Transportation Science, INFORMS, vol. 36(3), pages 271-291, August.
    9. Jian Wang & Muqing Du & Lili Lu & Xiaozheng He, 2018. "Maximizing Network Throughput under Stochastic User Equilibrium with Elastic Demand," Networks and Spatial Economics, Springer, vol. 18(1), pages 115-143, March.
    10. Meng, Q. & Yang, H. & Bell, M. G. H., 2001. "An equivalent continuously differentiable model and a locally convergent algorithm for the continuous network design problem," Transportation Research Part B: Methodological, Elsevier, vol. 35(1), pages 83-105, January.
    11. Lundgren, Jan T. & Peterson, Anders, 2008. "A heuristic for the bilevel origin-destination-matrix estimation problem," Transportation Research Part B: Methodological, Elsevier, vol. 42(4), pages 339-354, May.
    12. Michael Patriksson & R. Tyrrell Rockafellar, 2003. "Sensitivity Analysis of Aggregated Variational Inequality Problems, with Application to Traffic Equilibria," Transportation Science, INFORMS, vol. 37(1), pages 56-68, February.
    13. S. Dempe & A. Zemkoho, 2012. "Bilevel road pricing: theoretical analysis and optimality conditions," Annals of Operations Research, Springer, vol. 196(1), pages 223-240, July.
    14. Zhaoqi Zang & Xiangdong Xu & Anthony Chen & Chao Yang, 2022. "Modeling the α-max capacity of transportation networks: a single-level mathematical programming formulation," Transportation, Springer, vol. 49(4), pages 1211-1243, August.
    15. Byung Chung & Hsun-Jung Cho & Terry Friesz & Henh Huang & Tao Yao, 2014. "Sensitivity Analysis of User Equilibrium Flows Revisited," Networks and Spatial Economics, Springer, vol. 14(2), pages 183-207, June.
    16. Yang, Hai & Bell, Michael G. H., 2001. "Transport bilevel programming problems: recent methodological advances," Transportation Research Part B: Methodological, Elsevier, vol. 35(1), pages 1-4, January.
    17. Jafari, Ehsan & Boyles, Stephen D., 2016. "Improved bush-based methods for network contraction," Transportation Research Part B: Methodological, Elsevier, vol. 83(C), pages 298-313.
    18. Wang, Yu & Liu, Haoxiang & Fan, Yinchao & Ding, Jianxun & Long, Jiancheng, 2022. "Large-scale multimodal transportation network models and algorithms-Part II: Network capacity and network design problem," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 167(C).
    19. Paramet Luathep & Agachai Sumalee & H. Ho & Fumitaka Kurauchi, 2011. "Large-scale road network vulnerability analysis: a sensitivity analysis based approach," Transportation, Springer, vol. 38(5), pages 799-817, September.
    20. Gallo, Mariano & D'Acierno, Luca & Montella, Bruno, 2010. "A meta-heuristic approach for solving the Urban Network Design Problem," European Journal of Operational Research, Elsevier, vol. 201(1), pages 144-157, February.

    More about this item

    Statistics

    Access and download statistics

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:transb:v:41:y:2007:i:1:p:4-31. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/548/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.