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|3) except that the two 2-approximation algorithms run in O(|V|2 log|V|) time.
Wei Yu, Rui-Yong Dai, Zhao-Hui Liu
. Approximation Algorithms for Multi-vehicle Stacker Crane Problems[J]. Journal of the Operations Research Society of China, 2023
, 11(1)
: 109
-132
.
DOI: 10.1007/s40305-021-00372-7
[1] Frederickson, G.N., Hecht, M.S., Kim, C.E.:Approximation algorithms for some routing problems.SIAM J Comput 7(2), 178-193(1978)
[2] Rathinam, S., Sengupta, R., Darbha, S.:A resource allocation algorithm for multivehicle systems with nonholonomic constraints.IEEE Trans Autom Sci Eng 4(1), 98-104(2007)
[3] Atallah, M.J., Kosaraju, S.R.:Efficient solutions to some transportation problems with applications to minimizing robot arm travel.SIAM J Comput 17(5), 849-869(1988)
[4] Frederickson, G.N., Guan, D.J.:Nonpreemptive ensemble motion planning on a tree.J Algorithms 15(1), 29-60(1993)
[5] Calvo, R.W., Colorni, A.:An effective and fast heuristic for the Dial-a-Ride problem.4OR 5(1), 61-73(2007)
[6] Brassaia, S.T., Iantovicsb, B.:Artificial intelligence in the path planning optimization of mobile agent navigation.Proc.Econ.Finance 3, 243-250(2012)
[7] Parragh, S.N., Doerner, K.F., Hartl, R.F.:A survey on pickup and delivery problems, Part I:Transportation between customers and depot.J.Fddotur Betriebswirtschaft 58(1), 21-51(2008)
[8] Parragh, S.N., Doerner, K.F., Hartl, R.F.:A survey on pickup and delivery problems, Part II:Transportation between pickup and delivery locations.J.Fddotur Betriebswirtschaft 58(2), 81-117(2008)
[9] Berbeglia, G., Cordeau, J.F., Gribkovskaia, I., Laporte, G.:Static pickup and delivery problems:a classification scheme and survey.TOP 15, 1-31(2007)
[10] Garey, M.R., Johnson, D.S.:Computers and Intractability:A Guide to the Theory of NP-Completeness.Freeman, San Francisco (1979)
[11] Safilian, M., Hashemi, S.M., Eghbali, S., Safilian, A.:In:the Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp.669-675(2016)
[12] Zhang, L.:Polynomial algorithms for the k-Chinese postman problem.Polynomial algorithms for the k-Chinese postman problem.In:the Proceedings of the IFIP 12th World Computer Congress, pp.430-435(1992)
[13] Arkin, E.M., Hassin, R., Levin, R.:Approximations for minimum and min-max vehicle routing problems.J.Algorithms 59(1), 1-18(2006)
[14] Christofides, N.:Worst-case analysis of a new heuristic for the traveling salesman problem.In:Technical Report, Graduate School of Industrial Administration.Carnegie-Mellon University, Pittsburgh (1976)
[15] Serdyukov, A.:On some extremal walks in graphs.Upravlyaemye Sistemy 17, 76-79(1978).([in Russian])
[16] van Bevern, R., Slugin, V.A.:A historical note on the 3/2-approximation algorithm for the metric traveling salesman problem.Historia Mathematica 53, 118-127(2020)
[17] Xu, Z., Xu, L.:Rodrigues, B.:An analysis of the extended Christofides heuristic for the k-depot TSP.Oper.Res.Lett.39, 218-223(2011)
[18] Rathinam, S., Sengupta, R.:23 -approximation algorithm for two variants of a 2-depot Hamiltonian path problem.Oper.Res.Lett.38, 63-68(2010)
[19] Giannakos, A., Hifi, M., Kheffache, R., Ouafi, R.:An approximation algorithm for the three depots Hamiltonian path problem.In:the Proceedings of the the 1st International Symposium and 10th Balkan Conference on Operational Research, pp.351-359(2013)
[20] Eiselt, H.A., Gendreau, M., Laporte, G.:Arc routing problems, part I:The Chinese postman problem.Oper.Res.43, 231-242(1995)
[21] Nobert, Y., Picard, J.C.:An optimal algorithm for the mixed Chinese postman problem.Networks 27, 95-108(1996)
[22] Korte, B., Vygen, J.:Combinatorial Optimization:Theory and Algorithms, 6th edn.Springer, Berlin (2018)
