DocumentCode :
842094
Title :
K Constrained Shortest Path Problem
Author :
Shi, Ning
Author_Institution :
Sch. of Bus., Sun Yat-sen Univ., Guangzhou, China
Volume :
7
Issue :
1
fYear :
2010
Firstpage :
15
Lastpage :
23
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;
fLanguage :
English
Journal_Title :
Automation Science and Engineering, IEEE Transactions on
Publisher :
ieee
ISSN :
1545-5955
Type :
jour
DOI :
10.1109/TASE.2009.2012434
Filename :
4912443
Link To Document :
بازگشت