An exact second order cone programming approach for traffic assignment problems

Open Access

Issue		RAIRO-Oper. Res. Volume 58, Number 1, January-February 2024


Page(s)		847 - 864
DOI		https://doi.org/10.1051/ro/2023172
Published online		22 February 2024

K.A. Ackermann and R.O. Murphy, Explaining cooperative behavior in public goods games: how preferences and beliefs affect contribution levels. Games 10 (2019) 15. [CrossRef] [Google Scholar]
M.S. Aktürk, A. Atamtürk and S. GüRel, A strong conic quadratic reformulation for machine-job assignment with controllable processing times. Oper. Res. Lett. 37 (2009) 187–191. [CrossRef] [MathSciNet] [Google Scholar]
F. Alizadeh and D. Goldfarb, Second-order cone programming. Math. Program. 95 (2003) 3–51. [Google Scholar]
E. Angelelli, I. Arsik, V. Morandi, M. Savelsbergh and M.G. Speranza, Proactive route guidance to avoid congestion. Transp. Res. Part B: Methodol. 94 (2016) 1–21. [CrossRef] [Google Scholar]
E. Angelelli, V. Morandi and M.G. Speranza, Congestion avoiding heuristic path generation for the proactive route guidance. Comput. Oper. Res. 99 (2018) 234–248. [CrossRef] [MathSciNet] [Google Scholar]
E. Angelelli, V. Morandi and M.G. Speranza, Minimizing the total travel time with limited unfairness in traffic networks. Comput. Oper. Res. 123 (2020) 105016. [CrossRef] [MathSciNet] [Google Scholar]
E. Angelelli, V. Morandi, M. Savelsbergh and M.G. Speranza, System optimal routing of traffic flows with user constraints using linear programming. Eur. J. Oper. Res. 293 (2021) 863–879. [CrossRef] [Google Scholar]
A. Atamtürk, G. Berenguer and Z.-J. Shen, A conic integer programming approach to stochastic joint location-inventory problems. Oper. Res. 60 (2012) 366–381. [CrossRef] [MathSciNet] [Google Scholar]
C. Barnhart, E.L. Johnson, G.L. Nemhauser, M.W.P. Savelsbergh and P.H. Vance, Branch-and-price: column generation for solving huge integer programs. Oper. Res. 46 (1998) 316–329. [CrossRef] [MathSciNet] [Google Scholar]
S. Battles, Freight management operations, freight analysis framework. U.S. Department of Transportation, Federal Highway Administration, Office of Freight Management and Operations (2007). https://ops.fhwa.dot.gov/freight/freight_analysis/freight_story/congestion.htm. [Google Scholar]
V. Bayram, Optimization models for large scale network evacuation planning and management: a literature review. Surv. Oper. Res. Manage. Sci. 21 (2016) 63–84. [Google Scholar]
V. Bayram and H. Yaman, Shelter location and evacuation route assignment under uncertainty: a benders decomposition approach. Transp. Sci. 52 (2018) 416–436. [CrossRef] [Google Scholar]
V. Bayram and H. Yaman, A stochastic programming approach for shelter location and evacuation planning. RAIRO-Oper. Res. 52 (2018) 779–805. [CrossRef] [EDP Sciences] [MathSciNet] [Google Scholar]
V. Bayram, B.Ç. Tansel and H. Yaman, Compromising system and user interests in shelter location and evacuation planning. Transp. Res. Part B: Methodol. 72 (2015) 146–163. [CrossRef] [Google Scholar]
V. Bayram, B. Yıldız and M.S. Farham, Hub network design problem with capacity, congestion, and stochastic demand considerations. Transp. Sci. 47 (2023). DOI: 10.1287/trsc.2022.0112. [Google Scholar]
M. Beckmann, C.B. McGuire and C.B. Winsten, Studies in the economics of transportation. Technical report (1956). [Google Scholar]
M. Ben-Akiva, A. De Palma and K. Isam, Dynamic network models and driver information systems. Transp. Res. Part A: Gen. 25 (1991) 251–266. [CrossRef] [Google Scholar]
A. Ben-Tal and A. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS-SIAM Series on Optimization. Society for Industrial and Applied Mathematics (2001). [Google Scholar]
H.Y. Benson and Ü. Sağlam, Mixed-integer second-order cone programming: a survey, in Theory Driven by Influential Applications. INFORMS (2013) 13–36. [Google Scholar]
P. Bonami and M.A. Lejeune, An exact solution approach for portfolio optimization problems under stochastic and integer constraints. Oper. Res. 57 (2009) 650–670. [CrossRef] [MathSciNet] [Google Scholar]
R. Busch, Disrupting transportation: we need to think bigger than cars. McKinsey Global Institute, Voices (2017). https://www.mckinsey.com/industries/travel-logistics-and-infrastructure/our-insights/disrupting-transportation-we-need-to-think-bigger-than-cars. [Google Scholar]
H.C. Chen, J.W. Friedman and J.F. Thisse, Boundedly rational nash equilibrium: a probabilistic choice approach. Games Econ. Behav. 18 (1997) 32–54. [CrossRef] [Google Scholar]
G.B. Dantzig and P. Wolfe, Decomposition principle for linear programs. Oper. Res. 8 (1960) 101–111. [Google Scholar]
G. Desaulniers, M.M. Solomon and J. Desrosiers, Column Generation. Springer (2005). [CrossRef] [Google Scholar]
X. Di and H.X. Liu, Boundedly rational route choice behavior: a review of models and methodologies. Transp. Res. Part B: Methodol. 85 (2016) 142–179. [CrossRef] [Google Scholar]
M. Dror, Note on the complexity of the shortest path models for column generation in VRPTW. Oper. Res. 42 (1994) 977–978. [CrossRef] [Google Scholar]
EU, Sustainable urban mobility in the EU: no substantial improvement is possible without member states’ commitment. European Court of Auditors (2020). https://op.europa.eu/webpub/eca/special-reports/urban-mobility-6-2020/en/. [Google Scholar]
D.J. Fagnant and K. Kockelman, Preparing a nation for autonomous vehicles: opportunities, barriers and policy recommendations. Transp. Res. Part A: Policy Pract. 77 (2015) 167–181. [CrossRef] [Google Scholar]
S. Fleming, Traffic congestion cost the US economy nearly $87 billion in 2018. World Economic Forum, Future of the Environment (2019). https://www.weforum.org/agenda/2019/03/traffic-congestion-cost-the-us-economy-nearly-87-billion-in-2018/. [Google Scholar]
M. Frank and P. Wolfe, An algorithm for quadratic programming. Nav. Res. Logistics Q. 3 (1956) 95–110. [CrossRef] [Google Scholar]
C. Harrison, B. Eckman, R. Hamilton, P. Hartswick, J. Kalagnanam, J. Paraszczak and P. Williams, Foundations for smarter cities. IBM J. Res. Dev. 54 (2010) 1–16. [CrossRef] [Google Scholar]
H. Hijazi, P. Bonami and A. Ouorou, Robust delay-constrained routing in telecommunications. Ann. Oper. Res. 206 (2013) 163–181. [CrossRef] [MathSciNet] [Google Scholar]
R. Holden, Data-Driven Innovation: Big Data for Growth and Well-being. Organisation for Economic Co-operation and Development, OECD Publishing (2015). [Google Scholar]
O. Jahn, R.H. Möhring and A.S. Schulz, Optimal routing of traffic flows with length restrictions in networks with congestion, in Operations Research Proceedings 1999. Springer (2000) 437–442. [Google Scholar]
O. Jahn, R.H. Möhring, A.S. Schulz and N.E. Stier-Moses, System-optimal routing of traffic flows with user constraints in networks with congestion. Oper. Res. 53 (2005) 600–616. [CrossRef] [MathSciNet] [Google Scholar]
P. Jones, P. Anciaes, C. Buckingham, C. Cavoli, T. Cohen, L. Cristea, R. Gerike, C. Halpern and L. Pickup, Urban mobility: preparing for the future, learning from the past. European Union’s Horizon 2020 Research and Innovation Programme, grant agreement No 636573 (2018). https://nws.eurocities.eu/MediaShell/media/CREATE-ProjectSummaryReccommendations.pdf. [Google Scholar]
I. Klein, N. Levy and E. Ben-Elia, An agent-based model of the emergence of cooperation and a fair and stable system optimum using atis on a simple road network. Transp. Res. Part C: Emerg. Technol. 86 (2018) 183–201. [CrossRef] [Google Scholar]
M.S. Lobo, L. Vandenberghe, S. Boyd and H. Lebret, Applications of second-order cone programming. Linear Algebra App. 284 (1998) 193–228. [CrossRef] [Google Scholar]
Y. Lou, Y. Yin and S. Lawphongpanich, Robust congestion pricing under boundedly rational user equilibrium. Transp. Res. Part B: Methodol. 44 (2010) 15–28. [CrossRef] [Google Scholar]
L. Lozano, D. Duque and A.L. Medaglia, An exact algorithm for the elementary shortest path problem with resource constraints. Transp. Sci. 50 (2016) 348–357. [CrossRef] [Google Scholar]
H.S. Mahmassani, 50th anniversary invited article – autonomous vehicles and connected vehicle systems: flow and operations considerations. Transp. Sci. 50 (2016) 1140–1162. [CrossRef] [Google Scholar]
H.S. Mahmassani and G.L. Chang, On boundedly rational user equilibrium in transportation systems. Transp. Sci. 21 (1987) 89–99. [CrossRef] [Google Scholar]
H.S. Mahmassani and Y.H. Liu, Dynamics of commuting decision behaviour under advanced traveller information systems. Transp. Res. Part C: Emerg. Technol. 7 (1999) 91–107. [CrossRef] [Google Scholar]
R. Miyashiro and Y. Takano, Mixed integer second-order cone programming formulations for variable selection in linear regression. Eur. J. Oper. Res. 247 (2015) 721–731. [CrossRef] [Google Scholar]
V. Morandi, Bridging the user equilibrium and the system optimum in static traffic assignment: how the cooperation among drivers can solve the congestion problem in city networks. Preprint arXiv:2105.05804 (2021). [Google Scholar]
J. Paniati, Operational solutions to traffic congestion. U.S. Department of Transportation, Federal Highway Administration, Public Roads, FHWA-HRT-05-002. Vol. 68 (2004). https://highways.dot.gov/public-roads/novemberdecember-2004/operational-solutions-traffic-congestion. [Google Scholar]
PwC, Mobility insights: tackling the growing issue of congestion in urban areas. PricewaterhouseCoopers (2019). https://www.pwc.com/us/en/industrial-products/publications/assets/pwc-mobility-insights-congestion.pdf. [Google Scholar]
T. Roughgarden, How unfair is optimal routing? in Symposium on Discrete Algorithms: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete algorithms. Vol. 6 (2002) 203–204. [Google Scholar]
M. Savelsbergh and T. Van Woensel, City logistics: challenges and opportunities: 50th anniversary invited article. Transp. Sci. 50 (2016) 579–590. [CrossRef] [Google Scholar]
B. Schaller, The new automobility: Lyft, uber and the future of american cities. Schaller Consulting (2018). http://www.schallerconsult.com/rideservices/automobility.pdf. [Google Scholar]
J.L. Schofer and H.S. Mahmassani, Mobility 2050: A Vision for Transportation Infrastructure. AEM (2016). [Google Scholar]
A.S. Schulz and N.E. Stier-Moses, Efficiency and fairness of system-optimal routing with user constraints. Networks 48 (2006) 223–234. [CrossRef] [MathSciNet] [Google Scholar]
Y. Sheffi, Urban Transportation Networks: Equilibrium Analysis with Mathematical Programming Methods. Prentice-Hall, Inc., Englewood Cliffs, NJ (1985). [Google Scholar]
H.A. Simon, A behavioral model of rational choice. Q. J. Econ. 69 (1955) 99–118. [CrossRef] [Google Scholar]
V.V. Singh and A. Lisser, A second-order cone programming formulation for two player zero-sum games with chance constraints. Eur. J. Oper. Res. 275 (2019) 839–845. [CrossRef] [Google Scholar]
M.G. Speranza, Trends in transportation and logistics. Eur. J. Oper. Res. 264 (2018) 830–836. [CrossRef] [Google Scholar]
B. Stabler, H. Bar-Gera and E. Sall, Transportation networks for research. Transportation Networks for Research Core Team (2022). https://github.com/bstabler/TransportationNetworks. [Google Scholar]
W.Y. Szeto and H.K. Lo, Dynamic traffic assignment: properties and extensions. Transportmetrica 2 (2006) 31–52. [CrossRef] [Google Scholar]
W.Y. Szeto, Y. Wang and K. Han, Bounded rationality in dynamic traffic assignment, in Bounded Rational Choice Behaviour: Applications in Transport. Emerald Group Publishing Limited (2015) 163–187. [CrossRef] [Google Scholar]
TAM, Traffic Assignment Manual. Bureau of Public Roads, U.S. Department of Commerce (1964). [Google Scholar]
J.A. Taylor and F.S. Hover, Convex models of distribution system reconfiguration. IEEE Trans. Power Syst. 27 (2012) 1407–1413. [CrossRef] [Google Scholar]
UN, Analysis of the transport relevance of each of the 17 SDGs. United Nations, Department of Economic and Social Affairs, Sustainable Development (2015). https://sustainabledevelopment.un.org/content/documents/8656AnalysisoftransportrelevanceofSDGs.pdf. [Google Scholar]
UNDESA, Sustainable development goals. United Nations Department of Economic and Social Affairs (2015). https://sdgs.un.org/goals. [Google Scholar]
M. Van Essen, T. Thomas, E. van Berkum and C. Chorus, From user equilibrium to system optimum: a literature review on the role of travel information, bounded rationality and non-selfish behaviour at the network and individual levels. Transp. Rev. 36 (2016) 527–548. [CrossRef] [Google Scholar]
H. Van Essen, L. Van Wijngaarden, A. Schroten, D. Sutter, C. Bieler, S. Maffii, M. Brambilla, D. Fiorello, R. Parolin and K. El Beyrouty, Handbook on the external costs of transport. European Commission, Directorate-General for Mobility and Transport (2020). https://data.europa.eu/doi/10.2832/51388. [Google Scholar]
J.G. Wardrop, Road paper. some theoretical aspects of road traffic research. Proc. Inst. Civil Eng. 1 (1952) 325–362. [Google Scholar]
WHO, 7 million premature deaths annually linked to air pollution. World Health Organization (2014). https://www.who.int/news/item/25-03-2014-7-million-premature-deaths-annually-linked-to-air-pollution. [Google Scholar]
Wikipedia, Traffic congestion (2022). https://en.wikipedia.org/wiki/Traffic_congestion#cite_note-108. [Google Scholar]
J. Woetzel, J. Remes, B. Boland, K. Lv, S. Sinha, G. Strube, J. Means, J. Law, A. Cadena and V. Von der Tann, Smart cities: digital solutions for a more livable future. McKinsey Global Institute (2018). https://www.mckinsey.com/business-functions/operations/our-insights/smart-cities-digital-solutions-for-a-more-livable-future. [Google Scholar]
H. Ye and H. Yang, Rational behavior adjustment process with boundedly rational user equilibrium. Transp. Sci. 51 (2017) 968–980. [CrossRef] [Google Scholar]
G. Zhang and X. Liu, UAV collision avoidance using mixed-integer second-order cone programming. J. Guidance Control Dyn. 45 (2022) 1732–1738. [CrossRef] [Google Scholar]
H. Zhang, S.J. Moura, Z. Hu, W. Qi and Y. Song, A second-order cone programming model for planning pev fast-charging stations. IEEE Trans. Power Syst. 33 (2017) 2763–2777. [Google Scholar]
L. Zhenlong and Z. Xiaohua, Integrated-equilibrium routing of traffic flows with congestion. IFAC Proc. Vol. 17 (2008) 16065–16070. [CrossRef] [Google Scholar]
B. Zhou and X. Li, User equilibrium with length constrained users, in 2012 Fifth International Joint Conference on Computational Sciences and Optimization (CSO). IEEE (2012) 494–499. [Google Scholar]

Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.

Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.

Initial download of the metrics may take a while.