A composite-neighborhood tabu search approach to the traveling tournament problem

被引:47
作者
Di Gaspero, Luca [1 ]
Schaerf, Andrea [1 ]
机构
[1] Univ Udine, Dipartimento Ingn Elettr Gest & Meccan, I-33100 Udine, Italy
关键词
tabu search; local search; composite neighborhood; traveling tournament; tournament scheduling; traveling salesman;
D O I
10.1007/s10732-006-9007-x
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
The Traveling Tournament Problem (TTP) is a combinatorial problem that combines features from the traveling salesman problem and the tournament scheduling problem. We propose a family of tabu search solvers for the solution of TTP that make use of complex combination of many neighborhood structures. The different neighborhoods have been thoroughly analyzed and experimentally compared. We evaluate the solvers on three sets of publicly available benchmarks and we show a comparison of their outcomes with previous results presented in the literature. The results show that our algorithm is competitive with those in the literature.
引用
收藏
页码:189 / 207
页数:19
相关论文
共 27 条
[1]  
Ahuja R. K., 2000, International Transactions in Operational Research, V7, P301, DOI 10.1111/j.1475-3995.2000.tb00201.x
[2]   A simulated annealing approach to the traveling tournament problem [J].
Anagnostopoulos, A ;
Michel, L ;
Van Hentenryck, P ;
Vergados, Y .
JOURNAL OF SCHEDULING, 2006, 9 (02) :177-193
[3]  
[Anonymous], 1972, LECT NOTES MATH
[4]  
ARAUJO A, 2005, P 6 MET INT C MIC200, P70
[5]  
BIRATTARI M, 2004, THESIS U LIBRE BRUXE
[6]  
BIRATTARI M, 2005, RACE PACKAGE
[7]  
Conover WJ., 1999, Practical nonparametric statistics
[8]  
de Werra D., 1981, Studies on graphs and discrete programming, P381
[9]   EASYLOCAL++: an object-oriented framework for the flexible design of local-search algorithms [J].
Di Gaspero, L ;
Schaerf, A .
SOFTWARE-PRACTICE & EXPERIENCE, 2003, 33 (08) :733-765
[10]  
Dinitz J.H., 1994, J COMB DES, V2, P273