求解旅行锦标赛问题的改进混合局部搜索算法  

Mirrored Travelling Tournament Problem:An Improved Hybrid Local Search Approach

作　　者：韦炜[1] 藤村茂[2] 席裕庚[1] 

机构地区：[1]上海交通大学自动化系,上海200240 [2]日本早稻田大学情报生产系统研究科,福冈县北九州市8080135

出　　处：《计算机仿真》2012年第10期252-255,340,共5页Computer Simulation

基　　金：国家自然科学基金(60934007;61074060)

摘　　要：研究旅行锦标赛问题(Traveling Tournament Problem),属于体育类调试优化问题,涉及到球员、赛程安排和传播权等经济活动。针对体育联赛调度问题中碰到的赛程可行性与联盟队伍旅行总距离最优性的权衡问题,为了改善已有算法的效率及仿真结果,提出了一种全新的混合局部搜索算法:首先,通过改进的全面有效的构造算法以生成高质量的初始解,提出一种利用禁忌搜索和VND启发式算法,并具备迭代次数调整的混合局部搜索算法。改进算法能够通过各种有效的邻域移动遍历庞大的邻域结构。通过对标准问题集的仿真测试与结果对比,证明改进算法能够在合理的时间内实现优化调试,并得出非常具有竞争力的结果。The Traveling Tournament Problem is a sports scheduling problem that Abstracts the important issues in creating time tables： feasibility and team travel,where the objective is to minimize the total distance traveled by the teams.In this paper,we tackled the mirrored version of this problem.First,an effective and comprehensive constructive algorithm was applied which quickly obtains initial solution at a very high quality.Then a hybrid local search approach was proposed based on the combination of Tabu Search and Variable Neighborhood Descent meta-heuristic which explores large neighborhood with various and effective moves.Solutions of good competitiveness were obtained for benchmark instances.

关 键 词：体育排程 旅行锦标赛问题 混合局部搜索 禁忌搜索 

分 类 号：TP202.7[自动化与计算机技术—检测技术与自动化装置]