带约束条件的K最短路问题

K Constrained Shortest Paths Problem

在本文中,我们研究了一个生成K条满足一组约束条件的最短路问题。为了求解此问题,我们设计了一个结构化分支策略,将此问题划分为最多KN个子问题,这里N表示网络中的结点数。每个子问题通过一个网络修正步骤均可转化为一个带约束的最短路问题(constraintshortestpathproblem,CSP)。当这些约束条件满足所谓的可分性质时,子问题便可得到进一步简化。基于这个结构化分支策略,我们针对一个需要考虑资源和无回路约束的应用问题设计了一个专门的算法。数据实验表明,我们的算法十分有效而稳定。

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 ｜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 separable property, the subproblem can be further simplified. Based on this branching procedure, we propose a specific algorithm for an application where resource and loopless constraints have to be respected. Numerical results show that our algorithm is very efficient and robust.