An interactive bi-objective shortest path approach: Searching for unsupported nondominated solutions

In many network routing problems several conflicting objectives must be considered. Even for the bi-objective shortest path problem, generating and presenting the whole set of nondominated solutions (paths) to a decision maker, in general, is not effective because the number of these paths can be very large. Interactive procedures are adequate to overcome these drawbacks. Current et al. proposed an interactive approach based on a NISE-like procedure to search for nondominated supported solutions and using auxiliary constrained shortest path problems to carry out the search inside the duality gaps. In this paper we propose a new interactive approach to seach for unsupported nondominated solutions (lying inside duality gaps) based on a k-shortest path procedure. Both approaches are compared.