An interactive procedure using domination cones for bicriterion shortest path problems

In this paper an interactive procedure is developed for the bicriterion shortest path problem. It is assumed that the decision maker’s inherant utility function is quasi-concave and non-increasing, and that the network consists of non-negative, integer valued arc lengths. The proposed procedure uses the concept of domination cones, which it develops from pairwise comparisons of alternatives. These domination cones are used to fathom a large number of Pareto-optimal solutions. Extensive computational testing was performed on large grid networks, simulating the decision maker’s response using polynomial utility functions. The results indicate that the present proposed procedure is able to converge to the optimal solution in a reasonably small number of pairwise comparisons, even for those problems with a large number of Pareto-optimal solutions.