×

System optimal routing of traffic flows with user constraints using linear programming. (English) Zbl 1487.90210

Summary: For static traffic assignment problems, it is well known that (1) for some users the experienced travel time in a system optimum assignment can be substantially higher than the experienced travel time in a user equilibrium assignment, and (2) the total travel time in user equilibrium can be substantially higher than the total travel time in system optimum. By seeking system optimal traffic flows subject to user constraints, a compromise assignment can be obtained that balances system and user objectives. To this aim, a linear model and an efficient heuristic algorithm are proposed in this paper. A computational study shows that the proposed model, along with the heuristic algorithm, is able to provide fair solutions with near-optimal total travel time within very short computational time.

MSC:

90B20 Traffic problems in operations research
90B10 Deterministic network models in operations research
91A80 Applications of game theory

Software:

GitHub
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Angelelli, E.; Arsik, I.; Morandi, V.; Savelsbergh, M.; Speranza, M. G., Proactive route guidance to avoid congestion, Transportation Research Part B: Methodological, 94, 1-21 (2016)
[2] Angelelli, E.; Morandi, V.; Speranza, M., Congestion avoiding heuristic path generation for the proactive route guidance, Computers and Operations Research, 99, 234-248 (2018) · Zbl 1458.90600
[3] Angelelli, E.; Morandi, V.; Speranza, M., A trade-off between average and maximum arc congestion minimization in traffic assignment with user constraints, Computers and Operations Research, 110, 88-100 (2019) · Zbl 1458.90197
[4] Angelelli, E.; Morandi, V.; Speranza, M., Minimizing the total travel time with limited unfairness in traffic networks, Computers & Operations Research, 123 (2020) · Zbl 1458.90198
[5] Beckmann, M.; McGuire, C.; Winsten, C. B., Studies in the Economics of Transportation, Technical Report (1956), RAND Corporation
[6] Ben-Akiva, M. E.; Gao, S.; Wei, Z.; Wen, Y., A dynamic traffic assignment model for highly congested urban networks, Transportation Research Part C: Emerging Technologies, 24, 62-82 (2012)
[7] Ben-Akiva, M. E.; Lerman, S. R., Discrete choice analysis: Theory and application to travel demand (1985), MIT press
[8] Boyce, D.; Ralevic-Dekic, B.; Bar-Gera, H., Convergence of traffic assignments: How much is enough?, Journal of Transportation Engineering, 130, 49-55 (2004)
[9] Chen, A.; Jayakrishnan, R.; Tsai, W. K., Faster frank-wolfe traffic assignment with new flow update scheme, Journal of Transportation Engineering, 128, 31-39 (2002)
[10] Cominetti, R.; Correa, J. R.; Stier-Moses, N. E., The impact of oligopolistic competition in networks, Operations Research, 57, 1421-1437 (2009) · Zbl 1233.90064
[11] Correa, J. R.; Schulz, A. S.; Stier-Moses, N. E., Fast, fair, and efficient flows in networks, Operations Research, 55, 215-225 (2007) · Zbl 1167.90391
[12] de Dios Ortuzar, J.; Willumsen, L. G., Modelling transport (2011), John Wiley & Sons
[13] Fagnant, D. J.; Kockelman, K., Preparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations, Transportation Research Part A: Policy and Practice, 77, 167-181 (2015)
[14] Florian, M.; Hearn, D., Network equilibrium and pricing, Handbook of transportation science, 361-393 (1999), Springer
[15] Geißler, B.; Martin, A.; Morsi, A.; Schewe, L., Using piecewise linear functions for solving MINLPs, Mixed integer nonlinear programming, 287-314 (2012), Springer · Zbl 1242.90132
[16] Irnich, S.; Desaulniers, G., Shortest path problems with resource constraints, Column generation, 33-65 (2005), Springer · Zbl 1130.90315
[17] Jahn, O.; Möhring, R. H.; Schulz, A. S., Optimal routing of traffic flows with length restrictions in networks with congestion, Operations research proceedings 1999, 437-442 (2000), Springer · Zbl 1015.90023
[18] Jahn, O.; Möhring, R. H.; Schulz, A. S.; Stier-Moses, N. E., System-optimal routing of traffic flows with user constraints in networks with congestion, Operations Research, 53, 600-616 (2005) · Zbl 1165.90499
[19] Karakostas, G.; Kolliopoulos, S. G., Stackelberg strategies for selfish routing in general multicommodity networks, Algorithmica, 53, 132-153 (2009) · Zbl 1175.90067
[20] Krichene, W.; Reilly, J. D.; Amin, S.; Bayen, A. M., Stackelberg routing on parallel networks with horizontal queues, IEEE Transactions on Automatic Control, 59, 714-727 (2014) · Zbl 1360.91047
[21] Lee, J.; Leyffer, S., Mixed integer nonlinear programming, 154 (2011), Springer Science & Business Media
[22] Lohmann, T.; Rebennack, S., Tailored benders decomposition for a long-term power expansion model with short-term demand response, Management Science, 63, 2027-2048 (2016)
[23] Lujak, M.; Giordani, S.; Ossowski, S., Route guidance: Bridging system and user optimization in traffic assignment, Neurocomputing, 151, 449-460 (2015)
[24] Mahmassani, H. S.; Peeta, S., Network performance under system optimal and user equilibrium dynamic assignments: Implications for advanced traveler information systems, Transportation Research Record (1993)
[25] Mahmassani, H. S.; Peeta, S., System optimal dynamic assignment for electronic route guidance in a congested traffic network, Urban traffic networks: dynamic flow modeling and control (1995) · Zbl 0839.90035
[26] Merchant, D. K.; Nemhauser, G. L., A model and an algorithm for the dynamic traffic assignment problems, Transportation Science, 12, 183-199 (1978)
[27] Nisan, N.; Roughgarden, T.; Tardos, E.; Vazirani, V. V., Algorithmic game theory (2007), Cambridge university press · Zbl 1130.91005
[28] Papageorgiou, M., Dynamic modeling, assignment, and route guidance in traffic networks, Transportation Research Part B: Methodological, 24, 471-495 (1990)
[29] Patriksson, M., The traffic assignment problem: Models and methods (2015), Courier Dover Publications
[30] Peeta, S.; Ziliaskopoulos, A. K., Foundations of dynamic traffic assignment: The past, the present and the future, Networks and Spatial Economics, 1, 233-265 (2001)
[31] Roughgarden, T., Stackelberg scheduling strategies, SIAM Journal on Computing, 33, 332-350 (2004) · Zbl 1080.90046
[32] Schulz, A. S.; Stier-Moses, N. E., Efficiency and fairness of system-optimal routing with user constraints, Networks, 48, 223-234 (2006) · Zbl 1148.90307
[33] Sheffi, Y., Urban transportation network, Equilibrium analysis with mathematical programming methods (1985), Prentice Hall
[34] Stabler, B. (2018). Transportation networks for research github repository. https://github.com/bstabler/TransportationNetworks.git.
[35] Swamy, C., The effectiveness of stackelberg strategies and tolls for network congestion games, ACM Transactions on Algorithms, 8, 36:1-36:19 (2012) · Zbl 1295.91021
[36] Wardrop, J. G., Road paper. some theoretical aspects of road traffic research., Proceedings of the Institution of Civil Engineers, 1, 325-362 (1952)
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.