.png){kind=icon}
返回
EFFICIENT ALGORITHMS FOR SOLVING THE SHORTEST COVERING PATH PROBLEM
.png){kind=icon}
PRE
AI
DOI：10.1287/trsc.28.4.317.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
The Shortest Covering Path Problem (SCPP) is one of identifying the least cost path from a pre-specified starting node to a pre-specified terminus node. The path is constrained by the condition that it must cover every node in the network. A node is considered to be covered if it is within some pre-specified covering distance of a node on the path. This SCPP has many potential applications, especially in hierarchical network design, and bi-modal routing problems. In this paper we introduce two efficient algorithms for solving the SCPP. The first is a heuristic based upon a Lagrangian relaxation of the problem. The second is an exact algorithm based upon a branch and bound procedure which utilizes the bounds generated by the Lagrangian relaxation scheme. Computational tests indicate that both procedures are very efficient. The heuristic identified and verified the optimal solution for 135 of the 160 test problems solved. The optimal solution to the remaining 25 problems was readily identified by the exact algorithm.
Keyword:
TREE PROBLEMS
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
