Abstract: 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 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{ 9/5, 2-1/2k +1}, 2, 2, respectively. All the proposed algorithms have a time complexity of O(|V|³) except that the two 2-approximation algorithms run in O(|V|² log|V|) time.

Key words: Approximation algorithm, Vehicle routing problem, Stacker Crane Problem, Pickup and delivery problem