A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem. (May 2015)

• Record Type: Journal Article
• Authors: Sedeño-Noda, Antonio; Raith, Andrea
• Is Part Of: Computers & operations research. Volume 57(2015)
• Page Start: 83
• Page End: 94
• Publication Date: 2015-05
• Subjects: Biobjective path problems -- Supported efficient paths -- Label-setting algorithm; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2014.11.010
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We address the problem of determining all extreme supported solutions of the biobjective shortest path problem. A novel Dijkstra-like method generalizing Dijkstra׳s algorithm to this biobjective case is proposed. The algorithm runs in O( N ( m + n log n )) time to solve one-to-one and one-to-all biobjective shortest path problems determining all extreme supported non-dominated points in the outcome space and one supported efficient path associated with each one of them. Here n is the number of nodes, m is the number of arcs and N is the number of extreme supported points in outcome space for the one-to-all biobjective shortest path problem. The memory space required by the algorithm is O( n + m ) for the one-to-one problem and O( N + m ) for the one-to-all problem. A computational experiment comparing the performance of the proposed methods and state-of-the-art methods is included.