Geodesic
Truncated dynamic programming method in a closed traveling salesman problem with symmetric value function
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 1, pp. 121-129 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

A method for the exact solution of a closed traveling salesman problem with symmetric value function based on the dynamic programming method is presented. The method produces an optimal solution in a smaller number of operations as compared to the classical dynamic programming method. A short experiment, which compares the efficiencies of the classical scheme and of the new scheme in traveling salesman problems of different dimensions, is given in the end of the paper.
Keywords: dynamic programming method, traveling salesman problem. 
@article{TIMM_2013_19_1_a11,
     author = {E. E. Ivanko},
     title = {Truncated dynamic programming method in a~closed traveling salesman problem with symmetric value function},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {121--129},
     year = {2013},
     volume = {19},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a11/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Truncated dynamic programming method in a closed traveling salesman problem with symmetric value function
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2013
SP  - 121
EP  - 129
VL  - 19
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a11/
LA  - ru
ID  - TIMM_2013_19_1_a11
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Truncated dynamic programming method in a closed traveling salesman problem with symmetric value function
%J Trudy Instituta matematiki i mehaniki
%D 2013
%P 121-129
%V 19
%N 1
%U http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a11/
%G ru
%F TIMM_2013_19_1_a11
E. E. Ivanko. Truncated dynamic programming method in a closed traveling salesman problem with symmetric value function. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 19 (2013) no. 1, pp. 121-129. http://geodesic.mathdoc.fr/item/TIMM_2013_19_1_a11/

[1] Menger K., “Das botenproblem”, Ergebnisse eines Mathematischen Kolloquiums, 2, ed. K. Menger, Leipzig, 1932, 11–12

[2] Ivanko E. E., “Metod masshtabirovaniya v priblizhennom reshenii zadachi kommivoyazhera”, Avtomatika i telemekhanika, 2011, no. 12, 115–129 | MR

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

[4] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Voprosy teorii”, Avtomatika i telemekhanika, 1989, no. 9, 3–34 | MR

[5] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Tochnye algoritmy”, Avtomatika i telemekhanika, 1989, no. 10, 3–29 | MR | Zbl

[6] Melamed I. I., Sergeev S. I., Sigal I. Kh., “Zadacha kommivoyazhera. Priblizhennye algoritmy”, Avtomatika i telemekhanika, 1989, no. 11, 3–26 | MR | Zbl

[7] Chentsov A. G., Ekstremalnye zadachi marshrutizatsii i raspredeleniya zadanii: voprosy teorii, NITs “Regulyarnaya i khaoticheskaya dinamika”, M.–Izhevsk, 2008, 238 pp.

[8] Gimadi E. Kh., “Novaya versiya asimptoticheski tochnogo algoritma resheniya evklidovoi zadachi kommivoyazhera”, Metody optimizatsii i ikh prilozheniya, Tr. XII Baikalskoi mezhdunar. konf., v. 1, ISEM SO RAN, Irkutsk, 2001, 117–124

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

[10] Geri M., Dzhonson D., Vychislitelnye mashiny i trudnoreshaemye zadachi, Mir, M., 1982, 416 pp. | MR

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

[12] Grigorev A. M., Ivanko E. E., Chentsov A. G., “Dinamicheskoe programmirovanie v obobschennoi zadache kurera s vnutrennimi rabotami: elementy parallelnoi struktury”, Modelirovanie i analiz informatsionnykh sistem, 18:3 (2011), 101–124

[13] Sesekin A. N., Chentsov A. A., Chentsov A. G., Ekstremalnye zadachi marshrutizatsii s ogranicheniyami, Izd-vo UGTU-UPI, Ekaterinburg, 2009, 65 pp.