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

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