Geodesic
On one routing task with the optimization of the start--finish point
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 52 (2018), pp. 103-115.

Voir la notice de l'article provenant de la source Math-Net.Ru

The optimizing procedure for solving the problem of sequential visiting of megacities under precedence conditions and cost functions depending on the tasks list is considered. The formulation of the problem closed in the sense of coincidence of the starting point (process base) and terminal state is investigated (this is an analog of the closed travelling salesman problem). This condition is natural for applied problems concerning series of procedures with elements of routing. In particular, in problems involved in sheet cutting on CNC, in working with a series of parts corresponding to one cutting plan, the cutting tool must be returned to the starting point for repeated operations. In this setting, optimization of the starting point is interesting not only for theoretical, but also practical reasons. In a mathematical setting, it is not necessary to require the above-mentioned return to the starting point: this condition can be reflected by introducing the corresponding terminal function whose argument is the last point of visiting in the contours of the parts. Such an approach allows one to cover some more general cases where the cost of the terminal state, which includes the starting point in the form of a parameter, is given. As a result, the starting point and the finishing point are related by a functional dependence in the form of the value defining the quality of the final state of the process. This representation is used in the article.
Mots-clés : route
Keywords: track, precedence conditions. 
@article{IIMI_2018_52_a7,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {On one routing task with the optimization of the start--finish point},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {103--115},
     publisher = {mathdoc},
     volume = {52},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2018_52_a7/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - On one routing task with the optimization of the start--finish point
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2018
SP  - 103
EP  - 115
VL  - 52
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2018_52_a7/
LA  - ru
ID  - IIMI_2018_52_a7
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T On one routing task with the optimization of the start--finish point
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2018
%P 103-115
%V 52
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2018_52_a7/
%G ru
%F IIMI_2018_52_a7
A. G. Chentsov; P. A. Chentsov. On one routing task with the optimization of the start--finish point. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 52 (2018), pp. 103-115. http://geodesic.mathdoc.fr/item/IIMI_2018_52_a7/

[1] 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.

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

[3] Gutin G., Punnen A. P., The traveling salesman problem and its variations, Springer US, Boston, 2007 | DOI | MR | Zbl

[4] Cook W. J., In pursuit of the traveling salesman. Mathematics at the limits of computation, Princeton University Press, Princeton, New Jersey, 2012, 248 pp. | DOI | MR | 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 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] Little J. D.C., Murty K. G., Sweeney D. W., Karel C., “An algorithm for the traveling salesman problem”, Operations Research, 11 issue 6 (1963), 972–989 | DOI | Zbl

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

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

[11] Gimadi E. Kh., Khachai M. Yu., Extremal problems on sets of permutations, UMC UPI, Yekaterinburg, 2016, 220 pp.

[12] 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.

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

[14] Chentsov A. G., Chentsov P. A., “Routing under constraints: Problem of visit to megalopolises”, Automation and Remote Control, 77:11 (2016), 1957–1974 | DOI | MR | Zbl

[15] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967, xi+417 pp. | MR | MR

[16] Dieudonné J., Foundations of modern analysis, Academic Press, New York, 1960, 361 pp. | MR | Zbl

[17] Cormen T., Leizerson C., Rivest R., Introduction to algorithms, MIT Press, Cambridge, 1990 | MR | Zbl

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