Geodesic
Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2011), pp. 58-66 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

The criterion for the stability of optimal travelling salesman route in case of the insertion of a new vertex between two consequent vertexes is deduced. Number of experiments demonstrating stability areas are suggested for the Euclidean plane.
Keywords: travelling salesman problem, stability. 
@article{VUU_2011_1_a6,
     author = {E. E. Ivanko},
     title = {Criterion of the stability of optimal route in the travelling salesman problem in case of a~single vertex addition},
     journal = {Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹ\^uternye nauki},
     pages = {58--66},
     year = {2011},
     number = {1},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VUU_2011_1_a6/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
JO  - Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
PY  - 2011
SP  - 58
EP  - 66
IS  - 1
UR  - http://geodesic.mathdoc.fr/item/VUU_2011_1_a6/
LA  - ru
ID  - VUU_2011_1_a6
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition
%J Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki
%D 2011
%P 58-66
%N 1
%U http://geodesic.mathdoc.fr/item/VUU_2011_1_a6/
%G ru
%F VUU_2011_1_a6
E. E. Ivanko. Criterion of the stability of optimal route in the travelling salesman problem in case of a single vertex addition. Vestnik Udmurtskogo universiteta. Matematika, mehanika, kompʹûternye nauki, no. 1 (2011), pp. 58-66. http://geodesic.mathdoc.fr/item/VUU_2011_1_a6/

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

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

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

[4] Emelichev V. A., Kuzmin K. G., Leonovich A. M., “Ustoichivost v vektornykh kombinatornykh zadachakh optimizatsii”, AiT, 2004, no. 2, 79–92 | MR | Zbl

[5] Sotscov Yu. N., Leontev V. K., Gordeev E., “Some concepts of stability analysis in combinatorial optimization”, Discrete Applied Mathematics, 58 (1995), 169–190 | DOI | MR

[6] Lebedeva T. T., Semenova N. V., Sergienko T. I., “Ustoichivost vektornykh zadach tselochislennoi optimizatsii: vzaimosvyaz s ustoichivostyu mnozhestv optimalnykh i neoptimalnykh reshenii”, Kibernetika i sistemnyi analiz, 41:4 (2005), 89–100 | MR

[7] Devyaterikova M. V., Kolokolov A. A., “Ob ustoichivosti nekotorykh algoritmov tselochislennogo programmirovaniya”, Izv. vuzov. Matem., 2003, no. 12, 41–48 | MR | Zbl

[8] Poort E. S., Aspects of sensitivity analysis for the traveling salesman problem, PhD dissertation, University of Groningen, Groningen, 1997, 191 pp.

[9] Leontev V. K., “Ustoichivost zadachi kommivoyazhera”, Zhurn. vychisl. matematiki i mat. fiziki, 15:5 (1975), 1298–1309 | MR | Zbl

[10] Libura M., van der Poort E. S., Sierksma G., van der Veen J. A., “Stability aspects of the traveling salesman problem based on $k$-best solutions”, Discrete Applied Mathematics, 87 (1998), 159–185 | DOI | MR | Zbl

[11] Ivanko E. E., “Dostatochnye usloviya ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii novoi vershiny i pri udalenii suschestvuyuschei”, Vestnik Udmurtskogo universiteta. Matematika. Mekhanika. Kompyuternye nauki, 2010, no. 1, 48–57

[12] Bellman R., “Dynamic Programming Treatment of the Travelling Salesman Problem”, J. Assoc. Comput. Mach., 9 (1962), 61–63 | DOI | MR | Zbl

[13] Concorde TSP Solver, http://www.tsp.gatech.edu/concorde/index.html