Benders' cuts guided large neighborhood search for the traveling umpire problem |
| |
| Authors: | Michael A Trick Hakan Yildiz |
| |
| Institution: | 1. Tepper School of Business, Carnegie Mellon University, Pittsburgh, Pennsylvania 15213;2. Eli Broad College of Business, Michigan State University, East Lansing, Michigan 48824 |
| |
| Abstract: | This article introduces the use of Benders' cuts to guide a large neighborhood search to solve the traveling umpire problem, a sports scheduling problem inspired by the real‐life needs of the officials of a sports league. At each time slot, a greedy matching heuristic is used to construct a schedule. When an infeasibility is recognized first a single step backtracking is tried to resolve the infeasibility. If unsuccessful, Benders' cuts are generated to guide a large neighborhood search to ensure feasibility and to improve the solution. Realizing the inherent symmetry present in the problem, a large family of cuts are generated and their effectiveness is tested. The resulting approach is able to find better solutions to many instances of this problem. © 2011 Wiley Periodicals, Inc. Naval Research Logistics, 2011 |
| |
| Keywords: | personnel scheduling spots benders cuts large neighborhood search |
|
|
