A note on symmetry reduction for circular traveling tournament problems

Timo Gschwind and Stefan Irnich

European Journal of Operational Research, 2011, vol. 210, issue 2, 452-456

Abstract: The traveling tournament problem (TTP) consists of finding a distance-minimal double round-robin tournament where the number of consecutive breaks is bounded. Easton et al. (2001) introduced the so-called circular TTP instances, where venues of teams are located on a circle. The distance between neighboring venues is one, so that the distance between any pair of teams is the distance on the circle. It is empirically proved that these instances are very hard to solve due to the inherent symmetry. This note presents new ideas to cut off essentially identical parts of the solution space. Enumerative solution approaches, e.g. relying on branch-and-bound, benefit from this reduction. We exemplify this benefit by modifying the DFS* algorithm of Uthus et al. (2009) and show that speedups can approximate factor 4n.

Keywords: Timetabling; Sports; league; scheduling; Traveling; tournament; problem; Circular; instances; Symmetry; reduction (search for similar items in EconPapers)
Date: 2011
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377-2217(10)00552-7
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:210:y:2011:i:2:p:452-456

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().