Title: PowerPoint Presentation

Author: CanterburyMedia

This PDF 1.5 document has been generated by MicrosoftÂ® PowerPointÂ® 2013, and has been sent on pdf-archive.com on 26/04/2018 at 21:43, from IP address 68.235.x.x.
The current document download page has been viewed 204 times.

File size: 608.88 KB (1 page).

Privacy: public file

An innovative approach to solve the network design

problem concerning intelligent vulnerabilities

Naimi, A.; Golias, M. M.; Higgs, B.; Mishra, S.

Methodology

Abstract

In today’s congested transportation networks, disturbances 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

The vulnerability can be evaluated by measuring the increase in the total system travel time

Start

Concentrating on reducing the effects of potential disruptions to the network, may distract

the investments from the definite reduction of the total system cost under normal

No

Investment Function

Convergence Criteria

OD Matrix

Network Data

conditions, and to invest on infrastructures that might never be beneficial (if no disruptions

occur in future). Hence, an intellectual approach would be considering both aspects of

reducing the system-wide cost, and the potential vulnerabilities simultaneously. The aim of

𝑧(𝑥, 𝑦)

𝑥(y)

Yes

Converged?

for transportation agencies. This problem can be addressed using NDP methods

to improve various performance measures. Numerical experiments with

, 𝑥 y, z ,

𝑥(y)

vulnerability concerns showed the potential power of reduction of the future

y

Alternative User Level w/o Disruptions

User Equilibrium

Traffic Assignment

hazards’ effects. The objective of allocation of these resources can generally be

Designer Level

Minimize TSTT

Minimize Vulnerabilities

the maximization of social welfare. An intelligent adversary may look for

𝑧(𝑥, 𝑦)

the designer/defender is to invest on projects such that the social welfare and robustness of

parts of the network in order to disrupt the transportation operations, and

the network are maximized simultaneously. Since the value of the payoff considered as the

increase the overall transportation cost for the users.

increase in total system travel time, the adversary can look for the damage which results in

Often, the decision of improving the networks in transportation planning and

the maximum possible travel time of users of the system. In this case, at the designer level,

possible vulnerabilities. By considering the factor of vulnerability in their

A quantitative method for ranking the projects for budget allocation is essential

(TSTT). This way, the damage due to the disturbance are viewed over the whole system.

accessibility. Intelligent adversaries may take advantage of these vulnerable

management tasks are made without adequately taking into account the

Conclusions

vulnerabilities in the network to degrade its performance. At the planner’s level,

Adversary Level

Maximize Damage

Link Capacity

Flows

Cost of Construction

𝑥(y, z(y))

No

allocating resources without considering the potential of disruptions by the

Yes

z y ,y

intelligent adversary, may not help reduce the vulnerabilities, or similarly

Converged?

increase the robustness of the network.

two objective functions will form: the total system cost before the disruptions, and after the

disruptions by the attacker under his constraints. Therefore, the designer can pursue

User Level

User Equilibrium

Traffic Assignment

𝑥(y, z(y))

End

improving the current performance of the system, and at the same time, tries to alleviate the

decision, planners could prevent severe unforeseen disruptions in the future.

This study proposes an innovative model for designing robust networks against

Figure 1 Flowchart of the Solution Approach

possible system-wide costs as a result of intelligent disruptions. The general formulation of

The models were formed in multi-level optimization, considering flows of

this model is presented in equations (1) through (5).

intelligent attackers. In the model, three decision makers are considered: the

decisions are to be made in sequence. Therefore, a hierarchy structure of the

The designer of the network as the first mover, should search over the best possible

𝑚𝑖𝑛 𝐷(𝑥(𝑦), 𝑦)

(1)

𝑚𝑖𝑛 𝐷′(𝑥′(𝑦, 𝑧(𝑦)), 𝑦, 𝑧(𝑦))

(2)

and search to find the most crucial links of the network to be degraded or completely

(3)

disabled. And the last move is done by the users of the network who individually search for

enemy was assumed to damages/disable links. The results showed that the

(4)

the best route for themselves in terms of the least travel time. The overall flowchart of the

proposed model can search over the possible results for the designer and choose

(5)

solution algorithms for the three decision makers is presented in Figure 1. It should be

the most robust solution to compare to the other possible solutions. Results

1

noted that to keep the diagram simple, the convergence criteria for user-level problems is

showed promising achievements in terms of increasing the robustness of the

On this assumption, the designer possibly would face a set of solutions.

not demonstrated in this figure.

network against intelligent disruptions, and also improving other system-wide

𝑦

network manager/designer, the adversary (intelligent attacker) and the users of

the network. Numerical experiments were conducted, and the results proved the

𝑦

s.t. 𝑚𝑎𝑥 𝐴(𝑥′(𝑧), 𝑦, 𝑧)

potential benefits of the proposed model.

𝑧

𝑚𝑖𝑛 𝑈(𝑥, 𝑦)

𝑥

s.t.

Objectives

To address this issue, models were presented for designing robust networks.

𝑚𝑖𝑛 𝑈′(𝑥′, 𝑦, 𝑧)

𝑥′

solutions for the design of the network while the adversary should move after the designer

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

performance measures as presented in the bi-objective robust network design

Results

The objective and main contribution of this research is to provide a new

problem model. Other objectives can be defined for the designer and the

methodology 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.

adversary level.

Numerical experiments were conducted in order to evaluate the performance of the

method and observe the results. The designer and adversary level algorithm were

References

coded and solved using MATLAB, and the user level algorithm was implemented in

An appropriate way to model the vulnerabilities as a result of intelligent

disruptions, could be to model them as a player in a game that tries to achieve

his or her objective(s). Some of the studies focused on operational network

C++. The method was processed on a computer with an Intel i7-960 processor and

1.

24GB of RAM. The Sioux Falls network was selected, which consists of 76 links, and

2.

24 nodes which are also defined as the demand origin/destinations. It is assumed that

all the links in the initial network have three lanes. The links attributes and OD trips

design. However, the strategic network design against vulnerabilities needs to

were adopted from (Suwansirikul et al., 1987). Two scenarios were performed on this

be further studied. In addition, despite the works that have been done to design

network using different budgets available to the adversary: adversary entity can

robust networks against stochastic vulnerability, this approach could provide

3.

4.

5.

damage 1 link and 2 links.

new ways to analyze the vulnerabilities in networks in a higher level of detail.

Figure 3 Individuals solutions at by the two objectives of the designer at the 100st

6.

7.

generation for adversary budget equal to two.

8.

Since three decision makers are considered in this study, the possibly associated

zz 0

1

zz e

2

1

2

9.

models and objectives are reviewed. From a design point of view, the designer

3

4

5

6

3

may have multiple objectives when improving the performance of a network

9

12

11

10.

16

9

8

7

10

16

18

1

18

11

11.

17

1

17

12.

14

15

19

14

15

23

22

24

21

19

1

adversary viewpoint, the objective is to degrade the performance of the network

Figure 2 Links Included in Expansion, highlighted with green color (Left), and

13

0

www.PosterPresentations.com

6

7

12

they look for their optimal route choice, mode, and destination. From an

RESEARCH POSTER PRESENTATION DESIGN © 2012

8

10

reduction of pollution emission. On the other hand, from a user perspective,

consider the alleviation of potential disruptions.

5

1

such as total system cost, robustness against reliability and vulnerability and

to the maximum of his capabilities. Hence, a design for a robust network must

4

23

22

24

21

13

20

2.00

0

13.

14.

15.

20

2.00

improvement of the capacity expanded network compare to the initial conditions for

Figure 4 the optimal decisions of the attacker for the initial (Left) and improved

adversary budget of one (Right).

network (Right), and for adversary budget of two.

Allsop, R.E., 1974. Some possibilities for using traffic control to influence trip distribution

and route choice, in: Transportation and Traffic Theory, Proceedings.

Dziubiński, M., Goyal, S., 2013. Network design and defence. Games Econ. Behav. 79,

30–43. doi:10.1016/j.geb.2012.12.007

Gershwin, S.B., Tan, H.-N., others, 1979. Hybrid Optimization: control of traffic networks

in equilibrium.

Konur, D., Golias, M.M., Darks, B., 2013. A mathematical modeling approach to resource

allocation for railroad-highway crossing safety upgrades. Accid. Anal. Prev. 51, 192–201.

doi:10.1016/j.aap.2012.11.011

Leblanc, L.J., 1973. Mathematical programming algorithms for large scale network

equilibrium and network design problems.

Marcotte, P., 1983. Network Optimization with Continuous Control 17, 181–197.

Marcotte, P., 1986. Network design problem with congestion effects: A case of bilevel

programming. Math. Program. 34, 142–162.

Marcotte, P., Marquis, G., 1992. Efficient implementation of heuristics for the continuous

network design problem. Ann. Oper. Res. 34, 163–176.

Marcotte, P., Zhu, D.L., 1996. Exact and inexact penalty methods for the generalized

bilevel programming problem. Math. Program. 74, 141–157. doi:10.1007/BF02592209

Martin, P.A.S., Thesis, 2007. TRI-LEVEL OPTIMIZATION MODELS TO DEFEND

CRITICAL INFRASTRUCTURE.

Murray, A.T., Davis, R., Stimson, R.J., Ferreira, L., 1998. Public Transportation Access.

Transp. Res. Part D Transp. Environ. 3, 319–328. doi:10.1016/S1361-9209(98)00010-8

Murray-Tuite, P., Mahmassani, H., 2004. Methodology for Determining Vulnerable Links

in a Transportation Network. Transp. Res. Rec. 1882, 88–96. doi:10.3141/1882-11

Snelder, M., n.d. Designing Robust Road Networks.

Steenbrink, P.A., 1974. Optimization of transport networks. New York.

Suwansirikul, C., Friesz, T.L., Tobin, R.L., 1987. Equilibrium Decomposed Optimization:

A Heuristic for the Continuous Equilibrium Network Design Problem. Transp. Sci. 21,

254–263. doi:10.1287/trsc.21.4.254

Ali Poster.pdf (PDF, 608.88 KB)

Download PDF

Use the permanent link to the download page to share your document on Facebook, Twitter, LinkedIn, or directly with a contact by e-Mail, Messenger, Whatsapp, Line..

Use the short link to share your document on Twitter or by text message (SMS)

Copy the following HTML code to share your document on a Website or Blog

This file has been shared publicly by a user of

Document ID: 0000761506.