4.7 Article

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

Journal

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
Volume 289, Issue 2, Pages 495-507

Publisher

ELSEVIER
DOI: 10.1016/j.ejor.2020.07.038

Keywords

Logistics; OR in maritime industry and warehousing; Storage/retrieval system storage; High multiplicity ATSP storage; Polynomial time algorithm

Ask authors/readers for more resources

The study presents an algorithm for the high multiplicity asymmetric traveling salesman problem with feedback vertex set of size k, showing its potential for improving algorithms in automated storage and retrieval systems. The algorithm demonstrates efficient time complexity for minimizing total traveling time of the storage and retrieval machine under certain scenarios, outperforming previous approaches. The applicability and performance of the algorithm is further discussed and evaluated through extensive numerical experiments.
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(n(k) + n(3)) time when all depots are specialized (each depot fulfills one type of requests) and in O(n(2k) + n(3)) 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(n(6)) 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. (C) 2020 Elsevier B.V. All rights reserved.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available