Keywords

1 Introduction

Vehicle Routing Problem (VRP) is one of the main problems in logistics and operations research literature. After the first study by Dantzig and Ramsey [7], it has been applied to many fields and many studies have been published by deriving different extensions. Research on multi-featured VRPs, taking into account different features, constraints and systems, has been actively used to elicit realistic determinations and theoretical challenges, and to combine real-life cases and combinations of constraints in practice.

Especially in European countries, increasing the population of elderly people and patients with chronic diseases, having the lower cost compared to the hospital and the developments in health care technologies make the home health care (HHC) more preferable and advantageous. The other advantages of HHC are to cause reduction the patient densities and hospitalization periods in hospitals. In addition, it is allowed for the patients to be treated in their own homes by keeping away from the serious (bedridden and /or chronic) illnesses of hospital environment. Also, HHC, which is the only way to reach some patients and prevents unnecessary occupation of hospitals, draws the attention of the health sector and requires new strategies, policies, arrangements and solution approaches to be developed for arising new needs and problems.

Due to the demands and advantages of the HHC system, many hospitals have HHC departments and give variety of the services to patient their own home through health care staff/team. The team is included doctor, nurse, driver, dietitian, physical therapist, psychologist and the like. They have different qualifications so give variety of services to patient such as bloodletting, examine the patients, take the biological samples, exercise, prepare diet and so on. The staff members/caregivers are typically equipped with cars and other medical equipments and through this car, they make visits between patients’ home and hospital. At the patients’ side, they need specific treatments and this needs should be met by qualified staff members within a given time window.

Home Health Care Routing and Scheduling Problem (HHCRSP) is generally defined as determining which health care staff should be served in the patients who need to be visited by the health caregiver/staff in their homes. The aim of this problem is to minimize the travelling cost or any other selected criteria or to maximize the service quality with considering different constraints during the planning period.

The difference of HHCRSP from classical VRP can be summarized as follows; the need for continuity of care in the health care staff-patient match, the interdependence, separation of services and care services, and the consideration of health caregiver-patient characteristics.

In the HHC system, there is a connection with two main problems; the first one is which caregiver should be sent to the patient and the second one is routing the patients’ visits. These two problems can be handled separately or simultaneously. It is generally considered to be the problem of routing of home health care because of the demand from the patient or due to patients existing in the hospital system and corresponds to the different VRP models in the literature [11].

In this study, a problem definition is made based on real-life case and a mathematical model is proposed that is to route staff members and to schedule single, double and triple service operations for the HCC. This problem is called as HHCRSP. The following sections of the study are as follows. In Sect. 2, literature research for HHCRSP is presented. An extended mathematical model is explained in detail and demonstrated with a descriptive example in Sect. 3. Finally, the conclusion is given in Sect. 4.

2 Literature

In recent years, Home Health Care Routing and Scheduling Problem, which can be considered as an extension of VRP in the health sector, has attracted researchers’ attention. The study that is accepted as the first study is published by Begur et al. [2]. In the following years, many other researchers studies and three review articles were published in 2017 [6, 10, 13]. In these studies, in the literature, mathematical models have variety of objective functions and different constraints are considered thus different solution approaches are developed. In these studies, there are several differences among the proposed models and solution approaches. First one is related to the staff members (homogeneous or heterogeneous), second one is related to the services that are provided by the caregivers (number of the services and simultaneous or precedence services), third one is related to the objective function of the model (minimized travelling time or maximized service quality), fourth one is related to the scheduling time period (short or long term) and the last one is related to the methodology (exact methods and/or heuristics). Homogenous staff member are considered in studies [1, 5, 14]; heterogeneous are taken into consideration in studies [2, 3, 9, 12, 15]. Interdependent services is included to the model in papers [5, 9, 12, 14]. As an objective function, the studies with minimized traveling time/cost is dominant in the literature [1–3, 5, 9, 11, 12, 14, 15] however, the studies with maximized patient satisfaction/quality is rare [4, 8, 16]. Most of the researchers developed their model for short term period [1, 3, 4, 5, 9, 11, 12, 14, 15], with few of them to consider long term period [2, 8, 16]. Finally, the solution method is generally heuristics or metaheuristics [1, 2, 8, 3, 9], there are also studies that used both exact and heuristics methods together [4, 5, 12, 15]. The contribution of this study is extending a mathematical model for the HHCRSP that included time window, heterogeneous staff members and interdependent three consecutive services. Moreover, in order to meet the all patients’ needs, the model is allowed to enable tardiness and the sum of all tardiness is minimized while assigning the patients qualified staff members.

3 Mixed Integer Programming Model for HHCRSP

The problem discussed in this study is a routing and scheduling problem in which the patients are given by four different health care personnel / staff consisting of nurses, nurses and doctors, physiotherapists and dietitians, and there is a interdependency between the services. The objective function of the model is to minimize the total travel time of the staff members while serving the patients as much as possible within the specified time windows. Patients can request single, double or triple services. Within the scope of this study, it is seen that the related services are consecutive and at most three services could be given in consecutive terms.

The information regarding the types of staff members, the services provided is given in Table 1. Also, single, double and triple services are shown in Table 2.

Table 1. The type of staff members and the services they are provided.
Full size table
Table 2. Services based on the set of patients \( (C^{s} ,C^{d} ,C^{t} ) \).
Full size table

3.1 Assumptions

For the mathematical model, the following assumptions are made considering the characteristics of the system.

  • The planning period is one day.

  • All patients should be served during the day.

  • Each patient should be visited by staff member who is qualified to provide the requested service.

  • There are four different types of staff members.

  • The routes of the each staff member start and end in the hospital.

  • Each patient is serviced within the specified period of time (time windows).

  • Patients may request single or multiple services.

  • There is a temporary relationship between services.

  • The services requested by the patients can be given consecutively.

  • Patients are provided with up to three consecutive services.

  • Tardiness is allowed to serve all patients.

3.2 Notation

$$ C = Set\,of\,all\,patients $$
$$ S = Set\,of\,offered\,service \,types $$
$$ V = Set \,of\,staff\,members $$
$$ C^{0} = Set\,of\,all\,locations\,, C^{0} = C \,\mathop \cup \nolimits \,\{ 0\} $$
$$ C^{s} = Set\,of\,single\,service\,patients $$
$$ C^{d} = Set\,of\,double\,service\,patients, C^{d} = C^{sim} \,\mathop \cup \nolimits \,C^{prec} $$
$$ C^{t} = Set\,of\,triple\,service\,patients $$
$$ C^{sim} = Set\,of\,patients\,requiring\,simultaneous\,service $$
$$ C^{prec} = Set\,of\,patients\,requiring\,service\,with\,precedence $$
$$ a_{vs } = \left\{ {\begin{array}{*{20}l} {1, iff\,employee\,v\, \in \,V\, is\, qualified \,to\, provide \,service \,operation \,s\, \in \,S} \hfill \\ {0, \quad \quad \quad \quad \quad \quad \quad \quad \quad otherwise } \hfill \\ \end{array} } \right. $$
$$ r_{is} = \left\{ {\begin{array}{*{20}l} {1, iff \,patient \,i\, \in \,C \,requires\, service\, operation\, s\, \in \,S} \hfill \\ {0, \quad \quad \quad \quad \quad \quad \quad \quad otherwise} \hfill \\ \end{array} } \right. $$
$$ \delta_{i1}^{min} = Minimal\, time\, between\, 1^{st} \, and \,2^{nd} \,service\, start\, times\, at\, patient\, i\, \in \,C^{d} ,C^{t} $$
$$ \delta_{i1}^{max} = Maximal \,time\, between \,1^{st} \, and\, 2^{nd} \, service\, start\, times \,at\, patient \, i\, \in \,C^{d} ,C^{t} $$
$$ \delta_{i2}^{min} = Minimal\, time\, between \,2^{nd} \, and \,3^{rd} \, service\, start \,times\, at\, patient\, i\, \in \,C^{t} $$
$$ \delta_{i2}^{max} = Maximal \,time \,between \,2^{nd} \,and \,3^{rd} \,service \,start \,times \,at \,patient \,i\, \in \,C^{t} $$
$$ [e_{i} ,l_{i} ] = Time \,window \,of \,patient \,i\, \in \,C $$
$$ d_{ij} = Travelling \,distance\, between \,locations\, i \,and\, j;\, i, j\, \in \,C^{0} $$
$$ p_{is} = Processing \,time \,of \,service \,operation \,s \,at \,patient \, i\, \in \,C $$
$$ x_{ijvs} = \left\{ {\begin{array}{*{20}l} {1, iff\, staff\, member \,v \,moves \,from \,i\, to\, j \,for \,providing\, service\, operation \,s} \hfill \\ {0, \quad \quad \quad \quad otherwise } \hfill \\ \end{array} } \right. $$
$$ t_{ivs } = Start\, time \,of \,service\, operation \,s \,at patient\, i\, provided\, by \,staff\, member\, v $$
$$ z_{is} = Tardiness\, of \,service \,operation \,s \,at \,patient \,i $$

3.3 Mathematical Model

A mathematical model is extended based on the model proposed by Mankowska et al. [12], considering the characteristic of the pilot hospital. The model is explained in detail as follows.

$$ min \,Z = \lambda_{1} D + \lambda_{2} T + \lambda_{3} T^{max} . $$
(1)

subject to

$$ D = \mathop \sum \limits_{v \in V} \mathop \sum \limits_{{i \in C^{0} }} \mathop \sum \limits_{{j \in C^{0} }} \mathop \sum \limits_{s \in S} d_{ij} . x_{ijvs} . $$
(2)
$$ T = \mathop \sum \limits_{i \in C} \mathop \sum \limits_{s \in S} z_{is} . $$
(3)
$$ T^{max} \ge z_{is} \forall \,i \in C, s \in S . $$
(4)
$$ \mathop \sum \limits_{{i \in C^{0} }} \mathop \sum \limits_{s \in S} x_{0ivs } = \mathop \sum \limits_{{i \in C^{0} }} \mathop \sum \limits_{s \in S} x_{i0vs } = 1\quad \forall v \in V . $$
(5)
$$ \mathop \sum \limits_{{j \in C^{0} }} \mathop \sum \limits_{s \in S} x_{jivs } = \mathop \sum \limits_{{j \in C^{0} }} \mathop \sum \limits_{s \in S} x_{ijvs } \quad \forall \, i \in C, v \in V . $$
(6)
$$ \sum\nolimits_{v \in V} {\sum\nolimits_{{j \in C^{0} }} {a_{vs } . x_{jivs} = r_{is} } \quad \forall \,i \in C, s \in S} $$
(7)
$$ \begin{aligned} t_{{ivs_{1} }} + & p_{{is_{1} }} + d_{ij} \le t_{{jvs_{2} }} + M \left( {1 - x_{{ijvs_{2} }} } \right) \\ & \forall \, i \in C^{0} , j \in C, v \in V, s_{1} ,s_{2} \in S . \\ \end{aligned} $$
(8)
$$ t_{ivs } \ge e_{i} \quad \forall \,i \in C, v \in V, s \in S . $$
(9)
$$ t_{ivs } \le l_{i} + z_{is} \quad \forall \,i \in C, v \in V, s \in S . $$
(10)
$$ \begin{aligned} t_{{iv_{2} s_{2} }} - & t_{{iv_{1} s_{1} }} \ge \delta_{i1}^{min} - M \left( {2 - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{1} s_{1} }} - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{2} s_{2} }} } \right) \\ & \forall \,i \in C^{d} ,C^{t} , v_{1} ,v_{2} \in V,s_{1} , s_{2} \in S:s_{1} < s_{2} . \\ \end{aligned} $$
(11)
$$ \begin{aligned} t_{{iv_{2} s_{2} }} - & t_{{iv_{1} s_{1} }} \le \delta_{i1}^{max} + M \left( {2 - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{1} s_{1} }} - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{2} s_{2} }} } \right) \\ & \forall \,i \in C^{d} ,C^{t} , v_{1} ,v_{2} \in V,s_{1} , s_{2} \in S:s_{1} < s_{2} . \\ \end{aligned} $$
(12)
$$ \begin{aligned} t_{{iv_{3} s_{3} }} - & t_{{iv_{2} s_{2} }} \ge \delta_{i2}^{min} - M \left( {2 - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{2} s_{2} }} - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{3} s_{3} }} } \right) \\ & \forall \,i \in C^{t} , v_{2} ,v_{3} \in V,s_{2} , s_{3} \in S:s_{2} < s_{3} . \\ \end{aligned} $$
(13)
$$ \begin{aligned} t_{{iv_{3} s_{3} }} - & t_{{iv_{2} s_{2} }} \le \delta_{i2}^{max} + M \left( {2 - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{2} s_{2} }} - \mathop \sum \limits_{{j \in C^{0} }} x_{{jiv_{3} s_{3} }} } \right) \\ & \forall \,i \in C^{t} , v_{2} ,v_{3} \in V,s_{2} , s_{3} \in S:s_{2} < s_{3} . \\ \end{aligned} $$
(14)
$$ x_{ijvs } \in \left\{ {0, a_{vs} .r_{js} } \right\} \forall \,i,j \in C^{0} , v \in V, s \in S . $$
(15)
$$ t_{ivs } , z_{is} \ge 0\quad \forall \,i \in C^{0} , v \in V, s \in S . $$
(16)

In this study, three different performance measures are considered. The first one is indicated by D which is the total distance traveled by all staff members, second one is denoted by T and it is the total tardiness of services that start after the time windows and the last one is indicated by Tmax and measures the maximal tardiness noticed all service operations. The objective function shown in Eq. (1) is weighted and reflected the combination of these three performance measures. According to the decision maker, coefficients of the function can be modified. In constraints (2)–(4), we can see the determination of the performance measures. Route of each staff member starts and ends at the central office (hospital) and this condition is ensured by constraints (5). Constraints (6), keeps the network flow even and constant. Constraints (7) guarantee that every service operation s is provided by exactly one qualified staff member. Starting time of service operations is calculated in constraints (8) considering processing time of the service and travelling times between locations. Constraints (9) and (10) are time windows and also calculate the tardiness of the services. Constraints (11)–(14) show the temporal interdependencies for the double and triple service operations. Minimal time distance between the service start times is ensured by constraints (11) and (13); when maximal time distance is ensured by constraints (12) and (14). Constraint (15), determined the decision variable of the route. Lastly, constraint (16) is a non-negativity constraint for the other decision variables.

3.4 Example

To demonstrate the process of the extended model, a problem instance with nine patients, four services and four types of staff members is created. The locations of the hospital and the patients are generated randomly in 50x50 distance units. Travelling time is assumed to be the proportional to the travelling distance and it is Euclidean. Qualifications of the staff members, service requirements of the patients, time windows and time distances between services are displayed in Tables 3 and 4 respectively. There is six single service patients, one double service patients and two triple service patients. Processing time is assumed to be 10-time units for all service types. The weights of the each objective function subgoals are set as equal. The instance problem is solved using IBM ILOG CPLEX Optimization Studio linear programming software package Version 12.6.1 in the computer that is Intel® Core™ i3-3217U CPU @1.80 GHz, 4.00 GB Ram, 64-bit Operating System, x63-based processor. The optimal routing of the instance and the time space diagram of this solution is shown in the Figs. 1 and 2 respectively.

Table 3. Qualification of staff members.
Full size table
Table 4. Service requirements of the patients.
Full size table
Fig. 1.
figure 1

Optimal routing of the staff members for instance.

Full size image
Fig. 2.
figure 2

Time space diagram of the optimal solution for instance.

Full size image

4 Conclusion

HHCRSP is an important problem for many countries, especially European countries with high elderly population. In the literature, the number of studies on this subject has increased in recent years. In this study, a mathematical model for the home health care routing and scheduling problem is proposed with interdependent services. In real life, services that provided by health care staff members is diverse because of the patients needs and can be performed by at most three staff members simultaneously or consecutively. Therefore, this situation is considered in the mathematical model and variables to reflect this real-life case are created. Especially when the increasing demand and advantages of the HHC are taken into consideration, it is seen that many hospitals now have HHC departments and after this stage, many problems has arisen in the system. For these problems, researchers from different disciplines, especially industrial engineers, should make suggestions and develop approaches for the solutions.

For this purpose, in this study first the mathematical models for HHCRSP is considered as an extension of the VRP and the existing literature is investigated. Then an extended model is proposed for this problem. The proposed model is run for a sample problem using the data from the pilot hospital selected for this research. For staff members; acceptable travelling cost, for patients; reasonable waiting times and tardiness or a combination thereof is observed from the sample problem solutions.

To sum up, the problem defined in this study is HHCRSP, which has a time window, heterogeneous staff members and interdependent services. In the problem, different than the studies in the literature, the situation where three consecutive services can be handled is taken into consideration and the mathematical model is extended.