Geodesic
Optimization of the start point in the GTSP with the precedence conditions
Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 2, pp. 83-95 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The paper is devoted to the routing problem with constraints and cost functions that can depend on the list of tasks. It is assumed that the initial condition for the process with discrete time can be selected within a metric space that satisfies the condition of complete boundedness. It is supposed that the problem includes a visiting of a finite system of megalopolises (non-empty finite sets) with the fulfillment of some works. The cost of these works each time depend on the point of arrival and the point of departure. The costs of movement and work are aggregated additively. For the problem solution widely understood dynamic programming method providing $\varepsilon$-optimal solution for any $\varepsilon>0$ is used.
Keywords: route task; restrictions; start point. 
@article{VYURU_2018_11_2_a6,
     author = {A. G. Chentsov and P. A. Chentsov},
     title = {Optimization of the start point in the {GTSP} with the precedence conditions},
     journal = {Vestnik \^U\v{z}no-Uralʹskogo gosudarstvennogo universiteta. Seri\^a, Matemati\v{c}eskoe modelirovanie i programmirovanie},
     pages = {83--95},
     year = {2018},
     volume = {11},
     number = {2},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a6/}
}
TY  - JOUR
AU  - A. G. Chentsov
AU  - P. A. Chentsov
TI  - Optimization of the start point in the GTSP with the precedence conditions
JO  - Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
PY  - 2018
SP  - 83
EP  - 95
VL  - 11
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a6/
LA  - ru
ID  - VYURU_2018_11_2_a6
ER  - 
%0 Journal Article
%A A. G. Chentsov
%A P. A. Chentsov
%T Optimization of the start point in the GTSP with the precedence conditions
%J Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie
%D 2018
%P 83-95
%V 11
%N 2
%U http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a6/
%G ru
%F VYURU_2018_11_2_a6
A. G. Chentsov; P. A. Chentsov. Optimization of the start point in the GTSP with the precedence conditions. Vestnik Ûžno-Uralʹskogo gosudarstvennogo universiteta. Seriâ, Matematičeskoe modelirovanie i programmirovanie, Tome 11 (2018) no. 2, pp. 83-95. http://geodesic.mathdoc.fr/item/VYURU_2018_11_2_a6/

[1] G. Gutin, A.P. Punnen, The Traveling Salesman Problem and Its Variations, Springer, N.Y., 2002 | MR

[2] W.J. Cook, In Pursuit of the Traveling Salesman. Mathematics at the Limits of Computation, Princeton University Press, New Jersey, 2012 | MR | Zbl

[3] Melamed I.I., Sergeev S.I., Sigal I., “The Traveling Salesman Problem. Issues in the Theory”, Automation and Remote Control, 50:9 (1989), 1147–1173 | MR | Zbl

[4] Melamed I. I., Sergeev S. I., Sigal I., “The Traveling Salesman Problem. Exact Methods”, Automation and Remote Control, 50:10 (1989), 1303–1324 | MR | Zbl

[5] Melamed I. I., Sergeev S. I., Sigal I., “The Traveling Salesman Problem. Approximate Algorithms”, Automation and Remote Control, 50:11 (1989), 1459–1479 | MR | Zbl

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

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

[8] Chentsov A. G., “One Parallel Procedure for the Construction of the Bellman Function in the Generalized Problem of the Courier with the Inner Workings”, Automation and Remote Control, 2012, no. 3, 134–149

[9] Korobkin V. V., Sesekin A. N., Tashlykov O. L., Chentsov A. G., Routing Methods and Their Applications to the Enhancement of Safety and Efficiency of Nuclear Plant Operation, Novye tekhnologii, M., 2012 (in Russian)

[10] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, Journal of the Association for Computing Machinery, 9 (1962), 61–63 | DOI | MR | Zbl

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

[12] Little J., Murty K., Sweeney D., Karel C., “An Algorithm for the Traveling Salesman Problem”, Operations Research, 11:6 (1963), 972–989 | DOI | Zbl

[13] Kuratowski K., Mostowski A., Set Theory, North-Holland Publishing Company, Amsterdam, 1967 | MR

[14] Dieudonne J., Foundations of Modern Analysis, Academic Press, New York, 1960 | MR | Zbl

[15] Cormen T., Leiserson C., Rivest R., Introduction to Algorithms, MIT Press and McGraw-Hill, 1990 | MR | Zbl

[16] Engelking R., General Topology, Polish Scientific Publishers, 1977

[17] Chentsov A. G., Extreme Routing and Task Distribution Problems: Theory Questions, NITs “Regulyarnaya i Khaoticheskaya Dinamika”, Izhevsk, 2008 (in Russian)

[18] Chentsov A. G., Chentsov A. A., “On the Problem of Obtaining the Value of Routing Problem with Constraints”, Journal of Automation and Information Sciences, 6 (2016), 41–54

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

[20] Chentsov A. G., “To Question of Routing of Works Complexes”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2013, no. 1, 59–82 (in Russian)