Efficient solution generation for the bicriterion shortest path problems
type: Item
instance of: scholarly article
title: Efficient solution generation for the bicriterion shortest path problems
zbMATH Open document ID: 1200.90028
DOI: 10.1504/IJOR.2010.035522
author: Abdallah W. Aboutahoun
published in: International Journal of Operational Research
publication date: 2010-11-17T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 90B10
Mathematics Subject Classification ID: 90C29
zbMATH DE Number: 5816968
zbMATH Keywords: BSPP
zbMATH Keywords: biobjective shortest path problem
zbMATH Keywords: efficient extreme points
zbMATH Keywords: network optimisation
zbMATH Keywords: simplex based algorithms
zbMATH Keywords: non-dominated sets
zbMATH Keywords: continuous relaxation
MaRDI profile type: Publication
full work available at URL: ijor.2010.035522
OpenAlex ID: W2074906378
description: scientific article; zbMATH DE number 5816968