Geodesic
To the question of optimization of the starting point in the routing problem with restrictions
Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 55 (2020), pp. 135-154.

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

We consider the extreme routing problem with an additive criterion, the terminal component of which depends on the starting point. This dependence may be associated, in particular, with the requirement to return to the starting point region after completing the final system of tasks that need to be ordered. The work assumes that the tasks to be performed are related with visiting non-empty finite sets called megacities. In turn, the mentioned visits are associated with the performance of works, the costs of which are involved in the formation of the criterion. Finally, the costs of external movements (between megacities) supplement the formation of an additive criterion to be minimized. It is required to find a global extremum and a solution that includes a starting point, the order of visits to megacities and a specific trajectory of the process. The solution uses widely understood dynamic programming (DP). It is significant that procedures based on DP use starting point. Therefore, enumeration of mentioned points is required. The article proposes an approach to solving the problem of reducing this enumeration through the use of auxiliary DP that are universal with respect to the choice of a starting point. The optimal algorithm was built and implemented on a PC using the aforementioned approach.
Keywords: dynamic programming, precedence conditions.
Mots-clés : route 
@article{IIMI_2020_55_a8,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {To the question of optimization of the starting point in the routing problem with restrictions},
     journal = {Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta},
     pages = {135--154},
     publisher = {mathdoc},
     volume = {55},
     year = {2020},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIMI_2020_55_a8/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - To the question of optimization of the starting point in the routing problem with restrictions
JO  - Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
PY  - 2020
SP  - 135
EP  - 154
VL  - 55
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/IIMI_2020_55_a8/
LA  - ru
ID  - IIMI_2020_55_a8
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T To the question of optimization of the starting point in the routing problem with restrictions
%J Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta
%D 2020
%P 135-154
%V 55
%I mathdoc
%U http://geodesic.mathdoc.fr/item/IIMI_2020_55_a8/
%G ru
%F IIMI_2020_55_a8
A. G. Chentsov; P. A. Chentsov. To the question of optimization of the starting point in the routing problem with restrictions. Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 55 (2020), pp. 135-154. http://geodesic.mathdoc.fr/item/IIMI_2020_55_a8/

[1] Gutin G., Punnen A. (Eds.), The traveling salesman problem and its variations, Springer US, 2007, xviii+830 pp. | DOI | MR | Zbl

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

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

[4] Little G. 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

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

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

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

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

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

[10] Chentsov A. G., Chentsov P. A., “On one routing task with the optimization of the start–finish point”, Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, 52 (2018), 103–115 (in Russian) | DOI | MR

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

[12] Chentsov A. G., “To question of routing of works complexes”, Vestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki, 2013, no. 1, 59–82 (in Russian) | DOI | MR | Zbl

[13] Chentsov A. G., Chentsov P. A., “Optimization of the start point in the GTSP with the precedence conditions”, Vestnik Yuzhno-Ural'skogo Universiteta. Seriya Matematicheskoe Modelirovanie i Programmirovanie, 11:2 (2018), 83–95 (in Russian) | DOI | Zbl

[14] Kuratowski K., Mostowski A., Set theory, North-Holland, Amsterdam, 1967 | MR

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

[16] Cormen T. H., Leiserson C. E., Rivest R. L., Introduction to algorithms, MIT Press, Cambridge, MA, 1990 | MR | Zbl

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