Starten Sie Ihre Suche...


Durch die Nutzung unserer Webseite erklären Sie sich damit einverstanden, dass wir Cookies verwenden. Weitere Informationen

A note on symmetry reduction for circular traveling tournament problems

European journal of operational research. Bd. 210. H. 2. 2011 S. 452 - 456

Erscheinungsjahr: 2011

ISBN/ISSN: 0377-2217

Publikationstyp: Zeitschriftenaufsatz

Sprache: Englisch

Doi/URN: 10.1016/j.ejor.2010.08.015

Volltext über DOI/URN

GeprüftBibliothek

Inhaltszusammenfassung


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 symmet...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.» weiterlesen» einklappen

Autoren


Gschwind, Timo (Autor)

Klassifikation


DFG Fachgebiet:
Wirtschaftswissenschaften

DDC Sachgruppe:
Zeitschriften, fortlaufende Sammelwerke

Verknüpfte Personen