Models and algorithms for addressing complex constraints and objective functions: Applications from freight transportation and medical resident scheduling.

Abstract

In this dissertation, we develop models and algorithms to solve complex, real-world scheduling problems arising in the application areas of freight transportation and medical resident scheduling. These problems are interesting both from a theoretical perspective as they present difficult combinatorial challenges, and a practical perspective as they offer opportunities to improve system performance. However, developing optimization models to solve these scheduling problems is not always straightforward given the complex constraints of the problem, or the difficulty in defining an accurate objective function. In freight transportation, we present the load matching and routing (LMR) problem and explain how the non-linear cost structure, time windows of each of the loads, and large-scale nature of the problem pose challenges to optimization methods. Although traditional approaches such as multi-commodity flow models can be modified to address LMR, these modifications make multi-commodity flow models intractable for all except trivially-sized problem instances. We instead develop a model where the variables (called <italic>clusters </italic>) are designed to capture both the time-windows and non-linear cost structure implicitly within the variable definition. The resulting mathematical program has significantly fewer constraints; however, the number of variables is much larger. We develop <italic>cluster templates</italic> as a mechanism to enumerate candidate variables and overcome the difficulties associated with a pricing problem, and demonstrate how this allows us to generate high-quality solutions to real-world problem instances quickly. We next describe how our cluster-based modeling approach can be extended to capture additional problems faced by express package carriers---<italic>trailer assignment</italic> and <italic>equipment balancing</italic>. We then shift our focus to medical resident scheduling. In this problem, residents need to be assigned to a series of overnight call shifts. Generating on-call schedules that satisfy the constraints imposed by the residents' requirements, the hospitals, and federal safety regulations is difficult. A greater challenge, however, arises when trying to define an objective function that incorporates characteristics desirable to each of the residents, but is fair. We develop a technique that allows the chief residents to interact with a series of potential schedules, at each iteration identifying characteristics that should---and shouldn't---remain in subsequent schedules until a final schedule incorporating the desirable characteristics is created.