Efficient solution generation for the bicriterion shortest path problems

DOI10.1504/IJOR.2010.035522MaRDI QIDQ606615zbMATH OpenOpenAlexFDO

Authors Abdallah W. Aboutahoun

Publication date 17 November 2010

Published in International Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1504/ijor.2010.035522

zbMATH Keywords

biobjective shortest path problemBSPPcontinuous relaxationefficient extreme pointsnetwork optimisationnon-dominated setssimplex based algorithms

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Multi-objective and goal programming (90C29)

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.

Recommendations

• A parametric approach to solving bicriterion shortest path problems
• A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem
• A comparison of solution strategies for biobjective shortest path problems
• A label correcting approach for solving bicriterion shortest-path problems
• A genetic algorithms to solve the bicriteria shortest path problem

Cited in

(10)

• Finding non-dominated bicriteria shortest pairs of disjoint simple paths
• On the sum-max bicriterion path problem.
• Computing all efficient solutions of the biobjective minimum spanning tree problem
• A genetic algorithms to solve the bicriteria shortest path problem
• A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem
• A comparison of heuristic best-first algorithms for bicriterion shortest path problems
• A Bicriteria Approach for Saving a Path Maximizing Dynamic Contraflow
• A parametric approach to solving bicriterion shortest path problems
• A comparison of solution strategies for biobjective shortest path problems
• On algorithms for the tricriteria shortest path problem with two bottleneck objective functions

This page was built for publication: Efficient solution generation for the bicriterion shortest path problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q606615)