Date of Graduation

2015

Document Type

Dissertation

Degree Type

PhD

College

Statler College of Engineering and Mineral Resources

Department

Industrial and Managements Systems Engineering

Committee Chair

Avinash Unnikrishnan

Committee Co-Chair

Steve Boyles

Committee Member

Udaya Halabe

Committee Member

Antarpreet Jutla

Committee Member

David Martinelli

Abstract

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

Download

Share

COinS