A distributionally robust joint chance constrained optimization model for the dynamic network design problem under demand uncertainty. (English) Zbl 1338.90090
Summary: 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.
MSC:
| 90B15 | Stochastic network models in operations research |
| 90C15 | Stochastic programming |
| 90B20 | Traffic problems in operations research |
Keywords:
dynamic network design problem; distributionally robust joint chance constraints; worst-case conditional value-at-risk; semidefinite programming; demand uncertaintyReferences:
| [1] | Ben-Tal A, Nemirovski A (1998) Robust convex optimization. Math Oper Res 23(4):769-805 · Zbl 0977.90052 · doi:10.1287/moor.23.4.769 |
| [2] | Ben-Tal A, Nemirovski A (1999) Robust solutions of uncertain linear programs. Oper Res Lett 25(1):1-13 · Zbl 0941.90053 · doi:10.1016/S0167-6377(99)00016-4 |
| [3] | Ben-Tal A, Nemirovski A (2000) Robust solutions of linear programming problems contaminated with uncertain data. Math Program 88(3):411-424 · Zbl 0964.90025 · doi:10.1007/PL00011380 |
| [4] | Ben-Tal A, Nemirovski A (2002) Robust optimization-methodology and applications. Math Program 92(3):453-480 · Zbl 1007.90047 · doi:10.1007/s101070100286 |
| [5] | Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math Program 99(2):351-376 · Zbl 1089.90037 · doi:10.1007/s10107-003-0454-y |
| [6] | Ben-Tal A, El Ghaoui L, Nemirovski A (2009) Robust optimization. Princeton series in applied mathematics. Princeton University Press, Princeton · Zbl 1221.90001 |
| [7] | Ben-Tal A, Chung BD, Mandala SR, Yao T (2011) Robust optimization for emergency logistics planning: Risk mitigation in humanitarian relief supply chains. Transp Res B 45(8):1177-1189 · doi:10.1016/j.trb.2010.09.002 |
| [8] | Bertsimas D, Sim M (2004) The price of robustness. Oper Res 52(1):35-53 · Zbl 1165.90565 · doi:10.1287/opre.1030.0065 |
| [9] | Bertsimas D, Brown DB, Caramanis C (2011) Theory and applications of robust optimization. SIAM Rev 53(3):464-501 · Zbl 1233.90259 · doi:10.1137/080734510 |
| [10] | Boyce DE (1984) Urban transportation network-equilibrium and design models: recent achievements and future prospects. Environ Plan A 16(11):1445-1474 · doi:10.1068/a161445 |
| [11] | Calafiore GC, El Ghaoui L (2006) On distributionally robust chance-constrained linear programs with applications. J Optim Theory Appl 130(1):1-22 · Zbl 1143.90021 · doi:10.1007/s10957-006-9084-x |
| [12] | Charnes A, Cooper WW, Symonds GH (1958) Cost horizons and certainty equivalents: an approach to stochastic programming of heating oil. Manag Sci 4(3):235-263 · doi:10.1287/mnsc.4.3.235 |
| [13] | Chen W, Sim M (2009) Goal-driven optimization. Oper Res 57(2):342-357 · Zbl 1181.90203 · doi:10.1287/opre.1080.0570 |
| [14] | Chen W, Sim M, Sun J, Teo CP (2010) From CVaR to uncertainty set: implications in joint chance-constrained optimization. Oper Res 58(2):470-485 · Zbl 1226.90051 · doi:10.1287/opre.1090.0712 |
| [15] | Chen A, Zhou Z, Chootinan P, Ryu S, Yang C, Wong SC (2011) Transportation network design problem under uncertainty: a review and new developments. Transp Rev 31(6):743-768 · doi:10.1080/01441647.2011.589539 |
| [16] | Chung BD, Yao T, Xie C, Thorsen A (2011) Robust optimization model for a dynamic design problem under demand uncertainty. Netw Spat Econ 11(2):371-389 · Zbl 1213.90072 · doi:10.1007/s11067-010-9147-2 |
| [17] | Chung BD, Yao T, Zhang B (2012a) Dynamic traffic assignment under uncertainty: a distributional robust chance-constrained approach. Netw Spat Econ 12(1):167-181 · Zbl 1332.90066 · doi:10.1007/s11067-011-9157-8 |
| [18] | Chung BD, Yao T, Friesz TL, Liu HC (2012b) Dynamic congestion pricing with demand uncertainty: a robust optimization approach. Transp Res B 46(10):1504-1518 · Zbl 1213.90254 |
| [19] | Daganzo CF (1994) The cell transmission model: a dynamic representation of highway traffic consistent with the hydrodynamic theory. Transp Res B 28(4):269-287 · doi:10.1016/0191-2615(94)90002-7 |
| [20] | Daganzo CF (1995) The cell transmission model, part II: network traffic. Transp Res B 29(2):79-93 · doi:10.1016/0191-2615(94)00022-R |
| [21] | Delage E, Ye Y (2010) Distributionally robust optimization under moment uncertainty with application to data-driven problems. Oper Res 58(3):595-612 · Zbl 1228.90064 · doi:10.1287/opre.1090.0741 |
| [22] | Doan K, Ukkusuri SV (2012) On the holding-back problem in the cell transmission based dynamic traffic assignment models. Trans Res B 46(9):1218-1238 · doi:10.1016/j.trb.2012.05.001 |
| [23] | Janson BN (1995) Network design effects of dynamic traffic assignment. J Transp Eng 121(1):1-13 · doi:10.1061/(ASCE)0733-947X(1995)121:1(1) |
| [24] | Karoonsoontawong A, Waller ST (2006) Dynamic continuous network design problem: linear bilevel programming and metaheuristic approaches. Transp Res Rec: J Transp Res Board 1964:104-117 · doi:10.3141/1964-12 |
| [25] | Karoonsoontawong A, Waller ST (2007) Robust dynamic continuous network design problem. Transp Res Rec: J Transp Res Board 2029:58-71 · doi:10.3141/2029-07 |
| [26] | Karoonsoontawong A, Waller ST (2010) Integrated network capacity expansion and traffic signal optimization problem: robust bi-level dynamic formulation. Netw Spat Econ 10(4):525-550 · Zbl 1202.90030 · doi:10.1007/s11067-008-9071-x |
| [27] | Kouvelis P, Yu G (1997) Robust discrete optimization and its applications. Kluwer Academic Publishers, Boston · Zbl 0873.90071 · doi:10.1007/978-1-4757-2620-6 |
| [28] | Lin DY (2011) A dual variable approximation-based descent method for a bi-level continuous dynamic network design problem. Comput Aided Civ Infrastruct Eng 26(8):581-594 · doi:10.1111/j.1467-8667.2010.00705.x |
| [29] | Lin DY, Karoonsoontawong A, Waller ST (2011) A Dantzig-Wolfe decomposition based heuristic scheme for bi-level dynamic network design problem. Netw Spat Econ 11(1):101-126 · Zbl 1213.90254 · doi:10.1007/s11067-008-9093-4 |
| [30] | Löfberg J (2004) YALMIP: a toolbox for modeling and optimization in MATLAB. In Proceedings of the CACSD conference, Taipei · Zbl 1170.90328 |
| [31] | Lou Y, Yin Y, Lawpongpanich S (2009) Robust approach to discrete network designs with demand uncertainty. Transp Res Rec: J Transp Res Board 2090:86-94 · doi:10.3141/2090-10 |
| [32] | Lou Y, Yin Y, Lawpongpanich S (2010) Robust congestion price under rational user equilibrium. Transp Res B 44(1):15-28 · doi:10.1016/j.trb.2009.06.004 |
| [33] | Magnanti TL, Wong RT (1984) Network design and transportation planning: models and algorithms. Transp Sci 18(1):1-15 · doi:10.1287/trsc.18.1.1 |
| [34] | Minoux M (1989) Network synthesis and optimum network design problems: models, solution methods and applications. Networks 19(3):313-360 · Zbl 0666.90032 · doi:10.1002/net.3230190305 |
| [35] | Mudchanatongsuk S, Ordóñez F, Liu J (2008) Robust solutions for network design under transportation cost and demand uncertainty. J Oper Res Soc 59(5):652-662 · Zbl 1153.90341 · doi:10.1057/palgrave.jors.2602362 |
| [36] | Mulvey JM, Vanderbei RJ, Zenios SA (1995) Robust optimization of large-scale systems. Oper Res 43(2):264-281 · Zbl 0832.90084 · doi:10.1287/opre.43.2.264 |
| [37] | Nemirovski A, Shapiro A (2006) Convex approximations of chance constrained programs. SIAM J Optim 17(4):969-996 · Zbl 1126.90056 · doi:10.1137/050622328 |
| [38] | Patil GR, Ukkusuri SV (2007) System-optimal stochastic transportation network design. Transp Res Rec: J Transp Res Board 2029:80-86 · doi:10.3141/2029-09 |
| [39] | Rockafellar RT, Uryasev S (2000) Optimization of conditional value-at-risk. J Risk 2(3):21-41 |
| [40] | Rockafellar RT, Uryasev S (2002) Conditional Value-at-Risk for general loss distributions. J Bank Finance 26(7):1443-1471 · doi:10.1016/S0378-4266(02)00271-6 |
| [41] | Shapiro A, Kleywegt AJ (2002) Minimax analysis of stochastic problems. Optim Methods Softw 17(3):523-542 · Zbl 1040.90030 · doi:10.1080/1055678021000034008 |
| [42] | Sturm JF (1999) Using SeDuMi 1.02, a Matlab toolbox for optimization over symmetric cones. Optim Methods Softw 11(1-4):625-653 · Zbl 0973.90526 · doi:10.1080/10556789908805766 |
| [43] | Sumalee A, Zhong RX, Pan TL, Szeto WY (2011) Stochastic cell transmission model (SCTM): a stochastic dynamic traffic model for traffic state surveillance and assignment. Transp Res B 45(3):507-533 · doi:10.1016/j.trb.2010.09.006 |
| [44] | Ukkusuri SV, Waller ST (2008) Linear programming models for the user and system optimal dynamic network design problem: formulations, comparisons and extensions. Netw Spat Econ 8(4):383-406 · Zbl 1162.90515 · doi:10.1007/s11067-007-9019-6 |
| [45] | Ukkusuri SV, Mathew TV, Waller ST (2007) Robust Networks Design model using multi-objective evolutionary algorithms. Comput Aided Civ Infrastruct Eng 22(1):9-21 · doi:10.1111/j.1467-8667.2006.00465.x |
| [46] | Waller ST (2000) Optimization and control of stochastic dynamic transportation systems: formulations, solution methodologies, and computational experience. Ph.D. Dissertation, Northwestern University · Zbl 0964.90025 |
| [47] | Waller ST, Ziliaskopoulos AK (2001) Stochastic dynamic network design problem. Transp Res Rec: J Transp Res Board 1771:106-113 · doi:10.3141/1771-14 |
| [48] | Waller ST, Ziliaskopoulos AK (2006) A chance-constrained based stochastic dynamic traffic assignment model: analysis, formulation and solution algorithms. Transp Res C 14(6):418-427 · doi:10.1016/j.trc.2006.11.002 |
| [49] | Waller ST, Schofer JL, Ziliaskopoulos AK (2001) Evaluation with traffic assignment under demand uncertainty. Transp Res Rec: J Transp Res Board 1771:69-74 · doi:10.3141/1771-09 |
| [50] | Waller ST, Mousokos KC, Kamaryiannis D, Ziliaskopoloulos AK (2006) A linear model for the continuous network design problem. Comput Aided Civ Infrastruct Eng 21(5):334-345 · doi:10.1111/j.1467-8667.2006.00440.x |
| [51] | Yang H, Bell MGH (1998) Models and algorithms for road network design: a review and some new developments. Transp Rev 18(3):257-278 · doi:10.1080/01441649808717016 |
| [52] | Yao T, Mandala SR, Chung BD (2009) Evacuation transportation planning under uncertainty: a robust optimization approach. Netw Spat Econ 9(2):171-189 · Zbl 1170.90328 · doi:10.1007/s11067-009-9103-1 |
| [53] | Yazici A, Ozbay K (2010) Evacuation network modeling via dynamic traffic assignment with probability demand and capacity constraints. Transp Res Rec: J Transp Res Board 2196:11-20 · doi:10.3141/2196-02 |
| [54] | Yin Y, Lawpongpanich S (2007) A robust approach to continuous network designs with demand uncertainty. Proc 17th Int Sympo Transp Traffic Theory 111-126 |
| [55] | Yin Y, Lawpongpanich S (2008) Estimating investment requirement for maintaining and improving highway systems. Transp Res C 16(2):199-211 · doi:10.1016/j.trc.2007.07.004 |
| [56] | Yin Y, Madanat SM, Lu XY (2009) Robust improvement schemes for road networks under demand uncertainty. Eur J Oper Res 198(2):470-479 · Zbl 1163.90378 · doi:10.1016/j.ejor.2008.09.008 |
| [57] | Zhao Y, Kockelman KM (2002) The propagation of uncertainty through travel demand models: an exploratory analysis. Ann Reg Sci 36(1):145-163 · doi:10.1007/s001680200072 |
| [58] | Zhu F, Ukkusuri SV (2013) A cell based dynamic system optimum model with non-holding back flows. Transp Res C 36:367-380 · doi:10.1016/j.trc.2013.09.003 |
| [59] | Ziliaskopoulos AK (2000) A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transp Sci 34(1):37-49 · Zbl 1002.90013 · doi:10.1287/trsc.34.1.37.12281 |
| [60] | Zymler S, Kuhn D, Rustem B (2013) Distributionally robust joint chance constraints with second-order moment information. Math Program 137(1-2):167-198 · Zbl 1286.90103 · doi:10.1007/s10107-011-0494-7 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
