Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem

被引:43
作者
Karapetyan, D. [1 ]
Gutin, G. [1 ]
机构
[1] Univ London, Egham TW20 0EX, Surrey, England
关键词
Heuristics; Local search; Neighborhood; Generalized traveling salesman problem; Combinatorial optimization; TRANSFORMATION;
D O I
10.1016/j.ejor.2012.01.011
中图分类号
C93 [管理学];
学科分类号
12 ; 1201 ; 1202 ; 120202 ;
摘要
The generalized traveling salesman problem (GTSP) is a well-known combinatorial optimization problem with a host of applications. It is an extension of the Traveling Salesman Problem (TSP) where the set of cities is partitioned into so-called clusters, and the salesman has to visit every cluster exactly once. While the GTSP is a very important combinatorial optimization problem and is well studied in many aspects, the local search algorithms used in the literature are mostly basic adaptations of simple TSP heuristics. Hence, a thorough and deep research of the neighborhoods and local search algorithms specific to the GTSP is required. We formalize the procedure of adaptation of a TSP neighborhood for the GTSP and classify all other existing and some new GTSP neighborhoods. For every neighborhood, we provide efficient exploration algorithms that are often significantly faster than the ones known from the literature. Finally, we compare different local search implementations empirically. (C) 2012 Elsevier B.V. All rights reserved.
引用
收藏
页码:234 / 251
页数:18
相关论文
共 35 条
[1]  
[Anonymous], 2002, COMB OPT (SER)
[2]  
[Anonymous], 1998, COMBINATORIAL OPTIMI
[3]  
[Anonymous], MEMETIC COMPUT
[4]   Transformations of generalized ATSP into ATSP [J].
Ben-Arieh, D ;
Gutin, G ;
Penn, M ;
Yeo, A ;
Zverovitch, A .
OPERATIONS RESEARCH LETTERS, 2003, 31 (05) :357-365
[5]   A Memetic Algorithm with a large neighborhood crossover operator for the Generalized Traveling Salesman Problem [J].
Bontoux, Boris ;
Artigues, Christian ;
Feillet, Dominique .
COMPUTERS & OPERATIONS RESEARCH, 2010, 37 (11) :1844-1852
[6]  
Downey R. G., 1999, MG COMP SCI
[7]   A branch-and-cut algorithm for the symmetric generalized traveling salesman problem [J].
Fischetti, M ;
Gonzalez, JJS ;
Toth, P .
OPERATIONS RESEARCH, 1997, 45 (03) :378-394
[8]   THE SYMMETRICAL GENERALIZED TRAVELING SALESMAN POLYTOPE [J].
FISCHETTI, M ;
GONZALEZ, JJS ;
TOTH, P .
NETWORKS, 1995, 26 (02) :113-123
[9]  
FISCHETTI M., 2002, COMB OPT (SER), V12, P609
[10]   A memetic algorithm for the generalized traveling salesman problem [J].
Gutin, Gregory ;
Karapetyan, Daniel .
NATURAL COMPUTING, 2010, 9 (01) :47-60