期刊
COMPUTERS & OPERATIONS RESEARCH
卷 57, 期 -, 页码 83-94出版社
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2014.11.010
关键词
Biobjective path problems; Supported efficient paths; Label-setting algorithm
类别
资金
- Marsden [UOA1008 / 9075 362506]
- European Union Seventh Framework Programme (FP7-PEOPLE-IRSES) [246647]
- New Zealand Government, OptALI project [649378 v2]
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.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据