Optimizing multi-inserts in routing problems with constraints

A. G. Chentsov   ; A. M. Grigor'ev

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 28 (2018) no. 4, pp. 513-530

Résumé

We consider a problem of sequential traversal of megalopolises (nonempty finite sets) with travel cost functions depending on the set of pending tasks and precedence constraints. Its formulation is aimed at engineering problems in fission power generation connected with minimizing the exposure of staff to radiation and in machine engineering (routing of a CNC sheet cutting machine's tool). This discrete optimization problem is assumed to be sufficiently large-scale to necessitate the use of heuristics. We consider a procedure of local improvement for heuristics through a successive application of optimizing multi-inserts-finite disjoint sets of inserts. Each insert is assumed to be optimized by means of a broadly understood dynamic programming procedure. We show that in an “additive” routing problem of this kind (with precedence constraints and complex travel cost functions) the result's improvements are also aggregated additively. The proposed construction admits a parallel implementation for multiprocessor systems; in this case, the inserts are distributed to computational nodes and formed in an independent way.

Détail

Keywords: dynamic programming, multi-inserts, parallel algorithm.

Bibliographie

[1] Chentsov A. A., Chentsov A. G., “The problem of megalopolises consistent detouring”, Vestn. Tambov. Univ. Ser. Estestv. Tekh. Nauki, 19:2 (2014), 454–475 (in Russian)

[2] Petunin A. A., Chentsov A. G., Chentsov P. A., “Local dynamic programming incuts in routing problems with restrictions”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, no. 2, 56–75 (in Russian) | DOI

[3] Chentsov A. G., “The Bellmann insertions in the route problem with constraints and complicated cost functions”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2014, no. 4, 122–141 (in Russian) | DOI

[4] Chentsov A. G., “The Bellmann insertions in route problems with constraints and complicated cost functions. II”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 26:4 (2016), 565–578 (in Russian) | DOI | Zbl

[5] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Theoretical issues”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman's problem. II: Exact methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[7] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximate algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

[8] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer, 2002, 850 pp. | MR

[9] Cook W. J., In pursuit of the traveling salesman: Mathematics at the limits of computation, Princeton University Press, NJ, 2012 | MR | Zbl

[10] Bellman R., “Dynamic programming treatment of the travelling salesman problem”, Journal of the ACM, 9:1 (1962), 61–63 | DOI | MR | Zbl

[11] Held M., Karp R. M., “A dynamic programming approach to sequencing problems”, Journal of the Society for Industrial and Applied Mathematics, 10:1 (1962), 196–210 | DOI | MR | Zbl

[12] Little J. D. C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[13] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing methods and their applications in problems of improving the safety and efficiency of operation of nuclear power plants, Novye Tekhnologii, M., 2012

[14] Petunin A. A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo \linebreak Tekhnicheskogo Universiteta. Seriya: Upravlenie, Vychislitel'naya Tekhnika i Informatika, 13:2 (35) (2009), 280–286 (in Russian)

[15] Frolovskii V. D., “Computer-aided design of the control programs for thermal metal cutting on NPC machines”, Informatsionnye Tekhnologii v Proektirovanii i Proizvodstve, 2005, no. 4, 63–66 (in Russian)

[16] Ganelina N. D., Frolovskii V. D., “On constructing the shortest circuits on a set of line segments”, Sib. Zh. Vychisl. Mat., 9:3 (2006), 241–252 (in Russian)

[17] Petunin A. A., Chentsov A. G., Chentsov P. A., “On routing tool motion on the sheet cutting NPC machines”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2 (169), 103–111 (in Russian)

[18] Verkhoturov M. A.. Tarasenko P. Yu., “The software for the problem of the cutting instrument route optimization based on chain cutting when a flat figure is cut”, Vestnik Ufimskogo Gosudarstvennogo Aviatsionnogo Tekhnicheskogo Universiteta. Seriya: Upravlenie, Vychislitel'naya Tekhnika i Informatika, 10:2 (27) (2008), 123–130 (in Russian)

[19] Wang G. G.. Xie S. Q., “Optimal process planning for a combined punch-and-laser cutting machine using ant colony optimization”, International Journal of Production Research, 43:11 (2005), 2195–2216 | DOI

[20] Lee M. K., Kwon K. B., “Cutting path optimization in CNC cutting processes using a two-step genetic algorithm”, International Journal of Production Research, 44:24 (2006), 5307–5326 | DOI | Zbl

[21] Ye J.. Chen Z. G., “An optimized algorithm of numerical cutting path control in garment manufacturing”, Advanced Materials Research, 796 (2013), 454–457 | DOI

[22] Chentsov A. G., “On a parallel procedure for constructing the Bellman function in the generalized problem of courier with internal jobs”, Automation and Remote Control, 73:3 (2012), 532–546 | DOI | MR | Zbl

[23] Chentsov A. G., “A parallel procedure of constructing Bellman function in the generalized courier problem with interior works”, Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 2012, no. 12, 53–76 (in Russian)

[24] Chentsov A. G., Kosheleva M. S., “Dynamic programming in the precedence constrained TSP with the costs depending on a list of tasks”, Mekhatronika, Avtomatizatsiya, Upravlenie, 16:4 (2015), 232–244 (in Russian) | DOI

[25] Chentsov A. G., Grigoryev A. M., “Dynamic programming method in a routing problem: a scheme of independent computations”, Mekhatronika, Avtomatizatsiya, Upravlenie, 17:12 (2016), 834–846 (in Russian) | DOI

[26] Kuratovskii K., Mostovskii A., Theory of sets, Mir, M., 1970, 416 pp.

[27] Dieudonne J., Foundations of modern analysis, Mir, M., 1964, 430 pp.

[28] Cormen T., Leiserson Ch., Rivest R., Introduction to algorithms, 1st ed., MIT Press and McGraw-Hill, 1990 | MR | Zbl

[29] Chentsov A. G., Extremal problems of routing and assignment of tasks: questions of theory, Regular and Chaotic Dynamics, Institute of Computer Science, M.–Izhevsk, 2008, 240 pp.

[30] Chentsov A. G., “Problem of successive megalopolis traversal with the precedence conditions”, Automation and Remote Control, 75:4 (2014), 728–744 | DOI | MR | Zbl

[31] Chentsov A. G., Chentsov A. A., “Route problem with constraints depending on a list of tasks”, Doklady Mathematics, 92:3 (2015), 685–688 | DOI | DOI | MR | Zbl

[32] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Extremal routing problem with internal losses”, Proceedings of the Steklov Institute of Mathematics, 264, suppl. 1 (2009), 87–106 | DOI | MR

[33] Chentsov A. G., Chentsov A. A., “A model variant of the problem about radiation sources utilization (iterations based on optimization insertions)”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 50 (2017), 83–109 (in Russian) | DOI