Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 57, Issue -, Pages 83-94Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2014.11.010
Keywords
Biobjective path problems; Supported efficient paths; Label-setting algorithm
Categories
Funding
- Marsden [UOA1008 / 9075 362506]
- European Union Seventh Framework Programme (FP7-PEOPLE-IRSES) [246647]
- New Zealand Government, OptALI project [649378 v2]
Ask authors/readers for more resources
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. (C) 2014 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available