EUVIMEDEUVIMED entdecken
Crossref

Approaching the Traveling Tournament Problem with Randomized Beam Search

Nikolaus Frohner, Bernhard Neumann, Giulio Pace, Günther R Raidl

Evolutionary Computation · 2023

DOI: 10.1162/evco_a_00319 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Evolutionary Computation, 2023. Verfasst von Nikolaus Frohner und 3 weiteren Autor:innen. Beteiligte Einrichtung: Institute of Logic and Computation, TU Wien, Vienna, Austria nfrohner@ac.tuwien.ac.at. Hauptthemen laut MEDLINE: Algorithms, Sports. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 27 Literaturangaben.

AbstractSchlagwörterBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

The traveling tournament problem is a well-known sports league scheduling problem famous for its practical hardness. Given an even number of teams with symmetric distances between their venues, a double round-robin tournament has to be scheduled minimizing the total travel distances over all teams. We consider the most common constrained variant without repeaters and a streak limit of three, for which we study a beam search approach based on a state-space formulation guided by heuristics derived from different lower bound variants. We solve the arising capacitated vehicle routing subproblems either exactly for small- to medium-sized instances up to 18 teams or heuristically also for larger instances up to 24 teams. In a randomized variant of the search, we employ random team ordering and add small amounts of Gaussian noise to the nodes' guidance for diversification when multiple runs are performed. This allows for a simple yet effective parallelization of the beam search. A final comparison is done on the NL, CIRC, NFL, and GALAXY benchmark instances with 12 to 24 teams, for which we report a mean gap difference to the best known feasible solutions of 1.2% and five new best feasible solutions.

Schlagwörter

MeSH-Schlagwörter (MEDLINE)

AlgorithmsSportsHeuristicsTravel

Stichwörter der Autor:innen

Traveling tournament problembeam searchvehicle routing problem

Autor:innen und Institutionen

  • Institute of Logic and Computation, TU Wien, Vienna, Austria nfrohner@ac.tuwien.ac.at.
  • Institute of Logic and Computation, TU Wien, Vienna, Austria bernhard.neumann96@gmail.com.
  • Institute of Logic and Computation, TU Wien, Vienna, Austria giulio.pace93@gmail.com.
  • Institute of Logic and Computation, TU Wien, Vienna, Austria raidl@ac.tuwien.ac.at.

Zitieren

APA

Frohner, N., Neumann, B., Pace, G., & Raidl, G. R. (2023). Approaching the Traveling Tournament Problem with Randomized Beam Search. Evolutionary Computation. https://doi.org/10.1162/evco_a_00319

Vancouver

Frohner N, Neumann B, Pace G, Raidl GR. Approaching the Traveling Tournament Problem with Randomized Beam Search. Evolutionary Computation. 2023. doi:10.1162/evco_a_00319

BibTeX
@article{Frohner2023,
  author = {Frohner, Nikolaus and Neumann, Bernhard and Pace, Giulio and Raidl, Günther R},
  title = {Approaching the Traveling Tournament Problem with Randomized Beam Search},
  journal = {Evolutionary Computation},
  year = {2023},
  doi = {10.1162/evco_a_00319}
}
Kostenlos starten →