Efficient solution generation for the bicriterion shortest path problems

Abdallah W. Aboutahoun

International Journal of Operational Research, 2010, vol. 9, issue 3, 287-305

Abstract: In this paper, we present an algorithm to compute the set of all efficient extreme solutions in the objective space for the biobjective shortest path problem (BSPP). A simplex-based algorithm that generates all the efficient extreme points and edges in the objective space rather than the decision space is developed. Since not every extreme point of the decision space corresponds to an extreme point of the objective space, the number of these efficient extreme points in the objective space cannot exceed that of the decision space. Since the coefficient matrix associated with the flow conservation equations is totally unimodular for the BSPP, the efficient frontier is the non-dominated set of its continuous relaxation.

Keywords: BSPP; biobjective shortest path problem; efficient extreme points; network optimisation; simplex based algorithms; non-dominated sets; continuous relaxation. (search for similar items in EconPapers)
Date: 2010
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.inderscience.com/link.php?id=35522 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:9:y:2010:i:3:p:287-305

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().