Approximation Algorithms for Multi-vehicle Stacker Crane Problems  

作　　者：Wei Yu Rui-Yong Dai Zhao-Hui Liu 

机构地区：[1]Department of Mathematics,East China University of Science and Technology,Shanghai,200237,China

出　　处：《Journal of the Operations Research Society of China》2023年第1期109-132,共24页中国运筹学会会刊（英文）

基　　金：This research was supported by the National Natural Science Foundation of China(Nos.11671135 and 11871213);the Natural Science Foundation of Shanghai(No.19ZR1411800)。

摘　　要：We study a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP).The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E and arc set A,and a nonnegative integer cost function c on E∪A.We consider the following three problems:(1)k-depot SCP(k-DSCP).There is a depot set D⊆V containing k distinct depots.The goal is to determine a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized,where each closed walk corresponds to the route of one vehicle and has to start from a distinct depot and return to it.(2)k-SCP.There are no given depots,and each vehicle may start from any vertex and then go back to it.The objective is to find a collection of k closed walks including all the arcs of A such that the total cost of the closed walks is minimized.(3)k-depot Stacker Crane Path Problem(k-DSCPP).There is a depot set D⊆V containing k distinct depots.The aim is to find k(open)walks including all the arcs of A such that the total cost of the walks is minimized,where each(open)walk has to start from a distinct depot but may end at any vertex.We present the first constant-factor approximation algorithms for all the above three problems.To be specific,we give 3-approximation algorithms for the k-DSCP,the k-SCP and the k-DSCPP.If the costs of the arcs are symmetric,i.e.,for every arc there is a parallel edge of no greater cost,we develop better algorithms with approximation ratios max{9/5,2−1/2k+1},2,2,respectively.All the proposed algorithms have a time complexity of O(|V|3)except that the two 2-approximation algorithms run in O(|V|2log|V|)time.

关 键 词：Approximation algorithm Vehicle routing problem Stacker Crane Problem Pickup and delivery problem 

分 类 号：O15[理学—数学]