检索结果-内蒙古大学图书馆

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第1期276卷 106-118页

作者： Sedeno-noda, Antonio Colebrook, Marcos Univ La Laguna Dept Matemat Estadist & Invest Operat San Cristobal La Laguna 38271 Santa Cruz De T Spain Univ La Laguna Dept Ingn Informat & Sistemas San Cristobal La Laguna 38271 Santa Cruz De T Spain

We generalize the Dijkstra algorithm to the biobjective Shortest path (BSP) problem. The proposed method keeps only one candidate label per node in a priority queue of size n. In this way, we introduce a novel algorithm to solve the one-to-all BSP problem determining all non-dominated points in the outcome space and one efficient path associated with each of them. For the case of the one-to-one BSP problem, we incorporate the classical bidirectional search scheme in the proposed algorithm to reduce the number of iterations in practice. The proposed algorithm also includes pruning strategies to avoid the computation of unnecessary labels. The result is a fast algorithm to solve the one-to-one BSP problem in large networks. A computational experiment comparing the performance of the proposed method and the state-of-the-art methods is included. (C) 2019 Elsevier B.V. All rights reserved.

关键词： Network optimization biobjective path problems Efficient paths Dijkstra's algorithm

来源：评论

学校读者我要写书评

暂无评论

A Dijkstra-like method computing all extreme supported non-dominated solutions of the biobjective shortest path problem

引用

COMPUTERS & OPERATIONS RESEARCH 2015年 57卷 83-94页

作者： Sedeno-Noda, Antonio Raith, Andrea Univ La Laguna Dept Matemat Estadist & Invest Operat San Cristobal De La Lagu 38271 Santa Cruz De T Spain Univ Auckland Dept Engn Sci Auckland New Zealand

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.

关键词： biobjective path problems Supported efficient paths Label-setting algorithm

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：