Using Dominance in Solving Complex, Combinatorial Optimization Problems: Applications from Healthcare Provider Scheduling and Vehicle Routing

摘要

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.