Mathematical Programming Algorithms for Reliable Routing and Robust Evacuation Problems

Persistent Link:
http://hdl.handle.net/10150/195737
Title:
Mathematical Programming Algorithms for Reliable Routing and Robust Evacuation Problems
Author:
Andreas, April Kramer
Issue Date:
2006
Publisher:
The University of Arizona.
Rights:
Copyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.
Abstract:
Most traditional routing problems assume perfect operability of all arcs and nodes. However, when independent arc failure probabilities exist, a secondary objective must be present to retain some measure of expected functionality. We first briefly consider the reliability-constrained single-path problem, where we look for the lowest cost path that meets a reliability side constraint. This analysis enables us to then examine the reliability-constrained two-path problem, which seeks to establish two minimum-cost paths between a source and destination node wherein at least one path must remain fully operable with some threshold probability. We consider the case in which both paths must be arc-disjoint and the case in which arcs can be shared between the paths. We prove both problems to be NP-hard. We examine strategies for solving the resulting nonlinear integer program, including pruning, coefficient tightening, lifting, and branch-and-bound partitioning schemes. Next, we consider the reliable h-path routing problem, which seeks a minimum-cost set of h ≥ 2 arc-independent paths between a source and destination node, such that the probability that at least one path remains operational is sufficiently large. Our prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. We propose two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms. Finally, we examine the robust design of an evacuation tree, in which evacuation is subject to capacity restrictions on arcs. Given a discrete set of disaster scenarios with varying network populations, arc capacities, transit times, and time-dependent penalty functions, we seek to establish an optimal a priori evacuation tree that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, and we provide effcient methods for obtaining primal and dual sub-problem solutions. We analyze techniques for strengthening the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence.
Type:
text; Electronic Dissertation
Keywords:
mixed-integer; nonlinear; optimization; Benders decomposition; branch-and-bound; column generation
Degree Name:
Ph.D.
Degree Level:
doctoral
Degree Program:
Systems & Industrial Engineering; Graduate College
Degree Grantor:
University of Arizona
Advisor:
Smith, J. Cole
Committee Chair:
Smith, J. Cole

Full metadata record

DC FieldValue Language
dc.language.isoenen_US
dc.titleMathematical Programming Algorithms for Reliable Routing and Robust Evacuation Problemsen_US
dc.creatorAndreas, April Krameren_US
dc.contributor.authorAndreas, April Krameren_US
dc.date.issued2006en_US
dc.publisherThe University of Arizona.en_US
dc.rightsCopyright © is held by the author. Digital access to this material is made possible by the University Libraries, University of Arizona. Further transmission, reproduction or presentation (such as public display or performance) of protected items is prohibited except with permission of the author.en_US
dc.description.abstractMost traditional routing problems assume perfect operability of all arcs and nodes. However, when independent arc failure probabilities exist, a secondary objective must be present to retain some measure of expected functionality. We first briefly consider the reliability-constrained single-path problem, where we look for the lowest cost path that meets a reliability side constraint. This analysis enables us to then examine the reliability-constrained two-path problem, which seeks to establish two minimum-cost paths between a source and destination node wherein at least one path must remain fully operable with some threshold probability. We consider the case in which both paths must be arc-disjoint and the case in which arcs can be shared between the paths. We prove both problems to be NP-hard. We examine strategies for solving the resulting nonlinear integer program, including pruning, coefficient tightening, lifting, and branch-and-bound partitioning schemes. Next, we consider the reliable h-path routing problem, which seeks a minimum-cost set of h ≥ 2 arc-independent paths between a source and destination node, such that the probability that at least one path remains operational is sufficiently large. Our prior arc-based models and algorithms tailored for the case in which h = 2 do not extend well to the general h-path problem. Thus, we propose two alternative integer programming formulations for the h-path problem in which the variables correspond to origin-destination paths. We propose two branch-and-price-and-cut algorithms for solving these new formulations, and provide computational results to demonstrate the efficiency of these algorithms. Finally, we examine the robust design of an evacuation tree, in which evacuation is subject to capacity restrictions on arcs. Given a discrete set of disaster scenarios with varying network populations, arc capacities, transit times, and time-dependent penalty functions, we seek to establish an optimal a priori evacuation tree that minimizes the expected evacuation penalty. The solution strategy is based on Benders decomposition, and we provide effcient methods for obtaining primal and dual sub-problem solutions. We analyze techniques for strengthening the master problem formulation, thus reducing the number of master problem solutions required for the algorithm's convergence.en_US
dc.typetexten_US
dc.typeElectronic Dissertationen_US
dc.subjectmixed-integeren_US
dc.subjectnonlinearen_US
dc.subjectoptimizationen_US
dc.subjectBenders decompositionen_US
dc.subjectbranch-and-bounden_US
dc.subjectcolumn generationen_US
thesis.degree.namePh.D.en_US
thesis.degree.leveldoctoralen_US
thesis.degree.disciplineSystems & Industrial Engineeringen_US
thesis.degree.disciplineGraduate Collegeen_US
thesis.degree.grantorUniversity of Arizonaen_US
dc.contributor.advisorSmith, J. Coleen_US
dc.contributor.chairSmith, J. Coleen_US
dc.contributor.committeememberAskin, Ronald G.en_US
dc.contributor.committeememberKucukyavuz, Simgeen_US
dc.contributor.committeememberLopes, Leoen_US
dc.contributor.committeememberMirchandani, Pituen_US
dc.identifier.proquest1733en_US
dc.identifier.oclc659747485en_US
All Items in UA Campus Repository are protected by copyright, with all rights reserved, unless otherwise indicated.