The Robust Urban Transportation Network Design Problem

Table of Contents

INTRODUCTION
Contributions
Structure of the Manuscript

LITERATURE REVIEW
Introduction
Modeling Traffic Flow
Network Design Problem
Bi-level and Multilevel Optimization
Performance measures
Reliability
Resiliency
Vulnerability
Robust network design
Summary and Future Research Needs

METHODOLOGY
Introduction
Game theory
Players
Users
Adversary
Designer

Frameworks for vulnerability/robustness
3.4.1 Hierarchy of Decision Flows
3.4.2 Multi-period plan for NDP
3.4.3 Model 1 : Bi-objective Designer Model
3.4.4 Model 2: A Zero-Sum Model

SOLUTION METHODOLOGIES
4.1 Introduction
4.2 Algorithm for U sers
4.3 Algorithm for Designer and Adversary
4.4 Decoding and Chromosomal Representation
4.5 Genetic Algorithm Operations
4.5.1 Example Network 1 - Braess Network
4.5.2 Example Network 2-16 links network
4.5.3 Decoding/Encoding Genotype-Phenotype Space
4.5.4 Elitism
4.5.5 Crossover Operators
4.5.6 Mutation Operator
4.5.7 Sensitivity Analysis of Demand on Test Network 1 and

NUMERICAL EXPERIMENTS
5.1 Model 1 : Bi-objective Designer Model
5.2 Model 2: Zero-Sum Game Model

CONCLUSIONS AND FUTURE RESEARCH

Acknowledgements

I would like to take this opportunity to express my gratitude to all those who helped me during the various stages of my life to understand the potential of scientific thinking and conducting advanced research.

First and foremost, I would like to thank my advisors, Dr. Mihalis M. Golias (the University of Memphis) and Dr. Sabya Mishra (the University of Memphis), for their wonderful knowledge, guidance, patience and support throughout this research. I have benefited greatly from their advice on many research and projects over the years.

I am grateful to the members of my dissertation advisory committee: Dr. Mihalis M. Golias (committee chair), Dr. Sabya Mishra (committee member), Dr. Charles Camp (committee member), Dr. Kyriacos Mouskos (committee member), Dr. Dineer Konur (committee member), and Dr. Bryan Higgs. Their comments and advice were very helpful for improving the quality of this dissertation.

Last but not the least, I reserve my deepest gratitude for my family, who always believed in me and stood by me through all times.

Abstract

Năimi, Alireza. The University of Memphis. May 2016. The Robust Urban Transportation Network Design Problem (UTNDP). Major Professor: Dr. Mihalis M. Golias.

In today’s congested transportation networks, disruptions like crashes may cause unexpected and significant delays. All transportation networks are vulnerable to disruptions, to some extent, with temporary or permanent effects. Vulnerability is more important in urban transportation networks, due to heavy use and road segments that are close to each other. Small disturbances on an urban transportation network segment can have a huge impact on its accessibility. Intelligent adversaries may take advantage of these vulnerable parts of the network and disrupt transportation operations, increasing the overall transportation cost for the users.

Often, the decision about improving the networks in transportation planning and management is made without adequately considering the possible vulnerabilities. By considering the factor of vulnerability in their decision, planners could prevent or limit the impact of severe unforeseen disruptions.

This dissertation proposes two models for designing robust networks against intelligent attackers. In both models, three stakeholders are considered: i) the network manager/designer, ii) the adversary (intelligent attacker), and iii) the network users. The frameworks of both models and some other possible models are presented in this dissertation.

The first framework is a bi-objective designer model. The designer in this model has two objectives at the top level: to reduce the total system cost and to reduce the vulnerability of the network. The Sioux Falls network consists of 24 nodes and 76 links was chosen for to evaluate this framework. The decision of the designer and attacker was improving or destroying the links. Metaheuristic algorithm was used to solve the designer and attacker problems. For the user equilibrium problem, the Frank-Wolfe algorithm was implemented. The objective of the designer of the network in the first model, consist of two goals. The two goals may conflict on the amount of amount of limited available budget to be invested on the desired project/links. Therefore, a trade off solutions between these two objectives may forms. The results proved that the proposed multi-level model is able to find the Pareto front solutions for the two objectives of the designer. The second framework is a three-level zero-sum game model. In this framework, the payoffs from the designer are assumed to have the same value to the adversary entity. Therefore, the goal of this framework is to minimize the maximum gain that the adversary can achieve. An example network with 6 nodes and 16 links was used to examine this framework. The results showed that the model could be a valuable tool to reduce the potential vulnerability of networks. Other indicators of system performance can be implemented in the upper-level of this framework, in order to examine different goals. Both frameworks were tested using a medium size network with applications to larger scale networks as a future research direction.

List of Tables

1. Notations - Sets and Indices:

2. Notations - Parameters

3. Notations - Variables

4. Summary of methods for robust transportation network design

5. Examples of adversarial games

6. Metaheuristics algorithms for NDP

7. Data for Test Network 1 (5-Link)

8. The trip rates for the Sioux Falls network (1000 veh/time unit)

9. The local optimum solution for the first scenario on the 16 link network, Bz = 1

10. The local optimum solution for the second scenario on the 16 link network, Bz = 2

11. The local optimum solution for the first scenario on the Sioux Falls network, Bz=l

12. The local optimum solution for the first scenario on the Sioux Falls network, Bz=2

List of Figures

1. Complexity versus level of details in traffic flow modeling. Adopted from Washington (2008)

2. Operations of Network Design Problems

3. Vulnerability versus reliability. The thick line is the “risk curve” of Kaplan et al. (1981)

4. Example of investing and getting attack on the same link

5. Examples of hierarchy of sequences of player’s moves and structures of games

6. Examples of a hierarchy of three players’ decision flow

7. An example of the multi-period NDP results for Braess network

8. Four possible combinations of undirected graph with three nodes

9. Number of possible undirected networks by number of nodes

10. Domain size of Lane Addition (Discrete Variable)

11. Flowchart of the Solution Approach

12. Decoding Procedure

13. Genotype chromosome representation of adversary entity

14. Test Network 1 - Braess Paradox Network (5-Link)

15. Test Network 2 (16-Link)

16. Variation of reaching the solution by different size of bit-string in binary chromosome representation

17. Elitist selection with different size, for population size 100

18. Different Crossover operators (Crossover rate 10%)

19. Convergence of capacity expansion vector to optimum values by crossover rate (crossover type: Uniform Crossover (UPX), mutation rate: 2%, population size 30)

20. Crossover values by Mating rate (one-point Crossover)

21. Sensitivity test of the convergence to mutation rate

22. Test Network 2 (16-Link) Results

23. Total System Travel Time for Test Network 2 - (16-Link)

24. Sioux Tails network configuration

25. Links Included in Expansion (links with orange color) for the Sioux Tails network

26. Improvement of the two objectives at the designer level by generations

27. Individuals of the two objectives at the designer level by generations

28. Decision of the designer (Number of lanes to be added to the network)

29. The optimal decisions of the attacker

30. Improvement of the capacity-expanded network compare to the initial conditions.

31. Llows in the Initial and Improved network, before and after the disruptions (veh/day)

32. Travel times in the Initial and Improved network, before and after the disruptions (min)

33. Individuals of the two objectives at the designer level by generations

34. Decision of the designer (Number of lanes to be added to the network)

35. The optimal decisions of the attacker for the initial and improved networks

36. Flows in the Initial and Improved network, before and after the disruptions (veh/day)

37. Travel times in the Initial and Improved network, before and after the disruptions (mm)

38. The optimal decisions of the designer and the attacker

39. Flow on the links after the disruptions (veh/day)

40. Travel Time of the links after disruption

41. Travel system travel times by Bz in the Initial and Improved network after the disruptions

42. Test Network 1 (16-Link)

Abbreviations

Table 1

Notations - Sets and Indices

illustration not visible in this excerpt

Table 2

Notations - Parameters

illustration not visible in this excerpt

Table 3

Notations - Variables

illustration not visible in this excerpt

1 INTRODUCTION

Transportation networks are indispensable components of daily life in today’s society. Traffic engineers try to utilize available resources to provide an efficient transportation system for all users (both passenger and freight). However, a transportation network is usually not designed from scratch. The network design problem (NDP) aims to modify an existing or implement a new network to improve system performance (based on various and often conflicting objectives). It proves to be one of the most challenging problems for researchers in the field of transportation. There are various uncertainties that may be unknowns to the designer of a transportation network including uncertain input parameters (e.g., demand and supply) and disruptions (natural or man­made). The latter (i.e., disruptions) may reduce the supply of the network, change demand patterns, and may even completely interrupt the operations of a set of network elements. The research presented herein aims to develop mathematical models and solution algorithms that design a robust network considering intelligent disruptions.

Assessing vulnerability and optimizing network robustness have been studied in the literature using a variety of approaches. To date, no generally accepted indicator of robustness exists. Furthermore, there is a gap in designing robust transportation networks considering an intelligent adversary/enemy entity. This research aims to fill the latter gap in the literature and propose game theory-based frameworks to study the strategic robust network design against intelligent attackers. Two models are proposed in this dissertation for designing robust network. The proposed models consider the following three stakeholders:

1) Traffic management agency or government;
2) Users of transportation network; and
3) An adversary (or attacker).

In order to design a robust network, various distinct ways of representing games based on the order of play, the information available to each player and structure of formulation can be defined. In the frameworks provided in this dissertation, the traffic management agency is interested in designing a network that is less vulnerable to enemy entity moves. On the other hand, the adversary (or evil entity) is assumed to maximize the disruption to the network. The users respond to the adjusted network by the transportation agency and the evil entity. The proposed model can be customized and applied to other similar network designs, like telecommunications and biology networks.

As it will be described in more details in chapter 2 and 4, the corresponding discrete optimization problems for the designer and attacker are combinatorial and NP- hard to solve optimally (Feremans & Laporte, 2003). Hence, no efficient exact or heuristic methods are available to solve these problems in reasonable computational time. Therefore, metaheuristic approaches were used to solve these problems. On the other hand, traffic flow at the user level was modeled using Nash equilibrium concepts. The user equilibrium problem is convex and can be efficiently solved using methods like Frank-Wolfe or origin-based algorithm (Bar-gera, 1999).

1.1 Contributions

The main contribution of this research is to provide various frameworks for designing robust networks strategically, by considering an intelligent adversary entity, who attempts to exploit the vulnerabilities of the network to the maximum of his or her capabilities. As it also discussed earlier, no generally accepted vulnerability index exists (to the author’s knowledge). Therefore, the goal and achievements of the intelligent entity also need to be defined. One of the appropriate approaches to analyze and model the intelligent adversary’s rule in vulnerability could be modeling it as a player in a game who is interested in achieving his objective(s).

While designing a robust transportation network against stochastic vulnerabilities (due to the stochastic events, for instance, natural disasters) have been studied extensively in the literature, this research aims to provide additional insights by considering the network elements that are vulnerable to the intelligent adversary entity. Two frameworks are presented to model the interactions between the players.

To summarize, the main objectives of this research are:

1) To provide new frameworks to model robust UTNDP against potential intelligent attacks;
2) Develop metaheuristic methodology using genetic algorithm to solve the discrete problems, and a convex combination method to solve the user equilibrium problem; and
3) Demonstrate the proposed methodologies on small and medium sized networks.

1.2 Structure of the Manuscript

The structure of the rest of this dissertation is as follows: Chapter 2 presents a literature review of the related studies. The general design of transportation networks and the evaluation of vulnerabilities as a performance measure are provided in this chapter. Chapter 3 briefly explains the game theory and its application in the proposed frameworks. The mathematical formulation for each model and the role of each player in modeling the robust network design problems is presented. Chapter 4 discusses the algorithms to solve each player optimization model. The Genetic Algorithms parameter settings are also discussed. Numerical experiments were conducted in chapter 5 to test the performance of the proposed models. Lastly, chapter 6 concludes the dissertation and provides the possible topics for future research.

2 LITERATURE REVIEW

2.1 Introduction

In this chapter, a review of the literature is presented in order to provide the foundation to understand the models and algorithms proposed in this dissertation. Since three decision makers are considered in this research, the possible models to account for the interactions, objectives, and decision-making hierarchy are reviewed.

First, a brief introduction to game theory is provided followed by a review of the network design problem (NDP). The focus of this research is on NDP considering vulnerabilities against intelligent disruptions. Therefore, the robustness and the vulnerability as a network performance measure were reviewed in this chapter. The design of robust networks has captured the attention of many researchers. As it is often the case with popular terms, there is not a generally adopted notion for the vulnerability of networks (Jenelius, 2010). Robustness is the opposite of vulnerability. Therefore, a network that is vulnerable is not robust and vice versa (Snelder, 2010).

An appropriate approach to model the vulnerabilities of intelligent disruptors could be to model them as a player in a game, which is interested in achieving his objective(s). Therefore, the following objectives for each player can be defined: From the designer side, it might have various objectives to improve the performance of a network. The performance of a network can be represented as the total system cost, robustness against reliability and vulnerability, reduction of pollution emission and multiyear investments. On the other hand, from a user’s perspective, they look for their optimal route choice, mode, and destination. From an adversary viewpoint, the objective is to degrade the performance of the network to the maximum of his capabilities. Hence, a robust network design model must consider the alleviation of the potential disruptions. In the next section, first a general summary of three common methodologies to model traffic flow is described, followed by a brief introduction to network design problem and its methodology.

Figure 1 demonstrates the relationship between the complexity of modeling/simulation of traffic flow and the considered level of details in the models. In

2.2 Modeling Traffic Flow

The application of computer technology provided engineers with the capability to model complex transportation systems. Various types of models have been published during the last decades. They can be categorized based on the level of detail and their complexity into three categories: Microscopic, Mesoscopic, and Macroscopic models.

illustration not visible in this excerpt

Figure 1. Complexity versus level of details in traffic flow modeling. Adopted from Washington (2008).

In microscopic models, the smallest unit in the simulation is the driver-vehicle unit (or other types of flowing items, for example, vessels, airplanes, packages). Microscopic models provide an adequate amount of information to analyze most of the operational (e.g., operational lane changing models) and tactical (e.g., tactical lane changing models and tactical overtaking models) systems (Michoń, 1985; Moridpour, Sarvi, & Rose, 2006). In the case of modeling driver-vehicle, some behaviors (like lane changing and overtaking) requires large amounts of information, and modeling the decisions drivers are making based on these data, is difficult (Chamieh & El-kouatly, n.d.; Kano, Shiraishi, & Kuwahara, 2007; Suzuki & Mori, n.d.; Wheeler & Lie, n.d.). In addition, defining, simulating and validating rich cognitive driver behavior models, requires significant effort (Numrich & Tolk, 2010; Yılmaz, 2009).

Mesoscopic models, further simplify assumptions of microscopic models by combining the driver-vehicle units into groups of driver-vehicle (or other transport flow units). The Cellular Automata (CA) models usually model the transport units in groups that are moving from one cell to the others by advancing in simulation steps. Thus, these types of models fall into mesoscopic classification.

Macroscopic traffic flow models try to formulate the relationships between traffic deterministic relationships of the speed, flow, and density of a traffic stream (Washington, 2008). These types of models originated under a theory that traffic flows, as a whole, are similar to fluid streams systems. The characteristics of traffic flow in the network are typically considered homogeneous in a specific time unit (which usually ranges from a few minutes to days).

2.3 Network Design Problem

The natural population growth, and other factors such as the increase in income and employment, will result in the increase in travel demand on transportation networks. This may lead to problems such as congestion and safety in the system. The transportation agencies need to plan transport networks properly to alleviate these problems. This will require new infrastructures for serving the new transportation networks or improve the existing system. The planning, design, and managing these issues are traditionally addressed in network design problem (NDP). NDP is usually used for determining the optimal sub-network, which will result in improvement of the whole network. Various definitions of NDP are provided in the literature. For example, Fri esz (1985) defined it as: “network design problem is to determine the optimal locations of facilities to be added to a transportation network, or to determine the optimal capacity enhancements of existing facilities in a network” (p. 413).

Modeling the transportation planning problems is typically complex (Beimborn, 1995). Hence, in practice, these problems are typically decomposed into a sequence of subproblems. Some of the examples of decomposing the transportation problems into independent sub-problems are the classical four-step planning process, network design problem, and traffic signal setting design.

The network design problem can be described using graph theory. Likewise, a complex network can be represented by a graph. A graph G = (N, Ľ) is characterized by a set of links L and a set of nodes N. Each link connecting two nodes, and can be directed or undirected. Attributes like weight/cost (C) can be assigned to each nodes and link (Figure 2). NDP transforms an existing network (graph G = {N, L, C}) into a new improved network (graph F = {N ' , Ľ, Č”}). In road transportation network, distances between end points of links or travel time are well known attributes of links.

illustration not visible in this excerpt

Figure 2. Operations of Network Design Problems

Finding the optimal road design has been the subject of transportation studies for a long while, and is known to be one of the most complicated problems in transportation. A large number of methodologies and solution algorithms have been presented over the last 50 years to provide solutions to these complex mathematical problems (S.-W. Chiou, 2005a; Leblanc, 1973; Murray, Davis, Stimson, & Ferreira, 1998; Suwansirikul, Friesz, & Tobin, 1987).

2.3.1 Bi-level and Multilevel Optimization

Advances in computer technology gave researchers ability to study the design of the networks in new aspects, and in more analytical details. Among the possible modeling approaches, bi-level programming received more attention. It provides a comprehensible representation of the designer and the users of the network as independent sub-problems. The bi-level programming problem is a subcategory of multi­level programming problem, with two level. In problems with conflicting objectives within a hierarchical structure based on the sequential order of two decision makers, bi­level optimization is an effective solution approach. It originated from the fields of game theory and it can describe a number of problems in transportation planning and modeling. Its hierarchal framework involves two separate optimization problems at different levels. In case of Stackelberg competition, the first problem - called the upper-level or leader problem - has a feasible solution set. The solution set is determined by the optimization problem at the second level. The second problem is the lower-level problem or the follower problem. This concept can be expanded to define multi-level programs with any number of levels (Vicente & Calamai, 1994a). The bi-level program is an NP-hard problem; hence, it is difficult to solve using exact algorithms. Ben-Ayed (1993) and Ayala (2013) investigated on bi-level problems and concluded that even a simple bi-level problem with both linear upper-level and lower-level problems is also NP-hard. One reason is that bi-level model for NDP is non-convex (Gangi, Pianificazione, & Luongo, 2005). Luo, Pang, and Ralph (1996) also mentioned that even if both problems at upper- level and lower-level is convex, the convexity of the bi-level problem is not guaranteed. The no convexity of the problem makes it difficult to solve optimally.

Multi-level programming, which has received significant attention during the last few decades, is a branch of mathematical programming that can be viewed as either a generalization of minimization-maximization problems or as a particular class of Stackelberg games. The network design problem can be cast into such a framework. Marcotte (1986) presented a formal description of the problem and developed various suboptimal procedures to solve it. Multilevel optimization problems have shown to be (usually) non-convex and are thus difficult to solve using exact optimization algorithms (Konur, Gobas, & Darks, 2013).

The very first studies in bi-level NDP were investigated by Leblanc (1973), Bruynooghe (1972), and Ochoa-Rosso (1969). They used the branch and bound techniques for solving the NDP. Moreover, Poorzahedy and Turnquist (1982) studied a typical heuristic algorithm to find the solution using integer programming model.

Further research has been done to find more efficient heuristic algorithms, which may give near optimal solutions or local optimum solutions (Allsop, 1974; Steenbrink, 1974). Methods like equilibrium decomposed optimization EDO (Suwansirikul, 1987), which are computationally efficient but result in suboptimal solutions and not suitable for large real networks problems. Gershwin and Tan (1979) formulated the continuous network design problem (CNDP) as a constrained optimization problem in which the constrained set was expressed in terms of the path flows. Patrice Marcotte & Marquis (1992) presented heuristics for CNDP on the basis of system optimal approach and obtained good numerical results. However, these heuristics have not been extensively tested on large-scale networks generally.

Advances in metaheuristic models, (e.g. evolutionary algorithms, and simulated annealing) drew the attention of researchers in mid-90s and 2000s. The benefit of using metaheuristics is their globality, parallelism, robustness and ease in implementation (Mathew & Sharma, 2006). For an example, Friesz (1985) and Meng (2009) utilized simulated annealing (SA) method to solve the upper-level problem. Despite the faster runs of SA, especially for the larger problems, the solution quality of Genetic Algorithm (GA) was found to be better than SA and other metaheuristic algorithms (Adewole, 2012). Mathew and Sharma (2006) performed a study on using GA in CNDP. They applied their model to the small to large size problems. Mouskos (1991) utilized the Tabu search to solve the single class bi-level UTNDP with a Budget constraint where the decision variable was to improve (or not) each roadway link by one lane using the static traffic assignment as the lower level. Furthermore, Zeng (1998) utilized a hybrid SA­Tabu search method to solve the two-class (automobiles plus trucks) to solve the bi-level UTNDP for large networks.

In many governments and public transportation projects, the cost-benefit analysis is utilized to determine if the estimated benefits provide an acceptable return on the expected costs and investments. From this point of view, Meng and Yang (2002) solved the bi-level benefit distribution for network design problem using the ratio of the benefits gained from the capacity expansion for each link. Their model was non-convex, non- differentiable, and continuous, so they chose simulated annealing method to solve their optimization problem. Their multi-objectives trying to maximize the total benefit among the links, while also trying to minimize the differential between beneficial gained by each link. In the next section, a brief introduction to resiliency, reliability, and vulnerability is presented.

The majority of planner’s decisions dealing with project selection involve single initial costs while benefits could spread over many years in the future. Brown (1980) applied dynamic programming to obtain a set of projects which provide an optimum, taking into consideration not only present costs but also the benefits that accrue over several years into the future. Moreover, Başkan performed a study utilizing bi-level optimization that took into consideration the increasing future congestion and limited budget constraints (Başkan, 2013). Optimal link capacity expansion values were found by minimizing the total system travel time as well as the associated link investment costs within roadway networks.

Regarding the sensitivity based approach applied to bi-level optimization problem, Falk and Liu (1995) investigated theoretic analysis for general non-linear bi­level optimization problem and proposed a descent approach in terms of the bundle method to solve the non-linear bi-level problem where the gradient of the objective function can be obtained when the subgradient information of the lower level is available. Chiou (2005) explored a mixed search procedure to solve an area traffic control optimization problem confined to equilibrium network flows, where good local optima can be effectively found via the gradient projection method.

Several attempts were made in the last few years to find the global optimum solution for network design problems. Wang, Meng, and Yang (2010) partitioned the feasible space of nonlinear travel time function into several regions and provided a path based MILP. Each region represents a piecewise linear function that can approximate the original nonlinear travel time function. The model required a heavy computational time and required using a large memory storage. Paramet Lauthep (2011) mentioned that Wang’s approach is inapplicable to the case of DNDP and MNDP, because the paths in their network structure are generated in advance, where it should change during the design process. He modified the model to a linked-based and provided an efficient mixed integer linear program. Li, Yang, Zhu, and Meng (2012) presented a model to convert bi­level CNDP into a sequence of single level concave programs, based on the concept of gap and penalty function. Furthermore, Wang, Meng, and Yang (2013) presented a global optimization method for DNDP. The presented model was not computationally efficient and may not be practical to large problems.

A comprehensive and scientific review of the literature of the various type of urban transportation network design problems was written by Farahani, Miandoabchi, Szeto, and Rashidi (2013). They classified the available models from different aspects: by type of performance measures, decision variables, transport mode, and solution algorithms. A list of the possible future roadmaps was also provided. The decision variables used in the previous studies were categorized into (1) strategic, (2) tactical, and (3) operational. Strategic decisions are about adding new links and expanding capacities. The two later are about to maintain the current network. In the next section, a review of the performance measures of transportation networks is presented.

2.4 Performance measures

The goal of transportation planning and management generally involves finding a set of optimal solutions, for certain decision variables by optimizing different system performance measures. Performance measures, which are defined as indicators of system efficiency, are progressively becoming an important factor in transportation planning (Pei, Fischer, & Amekudzi, 2010). They are the main factor in determining whether a roadway network is viable for the future. Some of the important performance measures in planning problems are congestion, emissions, accessibility, mobility, reliability, pollution emission, noise, and safety.

The typical performance measure in the basic structure of transportation NDP is the Total System Travel Time (TSTT). The level of congestion directly affects travel times. When a part of a network becomes overly congested, travel times will increase and level of services (LOS) will decrease. The effects of congestion can then spill into other portions of the network and increase the system-wide travel times. Another important performance measure is accessibility. Accessibility refers to how suitable is a public transport network for letting travelers go from the point that they enter the network to the point that they exit the network in a reasonable amount of time (Murray, 1998).

Similarly, mobility has attributes like having access to the point of interest, maintaining networks, benefiting from travel to social contacts and potential travel (Alsnih & Hensher, 2003). Safety is of critical importance in transportation. The key objective of the safety of a network is to reduce the annual number of crashes to a fraction of the current levels (Dijkstra, 2013). Resiliency, reliability, and vulnerability are three other comparable performance measures that are discussed in the following sections.

2.4.1 Reliability

The reliability of the transportation network refers to the probability that a system can perform its expected function to an acceptable level of performance for a given period of time (Bell, 2000). Berdica (2002) defined the reliability of a network as the possibility of moving freight or passengers from one place to another successfully. Yim, Wong, Chen, Wong, and Lam (2011) further defined reliability as the ability of the network and its elements to operate under capacity. Reliability gained more attention during the 90’s when the natural disasters like earthquakes damaged or completely lost the connectivity of some of the major roadways around the world (Yim, Wong, Chen, Wong, & Lam, 2011). Following the development of transportation networks, the reliability studies focus on alleviating the damage effects on the network and investigate the unpredictable variations caused by the uncertainties (Nicholson, Schmöcker, Bell, & Iida, 2003). Some of the main measure of the reliability of transportation networks are connectivity reliability, travel time reliability, and capacity reliability (Chen, Yang, Lo, & Tang, 2002). The types of measuring reliability in transportation can be categorized as following types:

1. Statistical range method, e.g. Standard deviation (STD) and Coefficient of variation (COV) of travel time.
2. Buffer time methods: The extra time a user has to add to the average travel time to arrive on time 95% of the time.
3. Tardy trip measures: The amount of trips that are late.
4. Probabilistic measures: The probability that travel times occur within a specified time interval.

The importance of the measuring reliability can lie on the fact that most of the users get a resiliency of the cost (Travel Time) over the time, and a sudden change on it can have a big effect on the network. This can be seen usually during the need for fast evacuation.

Transportation network planning efforts have traditionally relied on the localized level-of-service (LOS) measures such as the v/c (volume/capacity) ratio, to identify highly congested links that are considered as critical links. The problem with this approach is looking at the individual segments’ performance; the individual elements may not enable planners to identify the most critical highway segments or corridors in terms of maximizing system-wide, especially for system travel-time benefits by implementing highway improvement project.

Various approaches have been studied to analyze the reliability of networks. A reliability of transportation network by changing the cost or disutility function as the standard deviation of travel time was examined by Fosgerau and Karlström (2010). They found out that the maximum expected utility has linear mean and standard relationship correspondingly to the travel time. Markov Chain has been used by several researchers to replace the conventional transportation planning and predicting the future pattern of flow (Antoniou, Koutsopoulos, Yannis, & Model-based, 2007). Indrei (2006) tried to model the traffic flow system using Markov Chain theorem. However, his work only limits to a unit car. Iyer, Nakayama, and Gerbessiotis (2009) also used a continuous-time Markov chain (CTMC) model for predicting the reliability of a system by evaluating cascading failure procedure. They distinguished all the possible cascading failures of different sets of elements that lead to breakdown the whole system, and based on the Markov probabilities, they rank the elements by their contribution to system breakdown.

2.4,2 Resiliency

Resiliency is defined as the ability to resist, absorb, recover from, or successfully adapt to adversity or a change in conditions (Bhushan, Narasimhan, & Rengaswamy, 2008). In a transportation network or in a sequence of events, it can be seen how the different elements work together to recover after a disruption (such as flood, hurricane, tornado, etc.) happens. Resilience can be viewed as the opposite of brittleness, which describes a system that cannot tolerate disruptions, and loses the capacity (or functionality or other words that describe the productivity of a system). In this context, therefore, resiliency is an attribute that contributes to achieving the required reliability. However, resiliency is not an independent measure of reliability.

Resiliency gained more attention during the last decade, and various studies have been performed on this topic. Some of the studies focused on the resiliency of the maritime systems. In order to examine the resilience of ports, Kamal Achuthan (2012) developed a simulation model and performed a variety of analysis. He considered the interactions between different elements in a port and saw how statically they can incorporate in the resiliency of the port due to a disruption. He also considered the stakeholders contribution in his interdependencies model. The output of his model includes resilience matrices for before, during, and after disruption, the number of ships served by each resource and also queues and delays. Some of the important vulnerability indicators in literature are described in the rest of this section. To manage the resilience strategies in maritime systems, Mansouri and Mostashari (2009) developed a decision analysis methodology. They mainly focused on the costs (probable disruptions, investments in resilience strategies, losses, and gaining from using resilience strategies). Therefore, the study can be considered as a business work with a monetary focus.

A three-stage framework to analyze infrastructure resilience was defined by Ouyang (2012). The first stage was defined as a consistent mode, which can be used as a representation of disasters. The second stage defined as damage propagation, and the last two stages defined as a situation which the authorities trying to stop the damage propagation and recover it. He and his co-researchers chosen power grid model as a case study, and then they consider several disasters (in their case, random hazards and hurricane hazards) and different approaches to recovering the damages. They figured out that the annual resilience mainly happens due to its higher frequency of occurrence compare to hurricane hazards. In addition, they found out that the type of recovery sequences is important.

2.4,3 Vulnerability

As it was discussed in chapter 1, there is no universally accepted definition of vulnerability. Therefore, vulnerabilities can be evaluated and viewed from different aspects. From a transport side, the vulnerability can be defined as how vulnerable the transport system is in the case of failure of one or several of components of transportation systems (Erath, Birdsall, Axhausen, & Haj din, 2009). In another word, it defined as sensitivity to attack or injury. According to Jenelius (2010) the technological and social aspect of transportation networks can be distinguished from their perspective: From the technological point of view, he defined the infrastructure component’s importance by the impact of the failure of that element. Furthermore, criticality is defined as the combination of probability and the importance of failure. From the social side, exposure is defined as the equivalent of importance which shows the failure impact to an individual user. Likewise, vulnerability is defined as the combination of exposure and the probability of failure.

Vulnerability should be differentiated from reliability. One of the main differences between these two concepts is their focus on the magnitude and the probability of the adverse consequences. Figure 3 shows the “risk curve” of (Kaplan & Garrick, 1981) in probability format. The probability of occurrence of a scenario and its level of damage can be found by looking at this curve. The frequencies of occurrence of regular events are lower when its impact is higher.

illustration not visible in this excerpt

Figure 3. Vulnerability versus reliability. The thick line is the “risk curve” of Kaplan et al. (1981).

The interrelationships between infrastructures, impact of risks within the system, and consequence of events has not been studied well in the literature. A failure of a network component could also cause the breakdown of other critical infrastructures in a disruption event. For example, a disruption in a fuel transport network for a period time of several days to several weeks could have a sequence of further disruptions in other networks, such as transportation, energy; or a breakdown of telecommunication or energy network could affect the transportation system for foods (Murray & Grubesic, 2007). It should be noted that different transport materials also do not have the same importance in term of overcoming the critical situation. For instance, the transports of medicine and foods usually have a more crucial impact than the farm products in severe events. In terms of time, the interruptions in the service of an infrastructure may last for a short period (e.g., few hours), or longer periods (e.g., several days or weeks), or in extreme conditions, they can be permanent and last for an indefinite time.

The concept of vulnerability can be classified in the following ways: static which evaluates the vulnerability based on a physical property of a network, and does not depend on traffic flow; and dynamic that directly refers to the robustness of a network. Most of the works were focused on graph theory and their property correspond the possible vulnerability of the network. However, in road transportation network, more realistic model considers traffic flows, as they are the main concern of the designer of network if the impact for a single user under a specific scenario is to be evaluated, this may call for exposure of the user to that scenario Jenelius, Petersen, & Mattsson, 2006). Kröger and Zio (2011) also categorized different approaches for assessing the vulnerabilities of Critical Infrastructures (Cl). According to their research, vulnerability evaluation focuses on three main elements: degree of loss, degree of exposure, and degree of resilience.

The availability and quality of alternative routes are a very important indicator of vulnerability. The availability of spare capacity (capacity minus the flow) also could be an important indicator of vulnerability. Other examples could be v/c ratio, the number of OD-pairs that use a link, number of vehicles affected by spill back (the spare capacity can be used to bypass an incident), extra vehicle kilometers traveled as a result of link closure, travel time losses as a result of crashes.

Crucitti, Latora, and Marchiori (2004) and Latora and Marchiori (2001) provided a measure for the performance of a network, called ‘network efficiency’. The network efficiency E(G) of a network G is only depends on topological characteristics of a network. Their performance indicator is based on shortest path between nodes and number of nodes. Efficiency of the network defined based on the number of possible edges (higher number of edges increase the efficiency and reduce the disruptions in network), and shortest path between all the nodes (smaller shortest paths means higher efficiency).

Jenelius et al. (2006) presented a mathematical model to evaluate the vulnerability of link, nodes, and whole network. In his model traffic flow is considered as the source of vulnerability indicator, and was based on changes in the cost of travel and unsatisfied demands of links or nodes. He further transformed his model, by incorporating changes on the cost of travel and unsatisfied demands of elements covered in grids (Jenelius & Mattsson, 2012). In denser network areas, grids can be defined smaller to provide better accuracy to analysis performance ratio.

Equity of impacts if network degradation among all the users is considered as a key in analyzing and design network. Jenelius (2010) presented a methodology for link performance measure considering equity measures. In his model, equity importance measure in disruption events is defined as the coefficient of variation of increase in travel times. The degradation is measured using the total changes in travel time.

The link usage proportion-based algorithms are applied to solve bi-level transportation problems in which demands act as upper-level decision variables (H. Yang & H. Bell, 1998). In this algorithm, an influencing factor for each link is a ratio between its usage and its capacity. In this case, the link that is used to its capacity or over is likely to receive an improvement. This algorithm is applied to ramp (H. Yang & H. Bell, 1998), zone reserve capacity (H. A. Yang, 1997) and О-D matrix estimation (Jin & Yang, 2014).

Snel der (2011) presented a topological vulnerability indicator, based on the availability of alternative (backup) links, which can be translated to alternative routes. In her model, the links that cross a line perpendicular to the target link a are considered alternatives for the link a, if they meet the following requirements: The absolute angle between the link a and the alternative link must be smaller than 60 degrees. The vulnerability index in her model is based on: (1) the ratio of capacity of link a, over the summation of capacities of alternative links for link a, (2) a function of shortest path between link a and its alternative links, (3) and a parameter for the importance of the distance.

Reniers and Dullaert (2013) used a scoring system in GIS to evaluate the vulnerability in transport hazardous materials in four different modes. They subcategorize each type of materials by the mode type and give each route segments a score that represents the vulnerability on its transportation. They also used a score factor for the number of people that are influenced by the consequence grade.

Accessibility also considered in literature to evaluate vulnerability. In Chen (2007) model, vulnerability is assessed based on changes in accessibility measure (a utility function) due to the degradation of network structure. He combined trip distribution, mode, and assignment in the model. Taylor and D’Este (2007) defined a node to be vulnerable, if loss (or substantial degradation) of a small number of links significantly reduces the accessibility of the node, as measured by a standard index of accessibility. In their model, they did not consider traffic flow.

Gregoriades and Mouskos (2013) utilized a combination of the mesoscopic traffic simulator called VISTA and Bayesian Network to model the accident potential in links of the network. They proposed an index called ARI (accident risk index) which was the result of the Bayesian Networks (BN) output. The topography of BN comprised from different variables such as the pavement quality and link attributes; and includes two new parameters from VISTA: flow and speed. Having these two parameters, they claimed it would improve the prediction power of BN. The validation process shows about 81 percent prediction validity, which the authors mentioned it can improve by improving different input variable to BN. Berdica and Mattsson (2007) also developed a simulation- based method to evaluated vulnerability at the link or network level. They predefined twelve scenarios defined (i.e., Lane/link closure, change the BPR function element) to study the vulnerability.

Murray, Matisziw, and Grubesic (2007) developed four bi-objective optimization models to study the possible disruptions in a graph network. Furthermore, the bi- objective converted into a single objective using a weighted combination of the two objectives. The objective is to min/max the bandwidth of the network and the impacted population. She further studied vulnerability indicators and provided a structured approach to optimization to evaluate vulnerability for a set of nodes, or total interacted О/D pairs. The model was based on selected number of nodes to be interdicted, the optimization model seeks to find worst (best) nodes to be interdicted, such a way that the total О/D disconnected would be maximum (or minimum) (Murray et al., 2007). Bell (2000) and Bell, Kanturska, Schmocker, and Fonzone (2008) also developed a game theory approach to identify the vulnerable elements. They provided a min-max optimization model of the worst-case scenario.

A vulnerability index for each node/link or a set of node/link in a region or multiple regions could be defined by evaluating the total loss. The vulnerable infrastructure then could be ranked to improve its robustness against disruptions. The Network Robustness Index (NRI) was presented in Scott, Novak, and Guo (2005) and Scott, Novak, Aultman-Hall, and Guo (2006). This index provides a performance measure to assess the vulnerability of the link or the whole network. The NRI value is obtained by comparing the total changes before a link removal, to the state before disruptions. Therefore, the alternative route and the additional cost would be considered in the model. The Scott et al. (2005) model was further developed by Sullivan, Aultman- Hall, and Novak (2009). The new robustness index (NRI-m) is similar to the original NRI index, and the only difference is in the partial capacity reduction of the elements.

Qiang and Nagurney (2007) further improved Latora’s performance indicator by involving the flow of traffic. They proposed a new unified model to present the network performance measure. Their performance indicator provides importance identification and the ranking of network components. The model is based on equilibrium demand and disutility for О/D pairs. The defined efficiency/performance measure incorporates vulnerability and reliability in their model. A summary of vulnerability indicators is presented in Table 4.

Table 4

Summary of Vulnerability Indicators

illustration not visible in this excerpt

2.5 Robust network design

In the previous sections, the concept of robust network design has been discussed. The goal is to design reliable and robust networks that are less vulnerable to disruptions. Robust network design focus is on the reduction of the impact of disruptions in terms of reliability, vulnerability, and resiliency (Snelder, n.d., 2011). Disruptions could occur in the travel times, trip rates, capacity, traffic signals, and even the change in direction of a link. A network is more robust if it can withstand unexpected disruptions. Robust network design can be categorized based on design approaches:

1. Scenario specific (some manually selected scenarios)
2. Strategy-specific (same as 1, but guided, which means some arc/nodes are more likely to be disrupted.

3. Structured approaches (optimization-based)

Approach 1 and 2 are usually utilized in micro- or mesoscopic simulations based models. Several studies in literature utilized dynamic traffic assignment (DTA) in robust network design problem. A framework was presented by (Snelder, n.d., 2011) for robust network design problem, considering combined route choice, mode choice and trip distribution in the lower level DTA problem. In the model, the designer has the decision of adding capacity to link, route or buffer lanes. The vulnerability is considering using a term in the top-level objective function. This term, comprised from the multiplication of expected number of incidents, by total system travel time loss, and multiplying by the value of robustness (weight of robustness in top-level objective function). She assumed that the probability of an incident is a function that depends on the number of vehicle kilometers driven. The short-term variation in supply caused by incidents is also included in the model. They solved the model formulation using the genetic algorithm on several test networks.

Chiou (2015) presented a model for designing a robust network strategically. He transformed the bi-level hierarchical problem into a single level. The vector of link capacity expansion can be optimally determined in a worst-case scenario of travel demand growth for its equilibrium flow. The lower level UE problem is solved by parametric variational inequality, and a single level minimax model was provided.

Dziubiński and Goyal (2013) studied various games between a designer and an adversary. The designer tries to form a network consisting of n links - which are costly to construct - and protect a set of them against disruptions. On the other hand, the adversary entity is interested in damaging the network to the maximum of its capabilities. Perfect and imperfect information in different scenarios is assumed available to the designer. The difference is considered as the knowledge of the designer of the possible moves of the adversary, which depends on their payoffs. Their main finding was with limited available resources, the best defense would be in sparse networks, rather than centralized.

Murray-Tuite and Mahmassani (2004) studied four types of games between a transportation operation manager of a network, and an adversary entity who tries to damage the network, using bi-level formulation. In their method, the vulnerability index value is based on the utility of alternative routes, considering the current flow, and ratio of flow over demand. The utility is based on the ratio of free flow travel time over marginal travel time and the relative capacity. The utility values range from 0 to 1, where 1 indicates that the link is extremely important to the connectivity of specific О/D route.

Martin (2007) studied various types of network design against attacks and developed a tri-level defender-attacker defender model to design a robust network, which the defender in the inner model tries to minimize the users’ costs. The proposed framework assumes that the defender at the outer level uses limited defensive resources to protect a system from attacks. At the middle level, the attacker uses their limited resources to attack the unprotected components while at the inner level the defender operates the system to minimize operating costs from damage (resulting from the attacker).

Zhang, Xu, Hong, Wang, & Fei, (2012) tried to utilize the unified performance indicator defined by Qiang and Nagurney (2007) in order to provide a robust network design. The model is formulated using bi-level optimization. In the upper level, the designer of the network interested in maximizing the performance of the network, constraint by his available budget/resources. The lower level problem is user equilibrium. Maximizing the network performance will result in a more robust network.

Chen, Zhou, Chootinan, Ryu, Yang, and Wong (2011) presented a bi-objective model that optimized capacity reliability and travel time reliability. These performance measures give the supply and demand of a roadway network’s reliability. The minimization of total system travel time is a key objective when using bi-level optimization in transportation planning. Multiple works have been conducted on this topic (Ben-Ayed et al., 1988; Gao, Wu, & Sun, 2005; Yang & Bell, 1998). Melachrinoudis and Kozanidis (2002) presented a mixed integer knapsack solution to find the optimal set of projects which maximize the total reduction in the expected number of accidents constrained by a limited budget.

Furthermore, Dziubiński and Goyal (2013a) studied on the various shape of networks. They considered two players in the game, designer, and adversary. The designer forms link between a set of defined nodes. The adversary attacks on the nodes based on his resources. They found out that the best shape of the network in terms of affordability and reliability, is sparse and heterogeneous, and either fully or centrally protected (Dziubiński & Goyal, 2013a).

Table 5 presents a list of models for designing robust transportation networks.

Table 5

summary of methods for robust transportation network design

illustration not visible in this excerpt

2.6 Summary and Future Research Needs

The works studied in this chapter provide a basis for the research in this dissertation, which focuses on the development of models for identifying vulnerabilities within a network, and design the robust networks against intelligent disruptions.

Growing demand has forced the transportation authorities to improve the performance of transportation networks. They try to find a solution to improve the existing network under the budget constraint such a way that the social welfare and the network robustness is maximized while accounting for the equilibrium of the route choice of the network users. Improving a transportation network, with limited resources, could be done by considering various network performance measures. The historical approaches to model these types of problem and the solution methods have been reviewed and studied. Furthermore, an introduction to game theory and network design problem based on its concepts was presented. Likewise, the vulnerability indicators in transportation networks were reviewed. Vulnerabilities in the networks have been considered in many studies focusing on the initiate of the problem base on stochastic events. However, considering vulnerabilities due to the intelligent adversary entities’ behavior in network design process should be more studied.

In this study, three decision makers are considered to form the robust network design models. This type of optimization problem is hard to solve since sets of decision makers with different objectives are inherently involved. There is no clear urban transportation model based on the three earlier aforementioned decision makers. Therefore, attaining models that consider these players into the game forms the basis for provided.

3 METHODOLOGY

3.1 Introduction

This chapter first discusses the concept of game theory, followed by introducing the players that are used in the proposed frameworks. Furthermore, the proposed framework and the mathematical formulation of the models are presented. To formulate the models, the sets, parameters, and variables are defined in Table 1 through Table 3.

The notations are similar to model and graph representations in (Sheffi, 1985), and are adopted for the proposed models. To have a better understanding of the methodology, some essential information about game theory concepts are presented in the next section.

3.2 Game theory

Game theory provides mathematical tools for analyzing situations in which parties - called players - make independent decisions. A game is defined as a finite game when each player has a finite number of options, the number of players is finite, and the game cannot go on indefinitely. It can be defined as the study of mathematical models of conflict and cooperation between intelligent rational decision-makers. A solution to a game is the optimal decisions of the players, who may have similar, conflicting, or mixed interest and the outcomes that may result from these decisions.

Hence, a game is a set of strategies for each player that does depend on other players’ strategy. If the solution of any player does not depend on other players’ decision, the problem is not a game. In a game of regular network design problem, the decision of designer depends on the users of the network, and vice versa.

Games can be classified based on the information available to players:

- Perfect information available. A player that has perfect information knows everything about the moves in the game at all the time. They player with perfect information may not some information on other players payoff or the structure of their optimization. An example of this type of games is a game of chess. If one player is aware of another one, (i.e. human be aware of computer moves), the human can reduce the final computer score (or improve her ultimate score), but may not avoid lose/draw.

Imperfect information. Oppose of the previous one. An example is the game of poker. Each player does not know all of their opponents’ cards. The payoffs in this game could be represented by money.

Based on the bind between decision of the players in variable-sum games, games can be categorized into cooperative games and non-cooperative:

- Cooperative games: players in this type of game can communicate and have bound in their decision.
- Non-cooperative games: players in this game may communicate; however, they cannot make a binding agreement with their decision.

Furthermore, games can be classified into categories of simultaneous and sequential, based on order of moves:

- Simultaneous games are games where both players move simultaneously, or if they do not move simultaneously, the later players are unaware of the earlier players' actions (making them effectively simultaneous)
- Sequential games (or dynamic games) are games where later players have some knowledge about earlier actions. This need not be perfect information about every action of earlier players; it might be very little knowledge.

The mathematical representation of the problem can be provided in two formats: zero sum game and non-zero sum game. A zero-sum game is a situation in which a gain or loss in utility of each player is exactly balanced by the losses or gains of other players’ utility. In other words, if the total gains of the players are added up and the total losses are subtracted, the summation will be zero. On the other hand, in non-zero-sum games, the summation of losses and gains is not equal to zero. Zero sum games are strictly competitive, which means there exist some losses associated with each gain. Non-zero sum games can be competitive or non-competitive. One of the common approaches for solving zero-sum games is Minimax theorem. In game theory, Minimax is a decision rule for minimizing the worst-case scenario loss (maximum loss). For the two players finite zero-sum games, the solution from Minimax, Maximin, and Nash equilibrium are equivalent. Therefore, in a zero-sum game, the participant’s loss of utility is exactly equal to the gain of the utility of the other participant, while it is not the case for the non-zero sum games. Many conventional games are considered in this category. A list of some of the adversarial zero-sum games is provided in Table 6.

Table 6

Examples of adversarial games

illustration not visible in this excerpt

A player, who is playing against a perfect opponent, knows that his opponent is unpredictable. An adversarial search algorithm should for a search through possible sequences of moves to find the best next move. However, due to the time limits of most of running most of the known algorithms, it is usually impractical to consider all the possibilities. Considering chess game, the initial state is the current board configuration. Therefore, the operations to move in the search space are the moves of the players on the board. The final state of search could be won or lost. Exact minimax analysis for the chess game is infeasible with current solution algorithms and computational power in a reasonable time. In order to reduce the complexity of minimax search, technics like a-ß pruning are being utilized, which works by pruning portions of the search space. To evaluate the moves in the search space, a utility function (or payoff function) needs to be defined. The aim of the utility function is to measure how badly the opponent is beaten. The quantitative typical values are usually +1 (win) and -1 (lose), -infinity and -binfinity and 0 and 1. However, based on problem specific requirements, other quantitative payoffs could be defined.

Dealing with conflicting objectives in optimization problems has always been challenging for scientists. Multilevel optimization problems are referred to mathematical programs, which a subset of their variables constrained to an optimal solution of other programs parameterized by their remaining variables. When the other programs are pure mathematical programs, the problem is bi-level programming problem (BPP). When the other programs are bi-level themselves, the problem becomes three level programming. This notion can be extended to multilevel programs with any number of levels (Vicente & Calamai, 1994b). The simplest form of BPP in the linear form shown to be NP-Hard (Bard, 1998; Ben-Ayed et al, 1988; Vicente & Calamai, 1994b). Programs like linear integer problem, bilinear, quadratic, and minimax programs can be stated as a special instance of bi-level programs. There have been studies conducted to provide a link between bi-objective problems and BPP (Bard, 1998; ünlü, 1987). However, they were not succeeded in a sense that the optimal solution of a given bi-level program is Pareto optimal or efficient for both lower and upper-level problems. Game theory approaches are widely accepted solutions to deal with the conflicting problems. The main problem can be decomposed into sub-problems, which are the players in the game. In the next section, a review of the players involved in the proposed frameworks is provided.

3.3 Players

The problem and the solutions could be viewed from the aspect of three main players involved: the designer of the network, the users of it, and the adversary entity. Frameworks can be defined based on one or more of these players. The usage of any of the frameworks differs by the involved players and the order of moves.

Other elements that can be considered in the frameworks are the non-intelligent disruptors. Examples of these disruptions are natural disasters and unintended human mistakes. Natural disaster refers to natural events like earthquakes, tornados, and flooding. Other stochastic disruptions could be traffic accidents, telecommunication, and electrical interruption. These type of disruptions could be considered as components in the frameworks. However, it should be noted that these types of non-intelligent component, are not optimization models. The goal and decisions of each player are described in the following sections.

3.3.1 Users

Users are the travelers in the transportation network. They can be defined as persons, driver-vehicle units or any other modes of transportation. The goal of the user level problem is to decide upon their route, in order to minimize the individuals’ travel cost. The decision variables are flows on paths or bushes between the origin and the destination(s). Users may have a choice of transport modes, and the departure time choice.

Therefore, the problem at the user level is to assign the trip matrix into the network using the route choice algorithm. A first mathematical investigation of the problem has been done by Wardrop (as cited in Sheffi, 1985). He developed the so-called Wardrop’s first and second principle of equilibrium model that are based on the concept of Nash equilibrium in game theory. His model denotes that no user can experience a lower travel time by unilaterally changing routes. In simple terms, the equilibrium is achieved when the travel cost on all used paths is equal. This principle is behaviorally robust, computationally efficient, and possesses the unique solution. A convenient way to model the travel time of a roadway link is the Bureau of Public Roads (BPR) travel time function that is has been used widely to model the static traffic assignment problem. It is noted that this function is simplistic as it cannot capture the time dimension and the traffic control characteristics of a roadway link as well as the impact of other adjoining roadway links on the travel time of the subject roadway link and the interactions among various classes of vehicles. The BPR travel time function ta specific to a given link a is given by

illustration not visible in this excerpt

Where a_a and ß_a are link specific constants, and t₀ is the free flow time on link a. Generally, the constants a_a and ß_a are calibrated using the observed field data. One important feature of BPR function is its monotonically increasing convex format.

The nonlinear programming model for the user level problem is provided in equations (2) through (6):

illustration not visible in this excerpt

Subject to:

illustration not visible in this excerpt

Equation (2) denotes the objective function of the UE problem. Constraint (3) describes the demand conservation condition. That is to say, all trips should be assigned to the network. The flow on all routes between each OD pair has to be equal to the OD trip rate. Constraint (4) outlines the relation between flows on links and route(s), for each OD. The binary value of da k is1־when link a is on the path k, and it is zero otherwise. Constraint (5) and (6) satisfies the non-negativity of path flow and travel demand correspondingly, so the solutions are physically meaningful.

3.3.2 Adversary

Adversary or attacker is the entity who is trying to degrade the performance of the network. Its objective can be maximizing total system travel cost, the number of travelers who cannot reach their destinations, and other vulnerability related factors. Examples for the decision of this player are disabling/reducing the capacity of nodes/links/grids, manipulate VMSs/DMSs, and signal timing. The adversary entity possibly can increase his total gain by having some information about the vulnerability of the network.

The degradation of links due to the damages from adversary can be modeled in various approaches: 1) removing the link(s) from the graph, 2) Adding a big number as a constant term to the cost of using the disabled link(s), 3) decreasing the capacity of link(s), 4) increasing the free flow travel time of the link(s). The first approach is not suitable for this problem since it make the graph disconnected. One tactic to deal with this issue is eliminating the OD pairs that cannot make their trips and associating a cost to this removal. The second approach does not consider any property of links. The third approach would conflict with the capacity expansion procedure of the model. The last approach could provide a better modeling of degraded links.

3.3.3 Designer

This category belongs to conventional transportation NDP. The objective of the designer (or the defender) can be defined as a single level process to improve the performance of the network. Performance indicator can be any or combinations of vulnerability, reliability, system cost or etc. The objective of the designer is related to economic growth and is about to improve the desired performance measures. For instance, he may try to lower travel times, provides more reliable travel times, improve social equity, improve environmental conditions, and improve livability. Other objectives usually include, but are not limited to the following examples:

- Minimizing cost of construction
- Minimizing total system travel cost
- Minimizing environmental effects (e.g. emission pollution, noise)
- Maximizing indicator(s) of robustness (or similarly minimization of vulnerability)
- Maximizing of the consumer surplus
- Maximizing of spare capacity
- Maximizing the reliability of the network (or minimizing the probability of overloading the network links) objectives could be:

The decision variables available to the designer to achieve the mentioned objectives could be:

- Capacity
- New links
- Transit schedules
- Number of lanes
- Toll pricing
- Signal timing
- Safety related components
- Protection related components
- Maintenance

3.3.3.1 Conflicting problems of Designer and Adversary

In the games with asynchronous moves like Stackelberg games, each player has different benefits from the hierarchy structure of the optimizations. For example, in the Stackelberg game with two players, the follower player that moves after the leader, has the advantage of having perfect information regards the leader’s moves. On the other hand, the first player has the benefit of implicitly control the next player’s move, such a way that optimize his/her own goal. In this case, the evil entity has the advantage of moving after the designer move. The decisions by the designer already are in place, and at the time of adversary’s move, the designer cannot take any more actions. Hence, adversary entity has a perfect information about the designer’s move, while the designer does not. The objective can be defined in different approaches. For instance, it can be a maximization of the average travel time, minimizing the connectivity, maiming the total system travel time of a specific region or etc. However, a more realistic objective is to maximize the total travel time of the whole network.

As it mentioned previously, three players are involved in the proposed game method. The designer of the network does not have perfect information about the possible moves of the adversary. Therefore, an appropriate model should search over the possible moves of the adversary, and try to alleviate them.

The first move is completed by the designer of the network who has the advantage of putting his decision in place, and observing the reaction of the other players. The designer decision is defined by vector y. The value of ya shows the amount of expanding the capacity of link a. In this research, ya is the number of lanes to be added to link a. In the proposed model, it is assumed that the adversary entity finds the maximum possible damage to the network. His decision in the model is defined as vector z. The value of za = 1 shows the state to which link a is damged and not available to the users; otherwise, the link is not affected. The damage is evaluated as the increase in the total system travel time. After the decisions of the designer and the adversary were made, the users of the network complete the next move. The reaction of the users is modeled using user equilibrium principles. The bi-level formulation models the relationship between the network manipulated by designer and adversary at the upper level, and the users at the lower level problem. These problems are described in details in the rest of this chapter.

As discussed in chapter 2, considering the vulnerabilities of intelligent disruptions in the process of network design is crucial to alleviate the consequences of such events.

Furthermore, a selection of vulnerability indicators was presented. As it was studied in the literature, the vulnerability can be evaluated by measuring the increase in the Total System Travel Time (TSTT). This way, the damage due to the disturbance is evaluated over the whole system. One approach to deal with the robust design of the network would be modeling the problem as a bi-level formulation. Therefore, the solutions of NDP can be compared to the increase in their TSTT, after the disruption occurs; a network that its TSTT has less variation would be considered more robust. Hence, the goal of the NDP is defined as to reduce the maximum possible damages that the adversary entity can imply. From the designer side, the model formulated as a min-max optimization, where the designer tries to minimize the maximum damages which enemy entity would put on the network.

At designer level, the objective is to maximize the robustness (similarly minimize At designer level, the objective is to minimize the vulnerability of the network, by investing the available budget/resources in the expansion of the current capacity of links, by adding new lanes. Therefore, the designer makes his decision by adding new lanes to the network, considering his budget as a constraint. Then, the model examines the maximum damage that an adversary can inflict on the network, by incapacitating the links. Again, the model considers the limitation on adversary’s available resources/budget. Hence, the goal at upper level can be modeled as equation (7).

illustration not visible in this excerpt

where Dy Z represents the total payoff to the adversary. The value of the payoff can be considered as the increase in total system travel time. Therefore, the adversary can look for the damage which results in the maximum possible travel time of users of the system. In this case, the objective at the upper level may be written as:

illustration not visible in this excerpt

The decision of the designer and adversary are constrained by the following limits:

illustration not visible in this excerpt

Where Bd and Bz respectively represent the budget available to designer and adversary, ga is the total cost of adding ya lanes to link a, and da is the cost of constructing one lane for link a (eq. (11)). Finally, constraint (12) and (13) respectively requires non-negativity of designer’s decision, and the binary decision of the adversary entity:

ya ≥ 0, Va E A za = (ОД): Va E A

where za = 1 shows that link a is disabled, and za = 0 indicates that link a is not affected. The result of the upper-level of bi-level model is available to the users. The users’ move, is done after the first two players find their decisions, and passed it to the user level. In the next section, the behavior of users in reaction to the decisions made at upper-level is discussed.

3.4 Frameworks for vulnerability/robustness

In the proposed model, the infrastructure that is selected for investment by the designer might also be selected by the adversary. The model does not prevent the designer from investing in these type of infrastructures that are attractive to the adversary entity. One question may arise concerning why investing in a component, which the investment also makes it more attractive to the adversary.

A short answer can be provided by a simple example. Figure 4a shows a basic network of two links, connecting the same origin to a destination. There is a total flow of 100 units, which at the equilibrium, 70 units take link 1 and 30 units take link 2.1f the decision of the designer is to increase the capacity of the links, he has two options: scenario 1 to invest on link 1, and scenario 2 to invest on link 2. If the investment goes to link 1, it will be more attractive for the current users, which will result in diverting more traffic to link 1. If the adversary wants to damage this network by disabling one of the links, the worst-case scenario would be attacking link 1, since it carries the mainstream network since link 1 carries more traffic (Figure 4b).

illustration not visible in this excerpt

a) Base network b) Scenario 1 : Improvement on link 1 c) Scenario 2: Improvement on link 2

Figure 4. Example of investing and getting attack on the same link

On the other hand, if the designer decided to invest on link 2, the flow will be distributed more uniformly over the network, which decreases the total possible damage (Figure 4c). In this case, if the adversary decides to disable link 2, the maximum flow that he can affect is 60. On the contrary, if he decides to disable link 1, he will be able to gain more than the payoff from disabling link 2. A similar pattern could exist in networks that are more complex. By comparing the two scenarios, it can be concluded that even if the investment goes to a link that will be more vulnerable and more attractive to an adversary, it might be the case that this decision reduces the maximum potential damage.

3.4.1 Hierarchy of Decision Flows

Many decision processes consist of a hierarchy of decision makers, and at different levels of the hierarchy, decisions are to be made. One of the common approaches to deal with this kind of problems is to focus on one level and consider the decisions of the other levels as constant. The constraint domain of a multilevel problem is implicitly determined by a series of problems that should be solved in a predefined sequence. The general formulation of multilevel optimization problem (P) can be presented as follows (Migdalas, 1998):

illustration not visible in this excerpt

The first level problem Pi, represent the problem of the first player in the hierarchy. The decision maker at Pi tries to minimize his objective function ƒ!, by controlling the decision variable X1. This problem (P) known to be np-hard. Even a bi­level linear optimization problem is hard to solve and verify.

The bi-level problem of leader and follower was first proposed by Stackelberg (1952). The general bi-level programming problem (BLPP) can be written as follows:

illustration not visible in this excerpt

In the above formulation, 􀜺 is the feasible set of 􀝔 variables, and 􀜻 is the feasible set of y variables, which possibly depends on X. Similarly, a simpler mathematical formulation for BLPP can be written as: (Pi) min F(x, y(x))

illustration not visible in this excerpt

where y(x) is a solution to the lower level problem P2, for any fixed X variables.

illustration not visible in this excerpt

a) Conventional bi-level

illustration not visible in this excerpt

b) A conventional sequential minimax model

illustration not visible in this excerpt

c) A tri-level DAD model (G. Brown et al., 2006)

illustration not visible in this excerpt

d) A multi-objective bi-level model

Figure 5. Examples of hierarchy of sequences of players moves and stnic tures of games

Graphical representations of conventional bi-level, minimax, tri-level, and multi­objective bi-level problems are presented in Figure 5. Each pattern inside the circles represents different objectives. For instance, in the bi-level problem in Figure 5a, the leader problem at the upper-level problem ULP implicitly controls the lower level problem LLP, by feeding it with his/her own decision. Then, the LLP solved using the fixed decisions from ULP. The decision maker at ULP observes the reaction from LLP and further proceeds finding the optimal solution for himself/herself considering a stable solution at the LLP.

illustration not visible in this excerpt

Figure 6. Examples ofa hierarchy of three decision flow

The hierarchy of the decision makers’ tree in a three level optimization is presented in Figure 6. The decision makers at each level try to implicitly control the decision of his/her nested problems. In other words, the decision maker at each level is provided with a set of feasible solutions governed by its leader(s). The flow of the optimal solution at equilibrium is highlighted by the thicker lines.

3.4.2 Multi-period plan for NDP

The goal of classical network design problem is to find solutions that improve the network in a single period. Planners usually need to have the flexibility to change, delay, or abandon the future investments. In real world problems, the decisions of investment are usually spread over many years in the future. Therefore, models to find sequencing network investments over time are developed. An example of a multi-period NDP for the set of T periods is presented in equations (17) through (26).

illustration not visible in this excerpt

where Bp is the available budget at time period p, and Сд is the capacity of the link a at time period p. Variable Уд is the capacity expansion vector on link a at time p.

Figure 7 presents a numerical experiment on investing on the Braess network over a 3 year span. The investment budget is в 1=50 for the first year, B2=20 for the second and B3=30 for the last year.

illustration not visible in this excerpt

Figure 7. An example of the multi-period NDP results for Braess network

3.4.3 Model 1: Bi-objective Designer Model

Concentrating on reducing the effects of potential disruptions to the network, may distract the focus of the designer from the important objectives in NDP under normal conditions. In this case, the investments on important infrastructure might be diverted to infrastructures that are beneficial after the disruptions. However, it is possible that no disruptions occur. Hence, there is a tradeoff between focusing on improving the system under normal condition and after disruption events. An intellectual approach would be simultaneously considering both aspects of reducing the system-wide cost, and the potential vulnerabilities. The aim of the designer/defender is to invest on projects such that the social welfare and robustness of the network are maximized simultaneously. The methodology presents a bi-objective formulation for the road network planner to model the cooperation of the goals.

The general formulation for this model is presented in equations (27) through (31).

illustration not visible in this excerpt

in which z(y) is the solution to the problem A in equations (29) and (31); likewise, x(y) and x'(y, z) are the solutions to the problems и and u' in equations (30) and (31) respectively. Statements (27) and (28) form a bi-objective problem, which tries to reduce the total system cost of the network simultaneously at the normal condition (before attack) and at the degraded condition (after attack). The model formulation is written in (32) through (50).

illustration not visible in this excerpt

The defender/designer of the network not only minimizes the overall cost to users, similar to the conventional urban network design problems, but also they attempt to reduce the potential effect of any intelligent adversary movements. The decision of the designer implicitly affects the behavior of the users and the potential moves of the adversary entity. Therefore, the hierarchy of decision flow starts from the designer at level LÍ. From a high-level perspective, it has two objectives: minimizing a performance measure (e.g. total system travel cost), and concurrently minimizing vulnerabilities.

There are two players in the next sequence of the hierarchy structure of decision makers (L2): a user player for the normal condition of the network, and an adversary. The network modified by the adversary provides input data for the last player in the hierarchy sequence of decisions (L3). This user level is based on Wardrop’s first principle. His first principle states that no user can experience a lower travel time by unilaterally changing his/her routes. The road users individually select routes such a way that their travel costs are minimized, while the planners look for the best network improvement but have no control over the users’ route choices. Similar rules apply to adversary-user interactions, in which adversary entity has implicit control over the users’ decisions.

In equations (32) through (50), two separate user equilibrium problems are defined. The first problem is on the second level of optimization, which provides information regarding the flow in an undamaged network. The second one is at the third level, which feeds the adversary problem with information about the degraded network. The variables for the second user equilibrium problem are differentiated using the apostrophe after the variables’ letters.

Constraint (34) represents the total available budget Bd for network capacity improvements. Similarly, Constraint (50) shows the limitation on the number of elements that adversary entity can damage. The investment cost function at constraint (35) is adopted in the same way as Suwansirikul et al., (1987) and Abdulaal & LeBlanc (1979).

The bi-objective problem in equations (32) and (33) can be combined and form a single objective problem using weighted sum method:

illustration not visible in this excerpt

where(ץ)is the weight parameter. In this convex combination, the weighting factor tends to promote decisions toward the desired objectives.

3.4.4 Model 2: A Zero-Sum Model

Looking at the system-wide view to the network, the decision of the intelligent adversary could be reverse to the designer/defender, in the sense that both players try to minimize/maximize the total cost to the users. If the objective of both of the mentioned players is the same, the problem lies in the category of zero-sum games. In zero-sum games, the payoffs from one player to his/her opponent have the same value. Minimax problems are similar to the Stackelberg games, in the sense that two non-cooperative players form the game. However, in contrast to Stackelberg games in bi-level programming problem (BPP), minimax programs establish constant-sum games, where the two players have the same objective function (to be maximized for one player, and minimized for another one). This type of programming suitable for optimization under uncertainty and each player decision is in reaction to the other one in most destructive manner. Therefore, at any stage, each player is interested in a strategy which minimizes the worst possible future contingency (Tsoukalas & Wiesemann, n.d.) (Figure 5b). An example of minimax problem is the game of chess. In this game, each player tries to optimize his/her objective, which is a utility function that works as a scoring operator. The sequential movements of each player could end at the final move with the associated score of win, lose, or draw. The score at each node of the hierarchy is calculated by summing up the defined utility function’s scores, from leaves to that node. The optimal solution for the player at the root is the worst score for the opponent at the nodes right after the root.

The general formulation of this model is presented in equations (55) through (57):

illustration not visible in this excerpt

The proposed zero-sum based game for robust NDP against intelligent disruptions is formulated in equations (58) through (70):

illustration not visible in this excerpt

An important feature of this problem, and more generally of bi-level programs, is the hierarchical relationship between two independent, and possibly conflictual, decision makers. Mathematical program in equation (58)-(64) and (65)-(70) are connected using shared variables, specifically the decision of designer ya and adversary za at upper level, and flows xa at lower-level problem. Another important thing that should be noted is the fact that the decision of the planner cannot be computed until flows are known. This issue can be addressed by passing an initial vector of flows to the upper level, found by solving the flow assignment for the basic network. The designer and adversary cannot control the flows directly, but they can implicitly direct the users.

In the next chapter, solution algorithms to the problems defined in this chapter are provided in details.

4 SOLUTION METHODOLOGIES

4.1 Introduction

In this chapter, solution methodologies to the problems of the three players in the frameworks defined in chapter 2 are discussed in detail. First, the complexity and the feasible Region of the problem are investigated.

The Network design problem (NDP) is defined by (Friesz, 1985) as identifying a subset set of graph edges satisfying a set of constraints with minimum total weights (or costs). Such problems are combinatorial and NP-hard in nature.

Figure 8 demonstrates the քօ1Մ possible ways of creating an undirected network with three nodes. L·i the case ofa network with three nodes, at least, two links are needed to connect all nodes. The total number of different network confi^ations can be obtaüıed using the following eq^tion.

illustration not visible in this excerpt

Figure 8. Four possible combinations of undirected graph with three nodes

Number of possible networks [illustration not visible in this excerpt]

where n is the number of nodes in the graph. Figure 9 shows the number of possible undirected networks by the number of nodes. As it can be seen, the number of possible undirected graphs is growing exponentially by increasing the number of nodes.

illustration not visible in this excerpt

Figure 9. Number of possible midirected networks by number of nodes

In this example, the decision is whether to construct a link or not. In practice, other decisions like the number of lanes to be added, speed limit, signal timing and toll pricing might be considered. Therefore, due to the combinatorial nature of this problem, the domain size of the feasible solutions grows exponentially. For instance, if adding up to 5 lanes is considered in a problem, the size of the feasible solution will be as Figure 10.

illustration not visible in this excerpt

Figure 10. Domain size ofLaiie Addition (Discrete \Tariable)

For the users of the network, the feasible region of is his/her route choice. The assignment of flow to the links can be presented at node level (using nodes’ input/output, correspond to each OD demand), paths and bushes originated at each origin.

The decision of the adversary entity is to remove or reduce the capacity of specific section(s) of networks nodes, links, or a combination of nodes and links. The damage to the network can be applied by destroying a bridge or tunnel, staging a car accident, and stalling a vehicle. Models like (Qiang & Nagurney, 2007) and (Wu, Guo, & Wang, 2014) utilized the dynamic indicator of vulnerability by considering the availability of alternative routes. These models usually require computationally expensive algorithms (e.g., calculating a large amount of shortest paths and/or finding equilibrium flows). Similar to the network design problem, modeling the problem of an adversary entity as a modifier of network’s edges and vertexes is also a combinatorial problem. For an instance, consider a network that consists of 200 nodes and 1000 links. Reducing the capacity of (or completely removing) one node can be done in (2°°) = 200 different ways. If two nodes can be selected, the total number of possible combinations is (2°°) = 19,900. Similarly, expanding the limit to 10 nodes, make the size of solution feasible space equal to 2.2el6. If the decision were to focus on disabling links instead of nodes, the size of the problem would be even larger. In general, the larger discrete feasible space will require more time and effort for search algorithms to solve the problem.

Several studies have tried to decrease the size of the problem by discretizing the continuous feasible space into counterparts. For instance, in Jenelius’ approach, the geographic map of the network is divided into grids (fixed or variable sizes) (Jenelius, 2011 ; Jenelius & Mattsson, 2012). The grid based analysis method is said to be a vital complement to the existing studies of single link failures, since various types of events such as storms, wildfires, floods, and snowfall can cause widespread degradations in transportation network. In this way, the damages to the network affect the grids, which their size of the feasible region is usually smaller than the complete network. In his study, decreasing the size of the cell grids from 50 km to 12.5 km increased the calculation time (the time required for calculating the importance of every cell and the exposure of every county for a specific grid) from 2.5 hr to 10 hr.

Based on the type of variables in the programming models, various approaches have been used in literature to solve the NDP. For discrete NDP problems and non- convex problems (e.g., combinatorial optimization and integer programming), exact methods like enumeration and branch and bound and metaheuristics (e.g. genetic algorithm and simulated annealing) have been used. For continuous NDP, technics like gradient-based algorithms, Iterative-Optimization-Assignment (10A) algorithm, and sensitivity analysis based algorithms are common. Furthermore, other technics such as convert bi-level problems to single-level, and global optimization are of interest to researchers.

If the domain at design or adversary level is integer, a branch and bound method for small/medium size problem is found to be a good solution approach. Studies like Leblanc (1973) utilized Branch and Bound technique to solve the NDP problems. Further improvements on this method have been done in later methods like Bard’s algorithm (LeBlanc & Boyce 1986). However, Discrete variables make the problems NP-hard and non-convex. Therefore, exact methods like branch and bound method cannot solve these problems efficiently.

More efficient heuristics methods were discovered later. Heuristics are usually developed from the insight of the problem, but there may not be convergence (Farahani et al, 2013). Some of the heuristics approaches have been discussed in chapter 2. Many engineering problems deal with functions and/or constraints that their derivative information, either cannot be efficiently obtained or is not available. Methods like Derivative-Free Optimization (DFO) and Metha-Heuristics has latterly received considerable attention. For larger problems, metaheuristic approaches like Genetic Algorithms or Ant Colony approach showed a good performance to solve the NDP related problems. Table 7 presents a review of the metaheuristics approaches for solving network design problems. No studies found that utilized the Genetic Programming (GP) approach. However, it might not be a suitable approach for these types of problems.

Table 7

Metaheuristics algorithms for NDP

illustration not visible in this excerpt

Several studies tried to convert the bi-level problem into a single level problem. Methods like Benders decomposition were used in several studies (Gao et al, 2005; Martin 2007). Karush-Kuhn-Tucker conditions are also used to get the advantage of the dual problem of user equilibrium, and force its associated constrained in the bi-level problem to be feasible (Allende & Still, 2013; Dempe & Zemkoho, 2012; Wan, Mao, & Wang, 2014). However, the single level problem is not necessarily simpler than the bi­level problem to solve. The reason is the fact that the newly introduced constraints increase the complexity of the solution algorithms for the leader problem.

The overall flowchart of the solution algorithms for the three decision makers in model 2 (chapter 3) is presented in Figure 77. It should be noted that to keep the diagram simple, the convergence criteria for user-level problems is not demonstrated in this figure. The dashed box represents the inner bi-level problem of adversary and users. First, at the designer level, a base feasible network enhancement vector (y) is selected and passed to the bi-level problem of adversary and users. The adversary chooses a vector of decision to degrade the network (z). The new network, which is affected by decision of designer and adversary (z and y) will be transferred to the user level at the bi-level problem of adversary-users. The user level problem, provides a new link flows vector (x) which is passed to the adversary level. The adversary-level objective function will be computed to produce a new vector (z), and will be delivered to the user-level. This procedure is repeated until convergence. A second user-level problem, which shows the behavior of user (x') to the decision of designer (y) under normal condition, will be evaluated (independent of X and z). Then optimal solution of the bi-level problem of adversary-users (z) after convergence, along with users reaction under normal condition (.X׳) will be evaluated at designer level problem to determine the convergence. The procedure will continue until the convergence of the designer level will be satisfactory. Since there are multiple objective functions in designer level, a set on non-dominated chromosomes in a Pareto front will be formed.

illustration not visible in this excerpt

Figure 11. Flowchart of the Solution Approach

In the following sections, a detail review of the solution algorithm for each players is presented.

4.2 Algorithm for Users

Since the user level problem is a nonlinear derivable convex problem, it can be solved using efficient heuristic algorithms such as the Frank-Wolfe algorithm (FW), bush algorithm, gradient descent, and many other available gradient-based algorithms. The model formulation for Frank-Wolfe algorithm (also known as reduced gradient and convex combination algorithm) is provided in equations (2) through (6). The heuristic search algorithm is used for convergence of the objective function to its optimal value using the associated direction vector’s move size. The objective function is the sum of the integrals of the link performance functions. The steps of the Frank-Wolfe algorithm are as follows:

Step 0: Initialization

Perform all-or-nothing assignment based on ta = ta(0) Va. A new flow vector {xa} will be generated. Set counter n = 1.

Step 1: Update Set ta = ta(xa) Va Step 2: Finding Direction

Perform all-or-nothing assignment based on {ta}. A new auxiliary flow vector {x’a} will be generated.

Step 3: Line search

Find an (0 < a < 1) that solves equation (72):

illustration not visible in this excerpt

The line search problem is solved using bisection algorithm (Bolzano search). The converge criteria for the bisection method is defined as the distance between the lower bound and upper bound of the current section in bisection iterations.

Step 4: Move

Move to the new solution using equation (73).

illustration not visible in this excerpt

Step 5: Convergence test

If the convergence criterion is met, stop and accept the current solution {Xa+1}, as the set of equilibrium link flows. If the convergence criterion is not met, set n = n + 1 and go to step 1. The convergence is tested using equation (74):

illustration not visible in this excerpt

The Frank-Wolfe algorithm is relatively simple to implement and has a fast convergence in the first iterations. Since the update step is “one-at-a-time” generically, it is not parallelizable for better computational performance.

4.3 Algorithm for Designer and Adversary

In this research, decisions of the designer/defender and adversary are considered as discrete variables. In addition, since their objectives are nonlinear and non-convex, they fall into the category of NP-hard problems. Therefore, efficient exact and heuristic solutions do not exist, and approximate algorithms like meta-heuristic algorithms would be the best approach for medium to large-scale sizes of these types of problems. Meta­heuristics are a subfield of stochastic optimization that combines basic heuristic methods in higher-level frameworks, and their goal is to search effectively and efficiently. They are especially suited for problems with imperfect or incomplete information or limited computation capacity.

One of the population-based meta-heuristics is the category of evolutionary computations’ (EC) algorithms, and one of the well-known and efficient technic in the categories of EC algorithms is the Genetic Algorithm (GA). A genetic algorithm is a search heuristic that mimics the procedure of natural selection. The GA works by evolving a population of candidate solutions, also known as individuals or phenotypes, toward better solutions. Each candidate solution has a set of properties, which is its chromosome or also known as genotype. Its process routinely produces a new population by mutating and altering the current population. Each population - also known as generation - contains the candidate solutions.

The solution algorithm for the three-player model can be written as follows:

Step 0: Find an initial solution for the designer and user level Step 1: Find the next solution for the designer

Step 2: Calculate vulnerability measures of links from attacker point of view, and

select the most vulnerable ones to be attacked

Step 2-1: Find the user equilibrium flows base on decision of designer and attacker, and feed them

Step 3: If the designer solution is converged, finish. Otherwise, go to step 1

The problem size can vary based on the number of the links in the network, the number of the lanes, the number of nodes, and improvement approaches. A genetic algorithm is especially suited to deal with multi-objective problems.

The chromosomal representation for the designer and adversary is described in the next section. The problem of the upper level can be defined as a multi-objective problem. In a multi-objective problem, more than one objective is optimized at the same time. A good solution approach would be combining the objectives of the designer and adversary into a monotonie objective function. This monotonie function has the set of variables of both original objective functions, which can be solved using algorithms like GA.

The designer’s objective function result will be a trial additional number of lanes vector (ya). The designer’s decision variables are limited by the budget and resources constraints. The decision of the designer and adversary modifies the network, and passes it to the next player in the defined sequence of decision flow. The pseudo code of the algorithm is presented briefly as follows:

Step 0: Initialization. Create an initial random population of organisms (potential solution).

Step 1: Evaluate. Evaluate fitness of each organism/chromosome

- For the adversary, the fitness value is based on running traffic assignment on the degraded network, defined by the individual adversary solutions.
- For the designer, the fitness value is based on the new design of network defined by the individual designer solutions, which might be degraded by the adversary as a median player.

Step 2: Convergence criterion. If the fitness of all evaluated organisms demonstrates a good solution, then the procedure is finished. Otherwise, go to step 3.

Step 3: Exploit. Eliminate the weak organisms and produce new organisms based on individuals in the population with better fitness.

Step 4: Explore. Stochastically mutate organisms’ genes. Then repeat the process starting at step 1.

4,4 Decoding and Chromosomal Representation

Decoding is about representing the genotypes in a real phenotype feasible space. Each individual variable, when encoded into genotype, is converted to the real representation value of the objective function. Therefore, the output of the decoding function makes the suitable variables for inserting into the objective function(s). A computationally efficient representation for chromosomes is a one-dimensional series of binary variables. A simple example of decoding a binary representation of the chromosomes for the designer and adversary, using 3 bits of data, for 3 links is presented in Figure 12.

illustration not visible in this excerpt

Figure 12. Decoding Procedure

In the defined encoding/decoding procedure, the actual genome in a genetic algorithm process is first converted from the stream of binary values, into an integer representation value. If the integer number was greater than the defined upper bound value, the chromosome is not a legitimate solution, and it should be discarded. In this case, a new chromosome should be generated and checked for validity. This process should continue until a valid chromosome is found. This genotype representation can be used as a general form that can be scaled to any desired boundary defined by the specific problem. Depending on the boundaries defined by the specific problem, the integer representation value can scale the output of a genetic algorithm to the size of decision variables of the problem. The decision maker should be aware of the boundaries of the decision variables of their problem. Therefore, they can be confident that the genetic algorithm progress would not miss any solutions, because of not being able to touch all the feasible space of the problem. In the above example, each variable is encoded into 2 bits of data. Therefore, the scale of the genotype of each variable is ranging from 0 to 3. The boundaries of the phenotype variables in the actual problem are defined by the feasible space of the problem. In this case, each non-negative variable has a maximum value of three as their upper-level value. This value in the next step is used to scale the genotype value range to the actual feasible space range. The constraint of the adversary entity, which is the number of links that can be affected by its problem, can implement in the decoding/encoding procedure (Figure 13).

illustration not visible in this excerpt

Figure 13. Genotype chromosome representation of adversary entity

In this approach, the alleles with a binary value equal to one in the corresponding chromosomes represent the attacked links. The upper bound of the adversary budget constraint is defined by the summation or equivalently the total number of 1 s in the corresponding chromosomes. To have the problem feasible, in the solution algorithms, the mutation operators should be avoided. The moves in the genotype space can be performed by crossover operators.

To test the algorithm, and perform sensitivity analysis on the properties of the genetic algorithm, bi-level network design problems were defined for two small test networks. The network configurations are described in the next sections. The objective functions in network design problems are usually minimization. Therefore, a ranked based roulette is a good approach for the selection. The population size for the both problems is 100 individuals.

4.5 Genetic Algorithm Operations

In order to appropriately configure and implement the genetic algorithm technic, it is crucial to understand the GA operators and parameters. In this section, a review of the GA operators and the sensitivity to their parameters, along two NDP test networks are presented.

4.5.1 Example Network 1 - Braess Network

The first network is the simple Braess network (Figure 14). The Braess network data, demand and link attributes are adopted from the Suwansirikul et al. (1987).

illustration not visible in this excerpt

Figure 14. Test Network إ -Braess Paradox Network (5-Lmk)

The upper-level objective function for this network is total system travel time (Σ X= t). The lower level problem is based user equilibrium, defined in equations (2) through (6), with the Bureau of Public Roads (BPR) travel time-congestion function defined in equation (1). Table 8 presents the necessary input data that for the first test network.

Table 8

Data for Test Network 1 (5-Link)

illustration not visible in this excerpt

4.5.2 Example Network 2-16 links network

The second test network consists of 6 nodes and 16 links (Figure 15). Two OD pairs from nodes 1 to 6 and nodes 6 to 1 provide the flows on the network. Three cases of travel demand levels are used for illustration where case 1 = 2.5 - 5.0, case 2 = 5.0 - 10.0, and case 3 = 10.0 - 20.0. The travel time and investment cost functions used in problems 9 and 10 are adopted from Suwansirikul et al, (1987) together with the details of data input for each link.

illustration not visible in this excerpt

Figure 15. Test Network 2 (16-Link)

4.5.3 Decoding/Encoding Genotype-Phenotype Space

As it was described and shown in Figure 12, a good approach to encoding and decoding the phenotype space can be using a one-dimensional series of binary variables. The precision of the decoding and encoding operators directly depends on the number of bits assigned to each variable.

illustration not visible in this excerpt

Figure 16. Variation of reaching the solution by different size of bit-string in binary chromosome representation.

Figure 16 presents the convergence of the solutions in the Braess network, by six different bit-string size of decoding and encoding operators: 2, 4, 8, 16, 32, and 48 bit. The higher size of bit-string as a binary representation (for values in the actual problem) in phenotype space makes the solution become more accurate and provide better precision. If the decision maker is concern about a specific level of accuracy in the optimal solution, he or she can achieve that by choosing an appropriate length of bit­string. It should be noted that choosing a big size for bit-string would result in higher computational time. Furthermore, the convergence rate is also should be considered in deciding the best bit-string size for the GA decoding and encoding operators. A smartly chosen value can satisfy both accuracy and the computational time.

4.5.4 Elitism

Retaining the best individuals in unaltered from current generation to the next generation, is called elitism or elitist selection. It helps to avoid losing the best solution found, possibly by GA operators. This strategy guarantees that the solution quality obtained by the GA will not decrease from one generation to the next.

illustration not visible in this excerpt

Figure 17. Elitist selection with different size, for population size 100t

Figure 17 shows a variant of the best solution found in the ULP using Genetic Algorithm, with three different size for Elitism: no elitism, keep one best solution, and keep the best four solutions found. As it can be seen, the no elitism strategy, in some of the generations, losses the best solutions found, which resulted in increasing the minimization objective value. Retaining one best solutions in generations, avoids losing the best solution, which resulted in monotonically decreasing the objective value. Furthermore, increasing the size of retaining individuals to four further helped to have faster convergence. In this example, the size of retaining individuals larger than four percent did not significantly help the convergence of the algorithm procedure.

4.5.5 Crossover Operators

Crossover is a genetic operator used to vary a chromosome or chromosomes from one generation to the next, by combining the current chromosomes. It is analogous to reproduction in nature, upon which genetic algorithms are based. Crossover is a procedure of taking a portion of the solutions and generating offspring solutions from them.

illustration not visible in this excerpt

Figure 18. Different Crossover operators (Crossover rate 10%)

Figure 18 shows different types of crossover and their convergence rate. In this example, the only active GA operators were the crossover operators and the selection. No mutation operator is considered in this example, and the initial population of the solutions is populated with random individuals. Considering these assumptions, the Uniform Crossover (UPX) demonstrates the best results among other crossover operators. The results are based on stochastic nature of GA, and they might not show the same performance on different problems. However, it can give ideas to researchers that how each operator behaves in different problems.

illustration not visible in this excerpt

Figure 19. Convergence of capacity expansion vector to optimum values by crossover rate (crossover type: Uniform Crossover (UPX), mutation rate: 2%, population size 30)

Figure 19 shows the sensitivity of the model to crossover rates. The optimum capacity expansion vector for this example was {7.1, 0, 0, 0, 3.39}. As it can be seen in the figure, the optimum value for crossover rate was not at extremes 0 or 100 percent. The best value for crossover rate for this specific problem was found at around 50 percent. Figure 20 presents the sensitivity of GA convergence to the mating rate. In this test, the mutation rate was 0 percent and the initial populations of the solutions are populated with random individuals. In Figure 20, the higher mating rate shows faster convergence at the cost of lower quality of the solutions.

illustration not visible in this excerpt

Figure 20. Crossover values by Mating rate (one-point Crossover)

4.5.6 Mutation Operator

Mutation is a genetic algorithm operator used to keep genetic diversity from one generation of a population of chromosomes to the next generation. Its operations are similar to biological mutation. Mutation alters one or more gene values in a chromosome from its original state.

illustration not visible in this excerpt

Figure 21. Sensitivity test of the convergence to mutation rate

Figure 21 presents the sensitivity of convergence of the bi-level NDP to different the mutation rates. As it can be seen, the mutation rate has significant effect on the speed and quality of reaching the optimal solution. The low values of mutation may prevent exploration of not-visited feasible spaces and may slow down the genetic algorithm procedure. On the other hand, the high values of mutation may lead to a stochastic search that does not keep track of previous results efficiently. For this specific problem, a value close to two percent shows the best performance.

4.5.7 Sensitivity Analysis of Demand on Test Network 1 and 2

Figure 22 and Figure 23 show the graphical results for the sensitivity to demand for the following variables: the optimal capacity expansion vector, flow, and objective values for the upper and lower levels. The sensitivity of test network 2 to demand was tested for three different sets of О/D pairs. For this specific example, the higher demand shows faster convergence rate. The network users’ reaction to the changes in capacity expansion vector was evaluated by iteration. This reaction guides the direction of the search for the optimal solution to NDP.

illustration not visible in this excerpt

Figure 23. Total System Travel Time for Test Network 2 - (16-Link)

In the next chapter, implementations of the models presented in chapter 3 are discussed.

5 NUMERICAL EXPERIMENTS

This section discusses the results obtained from the methods covered in the previous section. Several numerical experiments were conducted in order to evaluate the performance of the models and observe the results. To implement the solution algorithms, the designer and adversary level algorithms were coded and solved in MATLAB. The user level algorithm was implemented in c++. The methods were processed on a 64-bit computer with an Intel İ7-960 processor and 24GB of RAM.

5.1 Model 1: Bi-objective Designer Model

Numerical experiments are conducted for the Sioux Falls network in order to evaluate the proposed methodology. The network consists of 76 links and 24 nodes, which are also, defined as the demand origin/destinations. Links and nodes ID and the lengths of the links are provided in Figure 24a and Figure 24b respectively. It is assumed that all the links in the initial network have three lanes. The links attributes and OD trips were adopted from (Suwansirikul et al., 1987). All of the links of the network are considered to have three lanes.

illustration not visible in this excerpt

a) Links and Nodes IDs

illustration not visible in this excerpt

b) Length of the lmks

Figure 24. Sioux Falls network configuration

The О/D matrix for these experiments is presented in Table 9. Similar to test network 1, two scenarios were performed on this network using different budget available to the adversary.

Table9

The Trip rates for the Sioux Fails network (1000 veh/time unit)

illustration not visible in this excerpt

Figure 25 demonstrates the 14 candidate links that are selected for improvements (Link numbers 13, 23, 30, 51, 27, 32, 34, 40, 49, 52, 53, 58, 39, and 74).

illustration not visible in this excerpt

Figure 25. Links Included in Expansion (links with orange color) for the Sioux Falls network

For the first experiment, the attacker upper bound was limited to 1 link. The three level algorithm performed to solve this problem. The designer level problem is a bi­objective problem of minimizing the total system travel time, and the total system travel time of the damaged network, which is obtained by solving the attacker problem in the second level of the model.

The designer decision is limited by the construction budget, which is available to them. In this experiment, the budget is assumed 20 million dollars. Their decision of adding lanes to the current links is also constrained by an upper bound of a maximum of three lanes per link.

For the designer, a population size of 50 indivi duals/chromosomes was considered; the chromosomal size for and attacker problem was 20. For the designer and the adversary problems, respectively 100 and 20 generations were populated by the individuals in each iteration of the optimization process.

illustration not visible in this excerpt

Best fitness value for designer objective 1 (TSTT imder damaged condition)

illustration not visible in this excerpt

Best fitness value for designer objective 2 (TSTT under normal condition)

Figure 26. Improvement of the two objectives at the designer level by generations

Figure 26 presents the trend of improving the two objectives of the designer/defender. As it can be seen in the figure, the designer objective under normal condition converged to its best solution after 16 generations. The convergence for the objective of the designer under the degraded network, which is damaged by the attacker best decision, occurs after 21 generations. The elitism selection feature of the genetic algorithm, prohibit the best solutions to be eliminated. Therefore, the best solutions retained in the rest of the optimization process.

illustration not visible in this excerpt

Figure 27. Individuals of the two objectives at the designer level by generations

Figure 27 presents the movements of the individuals by generations. As it can be seen in the figure, individuals tend to be closer to the best ones by proceeding in generations. The red dots represent the Pareto frontier solutions. The solutions with bad fitness values are removed during the process of the genetic algorithm. In the last iteration, all the individuals are confined to the best solutions. The best decision for the designer is to choose the solution from the Pareto front of the last generation. In this example, the optimal solution found was adding one lane to link 23, 34, 39, 40, 49, 53, 58, and adding 2 lanes to links 13, 27, 32, 51, 52, 74, and adding three lanes to link 30.

illustration not visible in this excerpt

Figure 28. Decision of the designer (Number of lanes to be added to the network).

The final decision of the designer is represented in Figure 28. The optimal decision of the adversary entity under the initial network and improved network conditions are provided in Figure 29. The numbers on links in the figure show the total number of lanes to be added to the links.

illustration not visible in this excerpt

Figure 29. The optimal decisions of the attacker

The initial total system travel time under normal conditions is reduced from 7.48xio6 minute to 5.98x1 o6 minutes in the improved network. Considering the degraded network after the attack, the total system travel time is 7.80/1 o6. This value is comparable to the value for the initial network after the attack, which is 10.89/1 o6 minutes. Figure 30 presents the changes in the total system travel time after the improvement. The additional system cost due to the attacks is represented by red stacks over the network under normal condition, which represented by blue bars. The addition of the new lanes to the network could reduce the total system travel time by 20.1 percent. However, the improvement by the proposed model is more significant from the vulnerability perspective. The new improved network could reduce the imposed additional system cost from 3.41 xio6 minutes to 1.82/1 o6 minutes, which is 46.4 percent less.

illustration not visible in this excerpt

Figure 30. Improvement of the capacity-expanded network compare to the initial conditions

The volume of traffic flows in the Initial and Improved network, and before and after the disruptions is presented in Figure 31. The addition of the lanes to the links, make them more attractive to the travelers. As it can be seen in Figure 31b and Figure 31c, damages to the links make traveler reroute and use alternative way, which makes higher cost on the spare paths.

illustration not visible in this excerpt

a) Initial network

illustration not visible in this excerpt

b) Improved network

illustration not visible in this excerpt

c) Initial network after the disruption

illustration not visible in this excerpt

d) Improved network after the disruption

The cost of travel in terms of travel times are provided in Figure 32. As it can be seen in the figure, the travel times are reduced in the improved network. The model increased the travel times of the damaged links, which penalize the use of them by the users. The links with hotter color in Figure 32 represent the higher travel times. The damages to the link 43 in the initial network reroute the users to its available alternative paths. Therefore, a percentage of the traffic volume transferred to other links, which especially can be seen on links 40, 48, and 51.

illustration not visible in this excerpt

a) Initial network

illustration not visible in this excerpt

b) Improved network

illustration not visible in this excerpt

illustration not visible in this excerpt

c) Initial network after the disruption

illustration not visible in this excerpt

d) Improved network after the disruption

illustration not visible in this excerpt

Figure 32. Travel times in the Initial and Improved network, before and after the disruption

The second experiment considers that two links can be damaged by the adversary entity. The both objective of the designer are converged after 20 generations. The goals of the individual solutions by generations are provided in Figure 33. Similar to the previous case, the chromosomes move toward the best solutions during the process of evolutionary optimization.

illustration not visible in this excerpt

Figure 33. Individuals of the two objectives at the designer level by generations

The optimal solution for the designer is presented in Figure 34. The optimal solution of the adversary entity correspond to the defender decision is demonstrated in Figure 35. The optimal solution found for the adversary was changed from the links 43 and 60 in the initial network to 23 and 27 in the improved network.

illustration not visible in this excerpt

Figure 34. Decision of the designer (Number of lanes to be added to the network).

illustration not visible in this excerpt

a) initial network

illustration not visible in this excerpt

b) improved network

Figure 35. The optimal decisions of the attacker for the initial and improved networks

Compared to the results of the previous experiment, links 34, 40, 52, 53, and 58 are collecting more investment in this test. The total system travel time for the initial network and the improved network are 7.48/1 o6 minutes and 5.97/1 o6 minutes respectively. The values for the degraded network are 13.53/106 minutes before improvements, and 11.90/1 o6 minutes after the improvements. Increasing the adversary entity’s budget, results in a larger total cost to the users in terms of damaging the network elements.

illustration not visible in this excerpt

e) initial network

illustration not visible in this excerpt

f) improved network

illustration not visible in this excerpt

g) Initial network after the disruption

illustration not visible in this excerpt

h) Improved network after the disruption

Figure 36. Flows in the Initial and Improved network, before and after the disniptions (veh/day)

The link volumes for initial and improved network, before and after the disruptions are provided in Figure 36. Similarly, Figure 37 provides the travel time of the links, under these volumes. The links with warmer color represent higher travel time. Since the damage to the links is modeled by increasing the travel time to a higher value, the travelers are not interested in using these links. However, there still exist low traffic volumes that use these links in the degraded network. This is due to the degree of damage to the network, in this test, is significant enough that a portion of users utilizes these links despite the higher cost. In other words, the damages to the mentioned links create high congestion on some of the alternative routes. The improved network influences drivers to use links other than centralized links. Hence, the potential damages that the attacker can incur on the whole network would be minimized.

illustration not visible in this excerpt

e) initial network

illustration not visible in this excerpt

f) improved network

illustration not visible in this excerpt

g) Initial network after the disruption

illustration not visible in this excerpt

h) Improved network after the disruption

Figure 37. Travel times in the Initial and Improved network, before and after the disruption (min)

Similar to the previous tests, several tests were conducted using higher available budgets to the adversary entity. To be able to compare the outcomes, the other parameters were kept similar to the previous tests. Since the size of the feasible space for the adversary is growing exponentially by increasing the budget available to him, finding a good solution would require more effort. To address this issue, the number of generations for the adversary was increased to 30 for the Bz equal to 5 links and more. This change increased the total number of user equilibrium processes from around 2 million to 3 million runs; therefore, more process time was required for these tests.

The solutions that were found in the designer and the attacker problem (before and after improvements) are presented in Figure 38 by different adversary’s budgets. It can be seen that the pattern of the investments is changing with increasing the available budget to the adversary. Different patterns of allocating resources slightly push the vehicles to reroute their initial path to a new lower cost path. These marginal changes will result in different patterns of attack by the adversary entity. However, as it will be seen in the next section, the influence of the designer’s decision on overall system cost is declining by increasing the adversary’s budgetary limit.

illustration not visible in this excerpt

Figure 38. The optimal decisions of the designer and the attacker

Figure 39 presents the flows on the links after the network is exploited by the adversary entity, under different budget available to him. Taking into account the links that are attacked in Figure 41, the higher costs of the damaged links push the vehicles to change their route to the available alternative routes. Providing the adversary with a higher available budget, makes the damages to the network more severe; in which, due to the new damages, the available alternative paths will be more restricted.

illustration not visible in this excerpt

Figure 39. Flow on the links after the disruptions (veh/day)

Under higher values of Bz, still the main target area for the adversary are in the more centralized links. Therefore, the damages limit the number of paths available through the center of the network. This new condition, force the vehicles to use the more paths with less centralized links, and the surrounding areas attract the excess flows.

illustration not visible in this excerpt

Figure 40. Travel Time of the links after disruption

Figure 40 presents the travel time of using the links of the initial network and the network after exploitation by the adversary. The travel times are presented by different budget available to the adversary entity. It should be noted that a higher value for travel time for a specified link means that fewer vehicles are motivated to use that link. The links with very high cost do not attract traffic flows. Therefore, they do not directly change the performance of the network, in terms of the total system travel time; and they have an indirect influence on the total cost of the system, by pushing the vehicles to use the alternative routes. The improvements of the network, reliefs the additional pressures due to the damages, especially for the cases with lower values for Bz. However, as the budget limit for the adversary increases, the magnitude of effects of the improvements that the robust NDP made to the network decreases.

illustration not visible in this excerpt

Figure 41 Travel system travel times by Bz in the Initial and Improved network after the disruptions

Figure 41 presents the total system travel time in the test networks, by various values for the adversary’s budget constraint Bz. From the figure, it can be argued that the damage to the network is increasing almost linearly by increasing the budget limit for the adversary. The influence of the methodology to reduce the effects of the adversary’s attacks is declining with increasing the adversary’s budget. However, large values for the adversary budget should be infrequent in reality. In addition, the test network size is not large, which makes it more vulnerable to the damages. In larger scale networks, more alternative routes are available to the users, which alleviate the pressure of the damages to the network. In adversary’s budget equal to one, the total system travel time after disruptions is reduced by 28.3%. The respective values for Bz = 2 (link) through Bz = 7 (link) were found 12.1%, 6.4%, 6.8%, 4.8%, 6.1% and 2.7%. The most benefits for the network designer were obtained at Bz = 1 and Bz = 2 (link), and it declined by increasing the budget for adversary.

The computational time required for each run with a different budget limit for the adversary was increased from around 20 hour for Bz < 5, to 28 hours for Bz > 5 (link). The additional computational time was due to the incensement in the number of generations for the adversary, which translates to higher number of computationally expensive user equilibrium process. In the next section, a zero-sum based game model will be discussed.

5.2 Model 2: Zero-Sum Game Model

Due to the nature of this study, a very basic network may not be an appropriate sample. The method requires damaging a portion of the network, and small networks consist of a few links, usually lose its connectivity. Hence, it may not represent the real world. The goal of this research is to improve the robustness of larger networks. Thus for the first example, to keep the simplicity, a network consists of 6 nodes and 16 links was selected (Figure 42). Two OD pairs from nodes 1 to 6 and nodes 6 to 1 are considered. The trips demand from node 1 to 6 is 2.5 units of flow (for example, thousands vehicle per hour (vph)), and from node 6 to 1 is 5.0 units of flow. The travel time and investment cost functions used in problems 9 and 10 are adopted from (Suwansirikul and Friesz, 1987) together with the details of data input for each link. The number of existing lanes of all the links considered as three.

illustration not visible in this excerpt

Figure 42. Test Network 1(16-Link)

Two tests were conducted on this network. First, considering the Bd = 100 budget unit (e.g. 1000 vph.mile.lane, or in million dollars using a monetary conversion factor) for the designer, and the maximum number of links that the adversary could disable considered as Bz = 1 (link). The best solution for the designer is shows on Table 10.

Table 10

The local optimum solution found for the first scenario on the 16 link network, Bz = 1 (link)

illustration not visible in this excerpt

The TSTT for the best found solution after the disruption was 96.76 time units (e.g. thousands vehicle hour during the analysis period). This is 18.4 percent improvement compare to the base network. One interesting finding was the adversary in most of the cases, only attacked link 14. Therefore, there exist varieties of solutions for the designer, with a relatively similar objective value of the upper level. This would give the designer larger available good solutions, and he could consider other factors such as lower required budget to make a decision.

The second test was conducted similar to test one, with the adversary constraint Bz = 2. The best solution for the designer is shows on Table 10 (the time units of TSTTs are in thousands vehicle hour per analysis period).

Table 11

The local optimum solution found for the second scenario on the 16 link network and for Bz = 2 (link)

illustration not visible in this excerpt

The TSTT in the degraded network for the best-found solutions in the second test was 109.74 time units for the solution number 1, and 113.07 time units for the solution number 2. This shows a 14.9 percent improvement compare to the base network, for the solution number 1. In the first solution, the adversary selected links 9 and 16 to be disabled, and in the second solution, he selected links 9 and 14. It should be noted that the behavior of response of adversary to the decision of the designer is changed in the second test. A small variation in the designer’s decision would result in changing the decision of the adversary. Hence, one can say that the higher resources available to the adversary make it more sensitive to the decision of the designer. This finding needs to be further investigated.

For the first scenarios on test network 2, the available budget to the designer considered as By = 300 budget unit. The first test was done using the one element that can be affected by adversary entity. A stochastic search was performed in order to find the best possible action for designer, against the attacks from enemy. The analysis found link 56 as the link that would be attacked under the optimal design solution of the designer of the network. The best solution according to the available budget for the designer is provided in Table 12.

Table 12

The local optimum solution for the first scenario on the Sioux Falls network, Bz = 1 (link)

illustration not visible in this excerpt

Under this design, the most vulnerable link would be link number 56. The TSTT for the best solution of the first scenario was 8.83e6 time units. It should be noted that the rest of the solutions that were examined, showed more damages after the attack of the enemy entity.

The second test was done considering two links as the enemy entity budget, and for the designer considered as By = 100 budget unit. The budget for designer selected lower compare to first scenario, because with the current equation for the designer budget constraint, the results shows a large number of links that would be selected to be improved on this scenario. The feasible space and computational time is much higher than the previous scenario. Selecting a set of potential links for the designer and adversary could significantly reduce the size of the problem. The total 2000+ solutions were examined in the analysis of the second scenario. It required running about half a million-traffic assignment to obtain the local optimal design. The total time required for this analysis was 20 hours. The results found in the second scenario on Sioux Falls network is provided in Table 13.

Table 13

The local optimum solution for the first scenario on the Sioux Falls network, Bz = 2 (link)

illustration not visible in this excerpt

The TSTT in the best solution found for the second scenario was 26.45e6 time units. This value increased significantly, due to the higher extent of damages and less available budget for improvements. The most vulnerable links in this analysis were link number 7 and 74. Link 19 was found to receive the most planner’s budget to have a more robust network.

6 CONCLUSIONS AND FUTURE RESEARCH

A quantitative method for budget allocation is essential for transportation agencies. Various objectives could be defined in order to improve the different indicators of the performance of the transportation network, for example maximizing the social welfare. One of the important objectives that the transportation agencies should consider is reducing the potential vulnerabilities, or in other words increasing the robustness of network against vulnerabilities. From this point of view, damages to the networks could be caused by natural disasters, or applied by an intelligent attacker. An intelligent adversary may look for vulnerabilities in the network to degrade its performance. At the planner’s level, allocating resources without considering the potential of disruptions by the intelligent adversary may not help reduce the vulnerabilities and their effects, or similarly, increase the robustness of the network.

To address this issue, this research presented two models for designing robust networks. The models were formulated in multi-level programming, considering flows of decisions are to be made in sequence. Therefore, a hierarchy structure of the movements is presented. The planner of the network is assumed to look for investing the assigned budget on the links/projects of the network while the enemy was assumed to damages the links. The results of the optimization of these players are passed to the lower level. The lower level problem provides flow vectors based on user equilibrium principles. The interaction between these three players forms a complex game with multi-levels optimization.

In order to deal with the proposed programming models, solution algorithms for each level of optimization (each player) were presented. Since the defined programming models for the designer and attacker are discrete optimizations, they are combinatorial and NP-hard in nature to approximate. Therefore, metaheuristics methodologies have proven to solve these problems efficiently. In this study, a genetic algorithm - which is an artificial intelligence search metaheuristic - was utilized to solve the attacker and planner level programming problems. Since the designer in the first framework has two objectives, it forms a bi-objective problem. The methodology for solving this problem can identify the best acceptable tradeoffs solutions, based upon multi-objective Pareto optimization. The last player in the frameworks is the user-level problem, which is a convex problem based on Nash equilibrium theory. The Frank-Wolfe algorithm was used to solve the defined programming model for the behavior of the users of the network.

Several test networks were examined to evaluate the performance of the two models and their algorithms. For the first model, Sioux Falls network, and for the second model, a 16 links network was used. The results showed that the proposed model could search over the possible results for the designer and choose an optimal solution for the robust network design problem. Results showed promising achievements in terms of increasing the robustness of the network against intelligent disruptions and simultaneously improving other system-wide performance measures as presented in the bi-objective model for robust network design problem. As an example, in the first model with attacker budget equal to one, considering the vulnerabilities of the intelligent adversary in the modeling could increase the total benefits (reduction in the imposed additional TSTT from the intelligent adversary entity) from 20.1% to 46.4%. The highest influence of the designer’s decision to the overall improvement of the system travel time after a disruption event was found in low values for adversary’s budget. The most benefits were gained at attacker’s budget equal to 1 and 2 links, with respectively 28 and 12% reduction in total system travel time after the improvement in a disruption event. Lower benefits gained at the higher budget for the attacker and the total benefits obtained at adversary’s budget equal to 7 was 2.7%. In the second model, similar results were found, with 18.4% improvement in TSTT compares to the base network for the adversary budget equal to 1 link, and 14.9% for the adversary budget equal to 2 links.

Further research could be performed to find a combined model considering other goals for the designer. Other objectives can include but are not limited to reducing pollution emission, safety and improving accessibility. The goal of the adversary and user could also be considered as multi-objective, to capture other aspects of their optimization models.

In this research, resources are allocated without considering the time factor of budget. Another research direction to consider is a multi-year investment, in which the budget is allocated during multi-year spans. The expected results would be the amount of budget that should be allocated for each year of the analysis period. In addition, risk analysis could be performed due to the uncertainties in demand, travel times, discount rate, and other parameters. Since a series of simulations would be incorporated into this approach, the computational performance should be considered. Furthermore, the methodologies provided in this research can be implemented on large-scale networks for testing the real-world applicability and the computational performance. Studying other metaheuristics search algorithm for the planner and adversary could make the models more suitable for the large-scale problems.

References

Abdulaal, M., & LeBlanc, L. J. (1979). Continuous equilibrium network design models. Transportation Research Part В: Methodological, 13( 1), 19-32. http://do1.org/10.1016/0191-2615(79)90004-3

Adewole, A. p. (2012). A Comparative Study of Simulated Annealing and Genetic Algorithm for Solving the Travelling Salesman Problem, 4(4), 6-12.

Allende, G. в., & Still, G. (2013). Solving bilevel programs with the KKT-approach. Mathematical Programming, 138, 309-332. http://doi.org/10.1007/sl0107-012- 0535-x

Allsop, R. E. (1974). Some possibilities for using traffic control to influence trip distribution and route choice. In Transportation and Traffic Theory, Proceedings (Voi. 6).

Alsnih, R, & Hensher, D. A. (2003). The mobility and accessibility expectations of seniors in an aging population. Transportation Research Part A: Policy and Practice, 37( 10), 903-916. http://d01.0rg/l0.1016/S0965-8564(03)00073-9

Antoniou, c., Koutsopoulos, H. N., Yannis, G, & Model-based, A. (2007). Traffic state prediction using Markov chain models, 5000, 2428-2435.

Ayala H., L. F., & Leong, c. Y. (2013). A robust linear-pressure analog for the analysis of natural gas transportation networks. Journal of Natural Gas Science and Engineering, 14, 174-184. http://doi.org/10.1016/jjngse.2013.06.008

Bard, J. F. (1998). Practical bilevel optimization : algorithms and applications . Nonconvex Optimization and Its Applications ; V. 30, V. 30, xii, 473 p. http://do1.org/10.1007/978-l-4757-2836-l

Bar-gera, H. (1999). Origin-based algorithms for Transportation Network Modeling, (103).

Başkan, о. (2013). Determining Optimal Fink Capacity Expansions in Road Networks Using Cuckoo Search Algorithm with Févy Flights. Journal of Applied Mathematics, 2013, 1-11. http://doi.org/10.1155/2013/718015

Beimborn, E. A. E. (1995). A transportation modeling primer. Inside the Blackbox: Making Transportation Models Work for Livable Communities, 2006( May 1995), 1­21. Retrieved from http : // WWW. j amescitycountyva. gov/j cep lans/2009_comprehensive_plan/ pdf/steering committee/1014_0 8models. pdf

Bell, M. G. . (2000). A game theory approach to measuring the performance reliability of transport networks. Transportation Research Part в : Methodological, 34(6), 533­545. http://d01.0rg/l 0.1016/SOI91-2615(99)00042-9

Bell, M. G. H., Kanturska, u., Schmocker, J. D., & Fonzone, A. (2008). Attacker- defender models and road network vulnerability. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 366( 1872), 1893-1906. http://doi.org/10.1098/rsta.2008.0019

Ben-Ayed, o. (1993). Bilevel linear programming. Computers & Operations Research, 20(5), 485-501.

Ben-Ayed, o., Boyce, D. E., & Blair III, c. E. (1988). A general bilevel linear

programming formulation of the network design problem. Transportation Research Part В : Methodological, 22(4), 311-318.

Berdica, K. (2002). An introduction to road vulnerability: what has been done, is done and should be done. Transport Policy, 9(2), 117-127. http://doi.org/10.1016/S0967- 070X(02)00011-2

Berdica, K., & Mattsson, L.-G. (2007). Vulnerability: a model-based case study of the road network in Stockholm. In Critical Infrastructure (pp. 81-106). Springer. Retrieved from files/3368/chp: 10.1007/978-3-540-68056-7_5.pdf

Bhushan, M., Narasimhan, s., & Rengaswamy, R. (2008). Robust sensor network design for fault diagnosis. Computers and Chemical Engineering, 32, 1067-1084. http ://doi. org/10.1016/j. compchemeng.2007.06.020

Brown, D. B. (1980). The use of dynamic programming in optimally allocating funds for highway safety improvements. Transportation Planning and Technology, 6(2), 131­138. http: doi.org 10.1080/03081068008717183

Brown, G., Carlyle, M., Salmerón, J., & Wood, K. (2006). Defending critical infrastructure. Interfaces, 36(6), 530-544. http://doi.org/10.1287/inte.1060.0252

Bruynooghe, M. (1972). An optimal method of choice of investments in a transport network. PTRC Proceedings.

Cao, J. X., Li, X. X., Wang, z. Y., & Wu, J. (2013). The Robust Model of Continuous Transportation Network Design Problem with Demand and Cost Uncertainties. Procedia - Social and Behavioral Sciences, 96(Cictp), 970-980. http://doi.Org/10.1016/j.sbspro.2013.08.lll

Chamieh, M., & El-kouatly, R. (n.d.). Impact of IDM Lane-Changing on the Performance of AODV on VANETs, 36-41. http : //doi. org/10.5013/IJSS ST. al 3.06.06

Chen, A., Kongsomsaksakul, s., Zhou, z., Lee, M., & Recker, w. w. (2007). Assessing network vulnerability of degradable transportation systems: an accessibility based approach.

Chen, A., Yang, c., Kongsomsaksakul, s., & Lee, M. (2007). Network-based accessibility measures for vulnerability analysis of degradable transportation networks. Networks and Spatial Economics, 7, 241-256.

Chen, A., Yang, H., Lo, H. K., & Tang, w. H. (2002). Capacity relaibility of a road network: an assessment methodology and numerical results. Transportation Research Part B: Methodological, http://doi.0rg/l 0.1016/S0191 -2615(00)00048-5

Chen, A., Zhou, z., Chootinan, p., Ryu, s., Yang, c., & Wong, s. c. (2011). Transport Network Design Problem under Uncertainty: A Review and New Developments. Transport Reviews, 31(6), 743-768. http://do1.Org/10.1080/01441647.2011.589539

Chiou, s. (2015). A bi-level decision support system for uncertain network design with equilibrium fl ow. Decision Support Systems, 69, 50-58. http://doi.Org/10.1016/j.dss.2014.12.004

Chiou, S.-W. (2005a). Bilevel programming for the continuous transport network design problem. Transportation Research Part B: Methodological, 39(A), 361-383. http://doi.Org/10.1016/j.trb.2004.05.001

Chiou, S.-W. (2005b). Bilevel programming for the continuous transport network design problem. Transportation Research Part B: Methodological, 39(A), 361-383. http://doi.Org/10.1016/j.trb.2004.05.001

Crucitti, p., Latora, V., & Marchi ori, M. (2004). Model for cascading failures in complex networks. Physical Review E, 69(A), 045104. http: doi.org/10.1103/PhysRevE.69.045104 de Araújo, D. R. B., Bastos-Filho, c. J. а., & Martins-Filho, J. F. (2015). An evolutionary approach with surrogate models and network science concepts to design optical networks. Engineering Applications of Artificial Intelligence, 43, 67-80. http : //doi. org/10.1016/j. engappai .2015.04.004

Dempe, s., & Zemkoho, a. B. (2012). On the KarushKuhnTucker reformulation of the bilevel optimization problem. Nonlinear Analysis, Theory, Methods and Applications, 75(3), 1202-1218. http://doi.Org/10.1016/j.na.2011.05.097

Dijkstra, A. (2013). Assessing the safety of routes in a regional network. Transportation Research Part c: Emerging Technologies, 32, 103-115. http://doi.Org/10.1016/j.trc.2012.10.008

Dimitriou, L., & Stathopoulos, A. (2009). Optimal co-evolutionary strategies for the competitive maritime network design problem. Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 5484 LNCS, 818-827. http://do1.Org/10.1007/978-3-642-01129- 0_92

Dziubiński, M., & Goyal, s. (2013a). Network design and defence. Games and Economic Behavior, 79, 30-43. http://doi.Org/10.1016/j.geb.2012.12.007

Dziubiński, M., & Goyal, s. (2013b). Network design and defence. Games and Economic Behavior, 79, 30-43. http://doi.Org/10.1016/j.geb.2012.12.007

Erath, A., Birdsall, J., Axhausen, K. w., & Hajdin, R. (2009). Vulnerability assessment methodology for Swiss road network. Transportation Research Record: Journal of the Transportation Research Board, 2137, 118-126.

Falk, J. E., & Liu, J. (1995). On bilevel programming , Part I : general, 70, 70-71.

Farahani, R. z., Miandoabchi, E., Szeto, w. Y., & Rashidi, H. (2013). A review of urban transportation network design problems. European Journal of Operational Research, 229(2), 281-302. http://do1.Org/10.1016/j.ejor.2013.01.001

Feremans, c., Labbé, M., & Laporte, G. (2003). Generalized network design problems. European Journal of Operational Research, 148( 1), 1-13. http://do1.org/10.1016/S0377-2217(02)00404-6

Flisberg, p., Lidén, в., & Rönnqvist, M. (2009). A hybrid method based on linear programming and tabu search for routing of logging trucks. Computers & Operations Research, 36(4), 1122-1144. http://doi.Org/10.1016/j.cor.2007.12.012

Fosgerau, M., & Karlström, A. (2010). The value of reliability. Transportation Research Part В : Methodological, 44( 1), 38-49. http://doi.Org/10.1016/j.trb.2009.05.002

Friesz, T. L. (1985). Transportation network equilibrium, design and aggregation: Key developments and research opportunities. Transportation Research Part A: General, 19(5-6), 413-427 http: doi.org/10.1016/0191 -2607(85)90041 -X

Gallo, M., Acierno, L. D., & Montella, B. (n.d.). Compendium of Papers A meta­heuristic algorithm for solving the road network design problem in regional contexts, (1984).

Gallo, M., D’Acierno, L., & Montella, в. (2012). A Meta-heuristic Algorithm for Solving the Road Network Design Problem in Regional Contexts. Procedia - Social and Behavioral Sciences, 54, 84-95. http://doi.Org/10.1016/j.sbspro.2012.09.728

Gangi, M. Di, Pianificazione, A., & Luongo, A. (2005). © Association for European Transport and contributors 2005, (1999).

Gao, z., Wu, J., & Sun, H. (2005). Solution algorithm for the bi-level discrete network design problem. Transportation Research Part в : Methodological, 39(6), 479-495. http://doi.Org/10.1016/j.trb.2004.06.004

Gershwin, s. B., Tan, H.-N., & others. (1979). Hybrid Optimization: control of traffic networks in equilibrium.

Gregoriades, A., & Mouskos, к. c. (2013). Black spots identification through a Bayesian Networks quantification of accident risk index. Transportation Research Part c: Emerging Technologies, 28, 28-43. http://doi.Org/10.1016/j.trc.2012.12.008

Grubesic, T. H., Murray, A. T., & Mefford, J. N. (2007). 10 Continuity in Critical Network Infrastructures : Accounting for Nodal Disruptions.

Indrei, E. (2006). Markov Chains and Traffic Analysis, 2(1), 1-15.

Iyer, S. M. S. M., Nakayama, M. K. M. K., & Gerbessiotis, A. v. a. V. (2009). A

Markovian Dependability Model with Cascading Failures. IEEE Transactions on Computers, 58(9), 1238-1249. http://doi.Org/10.1109/TC.2009.31

Jenelius, E. (2010a). Large-Scale Road Network Vulnerability Analysis, (October).

Jenelius, E. (2010b). User inequity implications of road network vulnerability, 2, 57-73.

Jenelius, E. (2011). Road net vul a grid based.

Jenelius, E., & Mattsson, L. G. (2012). Road network vulnerability analysis of area­covering disruptions: A grid-based approach with case study. Transportation Research Part a-Policy and Practice, 46(5), 746-760. http ://doi. org/10.1016/j. tra.2012.02.003

Jenelius, E., & Mattsson, L.-G. (2006). Developing a methodology for road network vulnerability analysis. Nectar Cluster, 1, 1-9. Retrieved from files/3349/Jenelius and Mattsson - 2006 - Developing a methodology for road network vulnerab.pdf

Jenelius, E., & Mattsson, L.-G. (2012). Road network vulnerability analysis of area­covering disruptions: A grid-based approach with case study. Transportation Research Part A: Policy and Practice, 46(5), 746-760. http://do1.Org/10.1016/j.tra.2012.02.003

Jenelius, E., Petersen, T., & Mattsson, L.-G. (2006). Importance and exposure in road network vulnerability analysis. Transportation Research Part A: Policy and Practice, 40(7), 537-560. http://doi.Org/10.1016/j.tra.2005.ll.003

Jin, X. z., & Yang, G. H. (2014). Robust synchronization control for complex networks with disturbed sampling couplings. Communications in Nonlinear Science and Numerical Simulation, 19(6), 1985-1995. http://doi.Org/10.1016/j.cnsns.2013.10.030

Kano, M., Shiraishi, T., & Kuwahara, M. (2007). Driver Behavior Model for ITS Evaluation System, 5(1), 17-25.

Kaplan, s., & Garrick, B. J. (1981). On The Quantitative Definition of Risk. Risk Analysis, 7(1), 11-27. http://do1.Org/10.llll/j.1539-6924.1981.tb01350.x

Karami, A., & Guerrero-zapata, M. (2015). Neurocomputing A hybrid multi objective RBF-PSO method for mitigating DoS attacks in Named Data Networking. Neurocomputing, 151, 1262-1282. http://doi.Org/10.1016/j.neucom.2014.ll.003

Konur, D., Golias, M. M., & Darks, B. (2013). A mathematical modeling approach to resource allocation for railroad-highway crossing safety upgrades. Accident; Analysis and Prevention, 51, 192-201. http://doi.Org/10.1016/j.aap.2012.ll.011

Kroger, w., & Zio, E. (2011). Vulnerable Systems. London: Springer London. http://doi.org/10 1007/978-0-85729-655-9

Latora, v., & Marchiori, M. (2001). Efficient Behavior of Small-World Networks. Physical Review Letters, 57(19), 198701. http://doi. org/10.1103/PhysRevLett. 87.198701

Latora, V., & Marchiori, M. (2004). Vulnerability and Protection of Critical

Infrastructures, 11-14. Retrieved from http://arxiv.org/abs/cond-mat/0407491vl

Leblanc, L. J. (1973). Mathematical programming algorithms for large scale network equilibrium and network design problems.

Leblanc, L. J. (2014). An Algorithm for the Discrete Network Design Problem, 9(3), 183-199.

Li, c., Yang, H., Zhu, D., & Meng, Q. (2012). A global optimization method for continuous network design problems. Transportation Research Part в : Methodological, 46(9), 1144-1158. http://doi.Org/10.1016/j.trb.2012.05.003

Li, M. (2006). Combining DTA Approaches for Studying Road Network Robustness. Ch’il Engineering, (November).

Luathep, p., Sumalee, A., Lam, w. H. к. K., Li, Z.-С., & Lo, H. K. (2011). Global optimization method for mixed transportation network design problem: A mixed- integer linear programming approach. Transportation Research Part B: Methodological, 45(5), 808-827. http://doi.Org/10.1016/j.trb.2011.02.002

Luo, Z.-Q., Pang, J.-S., & Ralph, D. (1996). Mathematical programs with equilibrium constraints. Cambridge University Press.

Mansouri, M., & Mostashari, A. (2009). A Decision Analysis Lramework for Resilience Strategies in Maritime Systems.

Marcotte, p. (1986). Network design problem with congestion effects: A case of bilevel programming. Mathematical1Programming, 34(2), 142-162.

Marcotte, p., & Marquis, G. (1992). Efficient implementation of heuristics for the continuous network design problem. Annals of Operations Research, 34( 1), 163­176.

Martin, p. A. s., & Thesis. (2007). TRI-LEVEL OPTIMIZATION MODELS TO DEPEND CRITICAL INFRASTRUCTURE, (September).

Mathew, T. V., & Sharma, s. (2006). Continuous Network Design with Emission Pricing as a Bi-Level Optimization Problem. Applications of Advanced Technology in Transportation, 804-809. http://doi.org/10.1061/40799(213)129

Melachrinoudis, E., & Kozanidis, G. (2002). A mixed integer knapsack model for allocating funds to highway safety improvements. Transportation Research Part A: Policy and Practice, 36(9), 789-803. http: doi.org 10.1016/S0965-8564(01 )00040- 4

Meng, Q., & Yang, H. (2002). Bene ® t distribution and equity in road network design, 36, 19-35.

Miandoabchi, E., Daneshzand, F., Szeto, w. Y., & Zanjirani Farahani, R. (2013). Multi­objective discrete urban road network design. Computers & Operations Research, 40( 10), 2429-2449 http: doi.org 10.101 òj.cor.2013.03.016

Michoń, J. A. (1985). A CRITICAR VIEW OF DRIVER BEHAVIOR MODELS : WHAT DO WE KNOW , WHAT SHOULD WE DO ?, 485-520.

Migdalas, A. (1998). Multilevel Optimization: Algorithms and Applications. (A.

Migdalas, p. M. Pardalos, & p. Värbrand, Eds.) (Voi. 20). Boston, MA: Springer US http://d01.0rg/l 0.1007/978-1 -4613-0307-7

Moridpour, S., Sarvi, M., & Rose, G. (2006). Modelling Lane Changing Behaviour of Heavy Commercial Vehicles, 1-15.

Mouskos, K. c. (1991). A Tabu-based Heuristic Search Strategy to Solve a Discrete Transportation Equilibrium Network Design Problem. University of Texas at Austin. Retrieved from https://books.google.com/books?id=UVhlnQEACAAJ

Murray, A. T., Davis, R, Stimson, R. I, & Ferreira, L. (1998). Public Transportation Access. Transportation Research Part D: Transport and Environment, 3(5), 319­328. http://doi.org/10.1016/s 1361 -9209(98)00010-8

Murray, A. T., & Grubesic, T. H. (2007). Critical Infrastructure. (A. T. Murray & T. H. Grubesic, Eds.). Berlin, Heidelberg: Springer Berlin Heidelberg. http://do1.org/10.1007/978-3-540-68056-7

Murray, A. T., Matisziw, T. c., & Grubesic, T. H. (2007). Critical network infrastructure analysis: interdiction and system flow. Journal of Geographical Systems, 9(2), 103­117. http: doi.org 10.1007/s 10109-006-0039-4

Murray-Tuite, p., & Mahmassani, H. (2004). Methodology for Determining Vulnerable Links in a Transportation Network. Transportation Research Record, 7552(1), 88­96. http://do1.org/10.3141/1882-l 1

Nicholson, A., Schmöcker, J. D., Bell, M. G. H, & Iida, Y. (2003). Assessing transport reliability: malevolence and user knowledge.

Numrich, s., & Tolk, A. (2010). Challenges for Human, Social, Cultural, and Behavioral Modeling. SCSM&s Magazine, 01, 1-9. Retrieved from http://www.scs.org/magazines/2010-01/index_file/Files/article_Numrich-Tolk.pdf

Ochoa-Rosso, F., & A, s. (1969). Optimum project addition in urban transportation networks via descriptive traffic assignment models.

Ouyang, M., Dueñas-osorio, L., & Min, X. (2012). A three-stage resilience analysis framework for urban infrastructure systems. Structural Safety, 36-37, 23-31. http: //doi. org/10.1016/j. strusafe.2011.12.004

Parvaresh, F., Husseini, s. M. M., Golpayegany, s. a H., & Karimi, B. (2014). Hub network design problem in the presence of disruptions. Journal of Intelligent Manufacturing, 25, 755-774. http://doi.org/10.1007/sl0845-012-0717-7

Patriksson, M., & Rockafellar, R. T. (2002). A Mathematical Model and Descent

Algorithm for Bilevel Traffic Management. Transportation Science, 36(3), 271-291. http 7/ doi. org/10.1287/trsc. 3 6.3.271 !7826

Pei, Y. L., Fischer, J. M., & Amekudzi, A. A. (2010). Performance Measurement in State Departments of Transportation: A Literature Review and Survey of Current Practice.

Poorzahedy, H., & Rouháni, o. M. (2007). Hybrid meta-heuristic algorithms for solving network design problem. European Journal of Operational Research, 182, 578-596. http ://doi. org/10.1016/j. ej or.2006.07.03 8

Poorzahedy, H, & Turnquist, M. A. (1982). Approximate algorithms for the discrete network design problem. Transportation Research Part в : Methodological, 16( 1), 45-55.

Qiang, Q., & Nagurney, A. (2007). A unified network performance measure with importance identification and the ranking of network components. Optimization Letters, 2(1), 127-142. http://doi.Org/10.1007/sll590-007-0049-2

Reniers, G. L. L. L. L., & Dullaert, w. (2013). A method to assess multi-modal Hazmat transport security vulnerabilities: Hazmat transport SVA. Transport Policy, 28, 103­113. http://doi.Org/10.1016/j.tranpol.2012.05.002

Scott, D. M., Novak, D. c., Aultman-Hall, L., & Guo, F. (2006). Network Robustness Index: A new method for identifying critical links and evaluating the performance of transportation networks. Journal of Transport Geography, 14(3), 215-227. http://doi.org/10.1016/jjtrangeo.2005.10.003

Scott, D. M., Novak, D., & Guo, F. (2005). Network Robustness Index : A New Method for Identifying Critical Links and Evaluating the Performance of Transportation Networks, (April).

Sharma, s., & Mathew, T. V. (2011). Multi objective network design for emission and travel-time trade-off for a sustainable large urban transportation network. Environment and Planning В : Planning and Design, 38(3), 520-538. http ://doi. org/10.1068/b37018

Sheffi, Y. (1985). Urban transportation networks.

Snelder, M. (2010). Designing Robust Road Networks.

Steenbrink, p. A. (1974). Optimization of transport networks. New York.

Sullivan, J. L., Aultman-hall, L., & Novak, D. c. (2009). A review of current practice in network disruption analysis and an assessment of the ability to account for isolating links in transportation networks. Transportation Letters: The International Journal of Transportation Research, 7(4), 271-280. http://do1.Org/10.3328/TL.2009.01.04.271-280

Suwansirikul, c., Friesz, T. L., & Tobin, R. L. (1987). Equilibrium Decomposed Optimization: A Heuristic for the Continuous Equilibrium Network Design Problem. Transportation Science, 27(4), 254-263. http://doi.0rg/10.1287/trsc.21.4.254

Suzuki, T., & Mori, M. (n.d.). CALIBRATION AND EVALUATION OF LANE- CHANGE MODEL ON HIGHWAY FROM MICROSCOPIC & MACROSCOPIC VIEWPOINTS, 1-12.

Tampere, c. M. L, Stada, L, Immers, в., & Leuven, к. и. (n.d.). Methodology for Identifying Vulnerable Sections in a National Road Network, 1-18.

Taylor, M. A. p., & D’Este, G. M. (2007). Transport network vulnerability : a method for diagnosis of critical locations in transport infrastructure systems. Springer. Retrieved from files/3398/chp: 10.1007/978-3-540-68056-7_2(l).pdf

Tsoukalas, A., & Wiesemann, w. (n.d.). Global Optimisation of Pessimistic Bi-Level Problems, 1-31.

Ünlü, G. (1987). A linear bilevel programming algorithm based on bicriteria
programming. Computers & Operations Research, 1-1(2), 173-179.

Vicente, L. N., & Calamai, P. H. (1994a). Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization, 5(3), 291-306. http://doi'org/10.1007/BF01096458

Vicente, L. N., & Calamai, P. H. (1994b). Bilevel and multilevel programming: A bibliography review. Journal of Global Optimization, 5(3), 291-306. http://doi'org/10.1007/BF01096458

Wan, Z., Mao, L., & Wang, G. (2014). Estimation of distribution algorithm for a class of nonlinear bilevel programming problems. Information Sciences, 256, 184-196. http://doi.Org/10.1016/j.ins.2013.09.021

Wang, D. z. w., & Lo, H. K. (2010). Global optimum of the linearized network design problem with equilibrium flows. Transportation Research PartB: Methodological, 44(4), 482-492. http://do1.Org/10.1016/j.trb.2009.10.003

Wang, s., Meng, Q., & Yang, H. (2013). Global optimization methods for the discrete network design problem. Transportation Research Part B: Methodological, 50, 42­60. http: doi.org/10.1016/j.trb.2013.01.006

Washington, S. E. (2008). Traffic Analysis Toolbox Volume VIII: Work Zone Modeling and Simulation— A Guide for Decision-Makers, !7///(August).

Wheeler, T. A., & Lie, R. B. (n.d.). A Probabilistic Framework for Microscopic Traffic Propagation.

Wu, J., Guo, X., Sun, H., & Wang, в. (2014). Topological Effects and Performance Optimization in Transportation Continuous Network Design. Mathematical Problems in Engineering, 2014, 1-7. http://doi.org/10.1155/2014/490483

Xu, M., & Gao, z. (2009). Chaos in a dynamic model of urban transportation network flow based on user equilibrium states. Chaos, Solitons & Fractals, 39(2), 586-598. http ://doi. org/10.1016/j. chaos.2007. о 1.077

Yang, H. A. (1997). SENSITIVITY ANALYSIS FOR THE ELASTIC-DEMAND, 37(1), 55-70.

Yang, H., & H. Bell, M. G. (1998). Models and algorithms for road network design: a review and some new developments. Transport Reviews, 18(3), 257-278. http: doi.org/10.1080/01441649808717016

Yilmaz, L. (2009). Agent-Directed Simulation and Systems Engineering. Systems Engineering, 897-904. http://doi.org/10.1002/9783527627783

Yim, K. K. w., Wong, s. c, Chen, A., Wong, с. K., & Lam, w. H. K. (2011). A reliability-based land use and transportation optimization model. Transportation Research Part c: Emerging Technologies, 19(2), 351-362. http://doi.Org/10.1016/j.trc.2010.05.019

Yun-peng, w., Yu-qin, F., Wen-xiang, L. I, Fulcher, w. c., & Zhang, L. (n.d.). Road network vulnerability analysis based on improved ant colony algorithm, 1-11.

Zeng, Q. (1998). Zeng , Qifeng 1998 A combined simulated annealing and TABU search strategy to solve network design problem with two classes of users.

Zhang, J., Xu, X., Hong, L., Wang, s., & Fei, Q. (2012). Attack vulnerability of self­organizing networks. Safety Science, 50(3), 443-447. http://doi.Org/10.1016/j.ssci.2011.10.005