Analysis of a constructive matheuristic for the traveling umpire problem

Chandrasekharan Reshma Chirayil (), Toffolo Túlio A.M. () and Wauters Tony ()
Additional contact information
Chandrasekharan Reshma Chirayil: KU Leuven, Department of Computer Science, CODeS & imec – Gebroeders De Smetstraat 1, 9000 Ghent, Belgium
Toffolo Túlio A.M.: KU Leuven, Department of Computer Science, CODeS & imec – Gebroeders De Smetstraat 1, 9000 Ghent, Belgium
Wauters Tony: KU Leuven, Department of Computer Science, CODeS & imec – Gebroeders De Smetstraat 1, 9000 Ghent, Belgium

Journal of Quantitative Analysis in Sports, 2019, vol. 15, issue 1, 41-57

Abstract: The Traveling Umpire Problem (TUP) is a combinatorial optimization problem concerning the assignment of umpires to the games of a fixed double round-robin tournament. The TUP draws inspiration from the real world multi-objective Major League Baseball (MLB) umpire scheduling problem, but is, however, restricted to the single objective of minimizing total travel distance of the umpires. Several hard constraints are employed to enforce fairness when assigning umpires, making it a challenging optimization problem. The present work concerns a constructive matheuristic approach which focuses primarily on large benchmark instances. A decomposition-based approach is employed which sequentially solves Integer Programming (IP) formulations of the subproblems to arrive at a feasible solution for the entire problem. This constructive matheuristic efficiently generates feasible solutions and improves the best known solutions of large benchmark instances of 26, 28, 30 and 32 teams well within the benchmark time limit. In addition, the algorithm is capable of producing feasible solutions for various small and medium benchmark instances competitive with those produced by other heuristic algorithms. The paper also details experiments conducted to evaluate various algorithmic design parameters such as subproblem size, overlap and objective functions.

Keywords: decomposition; integer programming; matheuristic; sports scheduling; TUP (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/jqas-2017-0118 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

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:bpj:jqsprt:v:15:y:2019:i:1:p:41-57:n:1

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/jqas/html

DOI: 10.1515/jqas-2017-0118

Access Statistics for this article

Journal of Quantitative Analysis in Sports is currently edited by Mark Glickman

More articles in Journal of Quantitative Analysis in Sports from De Gruyter
Bibliographic data for series maintained by Peter Golla ().