Parametric approach to solving bicriterion and singly constrained shortest path problems

Abstract

The bicriterion and singly constrained shortest path problems constitute important variations of the classical shortest path problem. In many real world applications of the shortest path problem, two "cost" parameters can be assigned to each arc. These applications can be modeled as a bicriterion shortest path problem where all Pareto-optimal paths from a source s to a destination t are desired. Often the decision maker is able to provide additional information about the two objectives considered. If the decision maker provides finite bounds on the trade-off between the two objectives, this information can be translated to a domination cone larger than that used to obtain Pareto-optimal paths. The resulting nondominated paths are a subset of Pareto-optimal paths. Networks where two parameters are assigned to each arc can also be modeled as a singly constrained shortest path problem, where, for example, the shortest distance needs to be determined, subject to a constraint that time taken should not exceed a specified amount. This dissertation develops a parametric approach to solve the three related problems described above. The parametric approach, exploits properties associated with a bicriterion network program. Computational testing on large networks comparing the performance of the parametric approach to existing approaches are performed. Also, such key issues as the number of pareto-optimal paths obtained, and the percentage of pareto-optimal paths that lie on the "convex hull" for networks with different topological characteristics is investigated.