| ABSTRACT:
The Classical Shortest Path Problem is concerned with finding the minimum distance, time or cost through a connecting network. This fundamental problem is alluring as it arises frequently in practice, it is easy to solve efficiently, it provides a benchmark for studying more complex models, and it frequently arises as subproblems when solving other network and combinatorial problems. In some cases paths are required to satisfy some additional constraints, besides being the shortest. The introduction of an additional constraint increases the order of complexity of the problem, in fact it renders the problem NP-complete. It is the purpose of my thesis to develop mathematical programming models as well as efficient methods for solving constrained path problems. In particular, we focus on the transit path problem which seeks a path that optimizes an objective function that relates to risk, reliability or cost and satisfies a transit time constraint.
|
