The Bellmann insertions in the route problem with constraints and complicated cost functions

A. G. Chentsov

Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 4 (2014), pp. 122-141

Résumé

The problem of sequential circuit of megalopolises with precedence conditions and cost functions that permit a dependence on tasks list is considered. Such problems can arise, in particular, in atomic energetic while investigating the questions connected with lowering of workers irradiation under permutations in radiative fields for realization of services connected with division of radiating elements. Another application of the developed methods is connected with important engineering problem of routing the instrument movements under the leaf cutting on numerically controlled machines. This problem has sufficiently large dimensionality and many precedence conditions: if a detail has not only exterior but at least one interior contours (the simplest example is a washer) then the interior contours must be cut before the cutting of exterior contour (finite sets located near corresponding contours are used as megalopolises). In this case the possible dependence of cost functions on tasks list can reflect various technological conditions. We note that perceptible dimensionality characterized by all contours in total leads to necessity of heuristics employment. Therefore, questions concerning at least local improvement of solutions appear sufficiently important for the investigation. The basic attention in the article is devoted to the construction of optimizing insertions in complicated conditions: it is required to reduce the fragment of precedence conditions and to transform the corresponding cost functions; in the last case, it is important to preserve the dependence on tasks list. Both above-mentioned moments are taken into account under the procedure construction having the sense of algorithm on functional level.

Détail

Mots-clés : route
Keywords: trace, precedence conditions.

Bibliographie

[1] Petunin A. A., “About some strategies of the programming of tool route by developing of control programs for thermal cutting machines”, Vestnik UGATU, 13:2(35) (2009), 280–286 (in Russian)

[2] Tashlykov O. L., Repair of equipment of nuclear power plants, USTU–UPI, Yekaterinburg, 2003, 320 pp.

[3] Garey M. R., Johnson D. S., Computers and Intractability, Macmillan Higher Education, New York, 1979, 340 pp. | MR | MR

[4] Chentsov A. G., “To question of routing of works complexes”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2013, no. 1, 59–82 (in Russian) | Zbl

[5] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Elements of dynamic programming in extremal route problems”, Problemy upravleniya, 2013, no. 5, 12–21 (in Russian)

[6] Chentsov A. A., Chentsov A. G., “Dynamic programming in the routing problem with complex dependence of costs on the list of jobs”, Journal of Computer and Systems Sciences International, 53:2 (2014), 172–185 | DOI | DOI | MR

[7] Chentsov A. G., Extremal problems of routing and assignment of tasks: questions of theory, Institute of Computer Science, Moscow–Izhevsk, 2008, 238 pp.

[8] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Problems of the theory”, Avtomatika i Telemekhanika, 1989, no. 9, 3–33 (in Russian) | MR | Zbl

[9] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Exact algorithms”, Avtomatika i Telemekhanika, 1989, no. 10, 3–29 (in Russian) | MR | Zbl

[10] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. Approximation algorithms”, Avtomatika i Telemekhanika, 1989, no. 11, 3–26 (in Russian) | MR | Zbl

[11] Bellman R., “Application of dynamic programming method for the traveling salesman problem”, Kibernet. Sb., 9, Mir, Moscow, 1964, 219–228 (in Russian)

[12] Kheld M., Karp R. M., “Application of dynamic programming method for the sorting problems”, Kibernet. Sb., 9, Mir, Moscow, 1964, 202–218 (in Russian)

[13] Sigal I. Kh., “A decomposition approach to solving a travelling salesman problem of large dimensionality and some applications”, Sov. J. Comput. Syst. Sci., 29:6 (1991), 48–58 | MR | Zbl

[14] Sergeev S. I., “Algorithms for the minimax problem of the traveling salesman. I: An approach based on dynamic programming”, Autom. Remote Control, 56:7 (1995), 1027–1032 | MR | Zbl

[15] Barvinok A., Gimadi E. Kh., Serdyukov A. I., “The Maximum TSP”, The Traveling Salesman problem and its variations, eds. Gutin G., Punnen A. P., Kluwer Academic Publishers, Dordrecht–Boston, 2002, 585–607 | MR | Zbl

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

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

[18] Kuratowski K., Mostowski A., Theory of sets, Mir, Moscow, 1970, 416 pp. | MR

[19] Dieudonne J., Foundations of modern analysis, Mir, Moscow, 1964, 430 pp.

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

[21] Petunin A. A., Chentsov A. G., Chentsov P. A., “Local dynamic programming incuts in routing problems with restrictions”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, no. 2, 56–75 | Zbl