A self-regulating pairwise swapping algorithm to search reliability-based user equilibrium

Abstract

The violation of monotonicity on reliability measures (RMs) usually makes the mathematical programming algorithms less efficient in solving the reliability-based user equilibrium (RUE) problem. The swapping algorithms provide a simple and convenient alternative to search traffic equilibrium since they are derivative-free and require weaker monotonicity. However, the existing swapping algorithms are usually based on linear swapping processes which cannot naturally avoid overswapping, and the step-size parameter update methods do not take the swapping feature into account. In this paper, we suggest a self-regulating pairwise swapping algorithm (SRPSA) to search RUE. SRPSA comprises an RM-based pairwise swapping process (RMPSP), a parameter self-diminishing operator and a termination criterion. SRPSA does not need to check the feasibility of either solutions or step-size parameter. It is suggested from the numerical analyses that SRPSA is effective and can swap to the quasi-RUE very fast. Therefore, SRPSA offers a good approach to generate initial points for those superior local search algorithms.

Keywords

travel time reliability / reliability-based user equilibrium / day-to-day dynamics / route swapping

References

[1] NieYu. Multi-class percentile user equilibrium with flow-dependent stochasticity [J]. Transportation Research Part B, 2011, 45(10): 1641-1659

[2] LoH K, TungY K. Network with degradable links: capacity analysis and design [J]. Transportation Research Part B, 2003, 37(4): 345-363

[3] ChenA, ZhouZ. The alpha-reliable mean-excess traffic equilibrium model with stochastic travel times [J]. Transportation Research Part B, 2010, 44(4): 493-513

[4] ZhangW-y, GuanW, SongL-y, SunH-jun. Alpha-reliable combined mean traffic equilibrium model with stochastic travel times [J]. Journal of Central South University, 2013, 20(12): 3770-3778

[5] BernsteinD, GabrielS APardalosP M, HearnD W, HagerW W. Solving the nonadditive traffic equilibrium problem [M]. Network Optimization, 1997, New York, Springer: 72102

[6] GabrielS A, BernsteinD. The traffic equilibrium problem with nonadditive path costs [J]. Transportation Science, 1997, 31(4): 337-348

[7] HanD-ren. A modified alternating direction method for variational inequality problems [J]. Applied Mathematics and Optimization, 2002, 45(1): 63-74

[8] XiuN-h, ZhangJ-zhong. Some recent advances in projection-type methods for variational inequalities [J]. Journal of Computational and Applied Mathematics, 2003, 152(1): 559-585

[9] ChenA, ZhouZ, XuX D. A self-adaptive gradient projection algorithm for the nonadditive traffic equilibrium problem [J]. Computers and Operations Research, 2012, 39(2): 127-138

[10] MounceR. Convergence in a continuous dynamic queuing model for traffic networks [J]. Transportation Research Part B, 2006, 40(9): 779-791

[11] HuangH-j, LamW H K. Modeling and solving the dynamic user equilibrium route and departure time choice problem in network with queues [J]. Transportation Research B, 2002, 36(3): 253-273

[12] NieX-jianThe study of dynamic user-equilibrium traffic assignment [D], 2003, Davis, University of California

[13] HanS-jin. A route-based solution algorithm for dynamic user equilibrium assignments [J]. Transportation Research Part B, 2007, 41(10): 1094-1113

[14] ChenB-y, LamW H K, SumaleeA, ShaoHu. An efficient solution algorithm for solving multi-class reliability-based traffic assignment problem [J]. Mathematical and Computer Modelling, 2011, 54: 1428-1439

[15] MounceR, CareyM. On the convergence of the MSA for calculating equilibrium in traffic networks [J]. Transportation Science, 2015, 49(3): 535-542

[16] MounceR, CareyM. Route swapping in dynamic traffic networks [J]. Transportation Research B, 2011, 45(1): 102-111

[17] SmithM J. The stability of a dynamic model of traffic assignment–An application of a method of Lyapunov [J]. Transportation Science, 1984, 18(3): 259-304

[18] SheffiYUrban transportation networks: Equilibrium analysis with mathematical programming methods [M], 1985, Englewood Cliffs, Prentice-Hall

[19] CareyM, GeY-en. Comparison of methods for path flow reassignment for dynamic user equilibrium [J]. Networks and Spatial Economics, 2012, 12(3): 337-376

[20] RasmussenT K, WatlingD P, PratoC G, NielsenO A. Stochastic user equilibrium with equilibrated choice sets: Part II–Solving the restricted SUE for the logit family [J]. Transportation Research Part B, 2015, 77: 146-165

[21] ZhangW-y, GuanW, MaJ-h, TianJ-fang. A nonlinear pairwise swapping dynamics to model the selfish rerouting evolutionary game [J]. Networks and Spatial Economics, 2015, 15(4): 1075-1092

[22] FosgerauM, KarlstromA. The value of reliability [J]. Transportation Research Part B, 2010, 44(1): 38-49

[23] PatrikssonMThe traffic assignment problem: Models and methods [M], 1994, Utrecht, VSP

[24] NagurneyANetwork economics: A variational inequality approach [M], 1993, Dordrecht, Kluwer Academic Publishers: 1415

[25] PangX-f, GaoL, PanQ-k, TianW-h, YuS-ping. A novel Lagrangian relaxation level approach for scheduling steelmaking-refining-continuous casting production [J]. Journal of Central South University, 2017, 24(2): 467-477

[26] HanJ-y, XiuN-h, QiH-duoNonlinear complementarity theory and algorithms [M], 2006, Shanghai, Shanghai Scientific & Technical Publishers: 132141