Title: Efficient solution generation for the bicriterion shortest path problems

Authors: Abdallah W. Aboutahoun

Addresses: Department of Mathematics, King Saud University, Riyadh, Kingdom of Saudi Arabia; Department of Mathematics, Alexandria University, Alexandria, Egypt

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.

DOI: 10.1504/IJOR.2010.035522

International Journal of Operational Research, 2010 Vol.9 No.3, pp.287 - 305

Published online: 30 Sep 2010 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article