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.


    Zugriff

    Zugriff über TIB

    Verfügbarkeit in meiner Bibliothek prüfen

    Bestellung bei Subito €


    Exportieren, teilen und zitieren



    Titel :

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



    Erschienen in:

    Transportation science ; 51 , 1 ; 19-33


    Erscheinungsdatum :

    2017




    Medientyp :

    Aufsatz (Zeitschrift)


    Format :

    Print


    Sprache :

    Englisch



    Klassifikation :

    Lokalklassifikation 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