Abstract
This is a summary of the dissertation of the author (Fontaine, Methodological Advances and New Formulations for Bilevel Network Design Problems, 2016) [12]. We propose a Benders decomposition algorithm to solve discrete-continuous bilevel problems to optimality. Using the underlying problem structure, the convergence is further improved by using the multi-cut version or pareto-optimal cuts. Numerical studies on existing problems from the literature (the Discrete Network Design Problem, the Decentralized Facility Selection Problem and the Hazmat Transport Network Design Problem) show run time improvements of more than 90% compared to the mixed-integer linear program.Moreover, the Discrete Network Design Problem is extended to a multi-period model for traffic network maintenance planning. We further introduce a population-based risk definition and extend the Hazmat Transport Network Design Problem to a multi-mode model to fairly distribute risk among the population.The numerical results show a better distribution of risk compared to classical models in the literature and a convex relation between risk equilibration and minimization.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Bard, J., & Moore, J. (1990). A branch and bound algorithm for the bilevel programming problem. SIAM Journal on Scientific and Statistical Computing, 11(2), 281–292.
Bianco, L., Caramia, M., & Giordani, S. (2009). A bilevel flow model for hazmat transportation network design. Transportation Research Part C: Emerging Technologies, 17(2), 175–196.
Bianco, L., Caramia, M., Giordani, S., & Piccialli, V. (2015). A game-theoretic approach for regulating hazmat transportation. Transportation Science.
Bundesministerium für Verkehr und digitale Infrastruktur (BMVI) (2014). Verkehrsverflechtungsprognose 2030.
Bundesministerium für Verkehr und digitale Infrastruktur (BMVI) (2016). Bundesverkehrswegeplan 2030.
Erkut, E., Tjandra, S. A., & Verter, V. (2007). Chapter 9 hazardous materials transportation. In C. Barnhart & G. Laporte (Eds.), Transportation (Vol. 14), Handbooks in Operations Research and Management Science. Elsevier.
Fontaine, P., Crainic, T. G., Minner, S., & Gendreau, M. (2016). Population-based risk equilibration for the multi-mode hazmat transport network design problem. Technical report CIRRELT-2016-63.
Fontaine, P., & Minner, S. (2014). Benders decomposition for discrete-continuous linear bilevel problems with application to traffic network design. Transportation Research Part B: Methodological, 70, 163–172.
Fontaine, P., & Minner, S. (2016). Benders decomposition for the decentralized facility selection problem. Working paper.
Fontaine, P., & Minner, S. (2016). Benders decomposition for the hazmat transport network design problem. Working paper.
Fontaine, P., & Minner, S. (2017). A dynamic discrete network design problem for maintenance planning in traffic networks. Annals of Operations Research, 253(2), 757–772.
Fontaine, P. S. R. (2016). Methodological Advances and New Formulations for Bilevel Network Design Problems. Ph.D. thesis, Dissertation, München, Technische Universität München.
Hansen, P., Jaumard, B., & Savard, G. (1992). New branch-and-bound rules for linear bilevel programming. SIAM Journal on Scientific and Statistical Computing, 13(5), 1194–1217.
Kara, B. Y., & Verter, V. (2004). Designing a road network for hazardous materials transportation. Transportation Science, 38(2), 188–196.
LeBlanc, L. J. (1975). An algorithm for the discrete network design problem. Transportation Science, 9(3), 183–199.
Schmidt, P. T., & Karowski, S. (2016). Hier droht Stau! Der Bauplan für 2016. http://www.merkur.de/lokales/muenchen/stadt-muenchen/muenchen-bauplan-moegliche-stauquellen-jahr-2016-meta-6021787.html.
Schneeweiß, C. (2003). Distributed Decision Making (2\(^{{\rm nd}}\) ed.). Berlin: Springer.
Statistisches Bundesamt Wiesbaden. (2015). Verkehr: Gefahrguttransporte 2013. Fachserie 8 Reihe 1.4.
Völklein, M. (2015). Baustellen in München. http://www.sueddeutsche.de/muenchen/baustellen-in-muenchen-hier-stehen-sie-im-stau-1.2287759.
Acknowledgements
While working on this thesis, the author was doctoral student in the School of Management at the Technical University of Munich. The author also gratefully acknowledges a fellowship of Deutscher Akademischer Austauschdienst (DAAD), which helped to start the work of the last project.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Fontaine, P. (2018). Methodological Advances and New Formulations for Bilevel Network Design Problems. In: Kliewer, N., Ehmke, J., Borndörfer, R. (eds) Operations Research Proceedings 2017. Operations Research Proceedings. Springer, Cham. https://doi.org/10.1007/978-3-319-89920-6_5
Download citation
DOI: https://doi.org/10.1007/978-3-319-89920-6_5
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-89919-0
Online ISBN: 978-3-319-89920-6
eBook Packages: Business and ManagementBusiness and Management (R0)