Finding Extreme Supported Solutions to the Bi-Objective Shortest Path Problem

The extreme supported solutions to the one-to-all bi-objective shortest path problem are analyzed. We start with the implementation of a ratio-labeling algorithm which obtains all these solutions in O(N(m+nlogn)) steps, where N is the total number of extreme supported solutions and n and m are the number of nodes and arcs in the graph respectively. Next we consider a setting where the input graph has the property of being acyclic, and propose a O(Nm) labeling algorithm to solve this problem. We conclude this thesis by showing how this same algorithm can easily be adapted to handle the scenario where either one or both of the criteria are of the bottleneck type. Due to the nature of the extreme supported solutions under this criterion function, a polynomial time algorithm with a complexity of O(m2) steps is found in this case.