Methodological Advances and New Formulations for Bilevel Network Design Problems

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.