First Advisor

Avinash Unnikrishnan

Term of Graduation

Fall 2019

Date of Publication

1-3-2020

Document Type

Thesis

Degree Name

Master of Science (M.S.) in Civil & Environmental Engineering

Department

Civil and Environmental Engineering

Language

English

Subjects

Civil engineering

DOI

10.15760/etd.7315

Physical Description

1 online resource (xi, 138 pages)

Abstract

In this thesis, a maximum flow-based network interdiction problem considering uncertainties in arc capacities and interdiction resource consumption is solved. The problem consists of two entities with opposing objectives: the goal of the adversary is to maximize the flow of illicit drugs through the network, while the goal of the interdictor is to minimize the maximum flow by completely interdicting arcs given a specified amount of resources. Lack of complete information about the usage patterns of the transportation network by the adversary results in an uncertain estimate of arc capacity and resources required for interdiction by the interdictor. To account for this uncertainty, a robust optimization framework is utilized, resulting in a Robust Network Interdiction Problem (RNIP).

A novel mixed-integer linear program is proposed that solves the RNIP. Three heuristics are proposed to solve RNIP, the first based on Lagrangian Relaxation, the second based on Benders' Decomposition, and the third based on Benders' Decomposition enhanced using the Lagrangian Relaxation presolve. Computational experiments show that the third heuristic performs the best with a final MIP gap of less than 5% and a computational time saving of more than 90% for all the test networks when compared to a state-of-the-art mixed integer program solver. Sensitivity analyses are performed to identify budgets of uncertainty that provide a realistic estimate of the actual maximum flow using a Monte Carlo simulation scheme. Finally, robust decisions are compared to decisions not accounting for any uncertainty to evaluate the value of robustness. It is found that robust decisions can provide fairly accurate estimates of possible actual maximum flows in the network. When the interdiction efforts are significant, robust decisions also lead to a reduction in actual maximum flows, as much as 78% on average for a series of test networks, when compared to decisions not accounting for any uncertainty.

Rights

In Copyright. URI: http://rightsstatements.org/vocab/InC/1.0/ This Item is protected by copyright and/or related rights. You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use. For other uses you need to obtain permission from the rights-holder(s).

Persistent Identifier

https://archives.pdx.edu/ds/psu/33157

Download

Share

COinS