Title: Decomposition and Local Search Based Methods for the Traveling Umpire Problem
Authors: Wauters, Tony * ×
Van Malderen, Sam *
Vanden Berghe, Greet #
Issue Date: 1-Nov-2014
Publisher: Elsevier
Series Title: European Journal of Operational Research vol:238 issue:3 pages:886-898
Abstract: The Traveling Umpire Problem (TUP) is a challenging combinatorial optimization
problem based on scheduling umpires for Major League Baseball. The TUP aims at
assigning umpire crews to the games of a fixed tournament, minimizing the
travel distance of the umpires. The present paper introduces two complementary
heuristic solution approaches for the TUP. A new method called enhanced
iterative deepening search with leaf node improvements (IDLI) generates
schedules in several stages by subsequently considering parts of the problem.
The second approach is a custom iterated local search algorithm (ILS) with a
step counting hill climbing acceptance criterion. IDLI generates new best
solutions for many small and medium sized benchmark instances. ILS produces
significant improvements for the largest benchmark instances. In addition, the
article introduces a new decomposition methodology for generating lower
bounds, which improves all known lower bounds for the benchmark instances.
ISSN: 0377-2217
Publication status: published
KU Leuven publication type: IT
Appears in Collections:Computer Science Technology TC, Technology Campuses Ghent and Aalst
Technologiecluster Computerwetenschappen
* (joint) first author
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
TUP-paper.pdf Published 500KbAdobe PDFView/Open


All items in Lirias are protected by copyright, with all rights reserved.

© Web of science