Tabu search with simple ejection chains for coloring graphs

被引：5
作者：
González-Velarde, JL
Laguna, M
机构：
[1] Ctr Sistemas Manufactura, Monterrey 64920, NL, Mexico
[2] Univ Colorado, Leeds Sch Business, Boulder, CO 80309 USA
来源：
ANNALS OF OPERATIONS RESEARCH | 2002年 / 117卷 / 1-4期
关键词：
graph coloring; metaheuristics; tabu search; ejection chains;
D O I：
10.1023/A:1021573507189
中图分类号：
C93 [管理学]; O22 [运筹学];
学科分类号：
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要：
We present a Tabu Search (TS) method that employs a simple version of ejection chains for coloring graphs. The procedure is tested on a set of benchmark problems. Empirical results indicate that the proposed TS implementation outperforms other metaheuristic methods, including Simulated Annealing, a previous version of Tabu Search and a recent implementation of a Greedy Randomized Adaptive Search Procedure (GRASP).
引用
收藏
页码：165 / 174
页数：10
相关论文
共 18 条
[1]  
[Anonymous], 1997, Tabu Search
[2]   SOME EXPERIMENTS WITH SIMULATED ANNEALING FOR COLORING GRAPHS [J].
CHAMS, M ;
HERTZ, A ;
DEWERRA, D .
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1987, 32 (02) :260-266
[3]  
Dorndorf U., 1994, ORSA Journal on Computing, V6, P141, DOI 10.1287/ijoc.6.2.141
[4]  
DORNE R, 1999, META HEURISTICS ADV, P33
[5]   GREEDY RANDOMIZED ADAPTIVE SEARCH PROCEDURES [J].
FEO, TA ;
RESENDE, MGC .
JOURNAL OF GLOBAL OPTIMIZATION, 1995, 6 (02) :109-133
[6]   A PROBABILISTIC HEURISTIC FOR A COMPUTATIONALLY DIFFICULT SET COVERING PROBLEM [J].
FEO, TA ;
RESENDE, MGC .
OPERATIONS RESEARCH LETTERS, 1989, 8 (02) :67-71
[7]   Genetic and hybrid algorithms for graph coloring [J].
Fleurent, C ;
Ferland, JA .
ANNALS OF OPERATIONS RESEARCH, 1996, 63 :437-461
[8]  
Garey M. R., 1979, Computers and intractability. A guide to the theory of NP-completeness
[9]   USING TABU SEARCH TECHNIQUES FOR GRAPH-COLORING [J].
HERTZ, A ;
DEWERRA, D .
COMPUTING, 1987, 39 (04) :345-351
[10]  
Holland J., 1992, ADAPTATION NATURAL A
12