High multiplicity asymmetric traveling salesman problem with feedback vertex set and its application to storage/retrieval system

Amir Gharehgozli, Chao Xu and Wenda Zhang

European Journal of Operational Research, 2021, vol. 289, issue 2, 495-507

Abstract: We describe an algorithm for the high multiplicity asymmetric traveling salesman problem with feedback vertex set of size k (HMATSP-kFVS) where each vertex can be visited a certain number of times and each cycle in a solution contains at least one vertex from the feedback vertex set. We show how it can be used to improve algorithms in automated storage and retrieval systems. An automated storage and retrieval system includes storage blocks and storage and retrieval machines that either move to retrieve unit loads from their current locations in the system to a depot or take unit loads from a depot and store them to specific locations in the system. Given n storage and retrieval requests in a system with k depots and one storage and retrieval machine, we show that our algorithm for HMATSP-kFVS can solve the problem of minimizing total traveling time of the storage and retrieval machine in O(nk+n3) time when all depots are specialized (each depot fulfills one type of requests) and in O(n2k+n3) time when depots are regular (each depot fulfills both types of requests). The best previous algorithm only solves the special case of the problem with 2 regular depots in O(n6) time. The applicability of our algorithm for several generalizations and special cases of the problem is also discussed. Furthermore, to evaluate the performance of our solution method, we perform extensive numerical experiments.

Keywords: Logistics; OR in maritime industry and warehousing; Storage/retrieval system storage; High multiplicity ATSP storage; Polynomial time algorithm (search for similar items in EconPapers)
Date: 2021
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221720306494
Full text for ScienceDirect subscribers only

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:eee:ejores:v:289:y:2021:i:2:p:495-507

DOI: 10.1016/j.ejor.2020.07.038

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().