×

An interactive bi-objective shortest path approach: Searching for unsupported nondominated solutions. (English) Zbl 0932.90005

Summary: In many network routing problems several conflicting objectives must be considered. Even for the biobjective 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. [J. R. Current, C. S. Revelle and J. L. Cohon [ibid. 17, 197-198 (1990)] proposed an interactive approach based on a NISE-like procedure to search for nondominated supported solutions and using auxiliar constrained shortest path problems to carry out the search inside the duality gaps. In this paper we propose a new interactive approach to search for unsupported nondominated solutions (lying inside duality gaps) based on a \(k\)-shortest path procedure. Both approaches are compared.

MSC:

90B10 Deterministic network models in operations research
90B40 Search theory
PDFBibTeX XMLCite
Full Text: DOI