Geodesic
The complexity of optimal recombination for the traveling salesman problem
Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 27-40.

Voir la notice de l'article provenant de la source Math-Net.Ru

The computational complexity of optimal recombination for the traveling salesman problem is considered in the symmetric and general cases. NP-hardness of these problems is proven and some approaches to their solution are indicated. Ill. 3, bibliogr. 15.
Keywords: traveling salesman problem, genetic algorithm, optimal recombination, computational complexity
Mots-clés : problem transformation. 
@article{DA_2011_18_1_a3,
     author = {A. V. Eremeev},
     title = {The complexity of optimal recombination for the traveling salesman problem},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {27--40},
     publisher = {mathdoc},
     volume = {18},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2011_18_1_a3/}
}
TY  - JOUR
AU  - A. V. Eremeev
TI  - The complexity of optimal recombination for the traveling salesman problem
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2011
SP  - 27
EP  - 40
VL  - 18
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2011_18_1_a3/
LA  - ru
ID  - DA_2011_18_1_a3
ER  - 
%0 Journal Article
%A A. V. Eremeev
%T The complexity of optimal recombination for the traveling salesman problem
%J Diskretnyj analiz i issledovanie operacij
%D 2011
%P 27-40
%V 18
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2011_18_1_a3/
%G ru
%F DA_2011_18_1_a3
A. V. Eremeev. The complexity of optimal recombination for the traveling salesman problem. Diskretnyj analiz i issledovanie operacij, Tome 18 (2011) no. 1, pp. 27-40. http://geodesic.mathdoc.fr/item/DA_2011_18_1_a3/

[1] Borisovskii P. A., Eremeev A. V., “Geneticheskii algoritm dlya zadachi o vershinnom pokrytii grafa”, Matematika i informatika: nauka i obrazovanie, 7, OmGPU, Omsk, 2008, 49–54

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

[3] Agarwal C. C., Orlin J. B., Tai R. P., Optimized crossover for the independent set problem, Working paper # 3787-95, Massachusetts Institute of Technology, Cambridge, MA, 1995, 17 pp.

[4] Balas E., Niehaus W., “Optimized crossover-based genetic algorithms for the maximum cardinality and maximum weight clique problems”, J. Heuristics, 4:2 (1998), 107–122 | DOI | MR | Zbl

[5] Borisovsky P., Dolgui A., Eremeev A., “Genetic algorithms for a supply management problem: MIP-recombination vs greedy decoder”, Europ. J. Oper. Res., 195:3 (2009), 770–779 | DOI | Zbl

[6] Cook W., Seymour P., “Tour merging via branch-decomposition”, INFORMS J. Computing, 15:2 (2003), 233–248 | DOI | MR

[7] Cotta C., Alba E., Troya J. M., “Utilizing dynastically optimal forma recombination in hybrid genetic algorithms”, Proc. 5th Int. Conf. on Parallel Problem Solving from Nature, Lect. Notes Comput. Sci., 1498, Springer-Verl., Berlin, 1998, 305–314

[8] Dolgui A., Eremeev A., Guschinskaya O., “MIP-based GRASP and genetic algorithm for balancing transfer lines”, Matheuristics Hybridizing metaheuristics and mathematical programming, Springer-Verl., Berlin, 2010, 189–208

[9] Eppstein D., “The traveling salesman problem for cubic graphs”, J. Graph Algorithms Appl., 11:1 (2007), 61–81 | MR | Zbl

[10] Eremeev A. V., “On complexity of optimal recombination for binary representations of solutions”, Evolutionary Computation, 16:1 (2008), 127–147 | DOI | MR

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

[12] Itai A., Papadimitriou C. H., Szwarcfiter J. L. “Hamilton paths in grid graphs”, SIAM J. Computing, 11:4 (1982), 676–686 | DOI | MR | Zbl

[13] Reeves C. R., “Genetic algorithms for the operations researcher”, INFORMS J. Comput., 9:3 (1997), 231–250 | DOI | Zbl

[14] Whitley D., Hains D., Howe A., “A hybrid genetic algorithm for the traveling salesman problem using generalized partition crossover”, Proc. 11th Int. Conf. on Parallel Problem Solving from Nature, Lect. Notes Comput. Sci., 6238, Springer-Verl., Berlin, 2010, 566–575

[15] Yagiura M., Ibaraki T., “The use of dynamic programming in genetic algorithms for permutation problems”, Europ. J. Oper. Res., 92 (1996), 387–401 | DOI | Zbl