Approximation Algorithms For Multi-Vehicle Stacker Crane Problems

With the development and progress of the society,logistics scheduling,path navigation and unmanned driving technologies are playing an increasingly important role in daily pro-duction and life,attracting the attention of many mathematics and economists.In this thesis,a variety of multi-vehicle generalizations of the Stacker Crane Problem(SCP)is studied,and some approximate algorithms are proposed.The input consists of a mixed graph G=(V,E,A)with vertex set V,edge set E,arc set A,and a nonnegative integer cost function c on E?A.We consider the following four problems.(1)k-depot Stacker Crane Problem(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-Stacker Crane Problem(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.(4)k-Stacker Crane Path Problem(k-SCPP).There are no given depots and each vehicle may start from any vertex and end at any vertex.The objective is to find a collection of k walks including all the arcs of A such that the total cost of the walks is minimized.We present the first constant-factor approximation algorithms for all the above four prob-lems.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 approxilation ratios max{9/5,2-1/2k+1},2,2,respectively.For the k-SCPP,we first give a 2-approximation algorithm for the case that the cost of arc of A are symmetric.Then,for the SCPP,the special case of k-SCPP when k=1,we develop a 3-approximation algorithm for all instances and a 9/5-approximation algorithm for the case that the cost of arc of A are symmetric.All the proposed algorithms have a time complex-ity of O(V|3)except that the three 2-approximation algorithms run in O(|V|2 log |V|)time.