Efficient solution generation for the bicriterion shortest path problems (Q606615)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Efficient solution generation for the bicriterion shortest path problems |
scientific article |
Statements
Efficient solution generation for the bicriterion shortest path problems (English)
0 references
17 November 2010
0 references
Summary: 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.
0 references
BSPP
0 references
biobjective shortest path problem
0 references
efficient extreme points
0 references
network optimisation
0 references
simplex based algorithms
0 references
non-dominated sets
0 references
continuous relaxation
0 references