| Scheduling and routing problems are two similar problem classes and distinction between them is not exactly clear as variants of them can be shown to be identical or similar. In this thesis, we develop methodologies, including large neighborhood search, simulated annealing, genetic algorithms, Bender's cuts, mixed-integer programming and constraint programming, to solve scheduling, routing and related problems. The applications we considered include scheduling of Major League Baseball (MLB) umpires, home-delivered meals provision and logistics planning at a manufacturer.;The scheduling needs of umpires differ from the needs of sports teams. For some sports, since umpires travel throughout the season, it is important to balance distance traveled with a wish to not handle the games of any particular teams too many times. In the first part of this thesis, we attempt to model these conflicts by introducing the Traveling Umpire Problem (TUP) as a multi-objective sports scheduling problem and we present results using several methodologies to solve it.;In the second part, we develop a large neighborhood search heuristic that uses network heuristics to solve the seemingly unrelated Graph Coloring problem. We provide results on benchmark instances.;In the third part, we present a Genetic Algorithm to solve the Home Delivered Meals Location-Routing Problem (HDM-LRP), which addresses facility location and design of delivery routes, while balancing efficiency and effectiveness considerations. We present results on benchmark LRP instances and also a case study on HDNI data for Allegheny County of Pennsylvania. In the last part, we undertake an integrated study of inbound and outbound logistics at a leading automotive parts manufacturer. We identify the opportunity for significant cost savings over the current system by matching opposite flows of material from and to the customers and suppliers. |
