Vehicle routing and resource allocation for health care under uncertainty.

摘要

In this research, we study optimization models for health care under uncertainty and resource constraints. In particular, we study two problems: Vehicle Routing Problem (VRP) in health care, and resource allocation to address an infectious disease outbreak. The first problem is inspired by the routing of vehicles to deliver medical samples and documents on a multi-shift basis in a health care organization. It is all too common to have a limited amount of resources (e.g., the number of vehicles) to conduct these activities. The second problem deals with resource allocation in large-scale emergency response to an infectious disease outbreak. In addition to a limited amount of resources, large-scale emergencies are faced with substantial uncertainties. Also, accurate parameter estimation can be extremely difficult for epidemic models.;In health care routing it is necessary to use multiple shifts to be able to meet around-the-clock demand. Therefore we study the multi-shift VRP (MSVRP). In this problem, a limited fleet of vehicles is used repeatedly to serve demand over a planning horizon of several days. We formulate the MSVRP as a Mixed Integer Programming (MIP) model, and develop a shift-dependent (SD) heuristic that takes overtime into account when constructing routes. We show that the SD algorithm has significant savings in total cost over constructing the routes independently in each shift, and it can obtain optimal or close to optimal solutions for small instances. Specialized cuts are introduced to obtain efficient lower bounds. The solution of the SD algorithm on the test problems is within 1.09--1.82 times the optimal solution depending on the time window width, with the smaller time windows providing the tighter bounds.;A large-scale infectious disease outbreak can potentially reach large portions of the population. Planning an effective response to such an emergency requires a coordinated effort in multiple locations to best allocate limited resources to the infected areas. We present a multi-city resource allocation model to distribute the medical supplies in order to minimize the total number of deaths. The model helps decide the amounts of supplies to deliver and which infection control measure (isolation, ring vaccination, or mass vaccination) to use in each location, taking into account both the number of deaths from the disease and the deaths due to the intervention. In addition, we consider the problem with uncertainty in the initial number of cases and the transmission rates, and build a two-stage stochastic programming model with integer variables in both stages. To solve instances of realistic size we use a heuristic based on Benders decomposition, where we obtain dual information from the subproblems by solving a linear program around the second stage optimal solution. Finally, we use sample average approximation (SAA) to get confidence intervals on the optimal solution. We illustrate the use of the model and the solution technique in planning an emergency response to a hypothetic national smallpox outbreak. Computations show the scalability of the algorithm, the sensitivity of the algorithm to different resource levels, and the effectiveness of the cuts proposed to speed up the algorithm. The value of stochastic solution and confidence intervals of the optimality gap are computed.