IDEAS home Printed from https://ideas.repec.org/a/kap/netspa/v14y2014i3p409-433.html
   My bibliography  Save this article

A Distributionally Robust Joint Chance Constrained Optimization Model for the Dynamic Network Design Problem under Demand Uncertainty

Author

Listed:
  • Hua Sun
  • Ziyou Gao
  • W. Szeto
  • Jiancheng Long
  • Fangxia Zhao

Abstract

This paper develops a distributionally robust joint chance constrained optimization model for a dynamic network design problem (NDP) under demand uncertainty. The major contribution of this paper is to propose an approach to approximate a joint chance-constrained Cell Transmission Model (CTM) based System Optimal Dynamic Network Design Problem with only partial distributional information of uncertain demand. The proposed approximation is tighter than two popular benchmark approximations, namely the Bonferroni’s inequality and second-order cone programming (SOCP) approximations. The resultant formulation is a semidefinite program which is computationally efficient. A numerical experiment is conducted to demonstrate that the proposed approximation approach is superior to the other two approximation approaches in terms of solution quality. The proposed approximation approach may provide useful insights and have broader applicability in traffic management and traffic planning problems under uncertainty. Copyright Springer Science+Business Media New York 2014

Suggested Citation

  • Hua Sun & Ziyou Gao & W. Szeto & Jiancheng Long & Fangxia Zhao, 2014. "A Distributionally Robust Joint Chance Constrained Optimization Model for the Dynamic Network Design Problem under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 14(3), pages 409-433, December.
    • Handle: RePEc:kap:netspa:v:14:y:2014:i:3:p:409-433
    DOI: 10.1007/s11067-014-9236-8
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s11067-014-9236-8
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s11067-014-9236-8?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    2. T. L. Magnanti & R. T. Wong, 1984. "Network Design and Transportation Planning: Models and Algorithms," Transportation Science, INFORMS, vol. 18(1), pages 1-55, February.
    3. Athanasios K. Ziliaskopoulos, 2000. "A Linear Programming Model for the Single Destination System Optimum Dynamic Traffic Assignment Problem," Transportation Science, INFORMS, vol. 34(1), pages 37-49, February.
    4. G. C. Calafiore & L. El Ghaoui, 2006. "On Distributionally Robust Chance-Constrained Linear Programs," Journal of Optimization Theory and Applications, Springer, vol. 130(1), pages 1-22, July.
    5. Doan, Kien & Ukkusuri, Satish V., 2012. "On the holding-back problem in the cell transmission based dynamic traffic assignment models," Transportation Research Part B: Methodological, Elsevier, vol. 46(9), pages 1218-1238.
    6. Daganzo, Carlos F., 1995. "The cell transmission model, part II: Network traffic," Transportation Research Part B: Methodological, Elsevier, vol. 29(2), pages 79-93, April.
    7. ,, 2000. "Problems And Solutions," Econometric Theory, Cambridge University Press, vol. 16(2), pages 287-299, April.
    8. Byung Chung & Tao Yao & Chi Xie & Andreas Thorsen, 2011. "Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 11(2), pages 371-389, June.
    9. Yin, Yafeng & Madanat, Samer M. & Lu, Xiao-Yun, 2009. "Robust improvement schemes for road networks under demand uncertainty," European Journal of Operational Research, Elsevier, vol. 198(2), pages 470-479, October.
    10. A. Ben-Tal & A. Nemirovski, 1998. "Robust Convex Optimization," Mathematics of Operations Research, INFORMS, vol. 23(4), pages 769-805, November.
    11. Anthony Chen & Zhong Zhou & Piya Chootinan & Seungkyu Ryu & Chao Yang & S. Wong, 2011. "Transport Network Design Problem under Uncertainty: A Review and New Developments," Transport Reviews, Taylor & Francis Journals, vol. 31(6), pages 743-768.
    12. Tao Yao & Supreet Mandala & Byung Chung, 2009. "Evacuation Transportation Planning Under Uncertainty: A Robust Optimization Approach," Networks and Spatial Economics, Springer, vol. 9(2), pages 171-189, June.
    13. Dimitris Bertsimas & Melvyn Sim, 2004. "The Price of Robustness," Operations Research, INFORMS, vol. 52(1), pages 35-53, February.
    14. Satish Ukkusuri & S. Waller, 2008. "Linear Programming Models for the User and System Optimal Dynamic Network Design Problem: Formulations, Comparisons and Extensions," Networks and Spatial Economics, Springer, vol. 8(4), pages 383-406, December.
    15. S Mudchanatongsuk & F Ordóñez & J Liu, 2008. "Robust solutions for network design under transportation cost and demand uncertainty," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 59(5), pages 652-662, May.
    16. Dung-Ying Lin & Ampol Karoonsoontawong & S. Waller, 2011. "A Dantzig-Wolfe Decomposition Based Heuristic Scheme for Bi-level Dynamic Network Design Problem," Networks and Spatial Economics, Springer, vol. 11(1), pages 101-126, March.
    17. Ben-Tal, Aharon & Chung, Byung Do & Mandala, Supreet Reddy & Yao, Tao, 2011. "Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1177-1189, September.
    18. A. Charnes & W. W. Cooper & G. H. Symonds, 1958. "Cost Horizons and Certainty Equivalents: An Approach to Stochastic Programming of Heating Oil," Management Science, INFORMS, vol. 4(3), pages 235-263, April.
    19. Daganzo, Carlos F., 1994. "The cell transmission model: A dynamic representation of highway traffic consistent with the hydrodynamic theory," Transportation Research Part B: Methodological, Elsevier, vol. 28(4), pages 269-287, August.
    20. Ampol Karoonsoontawong & Steven Waller, 2010. "Integrated Network Capacity Expansion and Traffic Signal Optimization Problem: Robust Bi-level Dynamic Formulation," Networks and Spatial Economics, Springer, vol. 10(4), pages 525-550, December.
    21. Erick Delage & Yinyu Ye, 2010. "Distributionally Robust Optimization Under Moment Uncertainty with Application to Data-Driven Problems," Operations Research, INFORMS, vol. 58(3), pages 595-612, June.
    22. D E Boyce, 1984. "Urban Transportation Network-Equilibrium and Design Models: Recent Achievements and Future Prospects," Environment and Planning A, , vol. 16(11), pages 1445-1474, November.
    23. John M. Mulvey & Robert J. Vanderbei & Stavros A. Zenios, 1995. "Robust Optimization of Large-Scale Systems," Operations Research, INFORMS, vol. 43(2), pages 264-281, April.
    24. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    25. Yong Zhao & Kara Maria Kockelman, 2002. "The propagation of uncertainty through travel demand models: An exploratory analysis," The Annals of Regional Science, Springer;Western Regional Science Association, vol. 36(1), pages 145-163.
    26. Sumalee, A. & Zhong, R.X. & Pan, T.L. & Szeto, W.Y., 2011. "Stochastic cell transmission model (SCTM): A stochastic dynamic traffic model for traffic state surveillance and assignment," Transportation Research Part B: Methodological, Elsevier, vol. 45(3), pages 507-533, March.
    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. Rashed Khanjani-Shiraz & Ali Babapour-Azar & Zohreh Hosseini-Noudeh & Panos M. Pardalos, 2022. "Distributionally robust maximum probability shortest path problem," Journal of Combinatorial Optimization, Springer, vol. 43(1), pages 140-167, January.
    2. Kathryn M. Schumacher & Richard Li‐Yang Chen & Amy E.M. Cohn & Jeremy Castaing, 2016. "Algorithm to solve a chance‐constrained network capacity design problem with stochastic demands and finite support," Naval Research Logistics (NRL), John Wiley & Sons, vol. 63(3), pages 236-246, April.
    3. Liu, Ming & Liu, Xin & Chu, Feng & Zheng, Feifeng & Chu, Chengbin, 2019. "Distributionally robust inventory routing problem to maximize the service level under limited budget," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 126(C), pages 190-211.
    4. Ming Liu & Rongfan Liu & E Zhang & Chengbin Chu, 2022. "Eco-friendly container transshipment route scheduling problem with repacking operations," Journal of Combinatorial Optimization, Springer, vol. 43(5), pages 1010-1035, July.
    5. Khooban, Zohreh & Farahani, Reza Zanjirani & Miandoabchi, Elnaz & Szeto, W.Y., 2015. "Mixed network design using hybrid scatter search," European Journal of Operational Research, Elsevier, vol. 247(3), pages 699-710.
    6. Bakker, Hannah & Dunke, Fabian & Nickel, Stefan, 2020. "A structuring review on multi-stage optimization under uncertainty: Aligning concepts from theory and practice," Omega, Elsevier, vol. 96(C).
    7. Wang, Weiqiao & Yang, Kai & Yang, Lixing & Gao, Ziyou, 2021. "Two-stage distributionally robust programming based on worst-case mean-CVaR criterion and application to disaster relief management," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 149(C).
    8. Ming Liu & Rongfan Liu & E Zhang & Chengbin Chu, 0. "Eco-friendly container transshipment route scheduling problem with repacking operations," Journal of Combinatorial Optimization, Springer, vol. 0, pages 1-26.
    9. Chang, Zhiqi & Song, Shiji & Zhang, Yuli & Ding, Jian-Ya & Zhang, Rui & Chiong, Raymond, 2017. "Distributionally robust single machine scheduling with risk aversion," European Journal of Operational Research, Elsevier, vol. 256(1), pages 261-274.

    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. Byung Chung & Tao Yao & Chi Xie & Andreas Thorsen, 2011. "Robust Optimization Model for a Dynamic Network Design Problem Under Demand Uncertainty," Networks and Spatial Economics, Springer, vol. 11(2), pages 371-389, June.
    2. Ben-Tal, Aharon & Chung, Byung Do & Mandala, Supreet Reddy & Yao, Tao, 2011. "Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains," Transportation Research Part B: Methodological, Elsevier, vol. 45(8), pages 1177-1189, September.
    3. Marla, Lavanya & Rikun, Alexander & Stauffer, Gautier & Pratsini, Eleni, 2020. "Robust modeling and planning: Insights from three industrial applications," Operations Research Perspectives, Elsevier, vol. 7(C).
    4. Chou, Chang-Chi & Chiang, Wen-Chu & Chen, Albert Y., 2022. "Emergency medical response in mass casualty incidents considering the traffic congestions in proximity on-site and hospital delays," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 158(C).
    5. L. Jeff Hong & Zhiyuan Huang & Henry Lam, 2021. "Learning-Based Robust Optimization: Procedures and Statistical Guarantees," Management Science, INFORMS, vol. 67(6), pages 3447-3467, June.
    6. Roos, Ernst & den Hertog, Dick, 2019. "Reducing conservatism in robust optimization," Other publications TiSEM ad0238cd-de7a-4366-b487-b, Tilburg University, School of Economics and Management.
    7. Tao Yao & Supreet Mandala & Byung Chung, 2009. "Evacuation Transportation Planning Under Uncertainty: A Robust Optimization Approach," Networks and Spatial Economics, Springer, vol. 9(2), pages 171-189, June.
    8. Chi Xie & Jennifer Duthie, 2015. "An Excess-Demand Dynamic Traffic Assignment Approach for Inferring Origin-Destination Trip Matrices," Networks and Spatial Economics, Springer, vol. 15(4), pages 947-979, December.
    9. Byung Chung & Tao Yao & Bo Zhang, 2012. "Dynamic Traffic Assignment under Uncertainty: A Distributional Robust Chance-Constrained Approach," Networks and Spatial Economics, Springer, vol. 12(1), pages 167-181, March.
    10. Kimms, A. & Maiwald, M., 2018. "Bi-objective safe and resilient urban evacuation planning," European Journal of Operational Research, Elsevier, vol. 269(3), pages 1122-1136.
    11. Grani A. Hanasusanto & Vladimir Roitch & Daniel Kuhn & Wolfram Wiesemann, 2017. "Ambiguous Joint Chance Constraints Under Mean and Dispersion Information," Operations Research, INFORMS, vol. 65(3), pages 751-767, June.
    12. Douglas Bish & Edward Chamberlayne & Hesham Rakha, 2013. "Optimizing Network Flows with Congestion-Based Flow Reductions," Networks and Spatial Economics, Springer, vol. 13(3), pages 283-306, September.
    13. Shao-Wei Lam & Tsan Sheng Ng & Melvyn Sim & Jin-Hwa Song, 2013. "Multiple Objectives Satisficing Under Uncertainty," Operations Research, INFORMS, vol. 61(1), pages 214-227, February.
    14. Ernst Roos & Dick den Hertog, 2020. "Reducing Conservatism in Robust Optimization," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1109-1127, October.
    15. Wenqing Chen & Melvyn Sim & Jie Sun & Chung-Piaw Teo, 2010. "From CVaR to Uncertainty Set: Implications in Joint Chance-Constrained Optimization," Operations Research, INFORMS, vol. 58(2), pages 470-485, April.
    16. Zhi Chen & Melvyn Sim & Huan Xu, 2019. "Distributionally Robust Optimization with Infinitely Constrained Ambiguity Sets," Operations Research, INFORMS, vol. 67(5), pages 1328-1344, September.
    17. Goh, Joel Weiqiang & Lim, Kian Guan & Sim, Melvyn & Zhang, Weina, 2012. "Portfolio value-at-risk optimization for asymmetrically distributed asset returns," European Journal of Operational Research, Elsevier, vol. 221(2), pages 397-406.
    18. Elnaz Miandoabchi & Reza Farahani & Wout Dullaert & W. Szeto, 2012. "Hybrid Evolutionary Metaheuristics for Concurrent Multi-Objective Design of Urban Road and Public Transit Networks," Networks and Spatial Economics, Springer, vol. 12(3), pages 441-480, September.
    19. Liu, Kanglin & Li, Qiaofeng & Zhang, Zhi-Hai, 2019. "Distributionally robust optimization of an emergency medical service station location and sizing problem with joint chance constraints," Transportation Research Part B: Methodological, Elsevier, vol. 119(C), pages 79-101.
    20. Gabrel, Virginie & Murat, Cécile & Thiele, Aurélie, 2014. "Recent advances in robust optimization: An overview," European Journal of Operational Research, Elsevier, vol. 235(3), pages 471-483.

    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:kap:netspa:v:14:y:2014:i:3:p:409-433. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.