Using Dominance in Solving Complex, Combinatorial Optimization Problems: Applications from Healthcare Provider Scheduling and Vehicle Routing
Hong, Young-Chae
2017
Abstract
The focus of this dissertation is to develop mathematical methods for the multi-criteria optimization problem and the vehicle routing problem. We approach these problems through the concept of Pareto dominance. Our goal is to develop general algorithms that utilize Pareto dominance and solve the problems in reasonable time. We first consider the problem of assigning medical residents to shifts within a pediatric emergency department. This problem is challenging to solve for a number of reasons. First, like many other healthcare personnel scheduling problems, it has a non-homogeneous work force, with each resident having different characteristics, requirements, and capabilities. Second, residency scheduling problems must not only ensure adequate resources for patient care but must also meet educational training needs, adding further complexity and constraints. Finally, since many factors should be taken into account when selecting the "best" schedule, there is no one clear, well-defined single objective function under which to optimize. Thus, it is difficult, if not impossible, to pre-assign weights that allow these factors and the preferences of the scheduler (typically, a Chief Resident) to be captured in a mathematical objective function. We propose an integer programming formulation and an iterative, interactive approach in which we use this integer program for ill-defined multiple objective criteria which are often in conflict with each other. After we identify quantifiable metrics through the interactive approach, we develop an integer programming-based approach embedded within a recursive algorithm to provide the Chief with a set of Pareto-dominant schedules from which to select. We then present our collaborative work with the University of Michigan C.S. Mott Children's Hospital in building monthly schedules, focusing on both the tractability of our methods and a case study to study how a Chief Resident would evaluate the Pareto set. When building schedules, an alternative is to use a column generation approach in which each variable represents complete sequences of tasks for a single agent to perform. In Chapter 4, we show how the concept of Pareto dominance can be used to generate columns efficiently. We evaluate dynamic programming-based column generation approaches for the vehicle routing problem since the models and algorithms proposed for the vehicle routing problems can be used effectively not only for the solution of transportation problems concerning the delivery or collection of goods but also for the solution of scheduling problems arising in healthcare as well. In particular, we consider a new variant of the Time-Constrained Heterogeneous Vehicle Routing Problem (TCHVRP). In this problem, the cost and travel time of any given arc vary by vehicle type within a heterogeneous fleet. We make no assumptions about Pareto dominance across vehicles; nor do we assume that cost and time are correlated. Our research is motivated by situations in which existing fleets are evolving to incorporate hybrid vehicles in addition to their existing vehicle types; for many vehicles, the cost per mile depends heavily on the type of driving (such as highway versus city). We formulate TCHVRP as a path-based model, which we solve using column generation. We introduce several different methods to solve the pricing problem. We conclude by conducting empirical analyses to assess the performance of the proposed approach.Subjects
Residency scheduling Multi-objective combinatorial optimization Pareto set vehicle routing problem column generation dynamic programming
Types
Thesis
Metadata
Show full item recordCollections
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.