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.


    Access

    Access via TIB

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

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



    Published in:

    Publication date :

    2017




    Type of media :

    Article (Journal)


    Type of material :

    Print


    Language :

    English



    Classification :

    Local classification TIB:    770/1935/7000
    BKL:    55.80 / 55.80 Verkehrswesen, Transportwesen: Allgemeines



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

    Gharehgozli, Amir Hossein / Yu, Yugang / Zhang, Xiandong et al. | British Library Online Contents | 2017


    Selecting routes to minimize urban travel time

    Campbell, James F. | Elsevier | 1991


    Vashi to Kalyan Depot Bus Route Travel Time Reliability

    Kukadiya, Lokesh / Thakkar, Yash / Vavaiya, Jayesh et al. | IEEE | 2018