.png){kind=icon}
返回
Minimum cost path problems with relays
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2010.04.010.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The minimum cost path problem with relays (MCPPR) consists of finding a minimum cost path from a source to a destination, along which relay nodes are located at a certain cost, subject to a weight constraint. This paper first models the MCPPR as a particular bicriteria path problem involving an aggregated function of the path and relay costs, as well as a weight function. A variant of this problem which takes into account all three functions separately is then considered. Formulating the MCPPR as a part of a bicriteria path problem allows the development of labeling algorithms in which the bound on the weight of paths controls the number of node labels. The algorithm for this constrained single objective function version of the problem has a time complexity of O(Wm+Wnlog(max{W, n})), where n is the number of nodes, m is the number of arcs and W is the weight upper bound. Computational results on random instances with up to 10 000 nodes and 100 000 arcs, are reported. (C) 2010 Elsevier Ltd. All rights reserved.
Keyword:
Relays
Shortest path problem
Bicriteria optimization
Labeling algorithms
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏 没有更多内容
没有更多内容