×

Link-based system optimum dynamic traffic assignment problems in general networks. (English) Zbl 1443.90122

Summary: Most current system optimum dynamic traffic assignment (SO-DTA) models do not contain first-in-first-out (FIFO) constraints and are limited to single-destination network applications. In this study, we introduce the link transmission model (LTM) for the development of SO-DTA models either with or without FIFO constraints for general network applications. The proposed SO-DTA models include the LTM and can lead to a linear programming (LP) formulation if the FIFO constraints are not explicitly captured. The vehicle holding problem can be addressed by adding a penalty term to the objective function. We also formulate FIFO constraints in terms of the relationship between link cumulative inflows and outflows and the link entry time. Optimization models that integrate the proposed FIFO constraints into the proposed LP formulations for SO-DTA problems without FIFO constraints are also developed to formulate SO-DTA problems with FIFO constraints. Based on the properties of the proposed optimization problems, branch-and-bound algorithms are developed to solve SO-DTA problems with FIFO constraints. Two methods are developed to identify FIFO violations in feasible flow patterns and to design a branching scheme for the proposed branch-and-bound algorithms. Finally, numerical examples are set up to demonstrate the properties of the proposed models and the performance of the algorithms.
The e-companion is available at https://doi.org/10.1287/opre.2018.1775.

MSC:

90B06 Transportation, logistics and supply chain management
90B10 Deterministic network models in operations research
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ban X, Pang JS, Liu X, Ma R (2012) Continuous-time point-queue models in dynamic network loading. Transportation Res. Part B 46(3):360-380.Crossref, Google Scholar · doi:10.1016/j.trb.2011.11.004
[2] Bliemer MCJ, Raadsen MPH, Smits ES, Zhou B, Bell MGH (2014) Quasi-dynamic traffic assignment with residual point queues incorporating a first order node model. Transportation Res. Part B 68:363-384.Crossref, Google Scholar · doi:10.1016/j.trb.2014.07.001
[3] Carey M (1987) Optimal time-varying flows on congested networks. Oper. Res. 35(1):58-69.Link, Google Scholar · Zbl 0629.90033
[4] Carey M (1992) Nonconvexity of the dynamic traffic assignment problem. Transportation Res. Part B 26(2):127-133.Crossref, Google Scholar · doi:10.1016/0191-2615(92)90003-F
[5] Carey M (2004) Link travel times I: Desirable properties. Networks Spatial Econom. 4(3):257-268.Crossref, Google Scholar · Zbl 1069.90023 · doi:10.1023/B:NETS.0000039782.48154.ef
[6] Carey M, Srinivasan A (1993) Externalities, average and marginal costs, and tolls on congested networks with time-varying flows. Oper. Res. 41(1):217-231.Link, Google Scholar · Zbl 0771.90034
[7] Carey M, Humphreys P, McHugh M, McIvor R (2014) Extending travel-time based models for dynamic network loading and assignment, to achieve adherence to first-in-first-out and link capacities. Transportation Res. Part B 65:90-104.Crossref, Google Scholar · doi:10.1016/j.trb.2014.04.002
[8] Chow A (2009) Properties of system optimal traffic assignment with departure time choice and its solution method. Transportation Res. Part B 43(3):325-344.Crossref, Google Scholar · doi:10.1016/j.trb.2008.07.006
[9] Daganzo CF (1995) The cell transmission model, part II: Network traffic. Transportation Res. Part B 29(2):79-93.Crossref, Google Scholar · doi:10.1016/0191-2615(94)00022-R
[10] Doan K, Ukkusuri SV (2012) On the holding back problem in cell transmission based dynamic traffic assignment models. Transportation Res. Part B 46(9):1218-1238.Crossref, Google Scholar · doi:10.1016/j.trb.2012.05.001
[11] Doan K, Ukkusuri SV (2015) Dynamic system optimal model for multi-OD traffic networks with an advanced spatial queuing model. Transportation Res. Part C 51:41-65.Crossref, Google Scholar · doi:10.1016/j.trc.2014.10.011
[12] Friesz TL, Bernstein D, Smith TE, Tobin RL, Wie B (1993) A variational inequality formulation of the dynamic networks user equilibrium problem. Oper. Res. 41(1):179-191.Link, Google Scholar · Zbl 0771.90037
[13] Guo RY, Yang H, Huang HJ (2018) Are we really solving the dynamic traffic equilibrium problem with a departure time choice? Transportation Sci. 52(3):603-620.Link, Google Scholar
[14] Han K, Friesz TL, Yao T (2013a) A partial differential equation formulation of Vickrey’s bottleneck model, part I: Methodology and theoretical analysis. Transportation Res. Part B 49:55-74.Crossref, Google Scholar · doi:10.1016/j.trb.2012.10.003
[15] Han K, Friesz TL, Yao T (2013b) A partial differential equation formulation of Vickrey’s bottleneck model, part II: Numerical analysis and computation. Transportation Res. Part B 49:75-93.Crossref, Google Scholar · doi:10.1016/j.trb.2012.10.004
[16] Han K, Piccoli B, Szeto WY (2016a) Continuous-time link-based kinematic wave model: Formulation, solution existence, and well-posedness. Transportmetrica B 4(3):187-222.Crossref, Google Scholar · doi:10.1080/21680566.2015.1064793
[17] Han K, Szeto WY, Friesz TL (2015a) Formulation, existence, and computation of boundedly rational dynamic user equilibrium with fixed or endogenous user tolerance. Transportation Res. Part B 79:16-49.Crossref, Google Scholar · doi:10.1016/j.trb.2015.05.002
[18] Han K, Friesz TL, Szeto WY, Liu H-C (2015b) Elastic demand dynamic network user equilibrium: Formulation, existence and computation. Transportation Res. Part B 81(Part 1):183-209.Crossref, Google Scholar · doi:10.1016/j.trb.2015.07.008
[19] Han K, Gayah V, Piccoli B, Friesz TL, Yao T (2014) On the continuum approximation of the on-and-off signal control on dynamic traffic networks. Transportation Res. Part B 61:73-97.Crossref, Google Scholar · doi:10.1016/j.trb.2014.01.001
[20] Han K, Liu H, Gayah V, Friesz TL, Yao T (2016b) A robust optimization approach for dynamic traffic signal control with emission considerations. Transportation Res. Part C 70:3-26.Crossref, Google Scholar · doi:10.1016/j.trc.2015.04.001
[21] Han S (2003) Dynamic traffic modelling and dynamic stochastic user equilibrium assignment for general road networks. Transportation Res. Part B 37(3):225-249.Crossref, Google Scholar · doi:10.1016/S0191-2615(02)00009-7
[22] Ho JK (1980) A successive linear optimization approach to the dynamic traffic assignment problem. Transportation Sci. 14(4):295-305.Link, Google Scholar
[23] Jiang Y, Szeto WY, Long JC, Han K (2016) Multi-class dynamic traffic assignment with physical queues: Intersection-movement-based formulation and paradox. Transportmetrica A 12(10):878-908.Crossref, Google Scholar · doi:10.1080/23249935.2016.1190421
[24] Jin W (2015) Point queue model: A unified approach. Transportation Res. Part B 77:1-16.Crossref, Google Scholar · doi:10.1016/j.trb.2015.02.015
[25] Lawler EL, Wood DE (1966) Branch-and-bound methods: A survey. Oper. Res. 14(4):699-719.Link, Google Scholar · Zbl 0143.42501
[26] Levin MW (2017) Congestion-aware system optimal route choice for shared autonomous vehicles. Transportation Res. Part C 82:229-247.Crossref, Google Scholar · doi:10.1016/j.trc.2017.06.020
[27] Lighthill MH, Whitham GB (1955) On kinematics wave. II. A theory of traffic flow on long crowed roads. Proc. R. Soc. London Ser. A 229(1178):317-345.Crossref, Google Scholar · Zbl 0064.20906 · doi:10.1098/rspa.1955.0089
[28] Lin WH, Wang C (2004) An enhanced 0-1 mixed-integer LP formulation for traffic signal control. IEEE Trans. Intelligent Transportation Syst. 5(4):238-245.Crossref, Google Scholar · doi:10.1109/TITS.2004.838217
[29] Liu Y, Nie Y, Hall J (2015) A semi-analytical approach for solving the bottleneck model with general user heterogeneity. Transportation Res. Part B 71:56-70.Crossref, Google Scholar · doi:10.1016/j.trb.2014.09.016
[30] Lo H (1999) A novel traffic signal control formulation. Transportation Res. Part B 33(6):433-448.Google Scholar
[31] Lo HK, Szeto WY (2002) A cell-based variational inequality formulation of the dynamic user optimal assignment problem. Transportation Res. Part B 36(5):421-443.Crossref, Google Scholar · doi:10.1016/S0191-2615(01)00011-X
[32] Long JC, Gao ZY, Szeto WY (2011) Discretised link travel time models based on cumulative flows: Formulation and properties. Transportation Res. Part B 45(1):232-254.Crossref, Google Scholar · doi:10.1016/j.trb.2010.05.002
[33] Long JC, Huang HJ, Gao ZY (2013a) Discretised route travel time models based on cumulative flows. J. Adv. Transportation 47(1):105-125.Crossref, Google Scholar · doi:10.1002/atr.1192
[34] Long JC, Chen JX, Szeto WY, Shi Q (2018) Link-based system optimum dynamic traffic assignment problems with environmental objectives. Transportation Res. Part D 60:56-75.Crossref, Google Scholar · doi:10.1016/j.trd.2016.06.003
[35] Long JC, Huang HJ, Gao ZY, Szeto WY (2013b) An intersection-movement-based dynamic user optimal route choice problem. Oper. Res. 61(5):1134-1147.Link, Google Scholar · Zbl 1291.90038
[36] Long JC, Szeto WY, Huang HJ, Gao ZY (2015a) An intersection-movement-based stochastic dynamic user optimal route choice model for assessing network performance. Transportation Res. Part B 74:182-217.Crossref, Google Scholar · doi:10.1016/j.trb.2014.12.008
[37] Long JC, Szeto WY, Gao ZY, Huang HJ, Shi Q (2016) The nonlinear equation system approach to solving dynamic user optimal simultaneous route and departure time choice problems. Transportation Res. Part B 83:179-206.Crossref, Google Scholar · doi:10.1016/j.trb.2015.11.005
[38] Long JC, Szeto WY, Shi Q, Gao ZY, Huang HJ (2015b) A nonlinear equation system approach to the dynamic stochastic user equilibrium simultaneous route and departure time choice problem. Transportmetrica A 11(5):388-419.Crossref, Google Scholar · doi:10.1080/23249935.2014.1003112
[39] Ma R, Ban XJ, Pang JS (2014) Continuous-time dynamic system optimum for single-destination traffic networks with queue spillbacks. Transportation Res. Part B 68:98-122.Crossref, Google Scholar · doi:10.1016/j.trb.2014.06.003
[40] Ma R, Ban XJ, Szeto WY (2017) Emission modeling and pricing on single-destination dynamic traffic networks. Transportation Res. Part B 100:255-283.Crossref, Google Scholar · doi:10.1016/j.trb.2017.02.007
[41] Merchant DK, Nemhauser GL (1978a) A model and an algorithm for the dynamic traffic assignment. Transportation Sci. 12(3):183-199.Link, Google Scholar
[42] Merchant DK, Nemhauser GL (1978b) Optimality conditions for a dynamic traffic assignment model. Transportation Sci. 12(3):200-207.Link, Google Scholar
[43] Mitten LG (1970) Branch-and-bound methods: General formulation and properties. Oper. Res. 18(1):24-34.Link, Google Scholar · Zbl 0225.90030
[44] Newell GF (1993) A simplified theory on kinematic wave in highway traffic, part I: General theory; part II: Queuing at freeway bottlenecks; part III: Multi-destination flows. Transportation Res. Part B 27(4):281-314.Crossref, Google Scholar · doi:10.1016/0191-2615(93)90038-C
[45] Ngoduy D, Hoang NH, Vu HL, Watling D (2016) Optimal queue placement in dynamic system optimum solutions for single origin-destination traffic networks. Transportation Res. Part B 92(Part B):148-169.Crossref, Google Scholar · doi:10.1016/j.trb.2015.11.011
[46] Nguyen S, Dupuis C (1984) An efficient method for computing traffic equilibria in networks with asymmetric transportation costs. Transportation Sci. 18(2):185-202.Link, Google Scholar
[47] Nie Y (2011) A cell-based Merchant-Nemhauser model for the system optimum dynamic traffic assignment problem. Transportation Res. Part B 45(2):329-342.Crossref, Google Scholar · doi:10.1016/j.trb.2010.07.001
[48] Pavlis Y, Recker W (2009) A mathematical logic approach for the transformation of the linear conditional piecewise functions of dispersion-and-store and cell transmission traffic flow models into linear mixed-integer form. Transportation Sci. 43(1):98-116.Link, Google Scholar
[49] Perakis G, Roels G (2006) An analytical model for traffic delays and the dynamic user equilibrium problem. Oper. Res. 54(6):1151-1171.Link, Google Scholar · Zbl 1167.90432
[50] Qian ZS, Shen W, Zhang HM (2012) System-optimal dynamic traffic assignment with and without queue spillback: Its path-based formulation and solution via approximate path marginal cost. Transportation Res. Part B 46(7):874-893.Crossref, Google Scholar · doi:10.1016/j.trb.2012.02.008
[51] Ramadurai G, Ukkusuri S (2010) Dynamic user equilibrium model for combined activity-travel choices using activity-travel supernetwork representation. Networks Spatial Econom. 10(2):273-292.Crossref, Google Scholar · Zbl 1187.90060 · doi:10.1007/s11067-008-9078-3
[52] Richards PI (1956) Shock waves on the highway. Oper. Res. 4(1):42-51.Link, Google Scholar · Zbl 1414.90094
[53] Shen W, Nie Y, Zhang H (2007) Dynamic network simplex method for designing emergency evacuation plans. Transportation Res. Rec. 2022:83-93.Crossref, Google Scholar · doi:10.3141/2022-10
[54] Szeto WY, Lo HK (2006) Dynamic traffic assignment: Properties and extensions. Transportmetrica 2(1):31-52.Crossref, Google Scholar · doi:10.1080/18128600608685654
[55] Ukkusuri SV, Waller ST (2008) Linear programming models for the user and system optimal dynamic network design problem: Formulations, implementations and comparisons. Networks Spatial Econom. 8(4):383-406.Crossref, Google Scholar · Zbl 1162.90515 · doi:10.1007/s11067-007-9019-6
[56] Ukkusuri SV, Han L, Doan K (2012) Dynamic user equilibrium with a path based cell transmission model for general traffic networks. Transportation Res. Part B 46(10):1657-1684.Crossref, Google Scholar · doi:10.1016/j.trb.2012.07.010
[57] Vickrey WS (1969) Congestion theory and transport investment. Amer. Econom. Rev. 59(2):251-260.Google Scholar
[58] Yperman I (2007) The link transmission model for dynamic network loading. PhD dissertation, Katholieke Universiteit Leuven, Leuven, Belgium.Google Scholar
[59] Zheng H, Chiu YC (2011) A network flow algorithm for the cell-based single-destination system optimal dynamic traffic assignment problem. Transportation Sci. 45(1):121-137.Link, Google Scholar
[60] Zheng H, Chiu YC, Mirchandani PB (2015) On the system optimum dynamic traffic assignment and earliest arrival flow problems. Transportation Sci. 49(1):13-27.Link, Google Scholar
[61] Zhu F, Ukkusuri SV (2013) A cell based dynamic system optimum model with non-holding back flows. Transportation Res. Part C 36:367-380.Crossref, Google Scholar · doi:10.1016/j.trc.2013.09.003
[62] Zhu F, Ukkusuri SV (2015) A linear programming formulation for autonomous intersection control within a dynamic traffic assignment and connected vehicle environment. Transportation Res. Part C 55:363-378.Crossref, Google Scholar · doi:10.1016/j.trc.2015.01.006
[63] Ziliaskopoulos AK (2000) A linear programming model for the single destination system optimum dynamic traffic assignment problem. Transportation Sci. 34(1):37-49.Link, · Zbl 1002.90013
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.