BUSINESS MANAGEMENT A+ WORK, ON TIME, NO PLAGARIZING; ON TIME
Pelicans!!322
Improving_decision_making_in_hecono600.pdf
Improving Decision Making in Healthcare Operations
Matthew D. Dean, Ph.D.
University of Connecticut, 2010
This dissertation examines three distinct problems in the healthcare operations field and
demonstrates how decision making can be improved in each setting. The first problem
addresses how to make dynamic, real-time allocation decisions of testing time slots for a
Cardiac Diagnostic Testing Center (CDTC) in the presence of multiple competing patient
classes. Using historical data from the CDTC at a partner hospital, we explore the
performance of a dynamic model which is based on a multi-commodity network flow
formulation of the CDTC's scheduling problem. It incorporates the possibility of
"bumping" different patient classes in order to accommodate requests from other patient
classes. Our results indicate that this approach will result in drastically improved quality
of service for inpatients with little or no reduction in the quality of service to the
outpatients, relative to existing policy at our partner hospital. We then shift to exploring
another important problem involving healthcare resources: during a Mass Casualty
Incident (MCI), to which one of several area hospitals should each victim be sent? These
decisions depend on resource availability (both transport and care) and the survival
probabilities of patients. We focus on the critical time period immediately following the
onset of an MCI and are concerned with how to effectively transport victims to the
different area hospitals in order to provide the greatest good to the greatest number of
patients while not overwhelming any single hospital. We explore two settings. First, we
examine the deterministic version of the problem. We compare our proposed model with
Matthew D. Dean - University of Connecticut, 2010
a model in the extant literature and also against several current policies commonly used
by the so-called incident commander. Finally, we explore a dynamic and stochastic
setting for the MCI problem, looking at how our decisions affect the expected number of
survivors as events unfold over time. To address the infamous "curse of dimensionality",
we develop a heuristic methodology that combines the use of a stochastic dynamic
program (SDP) and Monte Carlo simulation to arrive at a final decision policy. We call
this methodology "scenario iteration." Managerial insights are also discussed for each of
the MCI models.
Improving Decision Making in Healthcare Operations
Matthew D. Dean
B.S., The College of William and Mary, 1997
A Dissertation
Submitted in Partial Fulfillment of the
Requirements for the Degree of
Doctor of Philosophy
at the
University of Connecticut
2010
UMI Number: 3411477
All rights reserved
INFORMATION TO ALL USERS The quality of this reproduction is dependent upon the quality of the copy submitted.
In the unlikely event that the author did not send a complete manuscript and there are missing pages, these will be noted. Also, if material had to be removed,
a note will indicate the deletion.
UMT Dissertation Publishing
UMI 3411477 Copyright 2010 by ProQuest LLC.
All rights reserved. This edition of the work is protected against unauthorized copying under Title 17, United States Code.
A ® uest ProQuest LLC
789 East Eisenhower Parkway P.O. Box 1346
Ann Arbor, Ml 48106-1346
Copyright by
Matthew D. Dean
2010
APPROVAL PAGE
Doctor of Philosophy Dissertation
Improving Decision Making in Healthcare Operations
Presented by
Matthew D. Dean, B.S.
Major Advisor
Associate Advisor
Robert Day
Associate Advisor
Robert Garfinkel
Associate Advisor
Steven Thompson
University of Connecticut
2010
II
Table of Contents APPROVAL PAGE ii
Acknowledgements vi
Chapter 1 - Introduction 1
Chapter 2 - Dynamic Allocation of Cardiac Diagnostic Testing Time Slots .5
2.1 Introduction 5
2.2 Literature Review 9
2.3 Problem Setting 10
2.3.1 The State of the Hospital 12
2.4 An Overview of the Markov Decision Process 14
2.4.1 Decisions 14
2.4.2 Rewards to the hospital 14
2.4.3 Costs to patients 15
2.5 Details of the MDP 15
2.5.1 Notation 15
2.5.2 Process State 19
2.5.3 Constraints 20
2.5.4 Stage Reward 20
2.5.5 State Transition 22
2.5.6 Objective Function 23
2.6 A DSS Based on a Multi-commodity Flow Snapshot Model (MFSM) 23
2.6.1 Notation 25
2.6.2 Derivation of Inpatient Delay Costs under MFSM 26
2.6.3 Formulation 27
2.6.4 Size of the Model 28
2.7 Experimental Analysis 29
2.7.1 The MFSM versus the MDP 29
2.7.2 The MFSM versus the Current Approach 32
2.7.3 Results 34
2.8 Conclusions 37
CHAPTER 3 - Mass-Casualty Triage: Distribution of Victims to Multiple
Hospitals 39
iii
3.1. Introduction 39
3.2. Literature Review 43
3.3. Resource-Constrained Triage 44
3.3.1 Brief introduction to STM 45
3.3.2 Limitations of STM 46
3.3.3 Motivational Example 46
3.3.4 Our Enhanced Model 50
3.4. Formulation of the Resource-Constrained Triage Problem 52
3.4.1 Notation 52
3.4.2 Formulation 53
3.4.3 A Small Example 54
3.4.4 Enhanced Model's Performance vs. STM Model 55
3.5. Experiments 56
3.5.1 Experimental Setup 58
3.5.2 Low Score First Not Always Best Approach 61
3.5.3 Comparison of Enhanced Model to Heuristics 62
3.6. Managerial Implications and Conclusion 64
CHAPTER 4 - Investigating the Distribution of Victims to Multiple Hospitals in a Dynamic and Stochastic Setting 66
4.1. Introduction 66
4.2. Review of the Relevant Literature 68
4.3. Problem Description 70 4.3.1 Data Elements 71
4.3.2 The Stochastic and Dynamic Problem 73
4.4. Scenario Iteration 74
4.4.1 General Heuristic Algorithm 76
4.4.2 The Stochastic Dynamic Programming Model 77
4.4.3 The Monte Carlo Simulation 80
4.4.3 Convergence 83
4.5. Experimental Analysis 85
4.5.1 Experimental Setup 85
4.5.2 Model Performance 88
4.5.3 Performance of the Heuristic Methodology 90
4.5.4 Ability to Scale 90
4.6. Conclusion 93
IV
Chapter 5 - Conclusion and Future Directions 94
References 98
v
Acknowledgements
I would like to thank each member of my committee for their guidance and
encouragement. Their help along my winding journey are appreciated far more than they
know. My major advisor, Professor Suresh Nair, has reminded me of what a rewarding
experience it is to have the opportunity to work with a team of truly intelligent individuals.
He renewed my vigor to attack research problems head-on. His constant pressure to
provide results quickly made completing this dissertation a reality. Also, his insights and
ability to explain things clearly and simply have renewed my aspirations to be able to do
the same thing for all of my future students. The days when Bob Day and I would
brainstorm ideas on his whiteboard were treasured by me. His high energy and desire to
solve problems are contagious. Rob Garfinkel always expected my best effort and
wanted me to push myself as far as possible. Steve Thompson has been a steady and
valuable mentor to me both during our shared time at UConn and beyond.
I would also like to thank my fellow PhD students in the OPIM department for all
the times we shared together. During my early years, Steve helped ground my belief that
"real" research can be practical. Towards the latter part, Travis Maynard proved an
invaluable sounding board during our runs. His continued friendship is cherished.
Last, and most importantly, I thank my wife Jennifer for believing in me. Her
stead-fast love and patience throughout this process warrants, in my mind, her own
special "PhD." How she manages to raise two small boys while I am always at work, I do
not know. Cole and Evan have reminded me of the true definition of patience, even if I
do not always adhere to it. They always bring me joy at the end of the day. Without
Jennifer, I would not have succeeded. I cannot thank her enough.
Chapter 1 - Introduction
This dissertation examines three distinct problems in the healthcare operations field and
demonstrates how decision making can be improved in each setting. The first problem
addresses how to make dynamic, real-time allocation decisions of testing time slots for a
Cardiac Diagnostic Testing Center (CDTC) in the presence of multiple competing patient
classes. The second and third parts of the dissertation investigate how to determine
which of several area hospitals to send victims of a Mass Casualty Incident (MCI). In the
two MCI settings, first, we explore the problem in a deterministic setting. We compare
our proposed model with a model in the extant literature and also against several current
policies commonly used by the so-called incident commander. Finally, we explore a
dynamic and stochastic setting for the MCI problem, looking at how our decisions affect
the expected number of survivors as events unfold over time.
A CDTC makes real-time scheduling decisions that impact the use of its
equipment and rooms. Both inpatients and outpatients are frequent users of CDTC
resources, and physicians may prescribe one of several test protocols. The result is a
highly complex online decision-making environment, in which the decisions made by the
CDTC affect both direct revenues and costs associated with the patients undergoing
cardiac diagnosis, and the costs associated with other hospital resources, such as bed
availability. Using historical data from the CDTC at a local partner hospital, we explore
the performance of a dynamic model (instead of the currently used static policies), based
on a multi-commodity network flow formulation of the CDTC's scheduling problem that
incorporates the possibility of "bumping" or delaying of different patient classes in order
to accommodate requests from other patient classes. To demonstrate how this can be
1
done, we provide a descriptive model of the CDTC's scheduling problem in the form of a
Markov decision process (MDP). We then contrast the results obtained by using a
tractable, state-aggregated version of the MDP to the results obtained from using our
suggested protocol. Solving the full MDP representing the problem is impractical in the
online setting of this study and motivates the introduction of the proposed dynamic
network approach.
Our results indicate that this approach will result in drastically improved quality of
service for inpatients with little or no reduction in the quality of service to the outpatients,
relative to existing policy at our partner hospital. Our methods provide both an online
decision support tool and a framework by which simulation results may be used as
guidance for more profitable long-term capacity planning. In addition, hospital
administrators can use the results of the simulations to make strategic decisions about
how much capacity to reserve for inpatient tests in order to achieve their desired service
levels.
We then shift to exploring another important problem involving healthcare
resources: during an MCI, to which one of several area hospitals should each victim be
sent? These decisions depend on resource availability (both transport and care) and the
survival probabilities of patients. Simple heuristics used at present (such as, send the
most critical patient out first, to the closest hospital) may not result in the best utilization
of resources or the best overall outcome. In the first part of this problem, we focus on a
deterministic setting. Triaging victims of an MCI and subsequently transporting them to
area hospitals provides a challenge to the disaster response team. Because time is of
the essence, and there are multiple variables to consider in quick time, simple heuristics
are usually used. We describe an enhanced model that takes into account multiple
hospitals and their capacities and capabilities, victim-specific care times, degradation of
2
survival due to delays, increase of care time due to delays, and transport availability
depending on when and where these resources were deployed and dispatched.
We focus on the critical time period immediately following the onset of an MCI
and are concerned with how to effectively transport victims to the different area hospitals
in order to provide the greatest good to the greatest number of patients while not
overwhelming any single hospital. The Sacco Treatment Method (STM) model (Sacco et
al., 2005) is the only model that quantifies the term "greatest good to the greatest
number." They develop a "score-based" mathematical programming model that
maximizes the expected number of survivors from the MCI. Though this model is an
improvement over simple heuristics, there are many assumptions in the model which
may not be realistic in real time settings.
To address these issues, we propose three major enhancements to the STM
model, making our model more realistic and useful in practice. The enhancements we
make are: the time needed to treat/process a victim at a hospital varies depending on
the severity of the injury to the victim; care times for a particular victim will increase as
his score decreases (gets worse); we explicitly consider the treatment capacities and
capabilities of the area hospitals; and the availability of resources for transporting victims
depends upon where and when it was sent in the previous trip.
This resource-constrained triage problem is formulated as a mixed-integer
program. We compare our model to the STM model and show that, in our experiments,
our model has an average improvement of 36.5% and 69.0% in the expected number of
survivors, depending on how the STM model is implemented.
We then design a comprehensive experiment to compare our enhanced model
with three commonly used policies for allocating victims to hospitals during an MCI. Our
results indicate a marked improvement over all of these currently used heuristics. We
also discuss under which circumstances it would be advantageous to have more
3
transport resources available versus more hospital capacity, providing guidelines for
implementation of our model to incident commanders of mass casualty incidents.
The final part of the dissertation investigates the evacuation of victims of an MCI
in a dynamic setting. This problem is extremely challenging because of the large state
space that needs to be explored due to the number and dimension of state variables that
need to be modeled. Even very small instances of the problem can result in several
million states that need to be considered. To address this issue, we develop a heuristic
methodology that combines the use of a stochastic dynamic program (SDP) and Monte
Carlo simulation to arrive at a final decision policy. The simulation helps predict the
probability of occurrence of status of several state variables so they do not have to be
explicitly modeled in the SDP, thus reducing the size of the state space dramatically.
The SDP optimal policy table is then used in the simulation to determine decisions. The
simulation then generates an updated probability transition matrix to be used in the SDP.
We find that, using the scaling methodology proposed, this iterative solving of the SDP
and simulation converges to a stable policy table fairly quickly. We call this methodology
"scenario iteration."
We compare the performance of scenario iteration over several scaling methods,
and over several test data sets. We also compare the results and applicability of the
dynamic model compared to the static model developed in the second part of the
dissertation. Managerial insights are discussed for each of the MCI models.
4
Chapter 2 - Dynamic Allocation of Cardiac Diagnostic
Testing Time Slots
2.1 Introduction
Many hospitals in the United States provide a wide range of inpatient and outpatient
healthcare services to the communities they serve. Outpatient services tend to be more
lucrative because they require less infrastructural investment and have lower ancillary
support costs. The profits obtained from outpatient services are crucial, because they
enable the hospital to offset possible losses on certain inpatient services and invest in
new medical technologies. Thus, the units that provide outpatient services are often
treated as profit centers, each of which strives to maximize revenue. Inpatient services,
with the exception of some surgical services, are typically not highly lucrative. For these
services, the hospital typically receives a lump sum payment determined by the patient's
classification to a particular Diagnostic Related Group (DRG) at the time of admission.
However inpatient care requires a great deal of infrastructure and support personnel to
be constantly in place. This results in very high fixed costs, so that hospital units that
provide inpatient services must operate at high levels of utilization in order to break
even. The problem of optimally balancing the levels of inpatient versus outpatient
services is complicated by the fact that the demand for inpatient services is variable. The
need to maintain high levels of utilization and meet uncertain demand makes the
management of inpatient services challenging.
While low demand that results in poor utilization is a concern, high demand and
the associated congestion can also present a significant problem. For example, if a
5
given inpatient unit in a hospital does not have enough beds to accommodate all
patients in need, then some of them will be "held" in the emergency department (ED)
until a bed becomes available. When the ED becomes too crowded, it can no longer
function effectively. In the extreme case the hospital may have to deny admission to
potential inpatients. Often this takes the form of diversion of ambulances to other
hospitals, since this is a common manner of inpatient arrival. The hospital then loses the
revenue that would have resulted from treating those patients that were diverted, and its
reputation as a reliable provider is also damaged.
Some hospital facilities are commonly termed "outpatient units", although that is
not entirely accurate, as these units often provide services to inpatients as well. One
typical example is the cardiac diagnostic testing center (CDTC) at Windham Community
Memorial Hospital (WCMH) in Willimantic, CT. Like the CDTC at most hospitals, its
primary role is to provide a range of cardiac screening tests to outpatients. These
screenings are used for preventative care as opposed to the diagnosis of urgent,
potentially life threatening conditions. Patients are typically referred to the CDTC by their
physicians, and schedule appointments for prescribed tests, well in advance.
The other role of the CDTC is to perform cardiac screenings on inpatients. For
them, the stress test is generally the last test prior to discharge because it is the most
aggressive in terms of how much strain is placed on the patient's heart. When a patient
is admitted with chest pain a number of tests are done that do not place any strain on
the heart (blood tests, EKGs, etc.). The purpose of those tests is to find evidence that
the heart muscle is not receiving enough blood flow, causing the patient to experience
chest pain. When these tests are negative, the final test is a stress test to push the heart
and see if any symptoms arise. If the heart behaves normally under exercise conditions,
then it is safe to send the patient home. Only if symptoms appear during this final
screening, which in practice is uncommon, must the patient remain hospitalized. At
6
WCMH in particular, even if a stress test is not normal, patients still leave the hospital.
Rather than going home they are typically transferred to a larger facility that is able to
perform complex cardiovascular procedures such as angioplasty, coronary artery
stenting, coronary artery by-pass grafting, etc.
Providing screenings to inpatients presents a challenge because, unlike those for
outpatients, the requests for screening often come with little or no notice. If at the time of
the request there is no immediate opening, a scheduling decision must be made. In
essence, this involves choosing which among various classes of patients, some of whom
are inpatients and others outpatients, to service at a given time period. A serious area of
concern observed at WCMH prior to our study was that some outpatients do indeed
balk, presumably choosing to be screened elsewhere, if they are rescheduled from their
prearranged time slot. Further, in many cases physicians are affiliated with multiple
hospitals in a given area, and as a result, hospitals face competition from other hospitals
when the physicians feel that one hospital is providing better service. Hospitals can also
face competition from the physicians that are affiliated with the hospital. For example,
one of the cardiologists affiliated with WCMH made the decision a few years prior to our
study to stop working with the CDTC and open her own screening clinic. It follows that,
considering only the profit to the CDTC, part of an intuitively dominant decision rule
would be to give priority to outpatients. Thus an ad hoc strategy used by many hospitals,
including WCMH, is to give priority to outpatients except in some time slots that are
reserved for inpatients.
On the other hand, the CDTC can play a key role in maintaining patient flow and
helping the hospital avoid the negative consequences of an overcrowded ED. By
providing an inpatient screening the CDTC effectively "opens a bed" because that
patient can now almost always be discharged, either to home or to another hospital,
after its completion. This provides the hospital with the ability to accommodate an
7
additional patient, should one arrive. Note that any patient whose screening is delayed
must also be assigned a subsequent time slot. Thus, because there are two potential
classes of costs, we choose to follow many authors (e.g., Green et al. (2006)) and
optimize a composite "social welfare" function of the profits to the hospital from providing
patient services, costs to the hospital of lost opportunity, and "inconvenience" costs to
the patients of delays in treatment. It should be stressed that the resulting algorithm is a
decision support system, so that its users can certainly input any costs that they deem
appropriate, including the possibility of not considering patient inconvenience costs by
setting those values to zero.
The scheduling problem is complicated by the fact that there are different types
of cardiac screenings. Some have multiple phases, some span a two-day period, and
the phases in a multiple-phase test must be done in lockstep fashion over time. That is,
once a screening begins, or resumes on its second day, subsequent steps in that day
must be done in the immediately following time periods. The problem can be modeled as
a finite-horizon, discrete-time Markov decision process (MDP) as described in Section
2.8. However, one quickly finds that the computational methods based on this model
tend to be impractically slow and memory intensive when compared to the pace of the
actual decision making environment, motivating the introduction of a computationally
tractable scheduling tool.
Therefore, we introduce a decision support system based on a Multi-commodity
Flow Snapshot Model (MFSM), grounded in the theory of dynamic network optimization.
This approach is both flexible and robust, making it applicable to the various
configurations of patient and test-protocol types that may be found in practically any
CDTC. Based on historical data from WCMH, our experiments indicate that the MFSM
approach results in drastically improved quality of service for inpatients, with little or no
reduction in the quality of service to outpatients relative to the existing policy at WCMH.
8
The bottom line of the hospital will also show a healthy improvement. Our methods
provide both an online decision support tool and a framework by which simulation results
may be used as guidance for more profitable long-term capacity planning.
The rest of this chapter is organized as follows. The related literature is reviewed
in Section 2.2 and in Section 2.3 the problem is formally defined. In Section 2.4 we
provide an overview of the MDP approach with details following in Section 2.5. The
dynamic-network model is described in Section 2.6. In Section 2.7 we use simulation
and real data from WCMH to evaluate the results of the network model relative to the
MDP and to the prior decision making policy utilized by WCMH. Conclusions, with
managerial implications and directions for future research, are addressed in Section 2.8.
2.2 Literature Review
Efficiency of healthcare operations has been widely studied in the management science
literature, and detailed histories of the application of operations research models to
problems in the healthcare industry can be found in (Flagle, 2002) and (Brandeau et al.,
2004). A number of techniques have been employed to help improve patient flow
including dynamic allocation of patients to the inpatient units (Thompson et al., 2009),
bedside registration (Parker, 2004), and applications of simulation and queuing theory to
identify and remove patient flow bottlenecks (Litvak et al., 2001).
The problem of allocating CDTC time slots shares some traits with a number of
stochastic control applications. Allocating service capacity over time among several
competing customer classes has been studied in various settings outside of healthcare,
including hotel management (Lieberman and Yechiali, 1978; Bitran and Gilbert, 1996),
car rentals (Carrol and Grimes, 1995; Geraghty and Johnson, 1997), and airline yield
management (Belobaba, 1989). These articles fall into the category of revenue
management. One distinguishing feature between revenue management and our
diagnostic allocation problem is that in many instances of revenue management,
9
customers can choose which "fare class" they belong to, whereas in our setting, the
screening class is determined by a physician.
The more closely related problem of appointment scheduling and real-time
capacity allocation in an MRI setting was addressed by (Green et al., 2006). The use of
approximate dynamic programming to solve the problem of dynamically allocating
diagnostic imaging resources to multiple patient priority classes, in order to achieve
targeted wait times was investigated in (Patrick et al, 2008). While Patrick et al (2008)
and Green et al. (2006) consider allocation of time slots among multiple patient classes,
the problem addressed here is different for two reasons. First, we expand the state
space definition to include the number of available inpatient beds for different services.
This increases the size and complexity of the problem, but thereby more accurately
captures the costs that CDTC decisions impose on the rest of the hospital. Second, we
consider time slot allocation decisions for both multiple-phase and single-phase tests.
The distinction is that a multiple-phase test involves performing a set of procedures at
separate times. To the best of our knowledge a setting involving a mixture of single- and
multiple-phase tests with a mixture of patient classes in the operations research
healthcare literature, has not been investigated prior to this study. We utilize a dynamic
network flow model within our proposed approach to solving the problem. A recent
example utilizing dynamic network models to schedule and dispatch concrete trucks was
described by (Durbin and Hoffman, 2008).
2.3 Problem Setting
Cardiologists can typically choose from among a number of different types of screenings
for each patient. For example, at WCMH there were three options. All consist of one or
more of the stages listed below. Each of the three stages takes about one hour to
perform. The stages within a given day must be performed in consecutive periods, while
two-day screenings must be completed in successive days. The stages are:
10
• Exercise-Monitor: The patient is connected to an electrocardiograph
machine and the heart is monitored while the patient exercises.
• Rest-lnject-lmage: The patient rests and is then injected with a radio-opaque
isotope, and a special camera called a gamma camera is then used to take
images of blood flow through the heart.
• Inject-lmage: The patient is injected with the isotope and the camera takes
images of blood flow through the heart.
Then the three screening types are as follows:
1. One Day Regular. Exercise-Monitor.
2. One-day nuclear. Rest-lnject-lmage; Exercise-Monitor; Inject-lmage.
3. Two-day nuclear: Day 1 = Exercise-Monitor; Inject-lmage. Day 2 =
Rest-lnject-lmage.
Exercise or "stress" tests are performed in a different room than imaging. After
the stress test stage of a one- or two-day nuclear screening, once clean-up is
completed, another patient can be brought into the stress room. During each stage of
the screening the patient is observed one-on-one by a licensed clinician. Thus the only
limiting physical resources are the number of stress rooms and the number of cameras.
Because each of the screening types described above can be performed on inpatients
and outpatients, there are six distinct patient classes as shown in Table 2.1. They are:
Inpatient Regular (IR); Outpatient Regular (OR); Inpatient One-Day Nuclear (UN);
Outpatient One-Day Nuclear (01N); Inpatient Two-Day Nuclear (I2N); Outpatient Two-
Day Nuclear (02N)). Table 1 indicates the sequence of resources that are required for
each screening on each day. 'C and 'S' indicate stages that require a camera or a stress
room respectively.
11
Table 2.1: The screening classes at WCMH.
Class Day 1 IR, OR UN, 01N I2N, 02N
S C-S-C S-C
NA NA C
Initial outpatient reservations are made in advance through direct consultation
with the physician's office, the patient, and the scheduler at the CDTC. Appointments will
be made only if, at the time of scheduling, there are projected to be sufficient resources
to handle the various steps of the screening. Therefore initial scheduling of outpatients is
considered to be exogenous to the decision process. If it is determined, before an
outpatient arrives at the hospital, that the reservation cannot be honored, the patient or
doctor's office will be notified and the appointment rescheduled. On the other hand,
since inpatients are already in the hospital there is no need for external communication.
They can simply be rescheduled to a later period in the same day or perhaps to the
following day. Of course these decisions come with costs (see Section 2.4.2). More
significantly it is imperative that the decision model itself is able to verify that the
rescheduled beginning time (or resuming time in the case of two-day nuclear
screenings) is resource feasible.
2.3.1 The State of the Hospital
Since the primary motivation to prioritize inpatient screenings is to avoid patient flow
bottlenecks, the evolving state of the hospital in terms of the number of available beds
on the specialized inpatient units must be considered. A hospital is capable of providing
a number of different patient care services, e.g. cardiology, obstetrics, critical care,
neurosurgery, etc. A small community hospital may provide 1 5 - 2 0 different services,
while an academic medical center could easily provide more than 100 services. The
inpatient units are specialized in a manner that enables them to provide care to patients
12
in need of one or more of these services. A neonatal intensive care unit is an example of
a unit specialized to support a single service. In contrast, a general medical/surgical floor
can support several services. Often more than one unit can support a given service. For
example, in a large hospital there are typically several units that can provide care to a
patient admitted with hyperglycemia, a potentially deadly complication of diabetes.
Some of these services, e.g. cardiology, often require the patient to be on a
telemetry monitor in order to continuously monitor heart rhythm and rate. In this problem
setting, inpatients in need of cardiac screening directly impact the availability of beds
that are capable of supporting services that require telemetry monitoring. However, since
the inpatient units can potentially support more than one service, the decision to accept
an inpatient request for a screening can impact the flow of patients in need of services
that do not require telemetry. For example, consider an inpatient unit that can provide
services to cardiology patients (who require telemetry monitoring) and general medical
patients (who do not require telemetry and can use any type of bed). Assume the unit is
full, but has one patient who can be discharged after a cardiac screening. Once that
patient is discharged, the hospital now has the capacity to admit another cardiology
patient or another medical patient.
The state of the hospital is therefore defined as the number of beds available to
provide care to patients in need of each service. The state evolves over time as a
function of random arrivals and the exogenous decisions of bed managers and
physicians regarding which floors to assign to new patients, random departures (patients
discharged from the hospital), and decisions made by the CDTC. The probability
distributions of the random arrival and departure of patients needing these different
services are easily estimated from historical data.
13
2.4 An Overview of the Markov Decision Process
The problem can be modeled as a finite-horizon, discrete-time, Markov decision process
(MDP). Here we give an overview of the basic decisions, rewards, and costs since they
are needed in order to motivate the snapshot model of the following section. Further
details of the MDP can be found in the next section. Time is partitioned into fixed-length
one-hour time intervals. At the beginning of a period, the state of the process is
observed and a decision is made. Immediate costs and rewards are incurred based on
the state and the decision. As indicated earlier we follow Green et al. (2006) in
maximizing social welfare. That is, the function to be maximized adds the hospital's
expected profit and subtracts the inconvenience costs to the patients who are
rescheduled.
2.4.1 Decisions
The basic decisions to be made for each time period within a given day are:
• The number of each type of screening (IR, OR, UN, 01N, I2N, 02N at WCMH)
to initiate;
• The number of each type of two-day screening (I2N, 02N at WCMH) to resume
on their second day;
• The rescheduled day and time of each type of screening that was scheduled to
begin but was not initiated;
• The rescheduled time in the current day to resume each type of two-day
screening that was scheduled to resume but was not resumed.
2.4.2 Rewards to the hospital
Deterministic rewards to the CDTC are obtained when an outpatient's screening is
realized. These can be monetized based on the fee structure for such screenings.
Positive expected rewards accrue to the hospital based on the DRGs and their
14
corresponding fee structures of arriving inpatients. On the other hand negative expected
rewards to the CDTC are based on the loss of revenue from outpatients who balk after
being rescheduled.
2.4.3 Costs to patients
Both inpatients and outpatients incur inconvenience costs if their screenings are
delayed. How to monetize these is a subtle and flexible decision for the user of the
system. In our simulations we have followed Green et al. (2006) and based these on the
expected hourly wages of a typical patient.
2.5 Details of the MDP
One-day tests collect rewards when started, since the model constraints ensure that
they must finish, while two-day tests collect rewards when resumed. The transition
probabilities for subsequent states are also functions of the initial state and the decision.
2.5.1 Notation
The following notation is used in the MDP model (for some we include their realizations
at WCMH in parentheses):
Parameters
m The number of time periods in a workday. (In the WCMH model, m = 10.)
r The set of resource types consumed by the CDTC, ({camera (c), stress
room (s)}).
p{ The number of each resource, (e.g., pc = 2; ps = 1 indicates that the
hospital has two cameras and one stress room).
Z The set of healthcare services the hospital provides.
Zc c z The set of services that require patients to be on cardiac monitoring.
15
Zu The set of services that can be accommodated by inpatient unit u.
Uz The set of inpatient units that can accommodate service z.
W The set of services impacted by the decision to start or resume an
inpatient screening. A service z is an element of V if one of the following
conditions hold:
(1) zezc
(2){uue[/z}nzc*0
Q The set of all screening classes, ({IR, ..., 02N}).
Qin The set of classes of inpatient screenings, ({IR, UN, I2N}).
qout The set of classes of outpatient screenings, ({OR, 01N, 02N}).
Ql £ Q The set of classes with one-day protocols, ({IR, UN, OR, 01N}).
Q2 £ Q The set of classes with two-day protocols, ({I2N, 02N}).
p[ The number of first day phases in a class i protocol, (e.g., pT 02N = 2).
pf The number of second day phases for class i e Q2.
a?:{ ~ (1. ifthe/t/lfirstday phase of class i uses resource 1 (0, otherwise
a?'? = (1, if the;'tflsecond day phase of class i 6 Q2 uses resource 1 (0, otherwise
T - {1,...,T}: the index set of time periods, where period t is the current
period.
yv(/c) = k + (m-k)modm: the index of the last time period in the day that
includes time k 6 T.
at The reward for testing a patient of class i.
n z The expected reward for providing service z to a newly arrived patient into
the hospital.
16
pin The cost of delaying the scheduled first day start or second day
resumption of an inpatient screening by one period within a day.
pout -rne cost of delaying the scheduled first day start or second day
resumption of an outpatient screening by one period within a day.
ybed The expected opportunity cost (due to the inability to admit a newly arrived
patient) of making an inpatient wait overnight.
Yin The deterministic cost to the hospital of keeping an inpatient an additional
night (because they leave right after screening) in the hospital.
yout t n e expected cost, based on the probability of balking, of making an
outpatient wait an additional day before beginning a screening.
Decision Variables
At any time t, we make the decision to commit to a test by initiating or resuming it in the
current time period. Once a test is initiated or resumed, the necessary resources are
reserved for all time periods needed for the phases in the remainder of the current day.
When a two-day test is initiated, the second day resources are not committed until the
following day. This allows for the possibility that the final stage of the two-day nuclear
test could be performed at any time on the following day.
yf The number of class i 6 Q screenings to initiate at time t.
yf The number of class i G Q2 screenings to resume in their second days at
time t.
xf The number of class i e Q screenings currently scheduled to be initiated IK
at time t, "intraday" rescheduled for time k e [t + 1, ...,N(t) - p{ + 1} in
the current day.
17
x?k The number of class i e Q2 screenings currently scheduled to be
resumed at time t, intraday rescheduled for time fc e {t + 1 N(t)-
v{ +1}.
xf0 The number of class i e Q screenings currently scheduled to be initiated
at time t, that are instead "extraday rescheduled", i.e., not rescheduled
for any time k e [t + 1, ...,N(t) -p[ + l } . Note that patients returning for
the second day of a two-day nuclear screening cannot be extraday
rescheduled.
State Variables
wf the number of class i G Q screenings scheduled to start at time k.
w?k The number of class i e Q2 screenings scheduled to resume at time k.
ol The number of uncommitted resources -6 available at time k today, where
resources become committed from the decisions yf and yf.
bz the total surplus of available beds on units in Uz.
L' = f « » 4. „ °< ",l* + ""'-"•• • » n^ber of newly arrived patients in (-(A6Z + bz), otherwise J r
need of service z, that are diverted to a different hospital due to lack of bed
availability (the bbz are random variables defined below).
L°ut = A,(0-Pf
k=t
the total number of rescheduled class i e Qout patients that choose not to
return (the Ad[k and Adf0 are also defined below).
18
Random Variables
AdL The number of class i e Q°ut screenings rescheduled to start at time k e IK
{t + 1,..../V(t) - p{ + 1} that choose not to return.
Ad/' The number of class extraday rescheduled i e Qout screenings that choose
not to return.
AA£ The number of arrivals of patients in need of service z to inpatient unitu e Uz.
AS? The number of departures of patients in need of service z from inpatient unit
u E Uz.
Abz The change in the surplus of available beds on units in Uz (the change
happens during time t, i.e. entering time t +1). Abz is a function of AA" and
A5" and is used for notational convenience. The number of arrivals and the
number of departures are independent between services and each other.
Hence,
!P(Abz)= £ ^P(AA|-A5zy) uei/z zezu
&wf The number of new test requests to start class i screenings at time k.
2.5.2 Process State
The process state (5) depends on the number of patients waiting to have tests started,
the number of patients waiting to have tests finished, uncommitted numbers of resources
at each time period, and the number of available inpatient and ED beds. When a
decision is made to begin a test, the resources needed to complete the test are
committed to that test in the appropriate time periods.
19
2.5.3 Constraints
Feasible decisions at time t satisfy the following:
w(t)-Pf+i (2.1)
fe=t+i
w(t)-Pf+i (2.2)
*?+ Z fc=t+l
s = W?t V i G Q
Btfyf + otfy;) ieQ
< oi+j_x V ; E { I yv(t)-t}and^er (2.3)
Constraints (2.1) ensure that all screenings scheduled to begin at the current
time f are either initiated or rescheduled. Constraints (2.2) perform the same function for
the second day, except that extraday rescheduling is not an option because, once
started, the two-day nuclear stress tests must be completed by the end of the second
day. Constraints (2.3) guarantee that resource capacities are not exceeded at any period
in the current day.
2.5.4 Stage Reward
At state S, once a feasible decision D ••= (yf,x[0,x[k,y?,x?k) has been made there are
immediate benefits and costs that yield a net reward of R(S,D).
When t mod m * 0:
R(S,D)= h-h-h
where
iEQin ieQ'
N(t)-p{+l
h = pout £ £ x / + £ a.Lout
itQOUt k=t+l iEQout
20
N(t)-pf + l
iEQin k=t+l ZEZ
When t mod m = 0:
K(S,D)= h-h-h
where
f3=Y in Y x{0+Y^Lz
iBQin ZEZ
The reward for providing cardiac screening tests are captured in fx. The cost of
rescheduling outpatients to a different time period within the current day plus the cost of
losing the outpatients that choose to leave and have the service provided elsewhere are
expressed in f2 and /4. From a practical standpoint, the possibility of an outpatient
deciding to have the service provided elsewhere is only a risk when the decision is made
on whether or not to reschedule the initiation of the screening. For outpatients returning
for the second day of a two-day nuclear screening, even if the appointment is
rescheduled, it is not realistic that the patient would leave and start the entire screening
process again with a different provider. The cost of requiring inpatients to wait until a
later period in the day plus the expected cost of potential loss of inpatients due to
overcrowding, are found in /3 and f5. The determination of stage reward when
tmodm = 0 differs from those when tmodm * 0, since the waiting costs associated
with an overnight delay are higher than for those for a single time period within the
current day.
21
2.5.5 State Transition
Let S be the current state, D the chosen decision array, and S the state after arrivals and
departures occur. S is updated as follows:
Whent <N(t):
®fk ~ Wik+Awik + Xik-Mik
vv,> = wA. + xt Hk Hk T Aifc
**> " oh,-Yjtffy[ + alfyf) ieQ
rbz + Abz + Lz,
bz = \b7 + Ab7 + I *'+ Z yi ieQlnnQ1 iEQinnQ2
t = t + 1
Lz = 0
lout = o
When t = N(t),
®tk
K
t
=
=
=
wlk+AwL
bz + Abz + Lz
t + 1
Vi, vk = t + l,...,N(t)
vi, v/c = t + i, ...,yv(t)
V; e { 0 . . . . , t f ( t ) - t } ,
fe r
v z e zyy v z e ¥
V i e Q out
V/c = t + 1, ...,N(t)
Vz £ Z
The state transitions from 5 to 5 with probability
Ps,s(D) = Y\p(Aw[k) Y\ HO fl y « ) FK f[^ ieo J ieoout ieoout \-zez J \-zez I ieQ J [ i e Q 0 U t J Lie<20ut
We make the reasonable assumption that demands for screening classes and time slots
within classes are mutually independent, since demand arises from multiple independent
22
sources. Similarly, we assume that the probability that an outpatient who was
rescheduled decides not to return, is independent of both the screening class and the
time slot. Additionally, the net changes in the number of available beds of the various
services are assumed mutually independent.
2.5.6 Objective Function
Let Vt(S) be the maximum expected reward of a T stage problem that begins in state S,
and D be the set of feasible decisions that can be made. S is the state that results from
beginning in state S and taking action D e D and then random variables are realized.
The objective function is
Vt(S) = max\R(S,D) + £ Ps,§(D)Vt+1(S) , t < T
The "curse of dimensionality" becomes apparent when examining the dimension
of the state space. The state variable bz can range from having no available beds to
every bed capable of accommodating service z being open. Let bz be the total number
beds in Uz plus one (i.e., the cardinality of the range for bz). Within a single time period,
then, we will have a dimension on the order of X\z€Zbz. For example, a hospital with 20
services and a maximum capacity of 20 for each service results in a dimension of 212 0
for the state variable bz. Even before considering the other state variables, it is apparent
that this model becomes intractable quickly and motivates the desire for another
technique.
2.6 A DSS Based on a Multi-commodity Flow Snapshot Model (MFSM)
For any realistic problem instance, the MDP described above is too large to solve in
reasonable time (see Section 2.5). In particular, WCMH wanted to make allocation
23
decisions in an online context in less than 10 minutes. Therefore, we introduce a model
based on a current "snapshot" of the state of the hospital, prior to each decision point
with the stochastic elements represented by the expected profits (positive or negative)
associated with the various decisions. The problem is modeled via a dynamic maximum
profit multi-commodity flow formulation. This approach is both flexible and robust,
making it applicable to the various configurations of patient and test-protocol types that
may be found in practically any CDTC or similar center. The snapshot includes the
number of available beds on the inpatient units and in the ED. This information is
combined with the current CDTC schedule, any outstanding or new requests for cardiac
screenings, and patients currently in the screening process.
An integer multi-commodity time-space network flow model (MFSM) is then
constructed, where each test request is a commodity. Each node in the network
represents a point in time and a physical location. An arc between two nodes represents
a possible step in the process flow for that particular test request. Profits are associated
only with arcs that represent waiting (i.e., the decision to reschedule a patient) and arcs
that represent the initiation or resumption of an outpatient screening. The positive profits
associated with initiating outpatient tests, and the negative profits associated with
making patients wait, are deterministic. In contrast, the negative profits associated with
the opportunity cost of not testing inpatients, are based on expectations of new inpatient
arrivals in the future. Similarly, for outpatients, they are based on the expected loss from
balking.
The stochastic aspect of MFSM is captured by dynamically calculating the profits
on the arcs. Since the underlying structure of the network does not change dramatically
between time periods, updating the network is more efficient than rebuilding it at each
decision epoch. Therefore at each decision point the network is updated using the new
24
information (i.e., nodes and arcs are pruned or added and arc profits are adjusted
accordingly).
2.6.1 Notation
The following notation is used in the formulation of MFSM:
s The source node
t The sink (terminal) node
i,j Node indices
k Test index
K The set of test requests
V The node set
A The arc set
Vc The set of camera nodes
Vs The set of stress nodes
Vw The set of "waiting" nodes
y+co = 0':ay)e^) V~(0 = {j:(j,QeA}
Af+ The set of arcs leaving camera node i, i.e., {(£,;') \i e Vc, j £ K+(£)}
Af+ The set of arcs leaving stress node i, i.e., {(£,;') \i e Vs, j e V+(i)}
A?+ The set of arcs leaving wait node i, i.e., {(£,;') \i e Vw, j e V+(i)}
C The number of available imaging cameras
S The number of available stress rooms
zijk The flow over arc (ij) for test k
vUk The expected profit obtained by sending a single unit of flow over the arc
(i,j) for test k
25
Deterministic positive profit comes from the arcs associated with screening an
outpatient. That is, arcs (ij) where i e Vw and ;' e (Vc u Vs). On the other hand,
negative profit is assigned to the (rescheduling) arcs (i,y) where i e {s} u Vw, and
j £ yw in a future period. The specific derivation of these costs relies on the notation of
Section 2.5 and is shown immediately below in Section 2.6.2.
2.6.2 Derivation of Inpatient Delay Costs under MFSM
The negative profit consists of the sum of the deterministic inconvenience cost to the
patient and the expected lost opportunity associated with being unable to admit a new
inpatient. The opportunity cost relates only to the decision to delay an inpatient
screening request. It is a function of the profit associated with admitting a new inpatient
and the probability that, in the future time period, the number of available beds will be
less than the number of new inpatients. Inpatient arrival rates and the associated profits
are easily estimated from historical data. We used an aggregated Poisson distribution
with parameter Az to describe the arrival distribution for each service. To compute Az
using historical admission data, we aggregated the arrival rate for each service over all
units capable of treating that type of patient. Hence, Az = Zueuz<*z- Kolmogorov-Smirnov
tests at the a = 0.05 level showed that there was a strong goodness-of-fit between the
aggregated Poisson distributions and the historical patient arrivals.
The expected cost of delaying an inpatient is then calculated as£z6Z£2z:P(Az >
bz), where Az is the aggregated arrival rate for patients of service z as described above.
The P(-) term represents the probability that the number of patients that need a bed is
greater than the number of currently available beds. The values for ilz were estimated
using WCMH's billing records.
26
2.6.3 Formulation
Figure 2.1 illustrates the multi-commodity network flow formulation. It shows a simple
example consisting of a single day, three time slot scenario, and two patient classes (UN
and OR). A multi-commodity time-space network is constructed for two test requests
from the OR patient class (Test 1 and Test 3) and a single test request for a patient of
class UN (Test 2). Each node in the network represents a point in space and time, e.g.
the nodes labeled 2, 4, and 6 represent the stress test phase of the screening at a
particular time. The arc (1, 2) represents the possible decision to begin Test 1 during the
first time slot. The arc (1, 3) represents the alternate decision of rescheduling initiation of
Test 1 to the next time slot, etc.
Figure 2.1: An example network representation of a one-day, three-time-slot problem instance. For this miniature and illustrative example, all feasible arcs are shown, indicating the possible sequences of arriving, waiting, and being tested that three patients may experience.
Time Time Time Slot 1 Slot 2 Slot 3
OR Patient Class Waiting Room
UN Patient Class Waiting Room
Stress Room
Camera
• Test 2
* Test 3
27
• Testl
The formulation of the multi-commodity network flow problem is
vijkzijk max V Y„..,7,., (2.4) (i,j)EA k€K
subject to
2 « * " I *(*-<> VI6K\{,.t},*6ir (2.6) y6K+(i) 76V-(i)
V _ _ V 7 - - 1 for i = t, fc E ff (2.7)
I I
fee* ((,y)exf+
zi;'k — ^
V t £ Vs (2.8)
V i e r (2.9)
2Ufc £{0,1} V (i,j)eA,k EK (2.10)
The constraint sets (2.5) - (2.7) ensure the conservation of flow for each node.
The bundle constraints (2.8) - (2.9) restrict the flow out of the stress and camera nodes
to their respective capacities.
2.6.4 Size of the Model
The size of the problem is a function of the current CDTC schedule and the number of
new test requests. For example, for a 10-day time horizon, each with 10 time slots, of
which 80% of the slots are booked, a WCMH instance involving three new UN requests
on the first day results in 3,515 constraints and 6,214 variables. If the initial schedule is
90% filled, the number of constraints increases to 3,948, and the number of variables
increases to 6,928.
28
The model (2.4) - (2.10) is an integer program, and we have verified that its
underlying constraint matrix is not totally unimodular. However, as we discuss in Section
2.7.2, our experiments have shown empirically that this problem is quite easy to solve to
optimality.
2.7 Experimental Analysis
MFSM was evaluated in two ways. First, for small, computationally tractable problems,
we conducted an ex-post analysis to compare it to the MDP. In the second test we
compared it against WCMH's current rule of always prioritizing outpatients and reserving
occasional slots on the schedule to accommodate inpatients should the need arise.
2.7.1 The MFSM versus the MDP
A comparison of MFSM against the MDP required an ex-post analysis because, after the
first instance where the two methods make different decisions, the state space and
transition probabilities change, and we cannot expect them to yield directly comparable
solutions. This makes it impossible to compare performance based on, say the
percentage of time the same decision is made. Rather, after the conclusion of each
complete scenario, we calculate the value of the decisions made by each method using
the same cost structure.
Prior to determining the MDP optimal policy, several simplifying steps were taken
to reduce the size of the state space. This focus on "small" problems was done only for
the sake of comparing the MDP to MFSM. Without such simplifications the MDP quickly
became intractable, providing no basis for comparison; in any practical setting, MFSM
would not be limited to such a simplified, aggregate state space. To give an idea of the
difficulty of implementing the MDP, finding the optimal policy for this small instance took
over one hour. Additionally, the memory utilized during the policy generation was over
29
one gigabyte. The simplified problem setting included only the three most common
patient classes found at WCMH (UN, OR, and 02N), a single camera, a single stress
test room, and a time horizon of two days (i.e., 20 stages). We defined three classes of
unit specialization, cardiac, general medical/surgical, and emergency services. For ease
of exposition we will use bc = cardiac, bg = general, be = emergency services.
Additionally, the state of the hospital was consolidated and limited to four possibilities:
1. State V. bc= 3,bg = be= 2,
2. State 2: bc = bg = be = 1,
3. State 3: bc = bg = be =0,
4. State 4: bc = bg = be = -1.
We further restricted the number of patients of each class requesting a test to at
most two during each time period, and solved the MDP using backward recursion. The
optimal policy was then used in the simulation of the MDP methodology. Using arrival
patterns similar to the ones at WCMH, we generated four sets of new request arrivals for
the time horizon. We examined arrival rates of an average of two, four, six, and eight
new requests over the two-day time horizon. This equates to an average of one, two,
three, and four new requests per day. Two thousand unique requests were generated for
each of these four levels of arrival. The MDP simulation and the MFSM simulation both
used the same arrival sets. Three different initial CDTC schedules were simulated:
empty, 50% full (i.e., 10 screenings already scheduled during the 20 period horizon), and
80% full.
For the analysis between the two approaches, we calculate the percentage
"performance gap" for a single scenario as (om-on)/om, where om is the ex-post objective
value of the MDP and on is the ex-post objective value of the MFSM. In Table 2.2 the
mean percentage performance gap, along with its corresponding 95% confidence
30
Table 2.2: A comparison between the MDP and the MFSM. All numbers are rounded to two significant digits to the right of the decimal.
• > • • -.r- . v - 1 - •'..•
Empty Empty Empty Empty Half Full Half Full Half Full Half Full 80% Full 80% Full 80% Full 80% Full
^ : , ; f e j : r'^f>;iko 1 per day 2 per day 3 per day 4 per day 1 per day 2 per day 3 per day 4 per day 1 per day 2 per day 3 per day 4 per day
• ri&\\>- " : :
0.00% 0.07% 0.10% 0.62% 0.19% 0.76% 1.44% 0.76% 3.21% 7.89% 13.88% 17.99%
(0.00%, 0.00%) (-0.04%, 0.19%) (-0.07%, 0.26%) (0.23%, 1.01%) (0.11%, 0.27%) (0.50%, 1.01%) (0.53%, 2.34%) (-1.97%, 3.49%) (2.90%, 3.52%) (7.39%, 8.38%)
(11.41%, 16.35%) (12.93%, 23.04%)
interval, are reported for each of the twelve design points. Overall, as expected, there is
a small bias in favor of the MDP but MFSM performs well. Also, note that the confidence
intervals for four of the twelve design points indicate that there is no significant difference
between the two approaches (i.e., the ones that contain zero in the 95% confidence
interval). Otherwise, the values for the mean percentage performance gaps indicate that
the ex-post objective value of MFSM closely approximates that of the MDP. The higher
performance gap rates from the last two design points are a result of having more
patients requesting screenings than this experimental CDTC can accommodate within
the time horizon. We expect the MDP to outperform MFSM in these cases, because the
generated MDP policy explored all of the possibilities, while MFSM takes a snapshot
prior to each decision and uses the data to generate expected profits for the various
decisions.
On average, when computationally tractable, we expect the MDP to outperform
the MFSM heuristic. The difference between the two techniques is in the complexity of
31
how future events are anticipated. In any MDP, current decisions are made under the
assumption that future decisions will also be made optimally, but this comes with the
huge computational burden of planning decisions for all possible contingencies or
possible future states. The MFSM heuristic, on the other hand, ignores the impact of
future decisions, and instead simply projects average costs for current decisions, based
on probabilities of future events and their costs. Simply put, the MFSM ignores the fact
that we will respond to mitigate the effects of unexpected or low-probability events,
whether good or bad, while the MDP does not.
Thus for this small-scale test, we do find instances for which the MDP does a
better job of anticipating future events, consequently outperforming the MFSM heuristic.
As seen in Table 2.2, the MFSM heuristic performs very well compared to the MDP until
we get into a full schedule situation and there is an unexpectedly high volume of
inpatient add-on arrivals. It should be noted though, that for this unnaturally small
experiment (which was made small-scale enough to implement the MDP) the impact of
one suboptimal patient routing decision has a large impact on the system as a
percentage. But as we will see in the next section, where we compare MFSM to the
hospital's prior policy, we were able to verify through a larger-scale simulation the that
the MFSM network approach was robust, making vastly improved decisions in situations
where the schedule was full, arrivals were heavy, and the problem instance was of a
real-world size.
2.7.2 The MFSM versus the Current Approach
To compare MFSM with the hospital's current approach we simulated the CDTC's
operations for two-week planning periods. Under the current approach some time slots
are reserved, but when a conflict between an outpatient and an inpatient occurs, the
policy is to always prioritize the outpatient. We therefore refer to WCMH's current policy
32
as "POP" for prioritize outpatients. The 10 working days in the two-week planning period
are divided into 10 one-hour time slots. In order to gain additional insights, we vary the
proportion of CDTC capacity allocated to testing outpatients from 60% to 100% as
shown in Table 2.3 for a total of nine design points. (Prior to our study, WCMH typically
reserved 90% of the schedule for outpatients).
The simulation contained a common set of 200 independent "sequences" of
inpatient test requests. Each sequence of inpatient test requests was created by
randomly generating between zero and three inpatient requests ("add-ons") using a
discrete uniform distribution for each of the 10 days in the planning horizon. This
common set of inpatient test requests was used for each of the nine design points. For
the simulations we did not consider the possibility of rescheduling outpatients for another
day. So, while the outpatients can be delayed, if they cannot be tested on the day they
were originally scheduled we assume that the patient decides to be tested at another
facility and the hospital loses the revenue. This assumption gives a conservative
estimate of the impact of MFSM on the biweekly revenue change because, in reality, a
significant percentage (likely a majority) of these patients would be expected to still
choose to be tested at WCMH. Finally, we do not consider cancellations from the
outpatient schedule since the percentage of "no-shows" at the WCMH CDTC is less than
1%. We analyzed three performance metrics: difference in revenue, the percentage of
the outpatients and inpatients requests served, and the number of additional nights
rescheduled inpatients must remain in the hospital.
We used lp_solve v5.5 to solve all problem instances of MFSM. Problems were
first solved by relaxing the integrality constraints on the decision variables. We verified
that underlying constraint matrix is in fact not totally unimodular, but nonetheless the
structure of the objective function in this setting tends to result in optimal solutions that
are integer valued. In the rare occasions that fractional solutions were obtained (6.5% of
33
the instances during this experiment) lp_solve's branch-and-bound routine quickly
provided an integer solution with the same objective function value after only a single
branching. Thus, in our experience, each MFSM problem instance required a solution of
at most two linear programs, with any linear program instance solving in less than one
second using lp_solve. The average solution time was 0.6 seconds.
2.7.3 Results
Tables 2.3 and 2.4 show the average biweekly increase in revenue due to using MFSM
instead of POP and the 95% confidence interval for revenue increase. Since WCMH
typically allocates 90% of the CDTC capacity to outpatient testing and since the inpatient
census is typically elevated for the six month October-March period, we extrapolate an
expected revenue gain during this period of approximately $150,000 ($11,437.13 * 13).
The other half of the year MFSM could help them realize an additional $40,000 in
revenue gains (reduce the outpatient schedule to 80% corresponding to $3,142.73 * 13),
giving WCMH a yearly expected revenue gain of $190,000.
Table 2.3: Biweekly revenue increase when adopting MFSM. For all design points, the revenue gains were statistically significant using paired f-tests.
60% $1,296.41 80% $3,142.72 85% $5,509.32 87% $8,167.28
90% $11,437.13
92% $14,824.84 95% $18,943.79
8 97% $23,142.20
100% $28,108.32
34
Table 2.4: 95% confidence intervals for biweeklv revenue aain.
ISstelF^:! 1
2
3 4
5 6
'•:i,y.7. ;Vy . \
v-S->t':'^ V . 9 ,•"•""
@@; t̂etflfe'. 60%
80%
85% 87%
90%
92%
95%
97%
100%
J^teMBBi, $1,152.38
$2,623.67
$4,500.76
$6,802.22
$9,642.63 $12,695.79
$16,354.68 $20,115.97
$24,548.83
Igfi^KH $1,440.43
$3,661.77
$6,517.88
$9,532.34
$13,231.63
$16,953.90
$21,532.89 $26,168.42
$31,667.82
Table 2.5 compares MFSM to the POP approach in terms of the service provided
to inpatients and outpatients. Service level is calculated as the average percentage of
inpatient and outpatient requests that are honored during the two-week scheduling
period. The graphical illustration of service levels shown in Figures 2.2(a) and 2.2(b)
provides some interesting observations. By using MFSM, we are able to significantly
improve the inpatient service level with only a small decrease in the outpatient service
Table 2.5: A comparison of service quality.
1
2
3
• • • 4 - : - ' • • ' : . •
5
6
•7,-v-!;..:.;...
& :#B. 9
60%
80%
85%
87%
90%
92%
95%
97%
100%
100%
100%
100%
100%
100%
100%
100%
100%
100%
i mtm v?
100%
97.03%
86.86%
79.58% 66.58%
53.90%
33.89%
19.93%
0.00%
•um&mssxism
0 0.31
0.85
1.34
2.03
2.67
3.62
4.45
5.57
biases : 100%
98.72%
96.81%
95.75% 94.20%
92.83%
90.74%
89.34%
87.45%
100%
99.29%
97.36%
96.54%
95.02%
93.26%
90.62%
88.55%
85.38%
0 0.14
0.25
0.30
0.32
0.35
0.37
0.40
0.42
35
Figure 2.2: A comparison of service levels.
Outpatient Service Level
100% <m% so%
1 70% S 60% 8 50% '£ 40%
•S 30% 20% 10% 0%
• POP
MFSM
60% 80% 8S% 87%. 00% 92% 95% 97% 100%
Percentage of Capacity for Scheduled Outpatients
In patient Service Level
100% 30% 80%
E 70% 5 60% g 50%
i 40% X 30%
70% 10% 0%
• POP
MfSM
l l . (a) Outpatient Service Level
f>0% 80% 85% 87% 90% 92% 95% 97%, 100%
Percentage of Capacity for Scheduled Outpatients
(b) Inpatient Service Level
level. For example, when the CDTC allocates 90% of its testing capacity to outpatients
the POP approach provides an inpatient service level of 66.58% and an outpatient
service level of 100%. In contrast, MFSM provides an inpatient service level of 95.02%
and an outpatient service level of 94.20%.
We also investigate the additional number of nights inpatients have to spend in
the hospital. These results are in Table 2.5. Finally, Figure 2.3 compares the average
number of inpatient bed-days saved using MFSM and in place of the POP policy.
The difference in the reduction of inpatient bed-days was statistically significant
using paired Mests, in all design points except the first design point where only 60% of
the CDTC capacity was dedicated to outpatient tests. The result of reserving so much
capacity for inpatient tests is that even the POP approach is able to serve all requests
resulting in no avoidable additional inpatient nights. For all other design points MFSM
outperforms POP.
36
Figure 2.3: Comparison of the additional inpatient nights.
Average Additional Inpatient Nights
N ig
h
re e
A d d iti
o i
4
3
2 ••
1
n
• POP
MFSM
60% 80% 85% 87% 90% 92% 95% 97% 100%
Percentage of Capacity for Scheduled Outpatients
v.... The graphs in Figure 2.2 can also help the CDTC make strategic decisions
concerning their desired service levels under MFSM. For instance, if the hospital
administration decides to maintain a 90% outpatient service level then Figure 2.2(a)
implies that the hospital should fill 95% of CDTC capacity with outpatient tests. This
capacity allocation would also correspond to a service level of approximately 90% for
inpatients.
2.8 Conclusions
Real-time allocation of cardiac diagnostic screening time slots represents a complex
online decision-making problem of whether to screen inpatients or outpatients when
conflicts arise. The decision can impact the availability of beds on the inpatient units and
the financial performance of the hospital. In this paper we model the decision problem
facing the CDTC as a discrete time, finite horizon MDP. We also conclude that solving
the MDP is computationally intractable given the time constraints of the decision makers,
motivating the development of a decision support system based on a dynamic multi-
37
commodity network flow model. The proposed solution method is flexible and robust,
making it applicable to a CDTC at almost any hospital. The technique was tested with a
local partner hospital and showed that it is possible to achieve significant improvements
in quality of service to inpatients and overall hospital revenue, with only minor decreases
in outpatient service levels.
By considering the impact of inpatient census and ED congestion on patient flow,
we provide hospitals with the ability to dynamically prioritize inpatient and outpatient
requests for cardiac diagnostic testing services. The result is the ability to provide high
service levels to both populations, help ensure the availability of inpatient beds to the
individuals that need them, and a net improvement in financial performance. Future
research should be conducted to determine the optimal location of reserved time slots in
the scheduling horizon, in order to improve inpatient service levels while increasing
utilization. In addition, the capacity of the CDTC itself could be dynamically altered
through the use of overtime and modifications to the contracts with the cardiologists that
provide medical coverage. Dynamic capacity management can enable the CDTC to
achieve higher levels of utilization and service, and enable the hospital to achieve
improved patient flow, quality of care, and financial performance.
38
CHAPTER 3 - Mass-Casualty Triage: Distribution of
Victims to Multiple Hospitals
3.1. Introduction
Effective disaster management has gained the attention of the public due to numerous
recent natural catastrophes. However, in order to succeed at achieving effective disaster
management, the definition of the term "disaster" must first be agreed upon. Surprisingly,
experts in the disaster management field disagree on an exact definition of the term.
However, several common elements appear in most definitions. This dissertation utilizes
the definition of a mass casualty incident (MCI) as defined by the World Health
Organization and we use the terms disaster and MCI interchangeably throughout this
work. Their definition of a mass casualty incident (MCI) is "an incident which generates
more patients at one time than locally available resources can manage using routine
procedures" (WHO, 2007). Examples of MCI include disasters due to natural hazards
(e.g., floods, earthquakes, etc.) or manmade disasters such as a bioterrorism attack.
Effective response to a disaster, whether man-made or natural, should follow a
cyclical, four-step process. These steps include:
1. Preparedness
2. Response
3. Recovery
4. Mitigation
Preparedness refers to the actions taken before the disaster to allow effective response.
Response refers to the emergency actions taken just before, during, and just after the
onset of a disaster to reduce casualties, damage, and disruption. The actions taken after
39
a disaster to repair, rebuild, and restore community life to normalcy is the recovery
stage. Mitigation refers to the actions taken both after one disaster and before another to
reduce the physical impacts of hazards on a community.
We focus on the critical time period immediately following the onset of a MCI.
The typical casualty flow in disasters is shown in Figure 3.1. During the third phase in
Figure 3.1, triage, the medical evaluation and treatment must be rapid and accurate in
identifying the critically injured victims who require immediate life-saving care. The focus
of care must be on the population as a whole rather than the individual in order to
provide the greatest good for the greatest number (Frykberg, 2005). Triage plays a vital
role during this process. It is the process of assigning treatment and evacuation priorities
to victims of an MCI and is used to guide the allocation of the limited healthcare
resources; in effect, it determines who will be transported to the hospital. (For more
details on the principles and practice of triage see Frykberg (2005)).
Once the casualties have been triaged, the orderly distribution of victims from the
scene among different hospitals must take place. However, managing the patient load
during a disaster presents a major challenge to hospitals and disaster response
managers. Patient allocation decisions are typically made by the so-called "Incident
Command" based on resource availability, situation details (mechanism of injury, etc.),
and triage data. Figure 3.2 illustrates an example of the distribution of triaged victims to
hospitals during a disaster.
Initially the goal is to move all victims out of the immediate vicinity of the disaster
scene to a casualty collection area. The location of the casualty collection area should
be situated away from the disaster scene due to the dangers it can pose to both health
Figure 3.1: The typical flow of casualties during a disaster.
Rescue Decontamination Triage Evacuation
40
care providers and the survivors (Frykberg, 2002). Patients sent to the casualty
collection area are triaged, treated for immediately life threatening injuries, and
transported to area hospitals.
In practice, managing patient allocation across a group of hospitals is
challenging. Often the nearest hospitals, typically the major trauma centers, are quickly
overloaded. There are at least three reasons why the nearest hospitals become
overwhelmed. First, critically injured patients require medical intervention as soon as
possible. In many cases this necessitates that these patients go to the nearest hospital.
Second, for most disasters, the majority of the casualties are not critical. These so-called
"walking wounded" find their way on foot or by car to the nearest hospitals. Third,
decisions regarding the allocation of patients are complex and response managers do
not have the ability to dedicate large amounts of resources to that task.
Examples of hospital overload can be seen in the wake of the September 11,
2001 terrorist attacks. In that case the New York Downtown Hospital was so inundated
with casualties that it was forced to turn its cafeteria into a makeshift second emergency
room to treat more than 1200 patients (Landro, 2006). Likewise, in the aftermath of the
1994 aircraft crash at Pope Air Force Base in North Carolina, the closest hospital was
Figure 3.2: An example of victim distribution to a group of area hospitals during a disaster response.
41
inundated with a large number of casualties. Most of these patients were subsequently
sent to other area hospitals.
In order to avoid this geographic effect, a systematic method of distribution of
casualties from the casualty collection area among available hospitals should occur
according to injury severity and urgency, with the added goal of avoiding overloading
any single facility. One suggested approach within the urban setting is "leap-frogging" of
hospitals by sequential loads of transported casualties (Jacobs et al., 1983). The
problem with this type of "round-robin" allocation scheme is that it is often implemented
in a static fashion (e.g., every third casualty is routed to a specific hospital), whereas all
disasters are dynamic in nature. As new information concerning the disaster and the
supporting hospitals becomes available, the allocation mechanism should adjust to this
new information.
Most papers talk only about "doing the most good for the most number of people"
without actually precisely defining the objective. The two prevailing methods are START
(simple triage and rapid treatment) and SALT (sort, assess, life-saving interventions,
treatment and/or transport). Recent work has looked at the effectiveness of START
(Kahn et al., 2009) and compared the two methodologies (Cone et al., 2009; Lemer et
al., 2008). However, neither of these methods precisely defines what is meant by "the
most good for the most people". The one exception is the Sacco Triage Method (STM).
As described in the STM work (Sacco et al., 2005), the limitations of the current triage
methods, such as START, motivated their work.
The rest of this chapter is organized as follows. We provide a brief literature
review, highlighting papers relevant to decision making during the response stage of
disaster management in the next section. Section 3.3 describes the resource
constrained triage problem, highlights a current model, and describes our proposed
enhanced model to solving the problem. Section 3.4 provides the explicit formulation of
42
our enhanced model. We compare our model to several heuristics currently used in the
field in Section 3.5. In the final section we conclude by discussing the managerial and
policy implications of using our enhanced model.
3.2. Literature Review
There has been a great deal of research devoted to the general topic of disaster
response. Not surprisingly, the bulk of this research has been conducted by researchers
in the fields of emergency medicine, emergency response, and public policy. While a
great deal of useful clinical and applied knowledge has been obtained from these
studies, this literature review is focused more narrowly on disaster response literature
dealing with decision support systems and stemming from the operations management
literature.
Due to the inherent uncertainty surrounding the resources required to respond to
a specific mass casualty event, a great deal of research has been focused on issues
specific to certain types of disasters such as earthquakes (Barbarosoglu and Arda, 2004,
Fiedrich et al., 2000, Ozdamar et al., 2004), floods (Shim et al., 2002), industrial
accidents (Jianshe et al., 1994, Mould, 2001, Kourniotis et al., 2001), nuclear events
(Papamichail and French, 1999, Hobeika et al., 1994, French, 1996}, and terrorism
(Reshetin and Regens, 2003, Wright et al., 2006).
There has also been a great deal of research focused on supporting decision
making and interactive methods to aid response and relief efforts. Barbarosoglu et al.
(2002) developed an interactive approach for the hierarchical analysis of helicopter
logistics for disaster relief operations. Brown and Vassiliou (1993) studied real-time
allocation and assignment of response units in the context of disaster relief, allowing
human intervention in the underlying optimization and simulation processes. The
integration of simulation and geographic information systems to develop spatial decision
43
support tools to aid in recovery operations was studied by de Silva and Eglese (2000).
Other research is again specific to the problems that arise in the context of certain types
of disasters. For example, Lee et al. (2006a, b) develop a decision support system that
evaluates facility layout and staffing allocations for emergency large-scale dispensing of
pharmaceuticals following a disease outbreak. For a more exhaustive list of OR/MS
research in disaster operations management see Altay and Green (2006).
Response logistics has also seen a fair amount of research. These types of
decisions include, among other things, transportation and evacuation after a mass
casualty event occurs. The article by Barbarosoglu et al. (2002), which explores
helicopter logistics, falls into this category. The work by Jotshi et al. (2009) investigates
dispatching and routing emergency vehicles with the support of data fusion during the
aftermath of an earthquake. Christie and Levary (1998) model the transportation of the
critically injured patients to hospitals as a multi-server queuing system and show that the
length of time that patients wait for an ambulance increases rapidly with the increase in
the inter-arrival rate of patients to the initial treatment/waiting area.
This diversity among disaster management research prompted the recent
position paper by Brandeau et al. (2009). In it, the authors provide six recommendations
for the modeling of health sector disaster responses.
3.3. Resource-Constrained Triage
The very definition of an MCI implies that we dealing in a resource-constrained
environment. In particular, the major resources we consider are availability of
ambulances and the capacity for the various severities of casualties at each of the
hospitals. For simplicity, we refer to the hospital capacity as "beds" even though there
are numerous inter-related resources that go into treating and stabilizing a victim of an
MCI.
44
The main decisions we need to make are which patient class to send from the
casualty collection area to a hospital and which specific hospital each patient should be
transported to. Our goal is to maximize the expected number of survivors with respect to
restrictions on the timing and availability of ambulances needed for transport and the
treatment resources available at the hospitals.
In order to calculate the expected number of survivors from an MCI, we need
both an estimate of the survival probability and how that survival probability deteriorates
over time. One way to accomplish this is to assign each victim a "score" that is indicative
of his current condition and follows some deterioration rate. As victims wait to be
transported, their condition deteriorates. In general, a victim's initial severity and type of
injury directly influences his deterioration rate.
The time horizon for the decision-making environment starts after the immediate
onset of the MCI and ends when all of the victims have been transported. The type of
disaster dictates the length of the time horizon. We will focus on a disaster that results in
blunt trauma victims, but the overall process and methodology can be used for any type
of disaster.
3.3.1 Brief introduction to STM
The one paper that attempts to work through the resource-constrained problem is the
Sacco paper (Sacco et al., 2005). Their main motivation is to provide a model and
process that addresses how to specifically articulate the oft-cited objective of "do the
most good for the most people." One of their main contributions is the recommendation
to use a "score", which can be computed based on a victim's severity and is predictive of
his survival probability, as the basis to quantify the objective. They suggest using the
"RPM" score, which includes the respiratory rate, pulse rate, and motor response. They
show that by using RPM scores and associated survival probabilities for blunt injured
45
victims that the STM model performs better than the traditional START method used for
triage in all of their simulations, with marked improvements as the resources to transport
were tightened.
3.3.2 Limitations of STM
Overall, the STM can be viewed as a "macro" model. For example, the model assumes
up front that we know how many resources for transporting victims for each time period
will be available. However, if multiple hospitals are involved, the time it takes to evacuate
casualties will depend on which transport resources are sent to which hospitals in each
period. These decisions influence the number of transport resources available in each
period because some ambulances may still be in transit due to traveling to a more
distant hospital. The STM approach would work if only one hospital exists and the
ambulances will be back by next decision epoch.
The decisions from the STM model are not specific; they simply identify the
number of victims in each class to treat. We are interested in sending patients to multiple
hospitals and want to prescribe where to send each victim of each class at each
decision period.
We are not only looking at score-based treatment estimates (as indicated as one
of the extensions in STM paper), but rather looking at score-based treatment estimates
related to the timing of the decision. We explicitly consider available hospital capacity
when making evacuation decisions.
3.3.3 Motivational Example
We now provide a small, illustrative example, motivating the use of a different approach.
Assume there are five different score levels, two hospitals where one is "local" and the
46
Table 3.1: Victim distribution and survival probabilities.
other is "remote", and we are interested in a time horizon consisting of six time periods.
The one-way travel distance to the local hospital is a single time period, whereas it takes
two time periods to reach the remote hospital from the casualty collection area. Table
3.1 shows the distribution of the victims and their associated survival probabilities as
time progresses. Table 3.2 shows the care times for each score level. For this small
example, we assume both hospitals have the same technology and can treat any of the
score levels in the same amount of time and that the initial capacity for each score level
at both hospitals is five.
Suppose there are five ambulances available at the beginning of the time horizon
and that they are all dedicated to transporting victims from this MCI for the duration of
the time horizon. Recall that the STM model assumes that all of the ambulances will be
back by the next decision point and a single hospital. Let's assume that the STM model
is interested in sending victims to the local hospital because it is closer. Running the
STM model on this data, we get the following result shown in Table 3.3 with an objective
function of 13.37 expected survivors. However, we immediately notice infeasibilities in
this solution. Because we are sending patients to the local hospital, where the one-way
travel time is one time period, the ambulances we send in the first time period will not be
available again until the third time period. The highlighted cells in Table 3.3 illustrate the
ambulance infeasibilities encountered in this small example. We may also confront
47
Table 3.2: Care times for each score level for the time horizon.
1 2 • • • •
v &•••••:
' 4 ::*••
.,-:. - 5 , , i ;
4 M.^tus M^^^.^.^Sft^Jl^feafe^vs-M. .*^***. >>._!, a««~*
6 5 4 3 3
H. , » »
7 6 4 4 3
,.. &**. >&, .. *„-4
8 6 5 4 4
; * < 2 t 9 7 5 5 4
.® '" 10 7 6 5 5
. .„ *}& S
11 8 6 6 5
capacity infeasibilities with the STM model since it does not explicitly handle treatment
resources. The final type of infeasibility that may occur with the STM model is that it may
send more victims of a particular score level than are awaiting transport at the casualty
collection area.
There are many different ways that we could fix the infeasibilities encountered
with the STM model. For this small example, we suggest first eliminating the ambulance
infeasibilities since these are the easiest to recognize and fix. As a second step, we then
fix the capacity infeasibilities by first reducing the current number of victims to transport
to stay within the capacity for each score level. Then add victims (up until we run out of
ambulances) to be transported in the order of the most severe injury to the least severe
(low score first), ensuring capacity constraints are not violated. Finally, we need to verify
that we do not send more victims of each score level than we have waiting at the
casualty collection area.
48
Table 3.3: Decisions from the STM model.
tp<?p||tFW
1 2 3 4 5
»;T-Olŝ |̂ S<Ni.
' *f" *̂ Wlv#r>>''̂ SMfffliijdW^ '*•*?' ' f ^ ' f ^ . ' j • '
0 4 0 0 1
• f t >
;> " <§ 0 5 0 0 0
&$. .
V ' £r," 0 5 0 0 0
l 5-
; - £ > 0 0 4 0 1
. \ * .:
§ ' 0 0 1 4 0
'3 .,
• ' t 0 0 5 0 0
.. -& .
0 14 10 4 2
5? . . ^ T . u . *,k&..,,
Table 3.4 shows how we fixed the ambulance infeasibilities; simply remove the
decisions that were made in the second, fourth, and sixth time periods since ambulances
are in transit back from the local hospital. However, now notice that a violation of the
capacity constraint on the score level two occurs when we try to send five victims with
that score level during time period three. Utilizing the procedure outlined above, we
decrease the number of victims with score level two to a single patient (bringing the
hospital to capacity for that score level). Because the current practice of evacuation of
victims emphasizes sending the worst cases first, the four remaining ambulances are
used to send four victims with score level 1 to the hospital. (As we show in Section 3.5.2,
this may not be the best alternative, but it is what is currently being used in practice.) In
this example, we do not run into the last type of infeasibility. The resulting decisions are
shown in Table 3.5, with highlighted cells indicating where we fixed infeasibilities. The
resulting objective function is reduced to a total 5.975 expected survivors.
By not taking into account decision epochs that are shorter than the round-trip
distance to the hospital, the STM model introduces ambulance infeasibilities. Also, when
the treatment resources are not considered, the STM model may result in additional
infeasibilities that are of practical significance.
Figure 3.3 shows the possible percentage of improvement in the objective
function if we utilize the enhanced model rather than the STM model. The graph on the
49
Table 3.4: The decisions after fixing the ambulance infeasibilities.
1 2 3 4 5
Total Sent
^#«^S»'ii«
0 4 0 0 1 5
• * > | p ^ 0 0 0 0 0 0
V >> W ^ V
0 5 0 0 0 5
S , i $ 4 »
0 0 0 0 0 0
•\*HsK' 0 0 1 4 0 s
: * - § ^ 0 0 0 0 0 0
Q .i-.-9:.: ..:/•':
1 4 1
15
Table 3.5: The final decisions after fixing all of the infeasibilities.
left shows the improvement as we hold the capacity at each hospital constant at six beds
per score level and vary the number of ambulances that are used for transporting victims
during the MCI. Both implementations of the STM model are shown. The other graph
shows how our enhanced model improves as the hospital capacity for each score level
varies and we only have six ambulances at our disposal.
3.3.4 Our Enhanced Model
We add three major enhancements to the STM model.
1. The time needed to treat/process a victim at a hospital varies depending on the
severity of the injury to the victim. Care times for a particular victim will increase
as his score decreases (gets worse).
2. We explicitly consider the treatment capacities of the area hospitals.
3. The availability of ambulances for transporting victims depends upon where and
when it was sent.
50
Figure 3.3: Improvement over the STM model when using the enhanced model and varying either the hospital capacity or the ambulance capacity.
80.0%
70.0% ;
60.0% ;..
I 50.0% j
S 40.0% : ex
£ 30.0% '
20.0%
10.0% i
0.0% •
4
ImprovementOverSTM Model as Ambulance Capacity Changes
— — Local
Remote
5 6 7 8
Ambulance Capacity, ft
em
m p
ro ve
m
55
90.0% !
80.0% '
50.0% |
40.0% \
30.0%
20.0% [ ,
10.0%
0.0'<s
5
ImprovementOverSTM Model as Hospital
Loc.ll
Remote
Hospital Capacity, ft beds
The first enhancement should seem logical. As a victim waits at the casualty
collection area for transport, his condition will worsen (according to some deterioration
rate). As his condition worsens, more resources and time will generally be needed to
stabilize the patient once he arrives at the hospital. While the STM model does consider
deterioration rates of patients, it uses them exclusively for calculating the appropriate
objective function coefficients.
We consider the treatment capacities for each score at each hospital explicitly in
our model. The decision methodology must be cognizant of the ability of the hospitals to
be able to accept and process victims at a score-based level. In particular, we ensure
that a hospital has the capacity to accept a patient with his updated score level before
sending the patient to that hospital. Recall that a patient's condition deteriorates over
time, meaning that he will switch score levels as time progresses. We make sure that the
hospital can accept a patient with the updated score at the decision point rather than a
patient with the initial score. The STM model does not include treatment resources.
The final enhancement we add considers how available ambulances affect our
decisions and vice versa. Because we consider more than a single hospital, an
ambulance that travels to the "remote" hospital will be unavailable longer than one sent
51
to the "local" hospital. Resources for transportation of victims are handled differently in
the STM model. There, they simply assume a fixed number of ambulances and that all of
the vehicles return by the next decision epoch. (They use 30-minute decision epochs.)
3.4. Formulation of the Resource-Constrained Triage Problem
3.4.1 Notation
Data
S Set of victim scores (e.g., RPM values)
s Score index
H Set of area hospitals
h Hospital index
T The set of time periods
t Time period index
Dh One-way trip distance (in time periods) to hospital h from the casualty collection
area
C£ The amount of care time needed to "process" a victim of score s at hospital h
A The initial number of ambulances available
Bl The initial number of "beds" available at hospital h for score s
Pt s The probability of survival of a victim with score s at time r
Vs The number of victims of score s awaiting transport from the casualty collection
to one of the hospitals
Variables
xlt Number of patients with score s to send to hospital h during time period f
52
at The number of ambulances available at time period t
bfo The number of patients with score s that can be cared for at hospital h during
time period f (e.g., the number of resources such as beds available for victim
score s at hospital h during time period r)
Note that the "real" decision variables are xht and that the variables at and bht
are the "auxiliary" variables. For example, we will know the values of ax and bhx since
these represent the initial state.
3.4.2 Formulation
m a x ZZZ P t S ^ f
hen ter ses
(3.1)
subject to
heH
*ht < &ht V/iGtf, V t G 7 \ V s G 5 (3.3)
ax=A (3.4)
V t > 1 G T (3.5) at — ° t - i — y xM-\ + y xM-2x.Dh
hSH heH
b s h l = Bs
h V h G H, V s G S (3.6)
Ht = Kt-r ~ Xht-i + <t-{Dh+cH) VhEH, V t > 1 G 7, V s G 5 (3.7)
££*/[t<r' VSG5 (3'8)
7l6H teT
Xs ht G Z + V f t £ W , V t £ T , V S 6 5 (3.9)
53
The objective function expressed in (3.1) indicates that we are maximizing the number of
expected survivals from the MCI. Constraint (3.2) enforces the restriction that we cannot
send more patients to hospitals than we have ambulances. We ensure that we do not
violate the capacity of the hospitals via constraint set (3.3). Constraints (3.4) and (3.6)
simply set the initial values of the "state". The availability of ambulances at each time
period beyond the initial period is defined by (3.5). Similarly, (3.7) defines the capacity
availability of the hospitals during each time period beyond the first one. It should be
noted that the way (3.7) is formulated gives the implicit assumption that a bed is
reserved at the hospital once the decision is made to send a victim there. This is
expressed in the final term and the second subscript on the x variable: t - {Dh + Cft).
The Dh expresses the time it takes the ambulance to get to the hospital and is added to
the care time at that hospital, forcing the bed to remain "in use" during that time.
Constraint (3.8) ensures that we do not send more victims of a particular score to the
hospitals than actually exist. Finally, integer restrictions are expressed in (3.9).
3.4.3 A Small Example
We consider a small instance of the problem as an illustrative example to aid in
understanding the enhanced model. Using the same data from example from Section
3.3.3, we are interested in determining how the decisions from the proposed model differ
from those generated by the STM model. First, we expect several changes because we
are considering two hospitals, a local and a remote. Also, we avoid capacity
infeasibilities because we explicitly model these in our model.
Solving this small problem using Excel's built in Solver functionality, the decisions
shown in Table 3.6 are obtained. The table is expanded to show how many victims of
each score are sent to either the local ('L') or the remote ('R') hospital. We see that
having a second hospital as an option allows us to send more victims of score level 3
54
Table 3.6: The results using the proposed enhanced model.
J;-/ „\"
1 .': '2"
3 ; • - . • • > • : # : • : • • • ' • " •
5 Total Sent
• • • iV ^.' V Bcosf̂ tMfel ,* mmmf, f^'
0 0 3 0 2 5
' • $ >
0 0 0 0 0 0
i-AW^M'lk<M' -«. ' Q*\
0 0 0 0 0 0
• ts« 0 0 0 0 0 0
:' (T 0 0 1 4 0 5
: ® - 0 0 0 0 0 0
i R ^ - w M ^ l i ^ "§? "4.-"
0 0 0 0 0 0
, e r 0 0 0 0 0 0
nr 0 0 1 0 0 1
m 0 0 4 0 0 4
>• ' '•
- v ; . ^ . ' , . & » : 0 0 0 0 0 0
.m ' 0 0 0 0 0 0
? € « •^en^S&ly ^%
Q
W:':' • , . - ; § • •
•.••':;4Vf
2 11
' ' ^ ^ 0 0
• : T ' 4
•M : p ;.:,-
0 4
than with the STM model. Here, we send five, the capacity, to the local hospital and then
send four to the remote hospital. The corresponding objective function value is 9.067
expected survivors. This equates to a 51.7% increase over the STM model's objective
function value.
3.4.4 Enhanced Model's Performance vs. STM Model
The small example from before provides some motivation of the potential benefits to
using the enhanced model. We were also interested in getting a better picture of how it
may react when the number of available ambulances and the capacity levels of the
hospitals change. We varied the number of available ambulances from four to eight and
let the capacity levels for each score level range from five to seven. We then compared
the enhanced model's objective function to the STM model when it sent all victims to the
local hospital and when it sent victims to only the remote hospital. Over these 15
comparisons (five levels of ambulances and three levels of capacity at the hospitals), the
enhanced model provides an expected increase in the expected number of survivors.
The overall average improvement of the enhanced model over the STM model that uses
only the local hospital was 36.5% and the increase over the STM remote model was
69.0%.
55
Figure 3.4: Model reactions to varying ambulances and hospital capacity.
Objective Function as Ambulance Capacity 12 Increases
;- 10
S 6 i. •
Ambulance Capacity, H
10.00
9.50
9.00
8.50
3.00
7.S0
7.00
6.50
6.00
5.50
5.00
Objective Function as Hospital Capacity Increases
• • •
— • - Local
•••*••• Remote
• Enhanced
— — — — — — ——
Hospital Capacity, tf beds
Figure 3.4 provides a look at how the models react when holding one variable
constant and varying the level of the second. The graph on the left fixes the capacity of
the hospitals to six and varies the number of ambulances. The rightmost graph holds the
number of available ambulances constant at five and varies the hospitals' capacities.
3.5. Experiments
We are interested in determining how well our enhanced model does in comparison to
several heuristics that are currently used in real life. Three of the most common "rule of
thumb" approaches used are:
1. Closest first - send as many victims as possible to the closest hospital first.
When that hospital reaches capacity, send victims to the next closest hospital.
2. Furthest first - send as many victims as possible to the furthest hospital first.
When that hospital reaches capacity, send victims to the next furthest hospital.
3. Cyclical - send victims in a round-robin fashion to the area hospitals.
The logic behind using the closest first heuristic is to transport those victims
which we have decided to treat to a hospital as quickly as possible. The furthest first
heuristic is also used at times. It is known that victims deteriorate over time. If a large
56
number of serious casualties is expected, then the first ones found are sent to the
furthest hospital because the expectation is that they can survive the transport. After
some time passes the next batch of casualties will have deteriorated and the "reserved"
capacity at the closer hospital is a benefit because those victims could not survive the
wait and an extended travel time. Another part of the thinking is that many of the
"walking wounded" will make their own way to the closest hospital. By sending victims to
hospitals further away, we avoid inundating the closest hospital with both the transported
victims and those who find their own way there. The final common heuristic considers
sending victims in an alternating fashion to the different area hospitals. The benefit of
this heuristic is that we provide some "breathing room" for each hospital. That is, it
essentially assumes that no victims will get effective care if a hospital is blitzed beyond
its ability to respond.
Each of these heuristics can be implemented several ways. The most common
implementation in use is to transport the most critical, non-expectant victims first.
Intuitively, this seems like the best approach. However, as we show below, this may not
result in the best outcome if we measure the total expected number of survivors. In
direct contrast, another implementation possibility is to transport the least critical victims
first, leaving the most severely injured patients for transportation later. Obviously, these
are two extremes and various other schemes could be thought of.
The cyclical heuristic has even more flexibility in terms of implementation
possibilities. When alternating between different area hospitals, how many victims are
sent to each hospital before switching the destination to a different hospital is one way to
vary how the heuristic in implemented. For example, we could send one victim to the first
hospital, the next victim to the second hospital, etc. Alternatively, we could send the first
two victims to the first hospital, the next two victims to the second hospital, and so on.
Again, there exist many different ways to implement the cyclical heuristic.
57
3.5.1 Experimental Setup
For all of our experiments we use the following setup. We follow Sacco et al. (2005) in
many regards. For victim scores, we utilize the "RPM" score, which includes the
respiratory rate, pulse rate, and motor response (Sacco and Champion, 1983). The
RPM score is the sum of coded values as shown in Table 3.7. Additionally, we assume
we are dealing with blunt trauma victims and utilize both the survival probabilities and
the victim deterioration rates derived by Sacco et al. (2005). The survival probabilities
are shown in Table 3.8 and the deterioration rates based on 30-minute intervals are
shown in Table 3.9.
One of the enhancements of our model over the STM is that care time is directly
related to the current status (i.e., RPM score) of the victim. The care times we use in our
experiments is shown in Table 8. The care time is measured in minutes. It represents an
estimate of how long it would take to stabilize a patient with the associated score, thus
freeing the resources to be used on another victim. For simplicity and exposition
purposes, we refer to these resources simply as "beds" even though there are many
other intertwined resources involved.
We consider a fixed time horizon of six hours after the onset of a MCI. We
assume that victims are gathered at a common collection area from which emergency
medical vehicles depart to transport the victims to a hospital. We also assume that both
the number of victims and their associated distribution is known at the beginning of the
Table 3.7: RPM Coded Values.
<p(^l}^fal0\ ',,2 Respiratory Rate
Pulse Rate
Motor Response
4 ' 0
0
None
" 4 [ ' ,11- "> ' -< 1 - 9
1 -40 Extends/flexes from pain
r •-§. ' 36+
4 1 - 6 0 Withdraws from pain
• < ; « § ' • *
2 5 - 3 5
121 + Localizes pain
• a"* ; : ' 1 0 - 2 4
61 -120 Obeys commands
Source: Sacco et al. (2005).
58
Table 3.8: Probability survival estimates for RPM values and the associated care time.
BIB'̂ IiS1"" : . - ^ t r " • • • - • •
:...:''•: : - ' : 1 - ; - - s : > - v ; - •
• - • ' • • • • 2 '• ••
' 3 : A
5 6
. . / ; ' 7 • • . . :
•"':. 8
v • * • • - & t : : •••••-
; TO :
11 12
,vv^^^Q^®^fflS^''" 0.052 0.089 0.15 0.23 0.35 0.49 0.63 0.75 0.84 0.90 0.94 0.97 0.98
:mmmmmmmm]
180 170 160 150 140 130 120 110 90 60 50 40 30
Sacco et al. (2005) is the source of first two columns
time horizon. We consider three different distribution patterns of victims that are awaiting
transport: a uniform distribution, a left-skewed distribution, and a right-skewed
distribution. See Figure 3.5 for a pictorial representation of the victim distributions. Each
distribution considers the same number of overall victims: 130.
We also consider transit time between each hospital. We assume that the transit
time is deterministic, known, and the same for both the outbound and inbound directions.
Four different levels for the number of ambulances are examined. We consider two
hospitals: a "local" hospital and a "remote" one. Both hospitals have the same
technology resources and are able to treat all of the victims. Additionally, both hospitals
treat the victims in the same amount of time. We vary each of the hospitals capacity and
the distance of the remote hospital from the casualty collection area. Table 3.10 shows
the different levels we consider. Altogether we look at 384 different design settings. The
models were solved using the Gurobi solver.
59
Table 3.9: Deterioration of RPM scores in 30-minute time intervals.
0 1 2 3 4 5 6 7 8 9 10 11 12
: WT
• fe 0 0 0 1 2 3 4 6 8 9 10 11 12
*U ' '" *»
0 0 0 0 1 2 3 5 7 8 9 11 12
w ' A >
0 0 0 0 0 1 2 4 6 8 9 10 11
>
, * . v S
0 0 0 0 0 0 1 3 5 7 8 10 11
"* r 1i?Kaia'tote#a 'A. W ,NJL © I*
0 0 0 0 0 0 0 2 4 6 8 9 10
0 0 0 0 0 0 0 1 3 5 7 8 10
>•,#,.* 0 0 0 0 0 0 0 0 2 4 6 8 10
m... 0 0 0 0 0 0 0 0 1 3 6 7 10
'I1 i " - j !
k »«L.'. 0 0 0 0 0 0 0 0 0 2 5 7 9
, y -v i * •
m., 0 0 0 0 0 0 0 0 0 1 5 6 9
'
'm 0 0 0 0 0 0 0 0 0 0 4 6 8
y • , % «
, t ^ : 0 0 0 0 0 0 0 0 0 0 4 5 8
Adapted from Sacco, et al. (2005)
Figure 3.5: Distribution used during experiments.
Uniform Distribution
3 10 11 12
Left-Skewed Distribution
Right-Skewed Distribution
5 5 7 8 9 10 11 12
RPM Score
60
Table 3.10: Parameter settings for the experiments.
^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ H "• ' . ' • •;&; ." ' Initial available ambulances Distribution of victims Local hospital capacity for each RPM score Remote hospital capacity for each RPM score One-way distance to local hospital (minutes) One-way distance to remote hospital (minutes)
5, 10, 15,20 Uniform, left-skewed, right-skewed
2, 4, 6, 8 2, 4, 6, 8
5 8,20
3.5.2 Low Score First Not Always Best Approach
The logic behind using the closest first heuristic is to get critically injured victims
qualifying for transport needed care as quickly as possible. This approach seems
intuitive: see if we can provide the most badly injured victims help in time for them
survive. However, when we quantify the probability of survival and want to maximize the
overall number of expected survivors, the low-score-first heuristic may fall short of its
intended outcome. Instead, this objective may indicate that we should use a high-score-
first approach when making transportation decisions. Using our experimental setting
described above, we explore which circumstances lead to use of the low-score-first
heuristic versus the high-score-first approach.
In our experimental design victims with RPM scores of 0 and 1 would most likely
be declared "expectant" and tagged with a black tag (in START language). Therefore, in
reality we would not consider these victims when making transportation decisions. This
allows us to consider victims with RPM scores of 2 and higher. We look at the closest-
first heuristic, comparing a low-score-first implementation to a high-score-first one. We
vary the lowest score considered from 2 to 6. The results showing the percentage of the
time the low-score-first is at least as good as the high-score-first, in terms of the
objective function, are displayed in Table 10. Percentages for each of the individual
61
Figure 3.11: Results of testing a low-score-first implementation versus a high-score-first implementation.
3 'est Score nsidered
2 3 4 5 6
> ' - • ! < * • . » :
58.6% 79.7% 83.6% 93.8% 98.4%
52.3% 59.4% 72.7% 74.2% 93.0%
^^^ff i '»V fg»: 11.7% 36.7% 76.6% 88.3% 99.2%
wJJSKT 40.9% 58.6% 77.6% 85.4% 96.9%
distributions are based off of the 128 runs for that particular distribution. The overall
percentage (last column) is over all 384 runs.
From Table 3.11, we see that whether a low-score-first implementation is better
depends on both the underlying distribution of victims and which RPM score values we
consider. For example, when considering an RPM score of 2 as the lowest score with a
right-skewed distribution, only 11.7% of the runs showed a better objective function
using a low-score-first approach instead of a high-score-first one.
3.5.3 Comparison of Enhanced Model to Heuristics
We wish to see how well our enhanced model does against the commonly used
heuristics. As discussed earlier, each heuristic can be implemented in numerous ways.
Following the discussion above, we utilize a high-score-first implementation of each
heuristic, giving a conservative estimate of the improvement of our model over each
heuristic. For the cyclical heuristic, we provide three specific implementations: switch
hospitals after each patient, switch to a different hospital after two patients have been
sent to the current hospital in row, and go in round-robin fashion in groups of three. We
also implement a simplistic random heuristic for comparison purposes. For each time
period, if an ambulance is available, the random heuristic first picks the hospital with a
simple flip of a fair coin. Based on destination hospital, it then randomly picks one of the
62
Figure 3.6: Average improvement over the commonly used heuristics when using the enhanced model.
^ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ 60.00% •••: _. ,
Average Improvement 50.00%
40.00%
30.00%
20.00%
10.00%
0.00% .1111 Closest First Furthest Cyelical-1 Cyelical-2 Cyclical-3 Random
First
awaiting scores for which the destination hospital has capacity. The results showing
average improvement of our model over each heuristic are shown in Figure 3.6.
We are also interested in how the enhanced model compares to the various
heuristics as other attributes about the problem vary. First, we hold the capacity at each
hospital constant at six beds and vary the number of available ambulances. The results
are depicted in Figure 3.7 on the left. Next, we fix the number of available ambulances to
15, the capacity at the remote hospital to six beds, and vary the capacity at the local
hospital. The results are shown on the right in Figure 3.7. Only the closest-first and
cyclical-3 heuristics are shown in order to avoid cluttered graphs. The cyclical-3 heuristic
is very representative of the other two cyclical heuristics.
63
Figure 3.7: Improvement over heuristics when using the enhanced model and varying
50.00% ;
45.00%
40.00%
35.00% ;
s I 25.00* a- 2o.oo«
15.00*
10.00%
5.001,
0.00%
0
Average Improvement as Ambulances Vary
\ \ \ Closest First
\ Cvdical-3
\
\ ^ _ _ ^ ~ ~
5 10 15 20 25
Number of Ambulances
.... ,̂
i \
\.
35.00%
30.00%
25.00%
20.00%
15.00%
10.00%
5.00%
0.00%
t
Average Improvement as Local Capacity Varies \
\ \ \ \
Closest First
_^--~ . ^ _ <*<*«'-*
2 4 6 8 10
Local Capacity
3.6. Managerial Implications and Conclusion
The current triage methods of START and SALT do not provide specifics on how to
"provide the most good to the most people." The STM model filled this gap by
quantifying survival probabilities of victims and suggesting that use of overall number of
expected survivors as a quantifiable objective to use in order to capture the idea of "most
good to most people." However, the STM model is a macro model. We have suggested
a micro model that provides three major enhancements to the STM model. We have
shown that our enhanced model makes more sense, especially when we consider
multiple hospitals to which victims may be sent during an MCI. We have provided an
experimental design setting in which we are able to test various in-use heuristics. In
particular, we showed that the effectiveness of using a low-score-first implementation of
the closest-first heuristic depends upon the underlying victim distribution and which RPM
score value we start with. We also investigated how well our enhanced model performs
in comparison to several heuristics that are currently used in real life. We tested our
model against the heuristics that used a high-score-first implementation. A high-score-
first approach is not currently the way most evacuation heuristics are implemented in
64
practice, but comparing the enhanced model to the heuristics implemented in this
manner provides more conservative estimates of the improvement measures. The
enhanced model outperforms all of the heuristics on the order of 10% - 30% on average.
As the number of available ambulances varies but the hospital capacities remain
constant, we saw that the improvement of our model over the closest-first heuristic
stayed relatively stable at approximately 10%. Not surprisingly, as more ambulances are
added, the round-robin heuristics perform better. However, our model performs better
and it appears that the improvement gap between models starts to level off. We also
investigated keeping the number of available ambulances and the remote hospital's
capacity constant, while increasing the capacity at the local hospital. This experiment
shows the performance gap between our enhanced model and the heuristics as
remaining steady after having reached a capacity of four beds at the local hospital.
65
CHAPTER 4 - Investigating the Distribution of Victims to
Multiple Hospitals in a Dynamic and Stochastic Setting
4.1. Introduction
The previous chapter dealt with determining where, and in which order, to send victims
of a mass casualty incident (MCI) to various area hospitals in a deterministic setting.
While the model developed therein is useful, it is worthwhile to also investigate this
problem in a dynamic and stochastic setting. The situation surrounding an MCI will
unfold over time and inherently involves elements for which much of the data is
uncertain. For example, the travel times of the vehicles used for transport will likely vary
based on several exogenous influencing factors.
One of the issues with utilizing a deterministic model is that once a data
parameter deviates from its assumed value, "the script" no longer applies and
improvisation must be used in the decision making process. For example, consider the
possibility where the round-trip transportation time takes 30 minutes longer (e.g., due to
damaged or heavily congested roads) than the value used when solving a deterministic
model. How does this situation affect the well-thought out plans? What other alternative
courses of action are feasible to help compensate for this unplanned event?
One way to combat this issue is to model the problem as dynamic and
stochastic. That is, routing and allocation decisions are made sequentially, explicitly
taking into account the variability of the various input data elements. One modeling
technique to accomplish this task is stochastic dynamic programming (SDP). SDP
66
provides a formalized and eloquent way of describing sequential decision problems.
However, solving sequential decision problems can be another matter entirely.
One of the issues to be cognizant of is how the problem is modeled and defined.
Generally, when a sequential decision problem is formally described, the "state" of the
system must have an explicit form. The state definition must fully capture all the
information needed to make a decision, as well as the information needed to describe
how the system evolves over time. This may mean that a large number of attributes,
each of which may be multi-dimensional, are needed to describe the state. The more
descriptive and detailed the state variable, the more difficult the problem is to solve. In
fact, the explosion of the state space is the oft-cited "curse of dimensionality" that often
makes SDPs intractable for real-sized problems.
A major contribution of this work is that a novel solution methodology and
framework that combines SDP with Monte Carlo simulation as a way to overcome some
of these limitations in a practical setting is proposed. There are two end goals. First, an
easy-to-implement policy table that provides recommended decisions, even in the face
of uncertain data elements for the distribution of victims of an MCI to the surrounding,
appropriate healthcare providers, should be provided. In other words, this is a real
problem that requires providing practical recommendations to the decision maker that
will result in saving more lives. Second, the methodology proposed is applicable to other
settings where solving a stochastic sequential decision problem using the classical
approach is impractical.
The rest of this chapter is organized as follows. A brief review of the relevant
literature is provided first. Then, in Section 4.3, the problem of allocation and
transportation of victims from an MCI is modeled as a stochastic sequential decision
problem. The data necessary in order to capture an accurate depiction of the overall
problem is described. In Section 4.4, a new methodology, termed "scenario iteration," is
67
introduced. Its aim is overcoming some of the limitations of a typical SDP model. The
methodological framework and basic algorithm are detailed and the advantages of the
methodology are discussed. Next, in Section 4.5 the performance of the proposed
heuristic is examined through experimental analysis. In particular, a focus on the
performance of the model and on the performance of heuristic as a solution
methodology is considered. Finally, in Section 4.6, the chapter concludes and
recapitulates the main managerial insights.
4.2. Review of the Relevant Literature
For a review of the general literature on the broad field of disaster management and in
particular the literature stemming from the decision support and operations management
fields, please refer to the Section 3.2 of the dissertation. For this chapter, there are two
foci for the literature review. First, an exploration of some of the more relevant literature
from the operations management field is conducted and then the literature that is related
to the scenario iteration heuristic that is formally propose in Section 4.4 is reviewed.
One way to model the evacuation of victims of disasters that has been prevalent
in the extant literature is by using some variant of a multi-commodity flow formulation.
For example, Carolan et al. (1990) introduce the Patient Distribution System which
models the evacuation of patients from a European military conflict to U.S. hospitals over
a specified time horizon. They utilize a constant 11 commodities in a deterministic multi-
commodity network flow model, but the problem becomes quite large and more difficult
as the length of the time horizon, measured in days, extends. The study by Barbarosoglu
and Arda (2004) proposes a two-stage stochastic programming model to help plan the
transportation of medicine, food, clothing, etc. to disaster-affected areas. They, too, use
a multi-commodity formulation to describe the flow of these first-aid commodities over an
68
urban transportation network, and incorporate randomness by considering a finite set of
realizations of the random variables.
Much of the transportation literature focuses on evacuation of people for short-
notice disasters (e.g., an ensuing hurricane in the Gulf of Mexico). Examples of such
papers include Han et al. (2006) who explore the best way to assign destinations for
evacuees and Chiu and Zhen (2007) who explore a similar concept but consider
emergency response evacuation and logistic decisions within a multi-dimensional
simultaneous environment. Liu et al. (2006) propose a two-level integrated optimization
system for large-scale network evacuation planning. The top level optimization has the
goal of maximize the throughput for a mass evacuation scenario, while the second level
optimization seeks to minimize the travel and waiting time for the entire operation. For a
comprehensive review of the OR/MS research, the reader is urged to consult the article
by Altay and Green (2006).
The proposed methodology in Section 4.4 most closely resembles what is
commonly becoming known as approximate dynamic programming (ADP). ADP is a
blend of operations research methods such as dynamic programming and mathematical
programming, computer science fields such as artificial intelligence, simulation, and
statistics. This field is also sometimes known as neuro-dynamic programming or
reinforcement learning. ADP has received a large amount of interest in the recent past,
spawning, among many other things, the publication a book dedicated to the subject
(Powell 2007). The main difference between ADP and the proposed methodology is that
often the main goal an ADP is to approximate the optimal cost (objective) function. This
is done by generating one or more simulated system trajectories and associated costs
and using some form of "least squares fit" to see how good the approximated objective
function is. The approach described in this chapter is different. The interest here is in
finding the good approximations for the initially unknown transition probabilities. As
69
discussed in Section 4.4.3 once the process has converged, there will be two weapons
at our disposal: the "optimal" policy from the SDP and the ability to use the scaled-up
Monte Carlo simulation step of the algorithm to help make decisions for larger sized
problems in the field.
Simulation optimization (e.g., April 2003) is the other broad field that is
tangentially related to the scenario iteration heuristic. With simulation optimization the
goal is to find the best input parameters for a simulation. This is not the goal of the
proposed approach. Instead, good estimates of the unknown transition probability
distributions that are associated with our sequential decision problem are the desire. As
detailed in Section 4.4, the use of simulation helps accomplish this goal, rather than the
other way around.
4.3. Problem Description
The focus of this work is on the immediate time period following an MCI. In many
disaster scenarios, a casualty collection area is established outside of the immediate
vicinity of the disaster scene in order to avoid potential dangers to both the victims and
the disaster responders. Patients sent to the casualty collection area are triaged, treated
for immediately life threatening injuries, and transported to area hospitals. Figure 4.1
illustrates an example of the distribution of triaged victims to hospitals during a disaster.
Ideally, the distribution of victims to the various area hospitals should take place
in an orderly and systematic fashion. However, managing the patient load during a
disaster presents a major challenge to hospitals and disaster response managers.
Patient allocation decisions made by the so-called "Incident Command" should
incorporate information on resource availability, situation details (mechanism of injury,
etc.), and triage data. This information, however, is not static; it changes as the disaster
situation unfolds over time.
70
Figure 4.1: An example of victim distribution to a group of area hospitals during a disaster response.
Hospital
^ v ^^^w Hospital
^ ^ ^ / ^ Casualty " ^ y ^ - " - " " " " ' ^ I Hncnitai L— —'— V Collection Area J
The decisions include where a victim should be sent, which victim "class" to
send, and when to send the victim. As in the previous chapter, the overall objective is to
maximize the expected number of survivors from the MCI. The major resources on
which we have restrictions include availability of transport and the capacity level for
casualties at each of the hospitals. Hospital capacity is referred to simply as "beds" even
though there are numerous inter-related resources that go into treating and stabilizing a
victim of an MCI. Additionally, the term "ambulance" is used to mean any form of
transportation (e.g., a helicopter) that is available to help evacuate victims of the MCI to
the appropriate healthcare providers.
4.3.1 Data Elements
In the setting for this chapter, some of the data are stochastic. In particular, the transport
times and the care times are each independent random variables, and may depend on
the distance to be traveled and the severity of the injuries respectively. The care time
could also depend on which hospital a particular victim is sent to. In addition to the
decision of where to send a victim, the variability in the travel times directly influence the
availability of transport vehicles at each decision point. The variability in the care times,
which can differ with respect to both the hospital and the score, determines the capacity
71
availability at the healthcare provider's facility to take in more victims. The capacity also
depends on the number of beds, doctors and other resources the hospital may have on
a routine basis, and the surge capacity they may have during emergencies.
In order to accurately capture the system dynamics of the response to the MCI,
additional data needs to be kept track of. Instead of simply keeping track of the number
of ambulances, information on each ambulance must be retained and updated
accordingly. Relevant data on each ambulance includes
• when it became available (i.e., arrived at the casualty collection area),
• when the transport was dispatched,
• to where was the transport dispatched,
• which type of victim is it carrying, and
• the expected duration of the round-trip for this vehicle.
Also a more accurate accounting of each hospital is necessary. In particular, data
on each specific victim should be kept to allow easy calculation of the provider's
capacity availability and its current "load" or utilization at any point in time. Three of the
important data elements needed to help with these calculations include
• when did a patient arrive at the facility,
• the expected care time for the patient with that survival score in that
hospital, and
• how many resources (beds, surgeons, emergency room hours, surge
capacity, etc.) are available in each hospital.
These metrics directly influence the decisions on whether or not to send more
victims to a particular provider. For example, if a hospital has very little remaining
capacity and a victim is currently en route to the facility, then intuitively, the chance that
72
the facility will be able to effectively handle another victim in the near future is quite
small.
4.3.2 The Stochastic and Dynamic Problem
The objective we wish to maximize is the expected total number of survivors from the
MCI. A fixed time horizon, consisting of T time periods, is considered. A fixed time
horizon is consistent with this setting because the recommended decisions involve
sending injured victims immediately after the onset of an MCI and at some point in the
future resources (such as ambulances) are reallocated to causes other than the disaster
response effort.
The state of the process for a particular time period is described by the following
attributes:
• the number of victims for each score awaiting transport from the casualty
collection area to one of the surrounding hospitals,
• the set of hospitals that can handle at least some of the victims from the
MCI, and
• the set of ambulances or transport resources available.
On the surface this compact state representation might appear to be easily
solvable. However, some important historical information involving both the hospitals
and the ambulances must be kept track of in order to know when these valuable
resources become available for reuse. To know when capacity becomes free at a
provider's facility, the minimal attributes that must be monitored include when a victim
arrived, what score level he was, and his associated care time. Recall that in this setting
the care time will be a random variable, making it more difficult to accurately capture the
"release" time of the associated hospital resources. With the arrival time and an estimate
of the care time for each patient, the expected "processing" time can be calculated. This
73
allows an estimation of when the provider's resources will be freed to concentrate on
another victim. Similarly, to keep track of when a transport vehicle will return to the
casualty collection area and be able to evacuate another victim the minimal information
to keep track of includes when and to where each particular ambulance was dispatched.
The travel time of each ambulance is a random variable whose value can be estimated
by using the destination hospital and perhaps exogenous information regarding the
current traffic patterns, etc. This estimated return time then indicates when the transport
becomes reusable.
As indicated earlier, accurately capturing the problem using a SDP approach
may provide a useful description of the problem, but the size of the state space can
quickly make solving it intractable. This fact should be readily apparent from the
discussion above regarding the historical data that must be kept on each ambulance,
each victim that is transported, and each bed or resource that is used in the hospital.
Retaining this information makes the state space explode quickly. Exploring such a large
number of states makes solving even small instances of the problem prohibitive.
4.4. Scenario Iteration
The size of the fully-descriptive SDP model grows quickly making it intractable for real-
sized instances of the problem. This "curse of dimensionality" is one of the motivating
factors to find an alternative solution approach. Another, more subtle, reason to look for
an alternative approach is the fact that in this problem setting the outcome space can be
very large. That is, the random variables of travel time and care time can result in an
inordinately large number of possible realizations. Suppose, however, that it was
possible to aggregate the outcome space of the random variables in some meaningful
fashion (as is often done, perhaps implicitly instead of explicitly, in many applications).
74
The issue then changes from keeping track of history in a compact way to knowing the
transition probabilities between the various states. One way to accomplish this is to keep
track of state transitions from one period to the next. But doing this also requires keeping
track of history. Further, some compact way to determine when patients are discharged
is needed. Utilizing the concepts of waiting line theory, the proposed scenario iteration
approach keeps track of the utilization of resources at any time, rather than each
individual admit and discharge time. Then it is possible to track how the utilizations
transition from one time period to the other. But even doing this can be a challenge. For
instance, what is the best way to properly capture the transition of a hospital from one
utilization level to another level? The inability to measure the transition probabilities is a
concern in the application of distributing victims of an MCI to area hospitals. The
methodology proposed attempts to overcome both the explosion of the state space and
the inability to directly measure the transition probabilities.
The methodology developed combines the use of a SDP policy and Monte Carlo
simulation to arrive at a final decision policy. The simulation helps predict the probability
of occurrence of status of several state variables so they do not have to be explicitly
modeled in the SDP, thus reducing the size of the state space dramatically. The SDP
optimal policy table is then used in the simulation whenever decisions need to be made.
The simulation then generates updated probability transition matrices to be used in the
SDP. During the simulation, scaling is used and enables this iterative solving of the SDP
and simulation to converge to a stable policy table fairly quickly. The term "scenario
iteration" is coined for the proposed methodology and its purpose is twofold. First, a
tractable way to arrive at the transition probabilities associated with the problem is
desired. Second, the end goal is to provide the decision makers both a condensed,
easy-to-use decision-rule table and a framework to explore when different decision
policies might be necessary.
75
4.4.1 General Heuristic Algorithm
The basic steps of the scenario iteration methodology are:
Step 1. Generate the initial transition probability matrices.
Step 2. Solve the SDP, generating a decision policy.
Step 3. Run a scaled-up Monte Carlo simulation over an extended time horizon,
using the decision policy found in Step 2 to make decisions during the
simulation.
Step 4. Calculate the transition probability matrices from the Monte Carlo
simulation.
Step 5. Check to see if convergence has occurred. If so, generate the final
"optimal" SDP policy using the final transition probabilities. Otherwise, use
these new transition matrices and go to Step 2.
These steps are also depicted in the flowchart shown in Figure 4.2. Step 1 is
accomplished by running a small inline simulation over an extended time horizon. The
allocation decisions are based on an equal chance of sending a particular victim class to
each of the hospitals. These initial probability vectors are then used as input for Step 2.
The details of Steps 2 and 3, the SDP and the Monte Carlo simulation, are explained in
turn below. Step 4 uses the results from Monte Carlo simulation to calculate new
transition probabilities. A check is then performed to determine whether the process has
converged. If it has not, then the algorithm returns to Step 2 and begins again.
76
Figure 4.2: Flowchart showing the basic steps of the scenario iteration methodology.
Start
Generate Initial Transition
Probabilities using Simulation
Run the SDP
No
End W
Calculate New Transition Probabilities
using Simulation
Yes
_L Run the SDP to Generate Final
Policy Table
4.4.2 The Stochastic Dynamic Programming Model
The following notation is used to help explain the SDP.
Data
S Set of victim scores (e.g., RPM values)
5 Score index
H Set of area hospitals
h Hospital index
T The final time period
t Time period index
Sh One-way trip distance (in time periods) to hospital h from the casualty collection
area
c* The amount of care time needed to "process" / care for a victim of score s at
hospital h
A The index used to indicate we are talking about the transport / ambulance
77
vs The number of victims of score s awaiting transport from the casualty collection
to one of the healthcare provider facilities
i,j Indices for the different load groups
Ys The probability of survival of a victim with score s
ah The indicator bit of whether or not hospital h has available capacity
aA The indicator bit of whether or not an ambulance is available
ph The current load group for hospital h
pA The current load group for the ambulances
pi The probability of moving from load group /'to load groupy'for hospital h
pf- The probability of moving from load group /'to load groupy'for the ambulances
qf The probability that there will be availability at hospital h during the next time
period given that we are in load group /'this time period
qf The probability that an ambulance will be available during the next time period
given that we are in load group /' now
Variables
d% The decision to send a patient with score s to hospital h during the current time
period
Time is discretized into equal length intervals in a manner that only allows for the
decision of the routing and allocation of at most a single victim within each time period.
The decision to send a victim needs to be made only when we have the available
resources to both transport the victim and treat the victim at the healthcare provider's
78
facility. At the end of the time horizon it is assumed the only the option is to "do nothing".
At all other time periods, assuming the appropriate resources are available, the available
actions are denoted by d% for all h e H,s e S. Each decision variable is binary, with 0
meaning "do nothing," and, for example, d[ = 1 would mean "send the patient of score 1
to the local hospital."
The following attributes are used to capture the essence of the problem and
specify the state of the system. For each score class, the number of victims awaiting
transport are kept track of and denoted with vs. The next piece of information retained
concerns the availability of the main resources. Does each hospital have capacity? That
is, a single bit that tells indicates yes or no is recorded instead of using the specific
number of available beds. The notation utilized here is ah. The availability of transport
vehicles is treated similarly and aA represents whether or not an ambulance is available.
The final information incorporated into the definition of the state are the proxies for how
busy each of the resources are. The general idea is that some way to measure the
current capability (or utilization) of the hospitals and the ambulances is needed.
To accomplish the task of estimating the current capabilities of the hospitals and
the ambulances, the capability of a resource is broken into groups based on their
"loads." The load of a resource could be defined multiple ways. The definition used in
this chapter identifies the total number minutes remaining to finish processing the current
victims if no new victims were sent. For example, suppose the care time for a victim of
score 1 is 130 minutes. Suppose the current time period is the third in the time horizon
and in each of the previous two time periods, a victim of score 1 arrived at the local
hospital. If each time period is 15 minutes long, the load at the local hospital is 215
minutes. The first victim arrived at time period 1 giving a load of 130, but the current time
period is time period 3, indicating that the victim has been under care for 30 minutes.
79
This results in the first victim contributing 100 minutes to the load at the third time period.
The second victim was also a score 1 victim, indicating that his initial load is 130, but he
has been at the hospital for 15 minutes. Therefore the second victim contributes 115
minutes to the local hospital's load. Combined, the local hospital has a load of 215.
Using this definition for a load group, five load groups are used for both the
hospitals and the ambulances. Then the interest is in examining how the system
transitions between the different load groups. The load groups for the hospitals are
denoted by ph, and the load groups for the ambulances are denoted by pA.
The state of the system in time period t can be specified by (vs;a h,aA;ph,pA).
Let ft(ys',a h,aA;ph,pA') be the maximal expected number survivors from being in state
(ys; a h,aA;ph,pA) when optimal actions are taken in each time period from t to T.
The following recursive functional equation specifies the model:
ft T(vs;a
h,ccA;p\pA) = max Ys + E[ft T
+1(vs;d h,aA;ph
lp h)] (4.1)
where ys is the immediate "reward" of making the decision to send a victim of score s to
hospital h. This is simply the victim's survival probability. This immediate reward is
added to the expectation term E[ft'+1(vs;a h,aA;ph,ph)]. The expectation is calculated
over the set of reachable states, indicated by the tilde on each state variable, from the
current state. The boundary condition is given by:
ff(vs;a\aA;p\pA) = 0 (4.2)
4.4.3 The Monte Carlo Simulation
The immediate purpose of the Monte Carlo (MC) simulation portion of the algorithm is
meant to help predict the probability of occurrence of the status of several state variables
80
so they do not have to be explicitly modeled in the SDP. This allows a dramatic
reduction in the size of the state space of the SDP. For example, instead of explicitly
keeping track of each individual patient at the hospitals, the simple yes/no information
concerning the availability of beds at the hospitals is kept.
The beauty of using the MC simulation is that it is somewhat easy to keep track
of an "expanded state space." Another advantage is the ability to run the simulation for
an extended length of time to help find some resemblance of steady-state equilibrium.
By using the simulation scaling the condensed and aggregated SDP into a more
complex picture of the setting is possible. The Monte Carlo simulation enables the
scaling of the smaller SDP results to a problem of virtually any size that may be
encountered during a disaster. In Section 4.5, it is shown that as the results from the
Monte Carlo simulation are scaled back down, they closely approximate the results from
the SDP.
Within the simulation, the generated decision policy from the SDP is used to
make decisions at each decision epoch. Each of the various SDP-equivalent states
visited during the simulation is recorded. From this information the transition probabilities
between the different load groups and the probability of each resource being available in
the next time period are calculated. These probability distributions are then fed back to
another iteration of the heuristic that solves the SDP again. The pseudo-code for the MC
is shown in Figure 4.3, but to fully understand it, some preliminary information is
necessary.
Recall that in the SDP, the state is defined as (vs;a h,aA;ph,pA). In the MC
simulation, an "extended state", referred to as s ta tes im, is utilized instead. It is
composed of a time period, an array of awaiting victims, a set of hospitals, and a set of
ambulances. Each hospital keeps track of individual victims/patients that arrive to it from
81
the MCI. Each patient has an arrival time, a score level, a care time, and a "release"
time. From the set of patients, the hospital's associated load can be calculated. Each
ambulance in the set keeps track of the type of victim it is transporting, when it left the
casualty collection area, which hospital is it traveling to, and when it will return to the
casualty collection area. The load on the ambulances can be calculated from this
information. The MC must translate the s ta tes im to the state that is understood by the
SDP in order to look up the corresponding decision from the policy table. The MC scaled
up by a user-prescribed factor. In the experiments of Section 4.5, a factor of 60 is used,
meaning that the total number of time periods considered is 480 (since there are only
eight "real" decision points in the SDP).
When scaling is employed, translating from the s t a t e s i m to an SDP state is a
little tricky because the time periods and the number of awaiting victims will not match
because there are, for example, 60 times more time periods and initial awaiting victims
in the s ta tes im when compared to the SDP state. To reconcile these differences, the
"ceiling" of the result from taking the s ta tes im time period and dividing by the scaling
factor, e.g., 60, is used as the corresponding time period for the SDP state. Similarly,
each of the victim score levels is translated in the same manner.
During the simulation a warm-up period is used because the starting state
includes "empty" hospitals and all of the ambulances available for transporting victims.
After the warm-up period, each of the corresponding SDP states is captured for the
remaining portion of the time horizon. After the time horizon has been exhausted, the
new transition probabilities can be gleaned from the recorded SDP states.
82
Figure 4.3: The pseudo-code describing the Monte Carlo simulation step of the scenario iteration methodology.
t = 1; visitedSDPStates := empty; Initialize expandedState := (t; [vs]; [H]; [A]);
Do SDP state = convert(expandedState) If (t > warm-up time)
visitedSDPStates.add(SDP state);
dj = lookupDecision(SDP state); expandedState.[A] .nextAvailable().update(); expandedState.[Hn] .update(); expandedState. [vs] .update () ; expandedState.t++ ;
expandedState.[Hh] .dischargePatients(); Until t = T;
Iterate over visitedSDPStates calculate the new transition probabilities
Return new transition probabilities (to be tested against previous ones for convergence)
4.4.3 Convergence
There are numerous ways to test for convergence of the probability matrices between
SDP and MC iterations. As an example, descriptions of three of the ideas considered are
discussed. Two of the measures were ultimately rejected in favor of the third. Initially, the
idea was to test each element of each transition matrix against the corresponding
element of the previous matrices to see if each element was within a pre-specified
distance, e. This check turns out to be too strict because it means that every element of
every matrix must be within a certain percentage after the same iteration. The second
idea for testing for convergence considered was to check how close the objective
83
function value for the SDP was to the one from the previous iteration. This check is not
strict enough because it is too aggregated. That is, many different fluctuations could
occur within different transition matrices and still end up with an objective function that is
in roughly the same vicinity of another.
The convergence metric used in this chapter strikes a balance between being too
restrictive and too lenient. For each probability matrix, a single metric is calculated and
used it to determine if this probability matrix is within the pre-specified epsilon of the
corresponding previous one. In particular, each entry of the probability matrix is weighted
by its associated load group and weighted values are added up. The logic behind
weighting the probabilities by their load groups is as follows. For true convergence to
occur, the load group probabilities will be "close" to the previous ones. Weighting each
probability by its associated load group will provide a decent proxy for this "closeness"
measure. Intuitively, using this measure helps ensure that the system will not jump too
far away from load group that it was in during the previous iteration.
Consider the following simplified example to understand the process of checking
for convergence. Suppose the following probability matrix represents the availability of
an ambulance in the next time period when considering three load groups: qf =
[0.9 0.6 0.1]. Note that the elements do not have to sum to one. The first element
means that there is a 90% chance that an ambulance will be available next time period if
the system is currently in the first load group. (Obviously, this corresponds to a 10%
chance that no ambulance will be available during the next time period.) Similarly, the
second element indicates a 60% chance of an available ambulance in the next time
period if the system is currently in the second load group. After a single iteration of the
scenario iteration process, the Monte Carlo simulation gives a new probability matrix of
qf = [o.7 0.4 0.0]. If e is 0.05, has convergence occurred yet? First, calculate the
84
metric for the two probability matrices, the previous one and the current one. The
corresponding metric for the previous matrix is (0.9 x 1 + 0.6 x 2 + 0.1 x 3) = 2.4. The
current matrix has a corresponding result of 1.5. Now compare the two metrics by
looking at the absolute value of (current metric - previous metric) / previous metric and
see if it is within the given epsilon. In this small illustrative example, convergence has not
occurred yet because the result is 0.375. This result indicates that the new probability
matrices should be fed into the next iteration and used in the solving of the SDP.
This check is performed for each probability matrix found in the SDP. In other
words, 2 x (\H\ + 1) different matrices need to be checked. If any one of these fall
outside of the pre-specified value of epsilon, the conclusion is that convergence has not
occurred yet and another iteration of the process begins.
A time or iteration cutoff can also be used during the determination of whether
the process has converged. So, for example, in the experiments in Section 4.5, a cutoff
of six iterations is utilized. On the machine running these experiments, this equated to
approximately one hour of CPU time. More details can be found Section 4.5.
4.5. Experimental Analysis
Two main avenues are explored. First, an examination of how the model performs under
various configurations is desired. Second, the performance of the scenario iteration
heuristic process itself is of interest. For both investigations, a common experimental
setup is used and it is described next.
4.5.1 Experimental Setup
The SDP contains a total of nine time periods with the last one having only the option of
"do nothing." So, in effect, there are eight decision points. Two score levels, referred to
as Score 1 and Score 2 for simplicity, are considered. For the SDP, each score level can
85
have at most four victims awaiting transport at the casualty collection area. Two
hospitals are investigated, where one is "local" and one is "remote". Each hospital can
be in one of a total of five load groups. Similarly, five load groups are defined for the set
of ambulances. The size of the state space for the SDP that is used during Step 2 of the
scenario iteration process is therefore ( 9 x 5 x 5 x 2 x 2 x 2 x 5 x 5 x 5 ) = 225,000
states.
Five different probability distribution patterns for travel time are considered.
Specifically, we look at constant travel times, uniformly distributed, normally distributed,
a left-skewed distribution, and a right-skewed distribution. Similarly, we examine five
different distributions for the care times. The care time distributions also follow either a
constant time, uniformly distributed, normally distributed, skewed left, or a skewed right
distribution. Care times are score-dependent. To give a general idea of the shape of the
distributions, Figure 4.4 provides a pictorial representation of the local travel time
distributions used in the experiments. The remote travel times follow the distributions
from the same families, but the mean of each distribution is higher because the "remote"
hospital is further away.
Three different levels of capacity at the hospitals are used in the experiments:
five, six, and seven "beds." The final parameter in the experiments involves how close
the survival probabilities of the scores are to one another. The specific settings for the
survival probabilities are shown in Table 4.1 and are termed "base", "squeezed", and
"spread".
86
Figure 4.4: The local travel time distributions used in the experiments.
XI «a XI o
0.45
0.40
0.35 -
0.30
0.25
0.20
0.15
0.10 j
0.05 |
0.00 4-
0
Local Travel Time Distributions \
• Uniform
Normal
LeftSkewed
RightSkewecl
\
\ %. /
/ X ' • •
10 20 30 40
Minutes
50
V„..,
For all of the design points, in the SDP the start point for t = 1 in state is
(vs;a h,aA;ph,pA) = (v1,v2;a
L,aR,aA;pL,pR, pA) = (4,4; 1,1,1; 1,1,1).
That is, for both Score 1 and Score 2, there are four victims each waiting to transported
to a healthcare provider's facility; both hospitals have available beds and an ambulance
is available; and each of the load groups is at its minimum value. We set T = 9 for all
design points. During the scenario iteration process, a cutoff of six iterations is utilized if
the convergence has not yet been met. The heuristic is implemented in this fashion for
these experiments in order to be able to test a large number of different design points.
On the 2.0 GHz, dual core processor with 4.0 GB memory machine we were running the
experiments, a single iteration took approximately 15 minutes to complete. If the iteration
Table 4.1: The different survival probabilities used in the experiments.
Score 1 Score 2
& & * : • . '
Es|i=v>*# Illf'-̂ :
0.49 0.60 0.30
0.63 0.63 0.63
87
cutoff point (6 iterations) was reached before converging, it means approximately 1.5
hours was spent on each design point. With a large number of design points of interest,
this cutoff point seemed reasonable and the results in general do not appear to be
adversely affected (see below).
During the simulation portion of the experiments, a "warm-up" period (a user-
inputted parameter) is used before the start of recording data on the progress of the
simulation. The general idea is that it is better to let the system get to some steady-state
before data collected that will be used in the calculation of the new probability matrices is
started. Using this setup, the first exploration involves how well the model is doing. Then
the attention is turned to investigating the heuristic methodology itself.
4.5.2 Model Performance
To determine how well the model is doing, several different perspectives of the overall
outcome are provided. First, the care time for victims is held constant and the survival
probability is fixed at the base level. For each these 15 design points, the expected
number of survivors over the time horizon is captured. These results are shown in Table
4.2 (a). As the initial capacity of the hospitals increases, the results are monotonically
increasing with respect to each particular travel time distribution. This is the result
expected a priori: the greater the initial capacity at the hospitals, the higher the number
of survivors from the MCI. Basically, with additional capacity at each of the hospitals,
more victims are able to be "placed." The other noticeable result is that when the left-
skewed distribution is used for the travel times (hence they tend to be longer) the
objective function value is smaller than, say, the uniformly distributed travel times.
Similarly, the right-skewed travel time distribution provides a better outcome (larger
number of expected survivors) over the time horizon than, say, if the travel times are
normally distributed. Again, these results are expected a priori. Finally, these results
88
appear to confirm that the scenario iteration heuristic works well for a diverse set of
distributions for travel time and care times.
Table 4.2 (b) provides another example of the results indicating the model reacts
in the expected way. Here, the left-skewed care time distribution is used while holding
the survival probability at the base level. Again, the results are monotonic in each
particular row as expected. Table 4.4 (a) shows similar results when using normal travel
times and normal care times, but varying the survival probabilities.
Figure 4.5 illustrates one specific design point and tracks each iteration as it
converges to the ending survival score of the SDP. We chose the design point
corresponding to hospital capacity of five, uniformly distributed travel times, constant
care time, and the base survival probabilities. We allow this design point run longer in
order to try to capture the possible oscillations in the survival score.
Table 4.2: Two examples showing the results of the model.
Uniform 2.70 2.79 2.89 Normal 2.66 2.74 2.87 feftSkewed 2.64 2.68 2.81 Right Skewed 2.77 2.85 2.95
(a) Constant care times and a base (b) Left skewed care times and a survival probability. base survival probability.
Uniform 3.41 3.47 3.49 Normal 3.18 3.28 3.29 Left Skewed 2.86 2.93 3.02 RightSkewed 4.08 4.16 4.31
89
Figure 4.5: Convergence of the scenario iteration heuristic's survival score for the hospital capacities of five patients, uniformly distributed travel times, constant care times, and the base survival probabilities.
3.70
3.50
<u 3.30 o u (A
« 3.10
<̂ 2.90
2.70
2.50
Convergence of Scenario Iteration Heuristic
10 12
Iterations
4.5.3 Performance of the Heuristic Methodology
It is also important to investigate how the proposed scenario iteration methodology itself
performs. To understand how the heuristic reacts, the number of iterations each design
point required to converge was recorded. A few representative results are shown in
Table 4.3. The term "6*" indicates that the process stopped due to the imposed iteration
count limit. Additionally, see Table 4.4 (b) for how the heuristic methodology reacts when
using normal travel times and normal care times, but the survival probabilities vary.
4.5.4 Ability to Scale
As discussed earlier, one of the advantages to using the scenario iteration heuristic is
the ability to scale up the smaller-sized SDP results to a larger, and perhaps more
realistic, sized problem. In the experiments, an initial SDP state with four victims of each
patient class was used and then progressed through the time horizon of nine time
periods. For the simulation step of the process, a scaling factor of 60 was used. This
90
Table 4.3: Two examples showing the results of the how the scenario iteration process converges.
Constant Uniform Normal Left Skewed Right Skewed
(a) Constant care times and a base survival probability.
Constant Uniform Normal LeftSkewed Right Skewed
(b) Left skewed care times and a base survival probability.
scaling factor was chosen because it gave us approximately 500 time periods and a
large number of victims. At the end of the Monte Carlo simulation the survival score can
be calculated for the simulation and compared to the survival score generated by the
SDP. As Figure 4.6 shows, once the Monte Carlo results have been scaled back down
they are quite close to the SDP results. Here we use the design point corresponding to
hospital capacity of five, uniformly distributed travel times, constant care times, and the
base survival probabilities. We interpret the closeness of the two results to mean that the
scaling up during the simulation works well.
91
Figure 4.6: An evaluation of the SDP results to the results of the Monte Carlo simulation (after they have been scaled back down).
3.70
3.50
(U s_ o u </i
1 1
Su r
3.30 •-
3.10
2.90
Evaluation of the SDP and Monte Carlo Results
2.70
2.50
— SDP
— Monte Carlo
6 8
Iteration #
10 12
Table 4.4: Examples of how the different survival probabilities affect the survival scores and the number of iterations until convergence.
(a) Normal travel times and normal
care times.
(b) Normal travel times and normal
care times.
92
4.6. Conclusion
The problem of evacuating victims of an MCI in a dynamic setting was investigated in
this chapter. To accurately describe the problem in this setting, the state space grows
large quickly making it a challenge to explore the enormous state space for the optimal
answer. The novel methodology proposed, scenario iteration, significantly reduces the
state space helping overcome the "curse of dimensionality." The heuristic framework
combines stochastic dynamic programming with Monte Carlo simulation, resulting in a
final decision policy that can be easily understood and scaled up to meet the specific
attributes of a given MCI. Using the proposed scenario iteration methodology, the
dynamic setting is explored through the use of experiments. The model reacts in many
of the anticipated manners and appears to be providing policies that are better than the
heuristics currently used in practice. Additionally, the methodology itself seems robust
and flexible, making it applicable to other settings where the solving the stochastic
sequential decision problem using the classical approach is prohibitive. It should be
noted, however, that there is some art to implementing the scenario iteration
methodology including deciding which state variables should be estimated with the
equivalent "load groups" (using the language of this research) instead of explicitly
modeled. These decisions also directly affect the Monte Carlo implementation which
estimates the corresponding transition probabilities.
An avenue that should be explored in future research is the design of a proper
experiment to compare the dynamic model to the deterministic model described in
Chapter 3. Another interesting avenue for future research includes exploring different
ways to dynamically discover and modify the load groups as the process progresses.
93
Chapter 5 - Conclusion and Future Directions
In the preceding sections, several challenges that occur in the healthcare operations
field were examined and solutions were presented to provide improvements within the
decision making environments surrounding these operations. The three problems
examined in the paper, while distinct, demonstrate both the need and the opportunities
to improve decision making in diverse healthcare settings. Many of the current
procedures utilized by the decision makers in the different settings examined are not
providing the optimal outcomes. This dissertation attempts to address this fact by
providing better dynamic, real-time allocation decision aids for each of the settings.
We first examine the decision making process involved with allocating testing
time slots for a Cardiac Diagnostic Testing Center (CDTC). The challenge comes with
allocating the time slots among multiple competing patient classes. Real-time scheduling
decisions made in the CDTC are highly complex and have direct revenues and costs
associated with the patients undergoing cardiac diagnosis and the costs associated with
other hospital resources, such as bed availability. Thus, the decisions made in the CDTC
have a significant impact on the entire hospital.
We provide a superior solution for the CDTC's scheduling problem through the
implementation of a dynamic model that incorporates a multi-commodity network flow
formulation. We used the term MFSM to refer to the proposed model. The formulation
introduced allows for the possibility of "bumping" different patient classes in order to
accommodate requests from other patient classes. The solution is shown, through
extensive simulation studies using a partner hospital's data, to provide significant
improvement in the quality of service provided to inpatients while ensuring little to no
94
degradation in the quality of service provided to outpatients. Using the online decision
support tool and framework provided, hospital administrators are also able to make
better informed and more profitable decisions when it comes to long-term capacity
planning.
We then investigate the decision making involved in determining which of several
area hospitals to send victims of a Mass Casualty Incident (MCI). The heuristics
currently used after an MCI are not able to take into account complexities such as
resource availability and the survival probabilities of patients and seldom accomplish the
oft-cited goal of doing the most good for the most people. We first look at the problem in
a deterministic setting and, focusing on the critical time period immediately following the
onset of an MCI, develop a model that enhances the Sacco Treatment Method (STM)
model. The STM model is currently the only model that quantifies the term "greatest
good to the greatest number." The enhancements proposed in this dissertation help
overcome the difficulty in realistically implementing the STM model in real-time settings.
Our enhanced model, formulated as a mixed-integer program, has an average
improvement of 36.5% and 69.0% in the expected number of survivors when compared
to results from the STM model. Additionally, significant improvements are shown when
our proposed model is used in place of three commonly used policies for allocating
victims to hospitals during an MCI.
Finally, we look at the problem of evacuating the victims of an MCI in a dynamic
setting. The challenge in this setting lies in exploring the large state space created by the
state variables that need to be modeled. The novel methodology proposed significantly
reduces the state space helping overcome the "curse of dimensionality." The heuristic
framework combines stochastic dynamic programming with Monte Carlo simulation,
resulting in a final decision policy that can be easily understood and scaled up to meet
the specific attributes of a given MCI. Using our proposed "scenario iteration"
95
methodology, we compare the dynamic model results with the results from the static
model, discussed earlier, and provide managerial insights that can be applied in the
event of a MCI.
While the three essays contained in this dissertation make solid progress
towards helping use healthcare resources more efficiently, there is still much to be done
in the general healthcare setting. The three problems presented here are rich enough
that some future fruitful work can be explored. From the CDTC chapter, while we allude
and suggest that strategic level capacity decisions can benefit from our work, it would be
interesting to fully develop a decision support system whose main goal is to focus on
these types of decisions. Partnering with a supportive hospital with buy-in to the idea
would be vital to ensuring the success and use of such a tool.
Within the MCI setting, perhaps the most potential for fruitful future research is
within the stochastic setting. For example, can "optimal" scaling parameters be found for
use within Monte Carlo simulation step of the scenario iteration process? Is there a
minimum threshold that should be used for the scaling? Another interesting avenue
might be to see if there is an inventive way to be able to include many more score levels
within the heuristic. Incorporating them directly into the SDP intuitively seems somewhat
prohibitive. Can the addition of score levels somehow be accomplished in the Monte
Carlo portion?
One of the differences between the MIP enhanced model of Chapter 3 and the
scenario iteration heuristic of Chapter 4 is that the MIP can somewhat easily look at
hospital resources on a score-level basis whereas the scenario iteration methodology
has more difficulty implementing this effectively. The straight-forward approach to
incorporating this option in the scenario iteration process is to expand the SDP state
definition. However, a large state space for the SDP is exactly what we wish to avoid. Is
96
there an imaginative way to reconcile this difference between the two methods without
increasing the computational costs of the scenario iteration process too much?
Additionally, the methodology proposed in this dissertation has the strong
potential to be useful in other practical problem settings. Are there settings that are
"better" than others? If this is case, then why does it occur? Are some seemingly well-
matched problem settings that have the end result that scenario iteration is not that
effective? What are the common characteristics of the problem settings that indicate a
favorable outcome, and conversely an unfavorable one, when scenario iteration is used
in practice?
97
References
Nezih Altay and Walter G. Green, III. OR/MS research in disaster operations
management. European Journal of Operational Research, 175(3):475-493, 2006.
Jay April, Fred Glover, James P. Kelly, and Manuel Laguna. Practical Introduction to
Simulation Optimization. Proceedings of the 2003 Winter Simulation Conference.
71 - 7 8 .
Gulay Barbarosoglu and Y Arda. A two-stage stochastic programming framework for
transportation planning in disaster response. Journal of the Operational
Research Society, 55(1): 122 43-53, 2004.
Gulay Barbarosoglu, Linet Ozdamar, and Ahmet Cevik. An interactive approach for
hierarchical analysis of helicopter logisitics in disaster relief operations. European
Journal of Operational Research, 140(1): 118-133, 2002.
P. P. Belobaba. Application of a Probabilistic Decision Model to Airline Seat Inventory
Control. Operations Research, 37(2): 183-197, 1989.
G. R. Bitran and S. M. Gilbert. Managing Hotel Reservations with Uncertain Arrivals.
Operations Research, 44(1):35^9, 1996.
98
Margaret L. Brandeau, Jessica H. McCoy, Nathaniel Hupert, Jon-Erik Holty, and Dena
M. Bravata. Recommendations for modeling disaster responses in public health
and medicine: A position paper of the society for medical decision making.
Medical Decision Making, 29(4):438-460, 2009.
M. L. Brandeau, F. Sainfort, and W. P. Pierskalla, editors. Operations Research and
Health Care: A Handbook of Methods and Applications. International Series in
Operations Research and Management Science. Springer, 2004.
GG Brown and AL Vassiliou. Optmizing disaster relief-real-time operational and tactical
decision support. Naval Research Logistics, 40(1): 1-23, 1993.
William J. Carolan, James E. Hill, Jeffrey L. Kennington, Sandra Niemi, and Stephen J.
Wichmann. An Empirical Evaluation of the KORBX® Algorithms for Military Airlift
Applications. Operations Research, 38(2): 240-248, 1990.
W. J. Carrol and R. C. Grimes. Evolutionary Change in Product Management:
Experiences in the Car Rental Industry. Interfaces, 25(5):84-104, 1995.
Yi-Chang Chiu and Hong Zheng. Real-time mobilization decisions for multi-priority
emergency response resources and evacuation groups: Model formulation and
solution. Transportation Research Part E, 43(6): 710 - 736, 2007.
P. Maria Joseph Christie and Reuven R. Levary. The use of simulation in planning the
transportation of patients to hospitals following a disaster. Journal of Medical
Systems, 22(5):289-300, 1998.
99
David C. Cone, John Sera, Kevin Burnes, Donald S. MacMillan, Lias Kurland, and Carin
Van Gelder. Pilot test of the SALT mass casualty triage system. Prehospital
Emergency Care, 13 (4):536-540, 2009.
FN de Silva and RW Eglese. Integrating simulation modelling and GIS: Spatial decision
support for evacuation planning. Journal of the Operational Research Society,
51(4):423-430, 2000.
Martin Durbin and Karla Hoffman. The Dance of the Thirty-ton Trucks: Dispatching and
Scheduling in a Dynamic Environment. Operations Research, 56(1):3-19, 2008.
F. Fiedrich, F. Gehbauer, and U. Rickers. Optimized resource allocation for emergency
response after earthquake disasters. Safety Science, 35(1-3):41-57, 2000.
C. D. Flagle. Some Origins of Operations Research in the Health Services. Operations
Research, 50(1):52-60, 2002.
Simon French. Multi-attribute decision support in the event of a nuclear accident. Journal
of Multi-Criteria Decision Analysis, 5(1):39-57, 1996.
Eric R. Frykberg. Medical management of disasters and mass casualties from terrorist
bombings: How can we cope? The Journal of Trauma Injury, Infection, and
Critical Care, 53(2):201-212, 2002.
100
Eric R. Frykberg. Triage: Principles and practice. Scandinavian Journal of Surgery,
94:272-278, 2005.
M. Geraghty and E. Johnson. Revenue Management Saves National Car Rental.
Interfaces, 27(1): 107-127, 1997.
L. V. Green, S. V. Savin, and B. Wang. Managing Patient Service in a Diagnostic
Medical Facility. Operations Research, 54(1):11-25, 2006.
Lee D. Han, Fang Yuan, Shih-Miao Chin, and Holing Hwang. Global Optimization of
Emergency Evacuation Assignments. Interfaces, 36(6): 502 - 513, 2006.
Antoine G. Hobeika, Sigon Kim, and Robert E. Beckwith. A decision support system for
developing evacuation plans around nuclear power stations. Interfaces, 24(5):22-
35, 1994.
Lenworth M. Jacobs, Jr., Michelle M. Goody, and Anna Sinclair. The role of the trauma
center in disaster management. The Journal of Trauma Injury, Infection, and
Critical Care, 23(8):697-701, 1983.
Dai Jianshe, Wang Shuning, and Yang Xiaoyin. Computerized support systems for
emergency decision making. Annals of Operations Research, 51 (7):315-325,
1994.
101
Arun Jotshi, Qiang Gong, and Rajan Batta. Dispatching and routing of emergency
vehicles in disaster mitigation using data fusion. Soci-Economic Planning
Sciences, 43:1-24, 2009.
Christopher A. Kahn, Carl H. Schultz, Ken T. Miller, and Craig L. Anderson. Does
START triage work? An outcomes assessment after a disaster. Annals of
Emergency Medicine, 54(3): 424-430, 2009.
S.P. Kourniotis, C.T. Kiranoudis, and N.C. Markatos. A systematic approach to effective
chemical emergency management. Safety Science, 38(1):49-61, 2001.
Laura Landro. The informed patient: Hospitals step up disaster-preparedness. The Wall
Street Journal, pg. D.4, September 6, 2006.
Eva K. Lee, Siddhartha Maheshwary, Jacquelyn Mason, and William 210 Glisson.
Large-scale dispensing for emergency response to bioterrorism and infectious-
disease outbreak. Interfaces, 36(6):591-607, 2006a.
Eva K. Lee, Siddhartha Maheshwary, Jacuelyn Mason, and William Glisson. Decision
support system for mass dispensing of medications for infectious disease
outbreaks and bioterrorist attacks. Annals of Operations Research, 148:25-53,
2006b.
102
E. Brooke Lerner, Richard B. Schwartz, Phillip L. Coule, Eric S. Weinstein, David C.
Cone, Richard C. Hunt, Scott M. Sasswer, J. Marc Liu, Nikiah G. Nudell, Ian S.
Wedmore, Jeffrey Hammond, Eileen M. Bulger, Jeffrey P. Salomone, Teri L.
Sanddal, Graydon C. Lord, David Markenson, and Robert E. O'Connor. Mass
casualty triage: An evaluation of the data and development of a proposed
national guideline. Disaster Medicine and Public Health Preparedness,
2(Supplement 1):S25-S34, 2008.
Gl Mould. Assessing systems for offshore emergency evacuation. Journal of the
Operational Research Society, 52(4):401-408, 2001.
V. Lieberman and U. Yechiali. On the Hotel Overbooking Problem: An Inventory System
with Stochastic Cancellations. Management Science, 24(11):1117-1126, 1978.
Ying Liu, Xiaorong Lai, and Gang-Len Chang. Two-level Integrated Optimization System
for Planning of Emergency Evacuation. Journal of Transportation Engineering.
132(10): 800-807, 2006.
Linet Ozdamar, Ediz Ekinci, and Beste Kuciikyazici. Emergency logisitics planning in
natural disasters. Annals of Operations Research, 129(1-4):217-245, 2004.
E. Litvak, M. C. Long, A. B. Cooper, and M. L. McManus. Emergency Department
Diversion: Causes and Solutions. Academic Emergency Medicine, 8(11): 1108-
1110,2001.
103
KN Papamichail and Simon French. Generating feasible strategies in nuclear
emergencies-a constraint satisfaction problem. Journal of the Operational
Research Society, 50(6):617-626, 1999.
P. Parker. Move Care to a Higher Level with Emergency Systems. Nursing
Management, 35(9):82-84, 2004.
J. Patrick, M. L. Puterman, and M. Queyranne. Dynamic Multipriority Patient Scheduling
for a Diagnostic Resource. Operations Research, 56(6): 1507-1525, 2008.
Warren B. Powell. Approximate Dynamic Programming: Solving the Curses of
Dimensionality. 2007. Wiley Interscience.
Vladimir P. Reshetin and James L. Regens. Simulation modeling of antrhax spore
dispersion in a bioterrorism incident. Risk Analysis, 23(6): 1135-1145, 2003.
William J. Sacco and H. Champion. Field Testing of the Trauma Score. Honolulu, HI:
Proceedings of the Sixteenth Hawaii International Conference on System
Sciences, 1983.
William J. Sacco, D. Michael Navin, Katherine E. Fiedler, Robert K. Waddell II, William
B. Long, and Robert F. Buckman, Jr. Precise Formulation and Evidence-based
Application of Resource-constrained Triage, Academic Emergency Medicine,
12(8):759-770, 2005.
104
Kyu-Cheoul Shim, Darrell G. Fontane, and JohnW. Labadie. Spatial decision support
system for integrated river basin flood control. Journal of Water Resources
Planning and Management, 128(3): 190-201, 2002.
S. Thompson, M. Nunez, R. Garfinkel, and M. D. Dean. Efficient Short-Term Allocation
and Reallocation of Patients to Floors of a Hospital During Demand Surges.
Operations Research, 57(2):261-273, 2009.
World Health Organization (WHO). Mass Casualty Systems: Strategies and guidelines
for building health sector capacity. April 2007.
http://www.who.int/hac/techguidance/tools/mcm_guidelines_en.pdf. Last
accessed on March 30, 2010.
P. Daniel Wright, Matthew J. Liberatore, and Robert L. Nydick. A survey of operations
research models and applications in homeland security. Interfaces, 36(6):514-
529, 2006.
105
