Jp. Van Den Berg et Ajrm. Gademann, Optimal routing in an automated storage/retrieval system with dedicated storage, IIE TRANS, 31(5), 1999, pp. 407-415
We address the sequencing of requests in an automated storage/retrieval sys
tem with dedicated storage. We consider the block sequencing approach, wher
e a set of storage and retrieval requests is given beforehand and no new re
quests come in during operation. The objective for this static problem is t
o find a route of minimal total travel time in which all storage and retrie
val requests may be performed. The problem of sequencing a list of retrieva
ls is equivalent to the Traveling Salesman Problem (TSP), and thus NP-hard
in general. We show that the special case of sequencing under the dedicated
storage policy can be solved in polynomial time. The results apply to syst
ems with arbitrary positions of the input and output stations. This general
izes the models in the literature, where only combined input/output station
s are considered. Furthermore we identify a single command area in the rack
. At the end we evaluate the model against heuristic procedures.