LEADERSHIP ASSIGNMENT PART 2
BYSTANDER
PlanningStrategiesforHomeHealthCareDeliveryArticle2.pdf
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Asia-Pacific Journal of Operational Research Vol. 33, No. 5 (2016) 1650041 (26 pages) c© World Scientific Publishing Co. & Operational Research Society of Singapore DOI: 10.1142/S021759591650041X
Planning Strategies for Home Health Care Delivery
Mike Hewitt
Quinlan School of Business Loyola University, Chicago, IL 60611, USA
Maciek Nowak∗
Quinlan School of Business Loyola University, Chicago, IL 60611, USA
Nisha Nataraj
Industrial and Systems Engineering North Carolina State University
Raleigh, NC 27695, USA [email protected]
Received 29 August 2014 Revised 4 May 2016
Accepted 11 July 2016 Published 19 September 2016
In home health care (our motivating application), consistency is representative of the general health care principle of continuity of care, which is often correlated with quality
of care. Much of the existing research involving consistency in routing uses planning horizons that are a week or shorter. Yet in many settings the relationship between an organization and its customers lasts much longer. Hence, this paper looks at how one should plan when seeking consistency in routes extends the impact of caregiver-patient assignments. Specifically, the paper examines appropriate planning horizon length and, with an extensive computational study, demonstrates that a long planning horizon can have significant potential for savings in terms of transportation costs and staffing levels. Initially, a deterministic setting is considered, with all patient requests during the plan- ning horizon known a priori, and the routing cost of planning for two to three months is compared with the cost when planning is done on a weekly basis. With uncertainty inherent in planning for such a long time horizon, a methodology is presented that antic- ipates future patient requests that are unknown at the time of planning. Computational evidence shows that its use is superior to planning on a weekly, rolling horizon basis.
Keywords: Home health care; scheduling; tactical planning; uncertainty.
∗Corresponding author.
1650041-1
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
1. Introduction
Home health care refers to the care provided by skilled and non-skilled caregivers for patients, typically homebound, within their own homes. Services available for in-home care range from hospice care to wound and pain management to routine self-care activities such as feeding, bathing and cleaning. Patients are often recom- mended for home health care by their primary physician or after discharge from a hospital and the episode of care often lasts 60–90 days, during which time most individuals need to be visited multiple times each week by their caregiver(s).
In-home care is an attractive alternative to nursing homes and hospitals because it typically lowers costs and improves a patient’s quality of life. For example, Balin- sky (1999) reports that the cost of caring for “high-tech, ventilator dependent children. . . at home is 87 percent less than a hospital setting.” With all the asso- ciated benefits, it is not surprising that the use of home health care has become widespread. A study conducted by the National Association for Home Care and Hospice (2010) found that in 2008 approximately 33,000 care-givers made visits to approximately 12 million patients across the country. However, providing care in the home on that scale does involve significant transportation resources; the same study found that home health care workers drove close to 5 billion miles in the United States in 2006.
Given the numerous budget cuts that health care providers have faced (Home Care Association of New York State and New York Association of Homes & Services for the Aging, 2011), many are focused on reducing costs, particularly those related to transportation. However, care must be taken when reducing costs to ensure that a provider’s primary goal is still achieved: providing quality care. One important quality metric used by providers is continuity of care, wherein the goal is to see patients with the same caregiver on each visit (Jee and Cabana, 2006). Continu- ity of care has many benefits, including reducing the time and effort a caregiver spends reviewing a patient’s history and care plan, and fostering close relationships between patients and their caregivers (Saultz and Albedaiwi, 2004). The probability of hospitalization and emergent care decreases with greater consistency in nursing personnel while improvements in quality of life between admission and discharge from home health care are also evident (Russell et al., 2011). Thus, continuity of care is often correlated with quality of care and planning efforts for home health care agencies need to recognize the importance of continuity of care as well as costs (Saultz and Lochner, 2005; Van Walraven et al., 2010). However, maintaining a high level of continuity of care also reduces planning flexibility and opportuni- ties for savings. When patients are assigned to the same caregiver for two to three months, there are few opportunities for re-optimization when new patients require care.
The planning problem faced by home health care agencies is to assign caregivers to patients such that their weekly care plan is followed while continuity of care is pursued from week to week and costs are minimized. Models and solution methods
1650041-2
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
have been presented for the planning problem faced by home health care agencies. When considering a long-term perspective, relevant literature has focused on the problem of assigning patients to nurses in order to maintain consistency and a balance of workload, with Carello and Lanzarone (2014) and Lanzarone and Matta (2014) finding improvements in these factors when considering potential patient demand. Cardoso et al. (2015) determine the number of resources to use and how to allocate them in a long-term care network. Travel distance is considered when assigning patients to districts that indicate which nurses will treat them (Benzarti et al., 2013; Hertz and Lahrichi, 2009). However, the research on long-term resource assignment has not considered how to route these resources over time.
Alternatively, the research focused on routing home health care providers has been limited to a short-term perspective. In previous research, the problem horizon has varied from a day (Cheng and Rich, 1998; Bertels and Fahle, 2006; Kergosien et al., 2009; Mankowska et al., 2014; Braekers et al., 2015) to a week (Begur et al., 1997; Eveborn et al., 2006; Steeg and Schröder, 2008; Groër et al., 2009; Liu et al., 2014), with Bennett and Erera (2011) extending the horizon on a rolling basis. How- ever, in many settings the relationship between an organization and its customers lasts much longer. And in some settings, such as home health care, the length of that relationship is known with a fairly high degree of certainty when it begins. Despite this, most home health care providers make decisions on a week-by-week, or even a day-to-day, basis, generally due to the lack of a proper planning tool.
This paper posits that with a tactical perspective, such as considering a planning horizon on the order of months, decision makers can better recognize how consis- tency extends the impact of a nurse-patient assignment on both transportation and staffing. Thus, the first focus of this paper is not a new model or algorithm to sup- port consistent delivery operations but instead a study of what planning perspective should be taken when pursuing continuity of care; tactical, where decisions are made considering a two to three month horizon, or operational, with a daily or weekly horizon. To do so, an existing planning model and method are adapted to compare the transportation cost and staffing requirements of plans derived using different planning horizons. The planning problem is modeled as a variant of the consistent vehicle routing problem (ConVRP) presented in Groër et al. (2009) and solved with a modified version of their ConVRP Record to Record travel algorithm (ConRTR). We focus on two or three month periods of time and use the modified ConRTR to implement two planning strategies: a rolling, weekly strategy that is similar to what is often proposed in the literature, and a long term planning strategy where plan- ning is done once for the entire horizon. A computational study shows that longer planning horizons enable significant reductions in transportation cost and staffing requirements in a deterministic setting where all current and future patient service requests are known at the time of planning. Also a modification of the ConRTR is proposed that results in significantly better performance for instances that model long planning horizons.
1650041-3
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
The potential for efficiencies is next demonstrated in a stochastic setting where there is uncertainty with respect to when and where future patients will request care. To do so, another adaptation of the ConRTR is presented, based on an easily calculated point estimate of future patient requests. This revised algorithm antic- ipates these future requests when assigning known patients to nurses. Given that many agencies have rudimentary information systems and rely on manual planning processes, the method was designed so as to rely on data that agencies already have and that is easily explained, in hopes that doing so will increase the adoption rate of the planning method. Some automated decision support systems have already been developed for home health care agencies. The system developed by Begur et al. (1997) integrates a nurse routing component into a Spatial Decision Support Sys- tem that uses a Geographical Information System to aid schedule-making. LAPS CARE, a system that does not constrain continuity but includes it as an objec- tive, is developed and shown to be beneficial for Swedish home care organizations by Eveborn et al. (2006). However, neither of these systems considers a long term planning horizon. A computational study yields the same conclusions as the deter- ministic setting regarding taking a tactical perspective, that daily transportation costs and staffing levels may be lowered, and caregiver patient workloads can be more consistent from week to week.
While this work is motivated by the home health care industry, incorporating uncertainty with respect to when and where future patients will request care renders a planning problem similar to the Consistent VRP with Stochastic Customers. And, while the ConVRP has received a great deal of attention in the academic litera- ture (Kovacs et al., 2014), as of this writing there have been no algorithms published for the ConVRP with Stochastic Customers. In this sense, this last algorithm can be viewed as the first heuristic for producing high-quality solutions to the ConVRP with stochastic customers. The computational study in this paper thoroughly eval- uates the performance of this algorithm, including its sensitivity to instance param- eters such as geography, frequency of customers requiring visits, and the degree to which the set of customers remains constant. Solutions produced by the algorithm are benchmarked against those produced when all information is known (essentially calculating the “value of perfect information”). In the experimental results it can be seen that travel times are often within 5% of when all information is known, suggesting that the algorithm is producing high-quality solutions.
This paper makes three contributions to the literature on consistent delivery operations. First, it is shown that significant staffing and transportation savings can be found by taking a tactical perspective and considering long planning horizons (much longer than what is typically reported in the literature). Second, those savings are partially enabled by an enhancement to the ConRTR that significantly improves its performance when there is considerable variation in the number of visits each customer requires and a long planning horizon. Third, the first solution approach for the ConVRP with stochastic customers is presented and it is shown to be much more effective than planning on a rolling horizon basis. Ultimately, the results in
1650041-4
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
this paper show that planning for a longer period of time can lead to considerable gains in operational efficiency and lower staffing levels.
The rest of the paper is organized as follows. Section 2 formally defines the problem and related literature, the application of the ConRTR to the home health care setting and the enhancement of the ConRTR. Section 3 describes two planning strategies that, in a deterministic setting, are central to establishing the relation- ships between continuity of care, planning horizon, and cost. Section 4 presents a planning method for a stochastic version of the problem where not all patient requests for visits are known. Finally, the conclusions and scope for future work are discussed in Sec. 6.
2. Problem Description and ConRTR Enhancement
At the start of each week, a typical home health care agency must derive a set of patient-nurse assignments and routes for that week’s worth of patients, observing the previous week’s assignments. In addition to carrying over previous assignments, new patients must be added to the plan, taking the place of patients whose care period has expired. Associated with a new patient is a period of care (typically two to three months) and a care plan for each week (i.e. the days the patient is to be visited). An example schedule is for a patient to be seen twice a week, every Monday and Thursday, for eight weeks. We assume that the days that a patient requires a visit are fixed a priori, with many agencies determining this in advance based on the type of care prescribed. Once a visit schedule is established, it typically stays fixed for the remainder of the patient’s period of care. In some settings the agency must consider qualification levels when assigning a nurse to a patient. We focus on settings wherein all nurses are qualified to perform all care assignments, as is often seen in settings such as physical therapy. Also, the number of nurses is flexible as agencies often have the option of outsourcing patient visits to third-party providers during periods of high demand (the cost of an outsourced nurse is generally the same as a nurse on staff). With the visit schedule established for all patients to be visited that week, the agency then must assign nurses to visit those patients.
The objective of the home health care agency, and the model described here, is to maintain consistency of care for each patient while minimizing the total cost to provide that care. The total cost may include travel costs and wages for the health care provider. The model presented here will minimize the total time that the nurses spend providing the care, which includes the time spent with the patient and travel time, and the total number of nurses utilized to provide the care. Consistency of care is enforced by requiring a patient to be visited by the same nurse on each visit. The consistency of appointment times from day to day is regulated by maintaining approximately the same sequence of customers on daily routes.
This planning problem is often modeled as a variant of the vehicle routing prob- lem (VRP) (Begur et al., 1997; Cheng and Rich, 1998; Bertels and Fahle, 2006; Steeg and Schröder, 2008; Kergosien et al., 2009). The problem may be modeled on
1650041-5
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
a graph where agency and patient locations are represented by nodes and routes connecting those nodes are represented by arcs. The nurses begin from a central agency before visiting patients in this problem, which is modeled using a single depot. While the majority of existing work on the planning problem faced by home health care agencies view the problem as a static planning problem, Bennett and Erera (2011) study a dynamic home health care routing and scheduling problem for a single-nurse variant where some patient requests are not known in advance.
This paper presents a model of the planning problem faced by a home health care agency using the ConVRP Groër et al. (2009). The ConVRP aims to design routes that ensure a customer is visited by the same driver/vehicle each time he or she requires a visit. The ConVRP is similar to the Periodic VRP (Beltrami and Bodin, 1974; Russell and Igo, 1979), an extension of the VRP where vehicle routes are constructed to serve customers over a multi-period planning horizon and visit schedules are chosen from a set of possible visit frequencies. However, the ConVRP differs in that visit schedules are assumed to be determined a priori, as is the case in our problem. Other papers (Francis et al., 2006, 2007; Zhong et al., 2007; Smilowitz et al., 2013) have studied consistency or driver familiarity (which is a variation of consistency) in the small package industry, but consistency is primarily modeled through an objective rather than a constraint.
Each customer within the context of the ConVRP requires service on a spec- ified subset of days. The goal is to visit the customer at approximately the same time by the same driver on each day that service is required, with the objective of minimizing the total vehicle operating time over the problem horizon. To solve the ConVRP, Groër et al. (2009) propose the ConVRP Record to Record travel algo- rithm (ConRTR) and show that it is capable of producing high-quality solutions for instances of the ConVRP with up to several thousand customers very quickly while enforcing perfect consistency of service. It ensures this consistency by designing a set of template routes which visit all customers with multiple requests over the planning horizon. The template routes are not implemented in practice. Instead, they constitute a framework from which daily routes are derived.
ConRTR is based on the record-to-record travel algorithm developed by Li et al. (2005) to solve very large-scale VRPs. In the first stage of this algorithm, the tem- plate is created using the well known Clarke and Wright algorithm to route only those customers requiring service on multiple days. Three local search methods are used to improve the template: one-point move, where one customer is moved to a new position; two-point move, where two customers are swapped; and two-opt move, which replaces two existing edges with two new edges. A diversification phase, in which the solution space is explored through improving and deteriorating moves, is followed by an improvement phase, in which only improving moves are allowed until a local minimum is reached. In the second stage of the algorithm, the template routes are used to create routes for each day by removing customers who do not require service on that day and inserting customers who require service only on that day. By using the template routes in this fashion, it is guaranteed that each
1650041-6
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Template
Day 3
Day 1
Day 2
Legend Depot
Route Patient
Fig. 1. Deriving daily routes from a template route.
customer is visited by the same driver and customers are visited in approximately the same sequence each time they are served.
A similar methodology was first introduced by Jaillet (1988) in his work on the Probabilistic Traveling Salesman Problem. Figure 1 provides an example of one such template route and the daily routes developed from it. The ConRTR is an iterative algorithm that alternates between deriving and improving the template routes based on bounds on vehicle capacity and route length, then deriving and improving daily routes based on the set of template routes. If the travel time or capacity limit of any daily route is violated, the bound on the length or capacity of the template route is reduced and the template is regenerated, until the daily route is no longer infeasible. Alternatively, if a daily route is heavily under-utilized, the bounds on the template route is increased and the templates are again regenerated. This iterative loop continues until a good balance has been achieved.
While the ConRTR can produce high quality solutions for instances that con- sider a planning horizon of multiple months, when deriving and improving template routes it does not differentiate customers by the number of visits they require. For example, if two patients living in the same vicinity each require one month of service over a two month horizon, one for the first month and the other for the second, it may be most efficient to service them with the same nurse. However, the ConRTR may not place them on the same route as it cannot interpret that each patient only requires service for half of the problem horizon. Without considering this informa- tion, some efficiencies may be lost.
In order to distinguish patients based on the number of visits required, the service time per visit for each patient is discounted based on the number of days
1650041-7
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
the patient must be visited over the problem horizon. Given a required service time, si, for patient i, with ni visits over the length of the problem horizon H, the discounted service time, s∗i , is expressed as s
∗ i =
ni H
(si). For example, if a patient requires three visits per week, each lasting 60 min, for six weeks of an eight week problem horizon (with five days per week), the discounted visit time used for designing the template routes would be 3∗6
5∗8 ∗ 60 = 27 min. In the extreme case where a patient requires service every day over the course of the problem horizon, the visit time would not be discounted. Therefore, when the template routes are constructed, those patients requesting service most frequently will have the least discounted service time. Returning to the example with two patients each requesting one month of service over a two month horizon, each patient’s service time is reduced by 50% and it is more likely that the ConRTR may be able to fit both on the same template route.
3. Planning Strategies in a Deterministic Setting
In this section two planning strategies are presented, week-by-week and long-term, under a deterministic setting wherein all patient visit requests are known a priori. Week-by-week planning strategies have been used in previous research (Begur et al., 1997; Steeg and Schröder, 2008). In this strategy, only those patients that require service for the coming week are considered when assigning patients to nurses, with assignments and routes made in previous weeks carried forward. When a new patient requires service, he or she is added to a route from a previous week. In order to implement this strategy, the ConRTR is initially applied to the first week of service. For each of the following weeks, the template routes from the previous week are loaded and all new patients for the current week are inserted in a greedy manner that also yields feasible daily routes. This is done without changing the assignments from previous weeks such that consistency is maintained for all patients.
For the long-term planning strategy, the ConRTR is applied once at the begin- ning of the horizon, taking into consideration all patients who are to be seen over the problem horizon. Figure 2 illustrates the difference between the two strategies. In this basic example, consider a two week planning horizon with two nurses, A and B, that may service at most four patients per week. Six patients require ser- vice, with patients 2, 3, 4 and 6 to be serviced both weeks, while patients 1 and 5 require care in week 2. With week-by-week planning, in the first week nurse A may be used to service all patients in an effort to limit fixed costs associated with using an additional nurse, while minimizing travel costs. However, when this assignment is implemented in the second week, nurse B is required to handle the new demand and both nurses must make the longer trip to the 3, 4, 5, and 6 cluster of patients. With long-term planning, nurse B would start serving patient 2 in the first week to maintain consistency and save this nurse from making the longer trip to the more distant patient cluster. Note that this is a very basic example and with a full data set each nurse would work the entire day each day of the week. While this results
1650041-8
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Day 1 2 3 4 5 6 7 8 9 10 Patient 1 - - - - - - B - B - Patient 2 - A - A - - A - A - Patient 3 A A A A A A A A A A Patient 4 - A - A - - A - A - Patient 5 - - - - - - B - B - Patient 6 A - A - A A - A - A
Week-by-week planning
Day 1 2 3 4 5 6 7 8 9 10 Patient 1 - - - - - - B - B - Patient 2 - B - B - - B - B - Patient 3 A A A A A A A A A A Patient 4 - A - A - - A - A - Patient 5 - - - - - - A - A - Patient 6 A - A - A A - A - A
Long-term planning
2keeW1keeW
2keeW1keeW
Depot
Patient 2
Patient 5Patient 4
Patient 3
Patient 1
Patient 6
Fig. 2. Nurse assignments for week-by-week and long-term planning.
in both nurses used for both weeks, it shows that long-term planning can quickly lead to savings in travel cost.
4. Long Term Planning Under Uncertainty
A long-term strategy is likely to result in improved performance, particularly with perfect information. However, it is rare that a home health care provider will have such information looking forward two or three months. A stochastic model taking into account the uncertainty with respect to the care plan and location of new patients is necessary in any planning horizon, particularly one that is extended. Uncertainty may be modeled using a variety of techniques, but nearly all require
1650041-9
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
the determination of probability distributions. For home health agencies that do not employ sophisticated information systems, such methods may be difficult to imple- ment. Thus, next is presented a planning method for the ConVRP with stochastic customers that relies on data elements an agency will typically already have.
Many applications of the VRP involve uncertain parameters, such as customer demands, customer locations, and/or travel times. Most relevant to this work is the VRP with stochastic customers (VRPSC) (Gendreau et al., 1996) where demands are known, but customer locations and, if the problem is periodic, days to be seen are not known beforehand. Other related work includes Bent and Van Henten- ryck (2004), which proposes a multiple-scenario approach to solve the partially dynamic Vehicle Routing Problem with Time Windows with Stochastic Customers, and Campbell and Savelsbergh (2005), which defines the home-delivery prob- lem (HDP) for grocery delivery with stochastic customers and presents different profitability-based insertion heuristics to create a set of routes that will help eval- uate whether to accept or reject incoming customer requests.
Using historical data, an agency can derive an expectation of the average number of patients to be visited in a given week. This information may be used to anticipate requests and adjust routing accordingly. The planning method proposed here uses this expectation to anticipate and plan for future patients. By doing so, a more efficient set of template routes may be created, positioning the agency for better daily routes in future weeks.
Prior to creating the first set of template routes with the ConRTR, the expected number of patients visited per week is used to create a set of “dummy” patients that serve as a placeholder for potential future requests. With these dummy patients added to the initial known set of patients, the template routes are constructed for the entire problem horizon. The template routes are then used to create the daily routes for the first week. Then, on a weekly, rolling-horizon basis, daily routes are derived at the beginning of each week based on the previous week’s routes and information that is learned as new, actual patients request service. It is assumed that at the beginning of each week all patients whose care period begins that week are known.
In order to create a dummy patient, several parameters regarding every future patient must be estimated: (i) the week his or her period of care begins, (ii) his or her location, and, (iii) his or her weekly visit schedule. To evaluate the first parameter, for each week the number of patients still requesting service based on the initial schedule is compared with the expected number of patients for an average week. As home care is typically prescribed for a fixed period of time, it is assumed that the agency knows when each initial patient’s period of care will end. When there are fewer known patients than expected it is assumed that new patients begin their period of care in this week and these patients are added to the set of requests as dummy patients. The care period for a dummy patient continues through to the end of the problem horizon. For the second and third parameters to be estimated, the location is fixed at the depot and the patient is assigned a visit every day of
1650041-10
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Week 1
0
52
Week 2
Week 3 Week 4
6
Average = 13 Patients = 11 Dummy = 2 Dropped = 3
Average = 13 Patients = 14 Dummy = 0 Dropped = 0
Average = 13 Patients = 13 Dummy = 0 Dropped = 1
Average = 13 Patients = 8 Dummy = 5 Dropped = 6
Depot
Route Real patient
Number of dummy patients and location
Dropped patient
Fig. 3. Modeling expectation of future patients with dummy patients.
the week. As these dummy patients are placeholders, any arbitrary location should suffice and the depot is often close to the geographic center of all requests.
This methodology is illustrated in Fig. 3. Assume a four-week planning horizon, with 14 known patients in week 1, and an expectation of 13 patients each week. Also, it is known that in week 2, the period of care ends for one patient, decreasing the number of known patients in week 2 to 13. Thus, the difference between the number of known patients in week 2 and the number of expected patients is zero. No dummy patients are added. Week 3 sees two additional patients end service, with two fewer real patients than expected patients. Therefore, two dummy patients are added at the depot. Week 4 follows with three more patients ending service and three dummy patients added.
After the dummy patients are generated and added to the schedule of known patients requiring service, the ConRTR is applied over the entire planning horizon to derive template routes. These template routes are then used to create the daily routes for week 1. At the beginning of each of the following weeks, the actual requests for service are realized. If there are slots reserved for dummy patients on template routes, a dummy patient is selected for replacement in a greedy fashion such that the real patient is placed on the geographically closest route of a dummy patient and inserted into the route at the point where travel cost is minimized. If there
1650041-11
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
are more new real patients than dummy patients in a week, the additional new patients are placed on routes following the procedure for week-by-week planning. These new template routes are then used to create the set of daily routes for the week, continuing in this fashion until the end of the problem horizon.
5. Computational Study
Three planning methodologies are compared in this study: the deterministic algo- rithms using week-by-week planning (WbW) and long-term planning (LT), and the long-term planning under uncertainty (LTUU) algorithm that forecasts patient requests. As the objective of the model is to minimize both the number of nurses needed to serve all patients and the total time spent providing care, the primary metrics used to evaluate the performance of each methodology will be number of nurses used per week and the total travel time (the number of patients served and the time per visit is consistent regardless of the algorithm, so the time spent with the patients is the same).
5.1. Experimental setup
Problems with long-term horizons for the ConVRP have not been studied, so the instances used for testing in this paper were randomly generated. The procedure for generating these instances was similar to that used for the ConVRP instances. As planned visits rarely occur on the weekend, a five-day week and a four-week month are used. Each instance models an “urban” setting, wherein patients are randomly distributed in a circle with a radius of five miles, an “intermediate” setting, with patients randomly distributed in a circle with a radius of 15 miles, or a “rural” setting, wherein patients are randomly distributed in a circle with a radius of 25 miles. A nurse travels 30 miles per hour in an urban setting, 40 miles per hour in an intermediate setting and 50 miles per hour in a rural setting. Each nurse’s workday is 10 h. Based on conversations with a home health care agency, each patient visit requires one hour. The initial number of patients was set at 200, 400, and several values in between. While the number of patients requesting service in each week is not constant, to model an agency in a “steady-state” of demand, the number of patients whose period of care begins after week one is set equal to the number of patients whose period of care ends over the entire planning horizon. The length of care for each patient and the set of patients beginning service after the first week are randomly generated such that this steady-state is maintained. The weekly demand schedule is generated assuming a 70% chance that a patient will require a visit on each day.
The instances are summarized in Table 1, where column “Begin/End” provides the total number of patients whose period of care begins or ends after week one (i.e., for a value of 35, 35 new patients begin service over the problem horizon and 35 end service). Five unique instances were generated for each of these combinations of characteristics. Unless otherwise noted, the data represents the average of the
1650041-12
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Table 1. Problem instance characteristics.
Instance Initial patients Begin/End Geographic setting Horizon
200-35U8 200 35 Urban 8 weeks 200-70U8 200 70 Urban 8 weeks 200-35l8 200 35 Intermediate 8 weeks 200-70l8 200 70 Intermediate 8 weeks 200-35R8 200 35 Rural 8 weeks 200-70R8 200 70 Rural 8 weeks 200-55U12 200 55 Urban 12 weeks 200-110U12 200 110 Urban 12 weeks 200-55l12 200 55 Intermediate 12 weeks 200-110l12 200 110 Intermediate 12 weeks 200-55R12 200 55 Rural 12 weeks 200-110R12 200 110 Rural 12 weeks 235-35U8 235 35 Urban 8 weeks 270-70U8 270 70 Urban 8 weeks 235-35l8 235 35 Intermediate 8 weeks 270-70l8 270 70 Intermediate 8 weeks 235-35R8 235 35 Rural 8 weeks 270-70R8 270 70 Rural 8 weeks 255-55U12 255 55 Urban 12 weeks 310-110U12 310 110 Urban 12 weeks 255-55l12 255 55 Intermediate 12 weeks 310-110l12 310 110 Intermediate 12 weeks 255-55R12 255 55 Rural 12 weeks 310-110R12 310 110 Rural 12 weeks 400-35U8 400 35 Urban 8 weeks
400-70U8 400 70 Urban 8 weeks 400-35l8 400 35 Intermediate 8 weeks 400-70l8 400 70 Intermediate 8 weeks 400-35R8 400 35 Rural 8 weeks 400-70R8 400 70 Rural 8 weeks 400-55U12 400 55 Urban 12 weeks 400-110U12 400 110 Urban 12 weeks 400-55l12 400 55 Intermediate 12 weeks 400-110l12 400 110 Intermediate 12 weeks 400-55R12 400 55 Rural 12 weeks 400-110R12 400 110 Rural 12 weeks
results for the five instances. The algorithms are coded in C++ and executed on a machine with a 1.80 GHz AMD P820 triple-core processor with 4 GB of RAM.
5.2. Computational results
Table 2 presents a comparison of the three planning strategies with respect to the average and standard deviation of the number of nurses used per week over the entire horizon. Both LT and LTUU use fewer nurses to serve the same number of patients on an average weekly basis than WbW. Without any consideration for future patient requests, week-by-week planning requires the use of additional nurses as unforeseen demand is realized in later weeks. The initial set of nursing assignments are not created to allow for new patients to be added, with new nurses introduced in later
1650041-13
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
Table 2. Average number of nurses used per week with week-by-week (WbW), long- term (LT) and long-term planning under uncertainty (LTUU) planning.
Instance type WbW LT LTUU
Average Standard Average Standard Average Standard deviation deviation deviation
200-35U8 25.0 1.66 22.4 0.72 22.1 1.95 200-70U8 27.3 3.55 23.6 0.78 24.8 3.62 200-35l8 29.0 1.81 26.7 0.94 22.7 1.94 200-70l8 31.9 3.34 28.2 1.61 26.1 4.07 200-35R8 32.0 1.77 29.5 1.42 24.1 2.09 200-70R8 33.6 3.45 30.7 1.45 25.9 4.56 200-55U12 26.7 2.54 23.0 0.94 24.6 2.79 200-110U12 30.9 4.98 30.3 0.72 30.4 5.34 200-55l12 29.7 2.71 26.9 1.47 25.0 3.11 200-110l12 33.2 5.22 28.8 1.87 29.3 6.31 200-55R12 33.9 2.54 31.4 1.89 24.1 3.39 200-110R12 37.8 4.68 33.0 1.39 32.1 6.23 235-35U8 29.5 1.53 26.7 0.55 25.9 1.97 270-70U8 35.2 3.20 31.1 0.97 32.4 3.49 235-35l8 33.8 1.81 30.8 1.01 26.3 1.93 270-70l8 41.4 3.50 36.8 1.56 32.9 4.22 235-35R8 37.0 2.01 33.7 1.74 28.9 2.14 270-70R8 44.7 3.38 41.5 1.78 32.2 4.04 255-55U12 33.1 2.39 29.8 0.55 30.7 2.53 310-110U12 44.0 4.73 40.6 0.73 40.6 5.18 255-55l12 37.3 2.58 34.3 1.27 30.0 3.12 310-110l12 47.4 5.30 43.2 1.95 39.4 6.16 255-55R12 42.3 2.54 39.4 1.95 30.7 3.14 310-110R12 54.5 4.82 52.3 2.35 42.9 6.14 400-35U8 51.2 3.16 44.9 0.97 45.3 4.04 400-70U8 56.1 6.67 55.3 0.30 52.9 7.07 400-35l8 58.0 3.49 51.9 1.97 45.1 4.14 400-70l8 63.4 6.72 57.9 1.48 50.5 8.20 400-35R8 64.4 3.41 58.7 2.17 45.0 4.18 400-70R8 69.3 6.75 64.3 1.99 54.1 8.41 400-55U12 53.7 4.66 50.2 1.22 48.4 5.35
400-110U12 62.4 9.78 62.8 0.62 62.1 11.22 400-55l12 59.8 5.30 55.5 1.52 48.9 6.27 400-110l12 68.3 10.62 59.3 2.66 62.5 11.97 400-55R12 67.3 4.67 61.3 2.64 50.9 6.21 400-110R12 75.6 9.63 68.8 3.14 61.5 12.98
Average 44.5 4.2 40.7 1.5 37.0 5.0
weeks to service the new patients. Using LT, all patients are considered simultane- ously and nurse plans are created such that patients who discontinue service may be easily replaced with new patients. While LTUU is similar in that potential patients are considered, nurses are not dispatched until the potential patients are realized, such that the initial number of nurses used is smaller than under LT.
While LTUU results in the use of the fewest number of nurses, it also has the highest variability from week to week. This is emphasized in Fig. 4, which indicates
1650041-14
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
0
10
20
30
40
50
60
70
80
1 2 3 4 5 6 7 8 9 10 11 12
N um
be r o
f N ur
se s
Week
LT LTUU WbW
Fig. 4. Average number of nurses under week-by-week (WbW), long-term (LT) planning and long- term planning under uncertainty (LTUU) for instances with 400 initial patients (note that weeks 9–12 average only four instances).
the average number of nurses used per week for all instances with 400 initial patients. These instances showed the greatest variability in number of nurses from the begin- ning of the problem horizon to the end.
The initial set of template routes only visit the set of known patients and the dummy patients, such that the initial number of nurses is less than the initial number used with LT. When patients begin care in one of the last few weeks of a planning period, and these patients are in excess of the expected number of patients, they are inserted into the nearest daily routes the week that their period of care begins. This results in a greater number of nurses used in the final weeks in comparison to LT. Using LT, the template routes visit all patients, including those not visited until much later in the planning horizon. As a result, there may be template routes that contain patients whose period of care begins early in the planning horizon and patients whose period of care begins much later. While there may be a greater number of routes initially, the total number of nurses used is much more consistent throughout the problem horizon because of these template routes. Achieving the consistency found through the use of LT is desirable as it offers the nurses a standard workload from week to week and allows the provider to more easily staff their operation, all while providing a consistent level of service to patients.
The characteristics of the problem may have an impact on the differences in the number of nurses utilized. Table 3 presents the number of nurses used averaged over the instances with shared characteristics, including the geographic setting of
1650041-15
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
Table 3. Average number of nurses used per week classified by instance characteristics.
Instance type WbW LT LTUU
Average Standard Average Standard Average Standard deviation deviation deviation
Urban 39.60 4.07 36.73 0.76 36.67 4.55 Intermediate 44.41 4.37 40.03 1.61 36.56 5.12 Rural 49.37 4.14 45.37 1.99 37.70 5.29
200 Patients 30.91 3.19 27.86 1.27 25.94 3.78 235–310 Patients 40.02 3.15 36.69 1.37 32.72 3.67 400 Patients 62.45 6.24 57.58 1.72 52.26 7.50
35 Begin/End 39.99 2.30 36.14 1.28 31.71 2.71 55 Begin/End 42.63 3.32 39.09 1.49 34.81 3.99 70 Begin/End 44.76 4.51 41.06 1.32 36.87 5.29 110 Begin/End 50.46 6.64 46.56 1.71 44.52 7.95
patients, the number of initial patients and the number of patients that begin and end service over the problem horizon. Most dramatic here is the difference between urban, intermediate and rural settings. As the patients are more densely located, it is less costly to replace a patient finishing service with one beginning service on an established route. Therefore, the WbW algorithm is more effectively able to limit the number of nurses used, even without forecasting patient demand, with results that are closer to LT and LTUU. Home health care providers in cities that are more dense may be able to achieve a reasonable level of service without a great deal of forecasting. However, increasing the radius of the patient market from five to 25 miles has a considerable effect, and providers in rural settings must be more aware of customer trends.
While the impact of the number of initial patients is not as significant, the results behave as might be expected. As the number of patients increases, the number of nurses required does as well and the difference between the various algorithms increases in proportion. Interestingly, as the number of patients beginning or ending service increases, the difference decreases, particularly between LTUU and the other two algorithms. As more patients are introduced over time, it becomes more difficult to forecast all of these patients and the benefit of using LTUU diminishes. The routes created for dummy patients are useful, but eventually there are simply too many unpredicted patients and new routes must be added.
It is evident that planning over a longer period can improve metrics associated with staffing. Determining the impact on routing of the nurses is also of interest. Table 4 reports the total time nurses spend in transit during the planning horizon. With all patient requests known at the time of planning, LT outperforms both WbW and LTUU. This is expected, as LT considers all future requests and creates routes that best fit the entire demand plan. By anticipating future service requests with an estimate of the expected number of patients to be seen in a week, LTUU was also able to provide savings in travel time over WbW. Holding spots with dummy
1650041-16
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Table 4. Percentage improvement in travel time with long- term planning under uncertainty (LTUU) and long-term (LT) planning over week-by-week (WbW) planning.
Instance Travel time (hours) % improvement over WbW
WbW LT LTUU LT LTUU
200-35U8 567 532 539 6.1% 4.9% 200-70U8 626 568 608 9.2% 2.9% 200-35l8 1093 948 1001 13.3% 8.4% 200-70l8 1213 1013 1118 16.5% 7.8% 200-35R8 1284 1133 1158 11.7% 9.8% 200-70R8 1508 1197 1360 20.7% 9.9% 200-55U12 886 812 868 8.3% 2.0% 200-110U12 1088 1047 1082 3.7% 0.5% 200-55l12 1655 1455 1571 12.1% 5.1% 200-110l12 1791 1460 1667 18.5% 6.9% 200-55R12 2371 1922 2061 18.9% 13.1% 200-110R12 2700 2180 2483 19.3% 8.0% 235-35U8 651 631 621 3.1% 4.6% 270-70U8 791 742 762 6.2% 3.6% 235-35l8 1252 1135 1108 9.3% 11.5% 270-70l8 1497 1285 1367 14.1% 8.7%
235-35R8 1448 1297 1276 10.4% 11.9% 270-70R8 1900 1566 1657 17.6% 12.8% 255-55U12 1087 1033 1051 4.9% 3.3% 310-110U12 1487 1402 1448 5.7% 2.7% 255-55l12 2014 1790 1854 11.1% 7.9% 310-110l12 2408 2099 2228 12.8% 7.5% 255-55R12 2863 2416 2499 15.6% 12.7% 310-110R12 3626 3077 3345 15.1% 7.8% 400-35U8 1094 1038 1050 5.1% 4.0% 400-70U8 1209 1204 1193 0.4% 1.3% 400-35l8 2080 1851 1879 11.0% 9.7% 400-70l8 2249 1970 2058 12.4% 8.5% 400-35R8 2452 2172 2103 11.4% 14.2% 400-70R8 2899 2423 2642 16.4% 8.9% 400-55U12 1645 1621 1590 1.4% 3.3% 400-110U12 2026 2042 2049 −0.7% −1.1% 400-55l12 3134 2836 2886 9.5% 7.9% 400-110l12 3367 2966 3210 11.9% 4.7% 400-55R12 4374 3665 3933 16.2% 10.1% 400-110R12 5076 4108 4760 19.1% 6.2%
Average 1928 1684 1780 11.1% 7.0%
patients has a clear impact on routing. However, further improving the forecasting of future patient requests can lead to even greater cost savings.
As with the number of nurses, the savings in travel costs may vary based on problem characteristics. Table 5 presents the travel time averaged over instances with shared characteristics, including the geographic setting of patients, the number of initial patients and the number of patients that begin and end service over the
1650041-17
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
Table 5. Percentage improvement in travel time classified by instance characteristics.
Instance Travel time (hours) % improvement over WbW
WbW LT LTUU LT LTUU
Urban 1096 1056 1072 3.7% 2.2% Intermediate 1979 1734 1829 12.4% 7.6% Rural 2708 2263 2440 16.4% 9.9%
200 Patients 1398 1189 1293 15.0% 7.5% 235–310 Patients 1752 1539 1601 12.1% 8.6% 400 Patients 2634 2325 2446 11.7% 7.1%
35 Begin/End 1324 1193 1193 9.9% 9.9%
55 Begin/End 2225 1950 2035 12.4% 8.6% 70 Begin/End 1544 1330 1418 13.9% 8.1% 110 Begin/End 2619 2265 2475 13.5% 5.5%
problem horizon. Again, the dispersion of patients has the most significant impact. As a rural setting has greater distances and a sparser patient network, there are more opportunities to reduce the distance nurses must travel by limiting the number of routes and efficiently assigning new patients to routes. The characteristics associated with the number of patients offer less consistency. While there was a slight trend in a decrease in the benefit of using LT as the number of patients increased, in general this did not significantly impact the results. This is to be expected as varying the location of patients should have more of an effect on differences in travel time than simply changing the number of patients.
Increasing the number of patients beginning and ending service has a visible impact as well. As more patients are introduced over time, adjusting the routes to serve real patients converted from dummy patients becomes more difficult and the benefit of using LTUU diminishes relative to WbW. WbW also struggles to efficiently route the new patients compared to LT.
The instances tested show the influence that the number of patients, location of patients, frequency with which patients are added or dropped from the schedule and length of time horizon have on the results. It is also of interest to determine how the results change as the probability of a patient requesting service changes. For the presented results, the probability of a patient requiring service on any day is 70%. In order to evaluate this parameter, probabilities of 60% and 80% are tested for those instances with 235–310 initial patients.
Table 6 presents the average number of nurses used per week when a patient requires service with a probability of 60%, 70% and 80%. As the probability increases and more service is demanded, more nurses are needed. This increase is greater for the results found using the LT and LTUU algorithms. With the rise in this probability, the set of patients requiring service on a daily basis becomes more consistent and the routes are less likely to change from day to day or week to week. Therefore, the WbW algorithm does not have to adjust the number of nurses used
1650041-18
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Table 6. Average number of nurses used per week for 60%, 70% and 80% probability that a patient requires service.
Instance 60% 70% 80%
WbW LT LTUU WbW LT LTUU WbW LT LTUU
235-35U8 27.5 24.0 23.6 29.5 26.7 25.9 30.1 28.4 27.7 270-70U8 33.9 29.3 31.5 35.2 31.1 32.4 37.2 35.1 34.1 235-35l8 32.1 27.7 23.8 33.8 30.8 26.3 34.6 32.0 28.1 270-70l8 39.7 32.9 30.8 41.4 36.8 32.9 41.7 38.5 34.5 235-35R8 35.4 32.1 26.2 37.0 33.7 28.9 38.5 35.9 28.8 270-70R8 43.5 38.1 28.9 44.7 41.5 32.2 46.0 41.3 34.5 255-55U12 32.0 26.4 28.9 33.1 29.8 30.7 33.9 31.1 31.9 310-1 10U12 43.4 38.4 40.1 44.0 40.6 40.6 44.6 43.2 42.3 255-55l12 34.9 30.0 28.1 37.3 34.3 30.0 37.8 34.5 31.3 310-110l12 46.8 40.2 37.5 47.4 43.2 39.4 47.9 45.1 41.8 255-55R12 41.6 36.7 27.7 42.3 39.4 30.7 44.0 37.1 34.4 310-110R12 53.5 46.8 39.7 54.5 52.3 42.9 55.5 54.0 44.8
Average 38.7 33.6 30.6 40.0 36.7 32.7 41.0 38.0 34.5
per week and is able to more closely duplicate what the other algorithms do. This indicates that the more inconsistent the client base is in requiring service on a daily basis, the more important it is that forecasting is incorporated into the routing algorithm.
The difference in travel time between algorithms is also impacted by adjusting this probability. Table 7 provides the percentage improvement in travel time with the LTUU and LT algorithms over WbW for 60%, 70% and 80% probability that a
Table 7. Percentage improvement in travel time with long-term plan- ning under uncertainty (LTUU) and long-term (LT) planning over week-by-week (WbW) planning for 60%, 70% and 80% probability that a patient requires service.
Instance 60% 70% 80% % improvement % improvement % improvement
over WbW over WbW over WbW
LT LTUU LT LTUU LT LTUU
235-35U8 6.3% 6.1% 3.1% 4.6% 1.9% 1.5% 270-70U8 8.1% 2.0% 6.2% 3.6% −0.3% −0.2% 235-35l8 16.9% 14.8% 9.3% 11.5% 6.8% 5.3% 270-70l8 19.4% 11.3% 14.1% 8.7% 7.6% 6.3% 235-35R8 15.6% 17.8% 10.4% 11.9% 6.9% 10.0% 270-70R8 21.5% 17.0% 17.6% 12.8% 10.7% 9.3% 255-55U12 8.6% 2.8% 4.9% 3.3% 2.5% 1.7% 310-110U12 7.7% 4.2% 5.7% 2.7% 1.3% 1.4% 255-55l12 15.9% 9.4% 11.1% 7.9% 5.6% 5.0% 310-110l12 15.7% 9.2% 12.8% 7.5% 8.3% 5.1% 255-55R12 20.0% 18.2% 15.6% 12.7% 13.3% 7.3% 310-110R12 22.2% 12.8% 15.1% 7.8% 14.3% 7.0%
Average 14.8% 10.5% 10.5% 7.9% 6.6% 5.0%
1650041-19
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
patient requires service (the actual distances for 60% and 80% are on a comparable scale to those reported for 70%). The benefit of LTUU and LT over WbW reduces considerably as the probability increases. As with the difference in number of nurses, the WbW algorithm has to deal with less change from week to week with more con- sistent patient care requirements. The advantages of the LT and LTUU algorithms are somewhat limited under these circumstances.
Another parameter that may be evaluated is the length of patient visit. The sensitivity to this parameter is tested by decreasing visit time from 60 to 30 min for the instances with 235–310 patients. The results show little sensitivity to a change in visit time. Table 8 provides the average number of nurses used per week with each algorithm. The number of nurses used is considerably smaller as a nurse may serve many more patients with the shortened visit time. However, the ratio between algorithms is very similar, with LTUU resulting in the fewest average nurses used per week. LTUU also had similar variability in this value to WbW.
The differences in travel time were also similar to those with 60 min visit times. Table 9 presents the travel time differences for each algorithm. The distance trav- eled with each algorithm is shorter as fewer routes are necessary, resulting in less travel out of and into the depot. Both LTUU and LT again outperformed WbW, particularly in the intermediate setting. However, the LT algorithm performed even better relative to the other algorithms with 30 min patient visits. With the shorter stop times, this problem more closely resembles a pure routing problem. Under these circumstances, the advance planning of the LT algorithm is particularly use- ful. With visit times that are 60 min, assigning patients to nurses is more like a capacity-planning problem, particularly in an urban setting where travel times are relatively short. However, with 30 min (or shorter) visit times, routing is more important and a better method for modeling uncertainty with respect to the location
Table 8. Average number of nurses used per week for 30 min patient visits with week-by- week (WbW), long-term (LT) and long-term planning under uncertainty (LTUU) planning.
Instance WbW LT LTUU
Average Standard Average Standard Average Standard deviation deviation deviation
235-35U8 17.0 2.59 13.3 0.83 13.5 1.58 270-70U8 20.7 3.81 16.6 0.64 15.5 2.09 235-35l8 20.8 2.13 19.0 0.54 17.4 3.03 270-70l8 27.2 3.53 22.9 0.83 19.6 5.09 235-35R8 27.5 0.92 24.9 1.24 19.6 1.05 270-70R8 32.0 2.25 30.8 1.26 27.9 0.52 255-55U12 19.0 2.57 14.8 1.05 15.3 1.96 310-110U12 27.7 5.03 20.8 0.48 20.6 2.34 255-55l12 23.7 2.63 19.8 0.53 18.8 4.17 310-110l12 30.3 4.96 24.9 0.56 23.3 5.95 255-55R12 32.5 1.71 32.6 1.32 20.8 1.71 310-110R12 40.9 2.35 39.9 2.12 34.0 2.57 Average 26.6 2.9 23.3 0.9 20.5 2.7
1650041-20
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Table 9. Percentage improvement in travel time for 30 min patient visits with long-term planning under uncertainty (LTUU) and long-term (LT) planning over week-by-week (WbW) planning.
Instance Travel time (hours) % improvement over WbW
WbW LT LTUU LT LTUU
235-35U8 526 449 491 14.7% 6.5% 270-70U8 666 538 638 19.1% 4.2% 235-35l8 902 702 864 22.2% 4.2% 270-70l8 1246 878 1153 29.5% 7.5% 235-35R8 1116 1003 1007 10.2% 9.7% 270-70R8 1563 1385 1543 11.4% 1.2% 255-55U12 868 713 821 17.8% 5.4% 310-110U12 1280 956 1223 25.3% 4.5% 255-55l12 1593 1195 1456 25.0% 8.6% 310-110l12 2027 1345 1843 33.6% 9.1% 255-55R12 2203 1986 2002 9.9% 9.1% 310-110R12 2646 2513 2551 5.0% 3.6%
Average 1386 1139 1299 18.6% 6.1%
of future patients may be beneficial. Interestingly, as the distances grow with the rural instances, the improvement with the LT algorithm is similar to the 60 min visit time instances. Fewer patients may be visited on a route with rural distances and the problem again is more like a capacity-planning one.
The sensitivity of LTUU to the expected number of patients to visit each week is also tested. For each instance, LTUU is executed with the expected number of weekly patients both above and below the actual average number of weekly patients and the results for instance 200I-70-R-8H are reported in Table 10 (other instances have similar results). In the first column the value of the expected number of weekly patients is compared to the actual average number of patients seen in a week for that instance. Not surprisingly, LTUU performs best when the two values are equal, but even when the expected value is skewed from the average, LTUU is superior to WbW, suggesting that an exact forecast of the average number of weekly patients is not necessary for the method to yield savings.
Table 10. Percentage change in cost between LTUU and WbW with adjusted expected number of patients.
Expected number of Travel time (hours) % decrease patients in a week (E)
WbW LTUU
Average −10 1,625.00 13.6% Average −5 1,633.16 13.2% Average 1,880.60 1,601.70 14.8% Average +5 1,660.68 11.7% Average +10 1,631.28 13.3%
1650041-21
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
The results of the computational study, in terms of the reductions in staffing and travel time, are summarized in Figs. 5(a) and 5(b). To be precise, if N W bWUrban represents the average number of nurses used in a solution produced by the WbW algorithm (N LTUrban, N
LT UU Urban defined similarly), then Fig. 5(a) reports N
LT Urban/N
W bW Urban
and N LT UUUrban /N W bW Urban (and reports similar statistics for other instance parameters).
Similarly, if T T W bWUrban represents the average time nurses spend traveling in a solution
(a)
(b)
Fig. 5. Reductions over WbW strategy. (a) Staffing and (b) travel time.
1650041-22
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
produced by the WbW algorithm (and simiilar terms for LT and LTUU) then Fig. 5(b) reports T T LTUrban/T T
W bW Urban. With respect to staffing, LTUU leads to the
greatest reductions in staffing for Rural geographies and 30 minute visit times. Interstingly, the number of patients seen does not appear to have a great impact on the reduction in staffing. Turning to travel times, LTUU is very robust with respect to instance parameters; reducing travel times by 5–10% for all settings other than in Urban geographies. In general, the results indicate that organizations that serve large regions would benefit greatly (through reduced staffing and travel times) from either better forecasting or anticipating future customer requests.
6. Conclusions and Future Work
Home health care agencies can benefit from planning methods that enable them to reduce costs while still providing high levels of continuity of care, a metric often associated with quality care. In this paper we first illustrate that significant savings in travel time and nurse-staffing requirements can be realized by planning for a period of time that is much longer than what is typically seen in the vehicle routing literature. In the course of doing so we present an enhancement of an existing heuristic for the Consistent VRP that enables it to find better solutions in less time when applied to problems with variability in the amount of service required by each patient. As tactical planning introduces considerable uncertainty into the problem, we present a long term planning strategy that anticipates future service requests based on an easily calculated point estimate of those requests. We show computationally that this strategy is superior to planning on a rolling horizon, week by week basis.
There are multiple avenues for extending the research presented in this paper. Within the context modeling home health care operational realities more closely, we can modify the planning methods to take into account skill and licensing require- ments when assigning a patient to a nurse and support nurses departing from mul- tiple depots. Within the context of enhancing the performance of the method that anticipates future patient requests we intend to study other ways of modeling the location of a future patient. Lastly, the problem itself could be viewed as a dynamic or online scheduling and routing problem, which is how many agencies make schedul- ing decisions now.
References
Balinsky, W (1999). Pediatric home care: Reimbursement and cost benefit analysis. Journal of Pediatric Health Care, 13(6), 288–294.
Begur, S, D Miller and J Weaver (1997). An integrated spatial DSS for scheduling and routing home-health-care nurses. Interfaces, 27(4), 35–48.
Beltrami, E and L Bodin (1974). Networks and vehicle routing for municipal waste collec- tion. Networks, 4(1), 65–94.
Bennett, AR and AL Erera (2011). Dynamic periodic fixed appointment scheduling for home health. IIE Transactions on Healthcare Systems Engineering, 1(1), 6–19.
1650041-23
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
Bent, R and P Van Hentenryck (2004). Scenario-based planning for partially dynamic vehicle routing with stochastic customers. Operations Research, 977–987.
Benzarti, E, E Sahin and Y Dallery (2013). Operations management applied to home care services: Analysis of the districting problem. Decision Support Systems, 55(2), 587–598.
Bertels, S and T Fahle (2006). A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem. Computers & Operations Research, 33(10), 2866– 2890.
Braekers, K, RF Hartl, SN Parragh and F Tricoire (2015). A bi-objective home care scheduling problem: Analyzing the trade-off between costs and client inconvenience. European Journal of Operational Research.
Campbell, A and M Savelsbergh (2005). Decision support for consumer direct grocery initiatives. Transportation Science, 39(3), 313–327.
Cardoso, Y, MD Oliveira, A Barbosa-Póvoa and S Nickel (2015). An integrated approach for planning a long-term care network with uncertainty, strategic policy and equity considerations. European Journal of Operational Research, 247(1), 321–334.
Carello, G and E Lanzarone (2014). A cardinality-constrained robust model for the assign- ment problem in home care services. European Journal of Operational Research, 236(2), 748–762.
Cheng, E and J Rich (1998). A Home Health Care Routing and Scheduling Problem (Rice University, Texas, Tech. Rep. TR98-04).
Eveborn, P, P Flisberg and M Rönnqvist (2006). LAPS CARE — an operational system for staff planning of home care. European Journal of Operational Research, 171(3), 962–976.
Francis, P, K Smilowitz and M Tzur (2006). The period vehicle routing problem with service choice. Transportation Science, 40, 439–454.
Francis, P, K Smilowitz and M Tzur (2007). Flexibility and complexity in periodic distri- bution problems. Naval Research Logistics, 54, 136–150.
Gendreau, M, G Laporte and R Séguin (1996). Stochastic vehicle routing. European Jour- nal of Operational Research, 88(1), 3–12.
Groër, C, B Golden and E Wasil (2009). The consistent vehicle routing problem. Manu- facturing & Service Operations Management, 11(4), 630–643.
Hertz, A and N Lahrichi (2009). A patient assignment algorithm for home care services. Journal of the Operational Research Society, 60(4), 481–495.
Home Care Association of New York State and New York Association of Homes & Services for the Aging (2011). State budget cuts have imperiled New York’s home health care delivery system. (Technical report).
Jaillet, P (1988). A priori solution of a traveling salesman problem in which a random subset of the customers are visited. Operations Research, 36(6), 929–936.
Jee, SH, and MD Cabana (2006). Indices for continuity of care: A systematic review of the literature. Medical Care Research and Review, 63(2), 158–188.
Kergosien, Y, C Lenté and J Billaut (2009). Home health care problem: An extended mul- tiple traveling salesman problem. In 4th Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA’09), Dublin (Ireland), pp. 10–12.
Kovacs, AA, BL Golden, RF Hartl and SN Parragh (2014). Vehicle routing problems in which consistency considerations are important: A survey. Networks, 64(3), 192–213. Available at http://dx.doi.org/10.1002/net.21565 doi: 10.1002/net.21565.
Lanzarone, E and A Matta (2014). Robust nurse-to-patient assignment in home care ser- vices to minimize overtimes under continuity of care. Operations Research for Health Care, 3(2), 48–58.
1650041-24
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
Planning Strategies for Home Health Care Delivery
Li, F, B Golden and E Wasil (2005). Very large-scale vehicle routing: New test problems, algorithms, and results. Computers & Operations Research, 32(5), 1165–1179.
Liu, R, X Xie and T Garaix (2014). Hybridization of tabu search with feasible and infeasible local searches for periodic home health care logistics. Omega, 47, 17–32.
Mankowska, DS, F Meisel and C Bierwirth (2014). The home health care routing and scheduling problem with interdependent services. Health Care Management Science, 17(1), 15–30.
National Association for Home Care and Hospice (2010). Basic Statistics About Home Care (Technical report).
Russell, D, RJ Rosati, P Rosenfeld and JM Marren (2011). Continuity in home health care: Is consistency in nursing personnel associated with better patient outcomes? Journal for Healthcare Quality, 33(6), 33–39.
Russell, R and W Igo (1979). An assignment routing problem. Networks, 9(1), 1–17. Saultz, JW and W Albedaiwi (2004). Interpersonal continuity of care and patient satis-
faction: A critical review. The Annals of Family Medicine, 2(5), 445–451. Saultz, JW and J Lochner (2005). Interpersonal continuity of care and care outcomes: A
critical review. The Annals of Family Medicine, 3(2), 159–166. Smilowitz, K, M Nowak and T Jiang (2013). Workforce management in periodic delivery
operations. Transportation Science, 47(2), 214–230. Steeg, J and M Schröder. A hybrid approach to solve the periodic home health care problem
(2008). Operations Research Proceedings 2007, pp. 297–302. Van Walraven, C, N Oake, A Jennings and AJ Forster (2010). The association between
continuity of care and outcomes: A systematic and critical review. Journal of Eval- uation in Clinical Practice, 16(5), 947–956.
Zhong, H, R Hall and M Dessouky (2007). Territory planning and vehicle dispatching with driver learning. Transportation Science, 41(1), 74–89.
Biography
Mike Hewitt PhD, is an Associate Professor in the Information Systems and Supply Chain Management Department in the Quinlan School of Business at Loy- ola University Chicago. His research includes developing quantitative models of decisions found in the transportation and supply chain management domains, par- ticularly in freight transportation and home delivery. His work has assisted the decision-making of companies such as Exxon Mobil, Saia Motor Freight, and Yel- low Roadway. He has expanded his area of expertise to include workforce planning, including working on multi-disciplinary projects at the intersection of operations management and cognitive psychology. His research has been published in Trans- portation Science, European Journal of Operational Research, Computers & Opera- tions Research, Omega and INFORMS Journal on Computing. Before entering the PhD program at Georgia Tech, Dr. Hewitt worked as a software engineer, contribut- ing to the development of software to support consumer set-top boxes and content delivery to LED signs in mass transit stations.
Maciek Nowak, Ph.D., is an Associate Professor in the Information Systems and Operations Management Department in the Graduate School of Business at Loy- ola University. Dr. Nowak received his Ph.D. in Industrial and Systems Engineer- ing from Georgia Tech and his M.S.E. and B.S.E. degrees from the University
1650041-25
2nd Reading September 15, 2016 11:24 WSPC/S0217-5959 APJOR 1650041.tex
M. Hewitt, M. Nowak & N. Nataraj
of Michigan. He joined Loyola from Georgia Southern University where he was an Assistant Professor of Logistics. He was also a visiting scholar at Northwestern Uni- versity and the University of Tunis-El Manar. Dr. Nowak has received grants for research from the Federal Highway Administration, the U. S. Department of Trans- portation and the U. S. State Department. Dr. Nowak’s current research focuses on the use of various heuristic optimization techniques for vehicle routing problems. He is also interested in the adoption of tracking technologies within the supply network, as well as more general strategic supply chain problems. His research has been pub- lished in Transportation Science, Transportation Research Part E, European Jour- nal of Operational Research, Computers & OR, and the Journal of Transportation Management.
Nisha Nataraj is a PhD student and Research Assistant in the Industrial and Sys- tems Engineering department at North Carolina State University. She received her Masters in Industrial Engineering from Rochester Institute of Technology in 2012. Her research interests include applications of healthcare in simulation, predictive analytics and vehicle routing.
1650041-26
Copyright of Asia-Pacific Journal of Operational Research is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use.
