文献类型：期刊文献

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

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

机构：[1]East China Univ Sci & Technol, Dept Math, Shanghai 200237, Peoples R China

年份：2023

卷号：11

期号：1

起止页码：109

外文期刊名：JOURNAL OF THE OPERATIONS RESEARCH SOCIETY OF CHINA

收录：EI(收录号：20220211441016);WOS:【ESCI(收录号:WOS:000739751300001)】；

基金：This research was supported by the National Natural Science Foundation of China (Nos. 11671135 and 11871213), and 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 U A. We consider the following three problems: (1) k -depot SCP (k-DSCP). There is a depot set D c 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 C 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 constantfactor 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(, 2 2k1+1), 2, 2, respectively. All the proposed algorithms have a time complexity of 0 1V13) except that the two 2 -approximation algorithms run in 0(1V12 log 1V1) time,