文献类型：期刊文献

中文题名：Approximation Algorithms for Multi-vehicle Stacker Crane Problems

作者：Wei Yu[1];Rui-Yong Dai[1];Zhao-Hui Liu[1]

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

年份：2023

卷号：11

期号：1

起止页码：109

中文期刊名：Journal of the Operations Research Society of China

外文期刊名：中国运筹学会会刊（英文）

收录：Scopus;CSCD:【CSCD2023_2024】；

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

语种：英文

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

摘要：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.