Document Open Access Logo

An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two

Authors Diptendu Chatterjee , Bimal Kumar Roy

PDF
Thumbnail PDF

File

OASIcs.ATMOS.2021.16.pdf
  • Filesize: 0.66 MB
  • 15 pages

Document Identifiers

Author Details

Diptendu Chatterjee
  • Applied Statistics Unit, Indian Statistical Institute, Kolkata, India
Bimal Kumar Roy
  • Applied Statistics Unit, Indian Statistical Institute, Kolkata, India

Cite As Get BibTex

Diptendu Chatterjee and Bimal Kumar Roy. An Improved Scheduling Algorithm for Traveling Tournament Problem with Maximum Trip Length Two. In 21st Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2021). Open Access Series in Informatics (OASIcs), Volume 96, pp. 16:1-16:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/OASIcs.ATMOS.2021.16

Abstract

The Traveling Tournament Problem(TTP) is a combinatorial optimization problem where we have to give a scheduling algorithm which minimizes the total distance traveled by all the participating teams of a double round-robin tournament maintaining given constraints. Most of the instances of this problem with more than ten teams are still unsolved. By definition of the problem the number of teams participating has to be even. There are different variants of this problem depending on the constraints. In this problem, we consider the case where number of teams is a multiple of four and a team can not play more than two consecutive home or away matches. Our scheduling algorithm gives better result than the existing best result for number of teams less or equal to 32.

Subject Classification

ACM Subject Classification
  • Applied computing
Keywords
  • Traveling Tournament Problem
  • Double Round-robin
  • Scheduling
  • Approximation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Aris Anagnostopoulos, Laurent Michel, Pascal Van Hentenryck, and Yannis Vergados. A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9(2):177-193, 2006. Google Scholar
  2. Rishiraj Bhattacharyya. Complexity of the unconstrained traveling tournament problem. Operations Research Letters, 44(5):649-654, 2016. Google Scholar
  3. Dirk Briskorn, Andreas Drexl, and Frits CR Spieksma. Round robin tournaments and three index assignments. 4OR, 8(4):365-374, 2010. Google Scholar
  4. Robert Thomas Campbell and DS Chen. A minimum distance basketball scheduling problem. Management science in sports, 4:15-26, 1976. Google Scholar
  5. Dominique De Werra. Some models of graphs for scheduling sports competitions. Discrete Applied Mathematics, 21(1):47-65, 1988. Google Scholar
  6. Luca Di Gaspero and Andrea Schaerf. A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics, 13(2):189-207, 2007. Google Scholar
  7. Kelly Easton, George Nemhauser, and Michael Trick. The traveling tournament problem description and benchmarks. In International Conference on Principles and Practice of Constraint Programming, pages 580-584. Springer, 2001. Google Scholar
  8. Kelly Easton, George Nemhauser, and Michael Trick. Solving the travelling tournament problem: A combined integer programming and constraint programming approach. In International Conference on the Practice and Theory of Automated Timetabling, pages 100-109. Springer, 2002. Google Scholar
  9. Nobutomo Fujiwara, Shinji Imahori, Tomomi Matsui, and Ryuhei Miyashiro. Constructive algorithms for the constant distance traveling tournament problem. In International Conference on the Practice and Theory of Automated Timetabling, pages 135-146. Springer, 2006. Google Scholar
  10. Marc Goerigk, Richard Hoshino, Ken-ichi Kawarabayashi, and Stephan Westphal. Solving the traveling tournament problem by packing three-vertex paths. In Twenty-Eighth AAAI Conference on Artificial Intelligence, 2014. Google Scholar
  11. Richard Hoshino and Ken-ichi Kawarabayashi. The linear distance traveling tournament problem. In Twenty-Sixth AAAI Conference on Artificial Intelligence, 2012. Google Scholar
  12. Richard Hoshino and Ken-ichi Kawarabayashi. An approximation algorithm for the bipartite traveling tournament problem. Mathematics of Operations Research, 38(4):720-728, 2013. Google Scholar
  13. Shinji Imahori, Tomomi Matsui, and Ryuhei Miyashiro. A 2.75-approximation algorithm for the unconstrained traveling tournament problem. Annals of Operations Research, 218(1):237-247, 2014. Google Scholar
  14. Graham Kendall, Sigrid Knust, Celso C Ribeiro, and Sebastián Urrutia. Scheduling in sports: An annotated bibliography. Computers & Operations Research, 37(1):1-19, 2010. Google Scholar
  15. Andrew Lim, Brian Rodrigues, and Xingwen Zhang. A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174(3):1459-1478, 2006. Google Scholar
  16. Ryuhei Miyashiro, Tomomi Matsui, and Shinji Imahori. An approximation algorithm for the traveling tournament problem. Annals of Operations Research, 194(1):317-324, 2012. Google Scholar
  17. Rasmus V Rasmussen and Michael A Trick. Round robin scheduling-a survey. European Journal of Operational Research, 188(3):617-636, 2008. Google Scholar
  18. Clemens Thielen and Stephan Westphal. Complexity of the traveling tournament problem. Theoretical Computer Science, 412(4-5):345-351, 2011. Google Scholar
  19. Clemens Thielen and Stephan Westphal. Approximation algorithms for ttp (2). Mathematical Methods of Operations Research, 76(1):1-20, 2012. Google Scholar
  20. MA Trick. Challenge traveling tournament instances. http://mat.tepper.cmu.edu/TOURN/, 1999. Google Scholar
  21. Pascal Van Hentenryck and Yannis Vergados. Population-based simulated annealing for traveling tournaments. In Proceedings of the National Conference on Artificial Intelligence, volume 22, page 267. Menlo Park, CA; Cambridge, MA; London; AAAI Press; MIT Press; 1999, 2007. Google Scholar
  22. Stephan Westphal and Karl Noparlik. A 5.875-approximation for the traveling tournament problem. Annals of Operations Research, 218(1):347-360, 2014. Google Scholar
  23. Mingyu Xiao and Shaowei Kou. An improved approximation algorithm for the traveling tournament problem with maximum trip length two. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2016. Google Scholar
  24. Daisuke Yamaguchi, Shinji Imahori, Ryuhei Miyashiro, and Tomomi Matsui. An improved approximation algorithm for the traveling tournament problem. Algorithmica, 61(4):1077, 2011. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact