Geodesic
On routing problem with starting point optimization
Ural mathematical journal, Tome 6 (2020) no. 2, pp. 44-62 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

One problem focused on engineering applications is considered. It is assumed that sequential visits to megacities have been implemented. After all visits have been made, it is required to return to the starting point (a more complex dependence on the starting point is also considered). But the last requirement is not strict: some weakening of the return condition is acceptable. Under these assumptions, it is required to optimize the choice of starting point, route, and specific trajectory. The well-known dynamic programming (DP) is used for the solution. But when using DP, significant difficulties arise associated with the dependence of the terminal component of the criterion on the starting point. Starting point enumeration is required. We consider the possibility of reducing the enumeration associated with applied variants of universal (relative to the starting point) dynamic programming. Of course, this approach requires some transformation of the problem.
Keywords: dynamic programming, precedence conditions
Mots-clés : route. 
@article{UMJ_2020_6_2_a4,
     author = {Alexander G. Chentsov and Pavel A. Chentsov},
     title = {On routing problem with starting point optimization},
     journal = {Ural mathematical journal},
     pages = {44--62},
     year = {2020},
     volume = {6},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UMJ_2020_6_2_a4/}
}
TY  - JOUR
AU  - Alexander G. Chentsov
AU  - Pavel A. Chentsov
TI  - On routing problem with starting point optimization
JO  - Ural mathematical journal
PY  - 2020
SP  - 44
EP  - 62
VL  - 6
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/UMJ_2020_6_2_a4/
LA  - en
ID  - UMJ_2020_6_2_a4
ER  - 
%0 Journal Article
%A Alexander G. Chentsov
%A Pavel A. Chentsov
%T On routing problem with starting point optimization
%J Ural mathematical journal
%D 2020
%P 44-62
%V 6
%N 2
%U http://geodesic.mathdoc.fr/item/UMJ_2020_6_2_a4/
%G en
%F UMJ_2020_6_2_a4
Alexander G. Chentsov; Pavel A. Chentsov. On routing problem with starting point optimization. Ural mathematical journal, Tome 6 (2020) no. 2, pp. 44-62. http://geodesic.mathdoc.fr/item/UMJ_2020_6_2_a4/

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

[2] Chentsov A. A., Chentsov A. G., “Routization problem complicated by the dependence of costs functions and “current” restrictions from the tasks list”, Model. Anal. Inf. Sist., 23:2 (2016), 211–227 (in Russian) | DOI | MR

[3] Chentsov A. G., Ekstremal'nye zadachi marshrutizacii i raspredeleniya zadanij: voprosy teorii [Extreme routing and distribution tasks: theory questions], R Dynamics. Izhevsk Institute of Computer Research, M.-Izhevsk, 2008, 240 pp. (in Russian)

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

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

[6] Chentsov A .G., Chentsov P. A., “To the question of optimization of the starting point in the routing problem with restrictions”, Izv. IMI UdGU 2020, 55, 135–154 (in Russian) | DOI | MR | Zbl

[7] Cook W. J., In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation, Princeton Univer. Press, N. J., 2012, 272 pp. https://www.jstor.org/stable/j.ctt7t8kc | MR | Zbl

[8] Dieudonné J., Foundations of Modern Analysis, Academic Press, New York, 1960, 361 pp. | MR | Zbl

[9] Held M., Karp R.M., “A dynamic programming approach to sequencing problems”, J. Soc. Indust. Appl. Math., 10:1 (1962), 196–210 | DOI | MR | Zbl

[10] Gimadi E. Kh., Khachay M., Ekstremal'nye zadachi na mnozhestvah perestanovok [Extremal Problems on Sets of Permutations], Izdatel'stvo UMC UPI, Ekaterinburg, 2016, 220 pp. (in Russian)

[11] Gutin G., Punnen A. P., The Traveling Salesman Problem and Its Variations, Springer, Boston, 2007, 830 pp. | DOI | MR | Zbl

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

[13] Kosheleva M. S., Chentsov A. A., Chentsov A. G., “On a routing problem with constraints that include dependence on a task list”, Trudy Inst. Mat. i Mekh. UrO RAN, 21:4 (2015), 178–195 (in Russian) | MR

[14] Kuratowski K., Mostowski A., Set Theory, North-Holland, 1968, 417 pp. | MR | Zbl

[15] Lawler E. L., Efficient Implementation of Dynamic Programming Algorithms for Sequencing Problems, BW 106/79, CWI. Technical Reports. Stichting Mathematish Centrum. Mathematische Besliskunde, 1979, 16 pp.

[16] Melamed I. I., Sergeev S. I., Sigal I. Kh., “The traveling salesman problem. I: Issues in theory”, Autom. Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

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

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