A NOVEL HEURISTIC APPROACH TO THE MIRRORED TRAVELLING TOURNAMENT PROBLEM

Abstract

Abstract This project aims at applying a new hybrid heuristic approach to the mirrored Traveling Tournament Problem (TTP). TTP is a tournament scheduling problem which abstracts the tournament structure of Major League Baseball. In this type of league, every team plays with every other team, once at its home and once away (at opponent’s home). These type of tournaments are called Double Round Robin (DRR) tournaments. Aim of TTP is to make a schedule which incurs minimum travel distance for all the playing teams while conforming to some constraints like no team can play consecutively more than n matches home or away. While number of teams involved in standard benchmarks of TTP are no more than 32, still it is almost impossible to get an optimal schedule (with minimum travel cost) for even 10-team instance. TTP has been proved to be an NP-hard problem. Our aim is to apply hybridize Biogeography based optimization and Simulated Annealing heuristics to get good schedules of TTP. Simulated Annealing has shown its efficiency in tackling TTP benchmark instances with good results. However its very computation intensive technique and some instances take time even in number of days. Biogeography based optimization (BBO) is relatively new and fast heuristic approach which has not yet been applied to TTP. Although BBO itself is a global optimization technique, but due to its fundamental philosophy of sharing features among solutions, we cannot use it directly on TTP schedules because this can break the DRR structure of schedules and make them invalid. We use state of the art techniques to generate initial schedules fast. We modify these techniques so that their results can suitably be used by BBO. We use BBO as an intermediate step for fast convergence of solution to local optima. The best result produced by BBO is used as a starting point iv for simulated annealing heuristic. It has been suggested in literature that the goodness of solutions produced by simulated annealing depends on its starting point. We aim at giving a good solution to simulated annealing to start with, in very less time. The performance of our hybrid approach is evaluated on standard National League and Brazilian soccer league benchmarks of TTP. The results are compared to the current best results. Our approach produces competitive results while consuming much lesser time as compared to best techniques available.