Polynomial Time Algorithms to Minimize Total Travel Time in a Two-Depot Automated Storage/Retrieval System

Amir Hossein Gharehgozli (), Yugang Yu (), Xiandong Zhang () and René de Koster ()
Additional contact information
Amir Hossein Gharehgozli: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands
Yugang Yu: School of Management, University of Science and Technology of China, Hefei 230026, China
Xiandong Zhang: Department of Management Science, School of Management, Fudan University, Shanghai 200433, China
René de Koster: Rotterdam School of Management, Erasmus University, 3062 PA Rotterdam, Netherlands

Transportation Science, 2017, vol. 51, issue 1, 19-33

Abstract: 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.

Keywords: automated storage and retrieval system; two depots; total travel time; traveling salesman problem; polynomial time algorithm (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (17)

Downloads: (external link)
https://doi.org/10.1287/trsc.2014.0562 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:51:y:2017:i:1:p:19-33

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().