Geodesic
Sufficient stability conditions in the traveling salesman problem
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 17 (2011) no. 3, pp. 155-168
Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

Uniform sufficient conditions for the stability of optimal routes in the traveling salesman problem under various distortions of initial data are formulated and proved. The distortions include addition and removal of vertices and changes in the travel cost matrix. Polynomial-time algorithms are presented, which use the obtained sufficient conditions to construct stability domains on finite sets. Results of experiments in metric traveling salesman problems on the integer lattice are demonstrated.
Keywords: traveling salesman problem, routing problem, stability, combinatorial optimization. 
@article{TIMM_2011_17_3_a15,
     author = {E. E. Ivanko},
     title = {Sufficient stability conditions in the traveling salesman problem},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {155--168},
     year = {2011},
     volume = {17},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2011_17_3_a15/}
}
TY  - JOUR
AU  - E. E. Ivanko
TI  - Sufficient stability conditions in the traveling salesman problem
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2011
SP  - 155
EP  - 168
VL  - 17
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2011_17_3_a15/
LA  - ru
ID  - TIMM_2011_17_3_a15
ER  - 
%0 Journal Article
%A E. E. Ivanko
%T Sufficient stability conditions in the traveling salesman problem
%J Trudy Instituta matematiki i mehaniki
%D 2011
%P 155-168
%V 17
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2011_17_3_a15/
%G ru
%F TIMM_2011_17_3_a15
E. E. Ivanko. Sufficient stability conditions in the traveling salesman problem. Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 17 (2011) no. 3, pp. 155-168. http://geodesic.mathdoc.fr/item/TIMM_2011_17_3_a15/

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

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

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

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

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

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

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

[8] Ivanko E. E., “Dostatochnye usloviya ustoichivosti optimalnogo marshruta v zadache kommivoyazhera pri dobavlenii novoi vershiny i pri udalenii suschestvuyuschei”, Vestn. Udm. un-ta. Matematika. Mekhanika. Kompyuternye nauki, 2010, no. 1, 48–57

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