New version page

Population-Based Simulated Annealing for Traveling Tournaments

Upgrade to remove ads

This preview shows page 1-2 out of 6 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 6 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Population-Based Simulated Annealing for Traveling TournamentsPascal Van Hentenryck and Yannis VergadosBrown University, Box 1910, Providence, RI 02912AbstractThis paper reconsiders the travelling tournament prob-lem, a complex sport-scheduling application which hasattracted significant interest recently. It proposes apopulation-based simulated annealing algorithm withboth intensification and diversification. The algorithmis organized as a series of simulated annealin g waves,each wave being followed by a macro-intensification.The diversification is obt ained through the concept ofelite runs that opportunistically survive waves. A par-allel implementation of the algorithm on a cluster ofworkstations exhibits remarkable results. It improvesthe best known solutions on all considered benchmarks,sometimes reduces the optimality gap by almost 50%,and produces novel best solutions on instances that hadbeen stable for several years.IntroductionSport scheduling has become a steady source of chal-lenging applications for combinatorial optimization.These problems typically feature complex combinato-rial structures (e.g., round-robin tournaments with sideconstraints), a s well as objective functions measuringthe overall quality of the schedule (e.g., travel distance).The travelling tourna ment problem (TTP) is an ab-straction of Major League Baseball (MLB) proposedby Eas ton, Nemhauser, and Trick 2001 to stimulate re-search in sport scheduling. The TTP consists of find-ing a double round-robin schedule satisfying constraintson the home/away patterns of the teams and minimiz-ing the total travel distance. The TTP has been tack-led by numerous approaches, including constraint andintege r programming (and their hybridizations) (Eas-ton, Nemhauser, & Trick 2001), Lagrangian relaxation(Benoist, Laburthe, & Rottembourg 2001), and meta-heuristics such as simulated annealing (Anagnostopou-los et al. 2003; 2006 ), tabu search (Di Gas pero &Schaerf 200 6), GRASP (Ribeiro & Urrutia 2007), andhybrid algorithms (Lim, Rodrigues, & Zhang 2006) toname only a few. The best solutions s o far have bee nobtained by meta-heuristics, often using varia tio ns ofthe neighborhood proposed in (Anagnostop oulos et al.Copyrightc 2007, American Association for Artificial In-telligence (www.aaai.org). All rights reserved.2003). This includes new variations of the TTP basedon circular and NFL distances. It is also intere stingto observe that progress seems to have slowed down inrecent years and some of the early instances have notbeen improved for several years.This paper presents a population-based simulated an-nealing algorithm with both intensification and diver-sification components. The core of the algorithm is or-ganized as a series of waves, each wave consisting of acollection of simulated annealing runs. At the end ofeach wave, an intensification takes place: a majority ofthe simulated annealing runs are restarted from the bestfound solution. Diversification is achieved through theconcept of elite runs, a generalization of the concept ofelite solutions. More precisely, at the end of each wave,the simulated annealing runs that produced the k-bestsolutions so far continue their execution opportunisti-cally fr om their current states. This core procedur eis terminated when a number of successive waves failto pr oduce an improvement and is then restarted at alower temperature.This population- based simulated annealing was im-plemented on a cluster of workstations. It producesnew best solutions on all TTP instances considered, in-cluding the la rger MLB instances which had not beenimproved for several years, the circular instances, andthe NFL instances for up to 26 teams. Although sim-ulated annealing is not the most appropriate algorithmfor the c ircular instances, the population-based algo-rithm has improved all b e st solutions for 14 teams ormore on these instances (a nd MLB 12). The improve-ments are often sig nificant, re ducing the optimality gapby almost 40% on many instances. The parallel imple-mentation also obtained these results in relatively shorttimes c ompared to the simulated annealing algorithm in(Van Hentenryck & Vergados 200 6).The broader contributions of the paper aretwofold. First, it demonstrates the potential com-plementarity between the macro-intensification andmacro-diversification typically found in tabu-searchand population-based algorithms and the micro-intensification (temperature decr e ase) and micro-diversification (threshold acceptance of degradingmove) fea tur e d in simulated annealing. Second, the pa-per indica tes the potential benefit of population-basedapproaches for simulated annea ling, contrasting withrecent negative r e sults in (Onba¸so˘glu &¨Ozdamar 2001).The rest o f the paper s tarts by reviewing the TTPand the simulated algorithm TTSA. It then presentsthe populated-based simulated annealing scheme andgives the experimental results on the TTP. The paperconcludes by discussing related work.Problem DescriptionA TTP input consists of n teams (n even) and an n × nsymmetric matrix d, such that dijrepresents the dis-tance between the homes of teams Tiand Tj. A solu-tion is a schedule in which each team plays with eachother twice, once in each team’s home. Such a scheduleis called a double round-robin tournament. It should beclear that a double round-ro bin tournament has 2n − 2rounds. For a given schedule S, the co st of a team asthe total distance that it has to travel s tarting from itshome, playing the scheduled games in S, and returningback home. The cost of a solution is defined as the sumof the cost of every team. The goal is to find a sched-ule with minimal travel distance satisfying the followingtwo constraints:1. Atmost Constraints: No more than three consec-utive home or away games are allowed for any team.2. Norepeat Constraints: A game of Tiat Tj’s homecannot be followed by a g ame of Tjat Ti’s home.As a consequence, a double round-robin schedule is fea-sible if it satisfies the atmost and nore peat constraintsand is infeasible otherwise.The Simulated Annealing AlgorithmThis paper leverages the simulated annealing algorithmTTSA (Anagnostopoulos et al. 2006) which is used asa black-box. It is not necessary to under stand its speci-ficities which are described elsewhere. It suffices to saythat TTSA explores a large neighborhood whose movesswap the complete/partial schedules of two rounds o rtwo teams, or flip the home/away patterns of a game.The


Download Population-Based Simulated Annealing for Traveling Tournaments
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Population-Based Simulated Annealing for Traveling Tournaments and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Population-Based Simulated Annealing for Traveling Tournaments 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?