×

Approximation algorithms for some min-max and minimum stacker crane cover problems. (English) Zbl 1507.90155

Summary: We study two stacker crane cover problems and their variants. Given a mixed graph \(G=(V,E,A)\) with vertex set \(V\), edge set \(E\) and arc set \(A\), each edge or arc is associated with a nonnegative weight. The min-max stacker crane cover problem (SCCP) aims to find at most \(k\) closed walks covering all the arcs in \(A\) such that the maximum weight of the closed walks is minimum. The minimum stacker crane cover problem (MSCCP) is to cover all the arcs in \(A\) by a minimum number of closed walks of weight at most \(\lambda\). The min-max stacker crane walk cover problem (SCWCP)/minimum stacker crane walk cover problem (MSCWCP) is a variant of the SCCP/MSCCP with closed walks replaced by (open) walks. For the SCCP with weakly symmetric arc weights, i.e. for every arc there exists a parallel edge of no greater weight, we obtain a \(\frac{33}{5}\)-approximation algorithm. This improves on the previous \(\frac{37}{5}\)-approximation algorithm for a restricted case of the SCCP with weakly symmetric arc weights. If the arc weights are weakly symmetric, we devise the first constant-factor approximation algorithms for the SCWCP, the MSCCP and the MSCWCP with ratios 5, 5 and \(\frac{7}{2}\), respectively. Finally, we first propose a 4-approximation algorithm for the (general) MSCWCP.

MSC:

90C27 Combinatorial optimization
90C59 Approximation methods and heuristics in mathematical programming
Full Text: DOI

References:

[1] Arkin, EM; Hassin, R.; Levin, A., Approximations for minimum and min-max vehicle routing problems, J Algorithms, 59, 1-18 (2006) · Zbl 1112.68135 · doi:10.1016/j.jalgor.2005.01.007
[2] Atallah, MJ; Kosaraju, SR, Efficent solutions to some transportation problems with applications to minimizing robot arm travel, SIAM J Comput, 17, 5, 849-869 (1988) · Zbl 0662.68043 · doi:10.1137/0217053
[3] Bao, X.; Lu, C.; Huang, D.; Yu, W., Approximation algorithm for min-max cycle cover problem on a mixed graph, Oper Res Trans, 25, 1, 107-113 (2021) · Zbl 1488.90243
[4] Berbeglia, G.; Cordeau, JF; Gribkovskaia, I.; Laporte, G., Static pickup and delivery problems: a classification scheme and survey, TOP, 15, 1-31 (2007) · Zbl 1121.90001 · doi:10.1007/s11750-007-0009-0
[5] Calvo RW, Colorni A (2007) An effective and fast heuristic for the Dial-a-Ride problem. 4OR 5(1):61-73 · Zbl 1121.90019
[6] Christofides N (1976) Worst-case analysis of a new heuristic for the traveling salesman problem. Technical Report, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh
[7] Corberan, A.; Laporte, G., Arc routing: problems, methods, and applications, 101-127 (2015), Philadelphia: SIAM, Philadelphia · Zbl 1322.90006 · doi:10.1137/1.9781611973679
[8] Eiselt, HA; Gendreau, M.; Laporte, G., Arc routing problems, part I: the Chinese postman problem, Oper Res, 43, 231-242 (1995) · Zbl 0837.90037 · doi:10.1287/opre.43.2.231
[9] Eiselt, HA; Gendreau, M.; Laporte, G., Arc routing problems, part II: the rural postman problem, Oper Res, 43, 399-414 (1995) · Zbl 0853.90042 · doi:10.1287/opre.43.3.399
[10] Frederickson, GN; Hecht, MS; Kim, CE, Approximation algorithms for some routing problems, SIAM J Comput, 7, 2, 178-193 (1978) · doi:10.1137/0207017
[11] Frederickson, GN; Guan, DJ, Nonpreemptive ensemble motion planning on a tree, J Algorithms, 15, 1, 29-60 (1993) · Zbl 0784.68040 · doi:10.1006/jagm.1993.1029
[12] Gao, X.; Fan, J.; Wu, F.; Chen, G., Approximation algorithms for sweep coverage problem with multiple mobile sensors, IEEE/ACM Trans Netw, 26, 2, 990-1003 (2018) · doi:10.1109/TNET.2018.2815630
[13] Garey, M.; Johnson, D., Computers and intractability: a guide to the theory of NP-completeness (1979), San Francisco: Freeman, San Francisco · Zbl 0411.68039
[14] Korte, B.; Vygen, J., Combinatorial optimization: theory and algorithms (2018), Berlin: Springer, Berlin · Zbl 1390.90001 · doi:10.1007/978-3-662-56039-6
[15] Mao, Y.; Yu, W.; Liu, Z.; Xiong, J., Approximation algorithms for some minimum postmen cover problems, Discrete Appl Math (2022) · Zbl 1496.90079 · doi:10.1016/j.dam.2022.01.005
[16] Olivier, Q.; Andre, L.; Fabien, L.; Olivier, P.; Martin, T., Solving the large-scale min-max \(k\)-rural postman problem for snow plowing, Networks, 70, 3, 195-215 (2017) · Zbl 1539.90129 · doi:10.1002/net.21759
[17] Parragh SN, Doerner KF, Hartl R (2008a) A survey on pickup and delivery problems, Part I: transportation between customers and depot. J \(F \ddot{u}\) r Betriebswirtschaft 1:21-51
[18] Parragh SN, Doerner KF, Hartl R (2008b) A survey on pickup and delivery problems, Part II: Transportation between pickup and delivery locations. J \(F \ddot{u}\) r Betriebswirtschaft 2:81-117
[19] Safilian M, Hashemi SM, Eghbali S, Safilian A (2016) An approximation algorithm for the Subpath planning. In: The Proceedings of the 25th International Joint Conference on Artificial Intelligence, pp 669-675
[20] Treleaven, K.; Pavone, M.; Frazzoli, E., Asymptotically optimal algorithms for one-to-one pickup and delivery problems with applications to transportation systems, IEEE Trans Autom Control, 58, 9, 2261-2276 (2013) · Zbl 1369.90015 · doi:10.1109/TAC.2013.2259993
[21] Xu, W.; Liang, W.; Lin, X., Approximation algorithms for min-max cycle cover problems, IEEE Trans Comput, 64, 600-613 (2015) · Zbl 1360.68907 · doi:10.1109/TC.2013.2295609
[22] Yu, W.; Dai, R.; Liu, Z., Approximation algorithms for multi-vehicle stacker crane problems, J Oper Res Soc China (2022) · Zbl 1524.90274 · doi:10.1007/s40305-021-00372-7
[23] Yu, W.; Liu, Z.; Bao, X., Approximation algorithms for some min-max postmen cover problems, Ann Oper Res, 300, 267-287 (2021) · Zbl 1480.90216 · doi:10.1007/s10479-021-03933-4
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.