An Ant Based Hyper-heuristic for the Travelling Tournament Problem
An Ant Based Hyper-heuristic for the Travelling Tournament Problem
复制标题
DOI：
10.1109/scis.2007.367665
复制
发表时间：
2007-04
期刊：
影响因子：
--
通讯作者：
Pai-Chun Chen;G. Kendall;G. V. Berghe
中科院分区：
文献类型：
--
作者：
Pai-Chun Chen;G. Kendall;G. V. Berghe
巡回赛问题是一个具有挑战性的体育赛程安排问题，人们普遍认为它是NP难问题。其目标是制定一个可行的双循环赛赛程安排，且旅行距离最短。本文研究了一种基于蚂蚁的超启发式算法在该问题上的应用。蚂蚁算法是一种著名的元启发式算法，已成功应用于各种问题。而超启发式算法是一种新兴技术，它比元启发式算法具有更高的抽象层次。本文提出了一个将蚂蚁算法用作超启发式算法的框架。我们表明，与文献中的结果相比，这种方法能为巡回赛问题生成高质量的解决方案。
The travelling tournament problem is a challenging sports timetabling problem which is widely believed to be NP-hard. The objective is to establish a feasible double round robin tournament schedule, with minimum travel distances. This paper investigates the application of an ant based hyper-heuristic algorithm for this problem. Ant algorithms, a well known meta-heuristic, have been successfully applied to various problems. Whilst hyper-heuristics are an emerging technology, which operate at a higher level of abstraction than meta-heuristics. This paper presents a framework which employs ant algorithms as a hyper-heuristic. We show that this approach produces good quality solutions for the traveling tournament problem when compared with results from the literature