Ifsttar PhD subject

French version
Detailed form :

Title : Bilevel Optimization for Transport Network Resilience and Recovery

Main host Laboratory - Referent Advisor COSYS - LICIT  -  EL FAOUZI Nour-Eddin      tél. : +33 472142543

Director of the main host Laboratory LECLERCQ Ludovic  -

PhD Speciality mathématiques appliquées, Recherche opérationnelle, optimisation, ingénierie du trafic

Axis of the performance contract 2 - COP2017 - More efficient and resilient infrastructure

Main location Bron

Doctoral affiliation ENTPE

PhD school MEGA (MECANIQUE, ENERGETIQUE, GENIE CIVIL, ACOUSTIQUE)

Planned PhD supervisor EL FAOUZI Nour-Eddin  -  Université Gustave Eiffel  -  COSYS - LICIT-ECO7

Planned financing Contrat doctoral  - Ifsttar

Abstract

Transport networks are designed to provide mobility solutions for populations and are at the heart of metropolitan areas. They are vital for societies and their performance is thus of primordial importance to the economy. Yet transport networks in major cities are frequently congested and may not provide the expected level of service to their communities. The forecasted growth of worldwide population poses a natural threat to the welfare of transport networks. With more travel demand, more congestion can be expected along with substantial economic consequences for society. To accommodate for existing and future travel demand, transport networks need to adapt and evolve alongside societies. Further, the resilience of transport networks to natural disasters and malicious threats is critical to ensure the well-being of populations and the economy. Scheduling network maintenance projects and protecting vulnerable assets of the transport infrastructure require integrated models that are able to capture the reaction of populations to changing designs. Further, given the typically long-term, cost-intensive, strategic planning decisions at stake, the optimization of network design is critical to ensure that a maximal impact on network performance and social welfare will be achieved. Modelling the impact of design actions in transport networks can be viewed as a Stackelberg competition (Von Stackelberg, 1934), wherein a leader player seeks to make the best decision while anticipating the reaction of a follower player. This bilevel optimization framework has a natural interpretation in network design, wherein the leader player represents the transport authority and the follower player represents the collective choice of travelers under a Nash equilibrium (Wardrop, 1952). The optimal, i.e. exact, solution of this network design problem is non-trivial as bilevel optimization problems are known to be intractable, even in the simplest, linear case (Rey et. al., 2019). Yet, optimal network design is critical for enhancing network resilience and recovery, and fundamentally novel conceptual methodologies are required to advance the capability of solution algorithms and inform on sustainable planning policies.
The goal of this PhD project is to conceive, implement and validate new methodologies to model and to solve challenging decision problems encountered in transport network design and resilience. Network design and resilience plays a central role in the welfare of transport systems which are the backbone of modern and future cities. The outcomes of this project are expected to support the development and control of sustainable design policies for transport networks, and to address fundamental societal and economical challenges induced by congestion and security. Specifically, this project aims to introduce innovative and efficient formulations for Stackelberg games in transport networks and develop new mathematical algorithms for network design problems under traffic equilibrium to optimize the resilience and the recovery capacity of urban transport networks.

The network design problem (NDP) was introduced in the field of transportation in the 1970s. The NDP builds on the traffic assignment problem (TAP) which addresses the problem of assigning travel demand to a transport network under the condition that users behave selfishly, i.e. seek to minimize their travel time, also known as a Wardropian equilibrium (Wardrop, 1952). The TAP can be formulated as a convex optimization which has a unique solution in terms of link flows. The TAP has fundamental applications in urban design and transport planning for it provides an estimate of network congestion and can be used to measure network performance. Governmental transport authorities and city planners worldwide use traffic assignment to model network congestion and for strategic decision-making. In particular, traffic assignment is used for forecasting network performance under hypothetical network improvement scenarios. Yet, optimizing network performance under user equilibrium remains a very challenging decision problem. To date, proposed exact bilevel optimization solution methods can only solve small-scale NDPs (Rey, 2019).

Bilevel optimization has been used to assess the vulnerability and the resilience of networks to natural disaster or malicious threats in the long-term. The seminal work of Bell (2000) proposed a game-theoretic approach to measure the performance reliability of transport networks. A max-min formulation is used to model the impact of an evil entity aiming to maximize travel cost by failing one link in the network. This approach is extended by Bell et. al. (2008) which proposed an algorithm that obviates the enumeration of paths in the network. Brown et. al. (2006) proposed multi-level optimization formulation to identify the optimal defense strategy in attacker-defender (AD) and defender-attacker-defender (DAD) network security games. The latter formulation takes the form of a min-max-min problem wherein all optimization levels share the same objective function. Alderson et. al. (2015) discussed infrastructure resilience from the perspective of operator models, which represent the function of the infrastructure. In the context of the transportation, the operator model can be viewed as a TAP. This approach is adopted by Bhavathrathan and Patil (2015) which examined a min-max formulation wherein the attacker seeks to maximize network delay by influencing link capacities. Despite these increasing efforts to model and solve attacker-defender games, most proposed approaches adopt min-max or min-max-min formulations wherein the objective function and constraints are shared by all players. However, such min-max formulations may not be sufficient to model security games wherein user-equilibrium conditions prevail. In addition, authors have stressed theoretical and computational challenges inhered to multi-level optimization problems with inner level involving integer decision variables. Hence, there is an urgent need to advance the knowledge in this field by designing innovative models and solution algorithms to tackle large-scale attacker-defender games on transport networks.

References:
Alderson, D.L., Brown, G.G. and Carlyle, W.M., 2015. Operational models of infrastructure resilience. Risk Analysis, 35(4), pp.562-586.
Bell, M.G., 2000. A game theory approach to measuring the performance reliability of transport networks. Transportation Research Part B: Methodological, 34(6), pp.533-545.
Bell, M.G., Kanturska, U., Schmöcker, J.D. and Fonzone, A., 2008. Attacker–defender models and road network vulnerability. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366(1872), pp.1893-1906.
Bhavathrathan, B.K. and Patil, G.R., 2015. Capacity uncertainty on urban road networks: A critical state and its applicability in resilience quantification. Computers, Environment and Urban Systems, 54, pp.108-118.
Brown, G., Carlyle, M., Salmerón, J. and Wood, K., 2006. Defending critical infrastructure. Interfaces, 36(6), pp.530-544.
Rey, D., Bar-Gera, H., Dixit, V. V., & Waller, S. T. (2019). A Branch-and-Price Algorithm for the Bilevel Network Maintenance Scheduling Problem. Transportation Science, 53(5), 1455–1478.
Rey, D., & Bar-Gera, H. (2019). Long-term Scheduling for Road Network Disaster Recovery. International Journal of Disaster Risk Reduction.
Rey, D. (2019). Computational benchmarking of the discrete bilevel network design problem. EURO Working Group on Transportation (EWGT), Barcelona, Spain.
Von Stackelberg, H., 2010. Market structure and equilibrium. Springer Science & Business Media.
Wardrop, J.G., 1952. Some theoretical aspects of road traffic research. In Inst Civil Engineers Proc London, UK.

Keywords : Network resilience, infrastructure vulnerability, transport infrastructure optimization, Stackelberg competition, bilevel optimisation

Main host Laboratory - Referent Advisor	COSYS - LICIT - EL FAOUZI Nour-Eddin tél. : +33 472142543
Director of the main host Laboratory	LECLERCQ Ludovic -
PhD Speciality	mathématiques appliquées, Recherche opérationnelle, optimisation, ingénierie du trafic
Axis of the performance contract	2 - COP2017 - More efficient and resilient infrastructure
Main location	Bron
Doctoral affiliation	ENTPE
PhD school	MEGA (MECANIQUE, ENERGETIQUE, GENIE CIVIL, ACOUSTIQUE)
Planned PhD supervisor	EL FAOUZI Nour-Eddin - Université Gustave Eiffel - COSYS - LICIT-ECO7
Planned financing	Contrat doctoral - Ifsttar
Abstract Transport networks are designed to provide mobility solutions for populations and are at the heart of metropolitan areas. They are vital for societies and their performance is thus of primordial importance to the economy. Yet transport networks in major cities are frequently congested and may not provide the expected level of service to their communities. The forecasted growth of worldwide population poses a natural threat to the welfare of transport networks. With more travel demand, more congestion can be expected along with substantial economic consequences for society. To accommodate for existing and future travel demand, transport networks need to adapt and evolve alongside societies. Further, the resilience of transport networks to natural disasters and malicious threats is critical to ensure the well-being of populations and the economy. Scheduling network maintenance projects and protecting vulnerable assets of the transport infrastructure require integrated models that are able to capture the reaction of populations to changing designs. Further, given the typically long-term, cost-intensive, strategic planning decisions at stake, the optimization of network design is critical to ensure that a maximal impact on network performance and social welfare will be achieved. Modelling the impact of design actions in transport networks can be viewed as a Stackelberg competition (Von Stackelberg, 1934), wherein a leader player seeks to make the best decision while anticipating the reaction of a follower player. This bilevel optimization framework has a natural interpretation in network design, wherein the leader player represents the transport authority and the follower player represents the collective choice of travelers under a Nash equilibrium (Wardrop, 1952). The optimal, i.e. exact, solution of this network design problem is non-trivial as bilevel optimization problems are known to be intractable, even in the simplest, linear case (Rey et. al., 2019). Yet, optimal network design is critical for enhancing network resilience and recovery, and fundamentally novel conceptual methodologies are required to advance the capability of solution algorithms and inform on sustainable planning policies. The goal of this PhD project is to conceive, implement and validate new methodologies to model and to solve challenging decision problems encountered in transport network design and resilience. Network design and resilience plays a central role in the welfare of transport systems which are the backbone of modern and future cities. The outcomes of this project are expected to support the development and control of sustainable design policies for transport networks, and to address fundamental societal and economical challenges induced by congestion and security. Specifically, this project aims to introduce innovative and efficient formulations for Stackelberg games in transport networks and develop new mathematical algorithms for network design problems under traffic equilibrium to optimize the resilience and the recovery capacity of urban transport networks. The network design problem (NDP) was introduced in the field of transportation in the 1970s. The NDP builds on the traffic assignment problem (TAP) which addresses the problem of assigning travel demand to a transport network under the condition that users behave selfishly, i.e. seek to minimize their travel time, also known as a Wardropian equilibrium (Wardrop, 1952). The TAP can be formulated as a convex optimization which has a unique solution in terms of link flows. The TAP has fundamental applications in urban design and transport planning for it provides an estimate of network congestion and can be used to measure network performance. Governmental transport authorities and city planners worldwide use traffic assignment to model network congestion and for strategic decision-making. In particular, traffic assignment is used for forecasting network performance under hypothetical network improvement scenarios. Yet, optimizing network performance under user equilibrium remains a very challenging decision problem. To date, proposed exact bilevel optimization solution methods can only solve small-scale NDPs (Rey, 2019). Bilevel optimization has been used to assess the vulnerability and the resilience of networks to natural disaster or malicious threats in the long-term. The seminal work of Bell (2000) proposed a game-theoretic approach to measure the performance reliability of transport networks. A max-min formulation is used to model the impact of an evil entity aiming to maximize travel cost by failing one link in the network. This approach is extended by Bell et. al. (2008) which proposed an algorithm that obviates the enumeration of paths in the network. Brown et. al. (2006) proposed multi-level optimization formulation to identify the optimal defense strategy in attacker-defender (AD) and defender-attacker-defender (DAD) network security games. The latter formulation takes the form of a min-max-min problem wherein all optimization levels share the same objective function. Alderson et. al. (2015) discussed infrastructure resilience from the perspective of operator models, which represent the function of the infrastructure. In the context of the transportation, the operator model can be viewed as a TAP. This approach is adopted by Bhavathrathan and Patil (2015) which examined a min-max formulation wherein the attacker seeks to maximize network delay by influencing link capacities. Despite these increasing efforts to model and solve attacker-defender games, most proposed approaches adopt min-max or min-max-min formulations wherein the objective function and constraints are shared by all players. However, such min-max formulations may not be sufficient to model security games wherein user-equilibrium conditions prevail. In addition, authors have stressed theoretical and computational challenges inhered to multi-level optimization problems with inner level involving integer decision variables. Hence, there is an urgent need to advance the knowledge in this field by designing innovative models and solution algorithms to tackle large-scale attacker-defender games on transport networks. References: Alderson, D.L., Brown, G.G. and Carlyle, W.M., 2015. Operational models of infrastructure resilience. Risk Analysis, 35(4), pp.562-586. Bell, M.G., 2000. A game theory approach to measuring the performance reliability of transport networks. Transportation Research Part B: Methodological, 34(6), pp.533-545. Bell, M.G., Kanturska, U., Schmöcker, J.D. and Fonzone, A., 2008. Attacker–defender models and road network vulnerability. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366(1872), pp.1893-1906. Bhavathrathan, B.K. and Patil, G.R., 2015. Capacity uncertainty on urban road networks: A critical state and its applicability in resilience quantification. Computers, Environment and Urban Systems, 54, pp.108-118. Brown, G., Carlyle, M., Salmerón, J. and Wood, K., 2006. Defending critical infrastructure. Interfaces, 36(6), pp.530-544. Rey, D., Bar-Gera, H., Dixit, V. V., & Waller, S. T. (2019). A Branch-and-Price Algorithm for the Bilevel Network Maintenance Scheduling Problem. Transportation Science, 53(5), 1455–1478. Rey, D., & Bar-Gera, H. (2019). Long-term Scheduling for Road Network Disaster Recovery. International Journal of Disaster Risk Reduction. Rey, D. (2019). Computational benchmarking of the discrete bilevel network design problem. EURO Working Group on Transportation (EWGT), Barcelona, Spain. Von Stackelberg, H., 2010. Market structure and equilibrium. Springer Science & Business Media. Wardrop, J.G., 1952. Some theoretical aspects of road traffic research. In Inst Civil Engineers Proc London, UK.
Keywords :	Network resilience, infrastructure vulnerability, transport infrastructure optimization, Stackelberg competition, bilevel optimisation

List of topics

Applications closed