کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
481988 | 1446168 | 2008 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: An evolutionary approach for bandwidth multicoloring problems An evolutionary approach for bandwidth multicoloring problems](/preview/png/481988.png)
In this paper we consider some generalizations of the vertex coloring problem, where distance constraints are imposed between adjacent vertices (bandwidth coloring problem) and each vertex has to be colored with more than one color (bandwidth multicoloring problem). We propose an evolutionary metaheuristic approach for the first problem, combining an effective tabu search algorithm with population management procedures. The approach can be applied to the second problem as well, after a simple transformation. Computational results on instances from the literature show that the overall algorithm is able to produce high quality solutions in a reasonable amount of time, outperforming the most effective algorithms proposed for the bandwidth coloring problem, and improving the best known solution of many instances of the bandwidth multicoloring problem.
Journal: European Journal of Operational Research - Volume 189, Issue 3, 16 September 2008, Pages 638–651