| 带约束条件的K最短路问题 |
| |
| 引用本文： | 石宁,贾迎琳.带约束条件的K最短路问题[J].中大管理研究,2009,4(1). |
| |
| 作者姓名： | 石宁 贾迎琳 |
| |
| 作者单位： | 中山大学管理学院 |
| |
| 摘 要： | 在本文中，我们研究了一个生成K条满足一组约束条件的最短路问题。为了求解此问题，我们设计了一个结构化分支策略，将此问题划分为最多必｜N｜个子问题，这里｜N｜表示网络中的结点数。每个子问题通过一个网络修正步骤均可转化为一个带约束的最短路问题（constraint shortest path problem，CSP）。当这些约束条件满足所谓的可分性质时，子问题便可得到进一步简化。基于这个结构化分支策略，我们针对一个需要考虑资源和无回路约束的应用问题设计了一个专门的算法。数据实验表明，我们的算法十分有效而稳定。
|
| 关 键 词： | 物流 网络 运筹学 路径规划 |
K Constrained Shortest Paths Problem |
| |
| Shi Ning Jia Yinglin.K Constrained Shortest Paths Problem[J].China Management Studies,2009,4(1). |
| |
| Authors: | Shi Ning Jia Yinglin |
| |
| Institution: | Shi Ning Jia Yinglin |
| |
| Abstract: | Motivated by a real project for a sophisticated Automated Storage and Retrieval System(AS/RS),we study the problem of generating K shortest paths that are required to satisfy a set of constraints.We propose a structural branching procedure that decomposes the problem into at most K|N| subproblems,where |N| is the number of nodes in the network.By using a Network Modification procedure,each subproblem can be transformed into a constrained shortest path problem(CSP).When these constraints satisfy a so called ... |
| |
| Keywords: | logistics network operational research path-planning |
| 本文献已被 CNKI 维普 等数据库收录！ |
