Title :
Constrained Shortest Path Problem
Author_Institution :
Sch. of Bus., Sun Yat-sen Univ., Guangzhou, China
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 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.
Keywords :
computational complexity; constraint theory; operations research; optimisation; K constrained shortest path problem; automated storage system; loopless constraint; network modification procedure; resource constraint; retrieval system; separable property; structural branching procedure; Logistics; networks; operations research; routing;
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
DOI :
10.1109/TASE.2009.2012434