Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot AS/RS

Amir Gharehgozli, Y Yu, X (Xiandong) Zhang, Rene de Koster

Research output: Contribution to journalArticleAcademicpeer-review

41 Citations (Scopus)


We sequence storage and retrieval jobs to minimize total travel time of a storage/retrieval (S/R) machine in a two-depot automated storage/retrieval system. These systems include storage systems with aisle-captive S/R machines and storage blocks with bridge cranes. The S/R machine must move retrieval unit loads from their current locations in the system to one of the two depots. In addition, it must move storage unit loads from given depots to given locations in the system. We model the problem as an asymmetric traveling salesman problem, which is in general ??-hard. We develop an algorithm to solve the problem in polynomial time, using the property that the system has two depots and the S/R machine always returns to one of the depots to pick up or deliver a load. Furthermore, we develop additional polynomial time algorithms for the following four special cases: (1) retrieval loads have to be delivered to given depots; (2) the system has one input depot and one output depot; (3) the system has a single depot; and (4) there are arbitrary S/R machine starting and ending locations. The computational results show the effectiveness of the proposed algorithms. Compared to first-come-first-served and nearest neighbor algorithms, commonly used in practice, the total travel time reduces on average by more than 30% and 15%, respectively.
Original languageEnglish
Pages (from-to)19-33
Number of pages15
JournalTransportation Science
Issue number1
Publication statusPublished - 15 Dec 2014

Research programs



Dive into the research topics of 'Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot AS/RS'. Together they form a unique fingerprint.

Cite this