West Virginia University
Robust Shortest Path Problem: Models and Solution Algorithms
Abstract
dc:description.abstractShortest path is a key component of several network related problems and has been widely used and applied in numerous disciplines such as transportation, logistics and telecommunication networks. This problem in the base deterministic settings lends itself to elegant and efficient solution methods. Nevertheless, the initial formulation is limited in number of ways; one such limitation is the need to accounting for inherent uncertainty in real world transportation networks. In recent years there has been a growing interest in incorporating uncertainty within the transportation network analysis models and particularly the shortest path problem. This dissertation contributes to the growing body of literature in dealing with uncertainty in shortest path problem by developing formulations as well as efficient solution methodologies for these class of problems.;There are number of approaches across the literature for incorporating the stochastic features of network related parameters such as travel time into the shortest path problem. One such approach is to minimize mean-risk analysis which is to minimize both the average cost and the risks arising from the uncertainty assumptions. The chief complication of such modeling approach is that the size of the nonlinear part of the objective function will increase for the large size real world network problem which undermines the efficiency of the existing solution approach. In response to such needs a solution methodology based on outer approximation (OA) strategy is proposed and customized which is highly efficient for real world large size instances.;In addition, in this dissertation a robust optimization approach for the shortest path problem where travel cost is uncertain and exact information on the distribution function is unavailable has been applied. Robust shortest path under such conditions is shown to be formulated as a binary nonlinear integer program, which can then be reformulated as a mixed integer conic quadratic program.;Finally, both two modeling frameworks provide a generalization in which links have two cost components, representing the expected cost and risk measure on the links -- the former term is additive, but the latter is not. In the third and final part of this dissertation, a solution methodology for general formulation of shortest path problem with non-additive continuous convex travel cost functions is presented.
Degree
thesis:*- Name thesis:degree_name
- PhD
- Level thesis:degree_level
- Dissertation
- Discipline thesis:degree_discipline
- Industrial and Managements Systems Engineering
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Shahabi, Mehrdad
- Contributors dc:contributor
-
- Avinash Unnikrishnan
- Steve Boyles
- Udaya Halabe
- Antarpreet Jutla
- David Martinelli
Identifiers
dc:identifier.*- Identifier
- https://researchrepository.wvu.edu/etd/6609