Constant-Factor Approximation Algorithms for a Series of Combinatorial Routing Problems Based on the Reduction to the Asymmetric Traveling Salesman Problem

M. Yu. Khachay   ; E. D. Neznakhina   ; K. V. Ryzhenko

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 28 (2022) no. 3, pp. 241-258

Résumé

For the first time, algorithms with constant performance guarantees are substantiated for a series of asymmetric routing problems of combinatorial optimization: the Steiner cycle problem (SCP), the generalized traveling salesman problem (GTSP), the capacitated vehicle routing problem with unsplittable customer demands (CVRP-UCD), and the prize collecting traveling salesman problem (PCTSP). The presented results are united by the property that they all rely on polynomial cost-preserving reduction to appropriate instances of the asymmetric traveling salesman problem (ATSP) and on the $(22+\varepsilon)$-approximation algorithm for this classical problem proposed by O. Svensson and V. Traub in 2019.

Détail

Keywords: asymmetric traveling salesman problem, constant-factor approximation algorithm, polynomial-time reduction, Steiner cycle problem, generalized traveling salesman problem, prize collecting traveling salesman problem, vehicle routing problem.

Bibliographie

[1] Gutin G., Punnen A. P., The Traveling Salesman Problem and its variations, Springer, Boston; NY, 2007, 830 pp. | DOI | MR | Zbl

[2] Toth P., Vigo D., Vehicle routing: problems, methods and applications, SIAM, Philadelphia, 2014, 463 pp. | MR | Zbl

[3] Mor A., Speranza M. G., “Vehicle routing problems over time: a survey”, J. Oper. Res., 4OR-Q, 18:2 (2020), 129–149 | DOI | MR

[4] Chentsov A. G., Chentsov P. A., Petunin A. A., Sesekin A .N., “Model of megalopolises in the tool path optimisation for CNC plate cutting machines”, Internat. J. Product. Res., 56:14 (2018), 4819–4830 | DOI

[5] Chung S. H., Sah B., Lee J., “Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions”, Comput. Oper. Res., 123 (2020), 105004 | DOI | MR | Zbl

[6] Dantzig G. B., Fulkerson D. R., Johnson S. M., “Solution of a large-scale traveling-salesman problem”, J. Oper. Res. Soc. America, 2:4 (1954) | DOI | MR

[7] Dantzig G. B., Ramser J. H., “The truck dispatching problem”, Manag. Sci., 6:1 (1959), 80–91 | DOI | MR | Zbl

[8] Chentsov A. G., Korotaeva L. N., “The dynamic programming method in the generalized traveling salesman problem”, Math. Comp. Modelling, 25:1 (1997), 93–105 | DOI | MR | Zbl

[9] Chentsov A. G., Khachay M. Yu., Khachay D. M., “An exact algorithm with linear complexity for a problem of visiting megalopolises”, Proc. Steklov Inst. Math., 295:1 (2016), 38–46 | DOI | MR

[10] Archetti C., Bianchessi N., Speranza M., “Optimal solutions for routing problems with profits”, Discrete Appl. Math., 161:4–5 (2013), 547–557 | DOI | MR | Zbl

[11] Pecin D., Pessoa A., Poggi M., Uchoa E., “Improved branch-cut-and-price for capacitated vehicle routing”, Math. Program. Comp., 9:1 (2017), 61–100 | DOI | MR | Zbl

[12] Pessoa A., Sadykov R., Uchoa E., Vanderbeck F., “A generic exact solver for vehicle routing and related problems”, Math. Program., 183 (2020), 483–523 | DOI | MR | Zbl

[13] Avdoshin S., Beresneva E., “Local search metaheuristics for capacitated vehicle routing problem: a comparative study”, Proc. ISP RAS, 31:4 (2019), 121–138 | DOI

[14] Qiu M., Fu Z., Eglese R., Tang Q., “A Tabu search algorithm for the Vehicle Routing Problem with discrete split deliveries and pickups”, Comput. Oper. Res., 100 (2018), 102–116 | DOI | MR | Zbl

[15] Frifita S., Masmoudi M., “VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties”, International Transactions in Operational Research, 27:1 (2020), 291–313 | DOI | MR

[16] Smith S., Imeson F., “GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem”, Comput. Oper. Res., 87 (2017), 1–19 | DOI | MR | Zbl

[17] Nazari M., Oroojlooy A., Takac M., Snyder L. V., “Reinforcement learning for solving the vehicle routing problem”, Proc. of the 32nd International Conf. on Neural Information Processing Systems (NIPS'18), 2018, 9861–9871 | DOI

[18] Verbeeck C., Vansteenwegen P., Aghezzaf E.-H., “The time-dependent orienteering problem with time windows: a fast ant colony system”, Ann. Oper. Res., 254 (2017), 481–505 | DOI | MR | Zbl

[19] Zhukova G. N., Ulyanov M. V., Fomichev M. I., “A hybrid exact algorithm for the asymmetric Traveling Salesman Problem: Construction and a statistical study of computational efficiency”, Automat. Remote Control, 80:11 (2019), 2054–2067 | DOI | MR

[20] Papadimitriou C., “Euclidean TSP is NP-complete”, Theoret. Comput. Sci., 4:3 (1977), 237–244 | DOI | MR | Zbl

[21] Khachay M., Neznakhina K., “Towards tractability of the Euclidean Generalized Traveling Salesman Problem in grid clusters defined by a grid of bounded height”, Optimization Problems and Their Applications, Communications in Computer and Information Science, 871, 2018, 68–77 | DOI | MR

[22] Sahni S., Gonzales T., “P-complete approximation problems”, JACM, 23:3 (1976), 555–565 | DOI | MR | Zbl

[23] Asano T., Katoh N., Tamaki H., Tokuyama T., “Covering points in the plane by K-tours: Towards a polynomial time approximation scheme for General K”, Proc. of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC'97), ACM, NY, 1997, 275–283 | DOI | MR

[24] Bartal Y., Gottlieb L. A., Krauthgamer R., “The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme”, SIAM J. Comput., 45 (2016), 1563–1581 | DOI | MR | Zbl

[25] Khachay M., Ogorodnikov Yu., Khachay D., “Efficient approximation of the metric CVRP in spaces of fixed doubling dimension”, J. Glob. Optim., 80:3 (2021), 679–710 | DOI | MR | Zbl

[26] Christofides N., Worst-case analysis of a new heuristic for the Travelling Salesman Problem, Technical Report 388, Graduate School of Industrial Administration, Carnegie-Mellon University, 1976, 5 pp.

[27] Serdyukov A. I., “O nekotorykh ekstremalnykh obkhodakh v grafakh”, Upravlyaemye sistemy, 1978, no. 17, 76–79 | Zbl

[28] Asadpour A., Goemans M., Madry A., Gharan S. O., Saberi A., “An $O(log n/log log n)$-approximation algorithm for the Asymmetric Traveling Salesman Problem”, Oper. Res., 65:4 (2017), 1043–1061 | DOI | MR | Zbl

[29] Svensson O., Tarnawski J., Végh L., “A constant-factor approximation algorithm for the asymmetric Traveling Salesman Problem”, Proc. of the 50th Annual ACM Symposium on Theory of Computing (STOC), 2018, 204–213 | DOI | MR | Zbl

[30] Traub V., Vygen J., “An improved approximation algorithm for ATSP”, Proc. of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC 2020), 2020, 1–13 | DOI | MR | Zbl

[31] van Bevern R., Komusiewicz C., Sorge M., “A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: theory and experiments”, Networks, 70:3 (2017), 262–278 | DOI | MR

[32] Wahlström M., “Abusing the Tutte Matrix: An algebraic instance compression for the K-set-cycle problem”, STACS, 2013, 341–352 | DOI | MR | Zbl

[33] Steinová M., “Approximability of the minimum Steiner Cycle Problem”, Comput. Inform., 29:6+ (2010), 1349–1357 | MR | Zbl

[34] Das A., Mathieu C., “A quasipolynomial time approximation scheme for Euclidean Capacitated Vehicle Routing”, Algorithmica, 73:1 (2015), 115–142 | DOI | MR | Zbl

[35] Adamaszek A., Czumaj A., Lingas A., “PTAS for k-Tour Cover Problem on the plane for moderately large values of $k$”, Internat. J. Foundations Comp. Sci., 21:6 (2010), 893–904 | DOI | MR | Zbl

[36] M. Yu. Khachai, Yu. Yu. Ogorodnikov, “Approksimatsionnaya skhema Khaimovicha - Rinnoya Kana dlya CVRP v metricheskikh prostranstvakh fiksirovannoi razmernosti udvoeniya”, Tr. In-ta matematiki i mekhaniki UrO RAN, 25:4 (2019), 235–248 | DOI | MR

[37] Hall P., “On Representatives of Subsets”, J. London Math. Soc., 10:1 (1935), 26–30 | DOI

[38] Balas E., “The prize collecting traveling salesman problem”, Networks, 19:6 (1989), 621–636 | DOI | MR | Zbl

[39] Paul A., Freund D., Ferber A., Shmoys D., Williamson D., “Budgeted prize-collecting traveling salesman and minimum spanning tree problems”, Math. Oper. Res., 45:2 (2019), 576–590 | DOI | MR

[40] Bienstock D., Goemans M. X., Simchi-Levi D., Williamson D., “A note on the prize collecting traveling salesman problem”, Math. Progr., 59:1 (1993), 413–420 | DOI | MR | Zbl

[41] Khachay M., Ukolov S., Petunin A., “Problem-specific branch-and-bound algorithms for the precedence constrained generalized Traveling Salesman Problem”, Optimization and Applications - 12th International Conference (OPTIMA 2021), Proc., 2021, 136–148 | DOI | MR

[42] Bhattacharya B., Ćustić A., Rafiey A., Rafiey A., Sokol V., “Approximation algorithms for generalized MST and TSP in grid clusters”, Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 9486, 2015, 110–125 | DOI | MR | Zbl

[43] Khachay M., Neznakhina K., “Complexity and approximability of the Euclidean generalized traveling salesman problem in grid clusters”, Ann. Math. Artif. Intell., 88:1 (2020), 53–69 | DOI | MR | Zbl