Geodesic
The Bellmann insertions in route problems with constraints and complicated cost functions. II
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 4, pp. 565-578 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.
Mots-clés : insertion, route.
Keywords: dynamic programming 
@article{VUU_2016_26_4_a9,
     author = {A. G. Chentsov},
     title = {The {Bellmann} insertions in route problems with constraints and complicated cost {functions.~II}},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {565--578},
     year = {2016},
     volume = {26},
     number = {4},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2016_26_4_a9/}
}
TY  - JOUR
AU  - A. G. Chentsov
TI  - The Bellmann insertions in route problems with constraints and complicated cost functions. II
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2016
SP  - 565
EP  - 578
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/item/VUU_2016_26_4_a9/
LA  - ru
ID  - VUU_2016_26_4_a9
ER  - 
%0 Journal Article
%A A. G. Chentsov
%T The Bellmann insertions in route problems with constraints and complicated cost functions. II
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2016
%P 565-578
%V 26
%N 4
%U http://geodesic.mathdoc.fr/item/VUU_2016_26_4_a9/
%G ru
%F VUU_2016_26_4_a9
A. G. Chentsov. The Bellmann insertions in route problems with constraints and complicated cost functions. II. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, Tome 26 (2016) no. 4, pp. 565-578. http://geodesic.mathdoc.fr/item/VUU_2016_26_4_a9/

[1] Chentsov A. G., “The Bellmann insertions in the route problem with constraints and complicated cost functions”, Vestn. Udmurt. Univ. Mat. Mekh. Komp'yut. Nauki, 2014, no. 4, 122–141 (in Russian) | DOI

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

[3] 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

[4] 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, 238 pp.

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

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

[7] Chentsov A. G., Chentsov A. A., “On the question of finding the value of routing problem with constraints”, Journal of Automation and Information Sciences, 48:2 (2016), 11–27 | DOI

[8] 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

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

[10] 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

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

[12] Cook W. J., In pursuit of the traveling salesman: Mathematics at the limits of Computation, Princeton University Press, 2012, xvi+228 pp. | MR | Zbl

[13] Ivanko E. E., Stability and instability in discrete problems, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 2013, 208 pp.

[14] Little J., Murty K., Sweeney D., Karel C., “An algorithm for the traveling salesman problem”, Ekonom. Mat. Met., 1:1 (1965), 90–107 (in Russian)

[15] 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, 234 pp.

[16] 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)

[17] Frolovskii V. D., “Automation of designing control programs for thermal cutting of metal by CNC equipment”, Informatsionnye Tekhnologii v Proektirovanii i Proizvodstve, 2005, no. 4, 63–66 (in Russian)

[18] 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)

[19] Petunin A. A., Chentsov A. G., Chentsov P. A., “To the question about instrument routing in the automated machines of the sheet cutting”, St. Petersburg State Polytechnical University Journal. Computer Science. Telecommunication and Control Systems, 2013, no. 2(169), 103–111 (in Russian)

[20] 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 UGATU, 10:2(27) (2008), 123–130 (in Russian)

[21] 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

[22] 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

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

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

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

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

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

[28] Chentsov A. A., Chentsov A. G., Chentsov P. A., “Elements of dynamic programming in extremal routing problems”, Automation and Remote Control, 75:3 (2014), 537–550 | DOI | MR | Zbl

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