1 Introduction

Home Care Services (HCS) appeared in France and the United States of America in the 1920s, which was progressively adopted by other countries (cf. Callanquin et al. 2001; Chahed et al. 2008). The HCS have been considered as an efficient solution to the organizational and economic problems of the health care systems. The HCS were defined as an alternative that allows providing continuous and coordinated cares at patients’ homes. These structures are defined by Com-Ruelle and Leburn (2003) as “a mini network in a wider one”, since it requires coordination between actors with varied skills. The HCS are taking an increasingly important place in the health care sector. For example, the number of HCS in France has increased threefold between 2005 and 2012 from 123 to 305 services. The number of patients has also increased from 35,037 in 2005 to 100,100 in April 2012 (Redjem 2013). Chevreul et al. (2004a, b, 2005) have shown that the forms of the home care differ from one country to another at the organizational level. These differences between these forms may even appear in a same country, as countries organized as federal states or those based on a policy of provinces (Abelson et al. 2004). The most relevant example is Canada, which is divided into ten heterogeneous provinces and three different federal territories. Consequently, this organization may impact the nature of the care delivered, the accessibility to the home care, etc. Chevreul et al. (2004a, b) have already presented a comparative work between five home care systems, i.e. Australian, Canadian, French, Italian and English. The Table 1 summarizes this comparison.

Table 1 Comparison between the HCS in different countries
Full size table

The HCS differ according to the level of resources integration used to produce care activities. In fact, the HCS can use either internal or external human resources for performing care activities. We have observed three classes of resources’ management in the HCS:

  • The unintegrated model: the main actors are almost external to the structure of the management structure.

  • The semi-integrated model: management structure employees carry out some major activities, while the remaining activities are outsourced.

  • The quasi-integrated model: almost all mobilized human resources are internal to the structure except the patients’ responsible doctor and in many case the nursing caregiver.

In the quasi-integrated model, one of the main operational challenges is the daily caregivers’ (almost all internal) routing problem. This last involves a set of caregivers to serve a number of patients, at different locations, with various demands. The key challenge is to find routes for each caregiver, to satisfy all the patients at a minimal travelled and waited time, without violating customers’ time windows. The complexity of this problem is linked, on one hand, to the consideration of heterogeneous constraints, and on the other hand, to the frequency at which the problem should be solved due to the high pace of patients’ admission per day. To highlight the complexity of the problem of the routing of caregivers in HCS, we will take a simple example. Assume that there are multiple caregivers who all belong to the HCS. Each one follows a route to visit a list of assigned patients. Each patient is available in a given time window. Each visit of a caregiver is characterized by a given care time. In the HCS systems that take in charge complex pathologies, all the patients need multiple visits and some visits should be coordinated. In other words, the coordination between care activities defines the patients’ cares order to be performed. Moreover, several cares should not be planned at the same time.

In previous studies (cf. Redjem et al. 2010, 2011), we developed two based Mixed Integer Linear Programming (MILP) models and we observed that these models were very sensitive to the problem size. In this paper, we briefly recall our previous results obtained by the MILP models regarding the sensitivity of these models to two major axes of complexity. Afterward, we suggest a new approach based on a heuristic to solve the caregivers’ routing problem. This heuristic improves the performances of the classical MILP approaches and solves real world problems, in a short computational time while being insensitive to the complexity axes.

This paper consists of five sections. Firstly, we introduce the subject of study. The second section deals with reviewing the relevant literature of the problem of the routing of caregivers and scheduling the care activities in HCS. In the third section, we recall the main complexity axes of the operations management activity in the HCS. In the fourth section, we illustrate the model definitions and the general approach of the caregivers routing heuristic. Finally, we detail the used instances and the numerical results of the heuristic. Conclusion and perspectives are put forward in the final part.

2 Background

The operations management in HCS can be classified into two levels. The highest level addresses strategic decisions, such as, the resources sizing, the splitting or the districting of the covered space of the HCS and the assignment of resources to the districts. This level can be considered in presence of particular specific constraints, such as the continuity of care, the load balancing between districts, etc. (cf. Blais et al. 2003; Lahrichi et al. 2006; Hertz and Lahrichi 2006; Benzarti et al. 2012, etc.). The second level addresses the operational decisions, such as the visits assignment to caregivers and/or the problem of caregivers routing. In the remainder of this section, some studies on operations management related to the allocation and scheduling of caregivers activities are presented.

A decision support tool was presented by Begur et al. (1997) to design the nurses’ planning of cares and taking into account the patients’ availabilities, requirements, and nurses’ availabilities.

Eveborn et al. (2006) studied a tool based on heuristics for both patient’s allocation and care’s visits scheduling. They introduced some constraints, i.e. particular tasks had to be performed in each visit (i.e., cleaning, washing), in addition to nursing activities. Each staff member had skills and the same care provider always visits the same patient. Their objectives were to reduce the transportation time and to increase the patients’ satisfaction.

Bertels and Fahle (2006) proposed a multi-criteria method for the home care problem. The authors combined linear programming, constraint programming and meta-heuristics (tabou-search). Multiple constraints, such as the patients’ satisfaction, the nurses’ qualifications, the time windows, were taken into account and subjected to minimizing the travelling costs.

A linear integer-scheduling model was developed by Borsani et al. (2006) to support human resources short term planning in HCS. In particular, the model deals with the problem of deciding (1) which human resource should be used and (2) when to execute the service during the planning horizon. The goal was to satisfy the care plan for each patient served by the home care providers. The benefit of the proposed system was an increase in service quality and efficiency.

A novel application for planning and scheduling home caregivers was presented by Akjiratikarl et al. (2007). The model was based on a meta-heuristic approach called Particle Swarm Optimization (PSO). The tool was applied to a genuine situation arising in the UK. The proposed tool optimized the travelling distance, providing that the capacity and time windows constraints of services were not violated.

Using the same approaches based on vehicle routing, Steeg and Schröder (2008) proposed a solution for the planning and scheduling of caregivers. The work horizon of the proposed approach was equal to the care period and subjected to minimizing the caregivers travel duration and the number of caregivers.

The nurses’ routing problem was treated by Cheng and Rich (1998) using Vehicle Routing Problem with Time Windows (VRPTW). The problem was to find an optimal schedule, such that each nurse left home, visited a set of patients within their time windows, took a lunch break, and returned home, all within the nurses’ time window, while minimizing both the overtime for full-time and part-time nurses.

Nickel et al. (2012) resolved the problem of routing and scheduling problems in the context of HCS in Germany. The authors considered the home care problem (HHCP), which sought for a weekly optimal plan. However, in practice, a master schedule was generated and modified to incorporate operational changes. They took this approach into account by looking at the master schedule problem (MSP) and at the operational planning problem (OPP). The problems were solved using different meta-heuristics combined with methods from constraint programming. This allowed a flexible treatment of realistic constraints.

Cappanera and Scutellà (2013) proposed an integrated model that jointly addresses: (1) the assignment of operators to patients guaranteeing the appropriate levels of skill; (2) the visits scheduling in the planning horizon; and (3) the determination of tours set for every day of the week. The proposed variants of the model use the pattern (a priori given profile specifying a possible schedule for a given set of visits possibly characterized by different skills) as a key tool to formulate the problem. The proposed models were tested on a real life problem, and showed that the selection of the pattern generation policy is crucial to solve large instances efficiently.

Lanzarone and Matta (2012a) derived a structural policy to assign a newly admitted patient, while balancing the workload among the operators by minimizing the expected value of a cost function that penalizes the overtime of operators. The workloads already attributed to the operators were assumed to be random variables as they are in practice, while the demand related to the new patient was considered both deterministic and stochastic. Results revealed that new patient’s demand variability was negligible with respect to the variability of the already assigned workloads, and that similar assignments were obtained either in the presence or in the absence of this demand variability.

In another work, Lanzarone et al. (2012b) addressed the resource assignment problem for home care systems. A set of mathematical programming models to balance the workloads of the operators within specific categories was proposed. The models considered several peculiarities of home care services, for instance: the continuity of care constraint, operators’ skills, and the geographical areas to which patients and operators belonged. Given the high variability of patient demands, models were developed under the assumption that patients’ demands were either deterministic or stochastic. The analysis of the results demonstrated the applicability of the proposed models as well as the benefits that stemmed from applying them. Furthermore, the obtained results indicated that an acceptable level of continuity of care could not be obtained without modeling the continuity of care using hard constraints.

Bredström and Rönnqvist (2008) and Rasmussen et al. (2013) resolved the problem of routing and scheduling under time windows, with additional synchronization constraints between several vehicles. The vehicles (caregivers) in the proposed approach started each round from a warehouse to visit the pre-allocated customers. At the end of the round, vehicles returned to the warehouse. The shared customers were only those whose visits needed to be synchronized (i.e. the visits began at the same time). The proposed resolution formulated the precedence as synchronization constraints within an offset. The proposed model was not able to solve problems when multiple visits were allocated to the costumers. This situation was only valid when the patient needed two synchronized visits or sequenced visits.

The management of activities in HCS consists of solving simultaneously a set of NP complex sub problems. This multilevel complex problem consists of the following levels:

  1. (1)

    The HCS structure and the patients location

  2. (2)

    The patients allocation to caregivers

  3. (3)

    Building of the caregivers’ rounds under several constraints

In this paper, we address the third level of the problem of activities’ management, i.e., designing the caregivers’ rounds. Through this literature review, we studied works concerning the routing of the caregivers in HCS. The proposed approaches are diversified and concern several real home care systems. We noted that previous works were modeled and solved using several methods: exact implementations or heuristics. The main constraints taken into account allow respecting both the patients’ and the caregivers’ preferences, in addition to the HCS internal regulation, etc. This problem was generally considered in a classical VRPTW problem.

These studies did not address the temporal dependencies, except (Bredström et Rönnqvist 2008; Rasmussen et al. 2013). The temporal dependencies are sequencing relationship between the care activities for a customer (patient). For instance, the costumers may request many visits by different caregivers. In Bredström et Rönnqvist. (2008), Rasmussen et al. (2013), the shared customers are only those who are temporally dependent. The resolutions are not able to solve problems when multiple visits are allocated to the costumers. This situation is only valid while the costumer (patient) needs at most two synchronized or sequenced visits. However, an investigation that we have conducted with many French home care structures showed that the patients need several care activities per day in the HCS problem. Thus, these structures deal with patients with heavy pathologies. These limitations make inapplicable these approaches for dealing with the complex caregivers routing problem.

In previous studies (cf. Redjem 2013; Redjem et al. 2010, 2011) we have presented two MILP formulations for the caregivers routing problem. The first approach is based on multi-Coordinated Travelling Salesman Problem (m-TSPC). The second one is based on Resources Constrained Project Scheduling Problem (RCPSP).

The first formulation was based on an m-TSPC approach, and was used to evaluate both (1) the impact of the number of care activities per caregiver ratio and (2) the impact of the of the temporal dependencies rate. The second formulation was an RCPSP based approach. The performances of both approaches were compared and limitations were detailed.

Firstly, we have proved that the number of care activities per caregiver ratio is a real complexity axis of the caregivers routing problem (cf. Redjem. 2013; Redjem et al. 2010, 2011). The number of patients per caregiver is, by analogy with the TSP problem, the number of customers per salesman. This one was considered as the main complexity axis. Therefore, the number of patients is also considered as a complexity axis for the caregivers.

Secondly, we have shown that the temporal dependencies between the patients’ activities create strong dependencies between the different rounds. In fact, these constraints interconnect the multiple caregivers’ rounds. By analogy, with temporal dependencies finding a caregiver round needs to find a round for several caregivers interconnected. The higher percentage of temporal dependencies is, the greater the number of caregivers connected is. Indeed, the increase of the number of care activities temporally dependent leads to an increase of complexity.

Through these studies, we have concluded that the exact classical MILP approaches allow achieving optimal solutions for small and low complexity problem. Hence, even for a small problem (i.e., 10 caregivers and 10 patients) when the number of patients per caregiver ratio and/or the temporal dependencies rates increases, these models are not able to reach the optimal solutions in a reasonable computational time. Thus, we find that the complexity of the caregivers routing problem is linked to many axes. These axes will be illustrated in the next section.

3 Complexity axes of the caregivers’ routing problem

Through the analysis realized in Redjem (2013); Redjem et al. (2010, 2011) we have concluded that the complexity management of the caregivers’ activities can be expressed along three axes: (1) the number of activities per caregiver ratio, (2) the temporal dependencies between care activities (sequencing relationship between the care activities for a patient), and also (3) the environment of the HCS (cf. Fig 1).

Fig. 1
figure 1

The complexity axes of the care activities’ management in HCS

Full size image

The temporal dependencies (coordination) constraints: The temporal dependencies are a part of the patients’ therapeutic project. The therapeutic project may impose an order (temporal dependencies) between the activities for a patient, i.e., the care activities should be performed sequentially, i.e. in a predefined order. These temporal dependencies are called “coordination” between care activities.

The ratio of the number of care activities per caregiver: This ratio characterizes the complexity of the Traveling Salesman Problem (TSP); i.e., it characterizes both the caregivers’ workload and the problem of caregivers routing.

The environmental axis: This axis defines the geographical location of the HCS and the patients’ distribution in the covered territory by the HCS. This complexity axis refers to the allocation of resources to the identified districts. Several issues have to be considered, i.e., variation of the workload in a district, patients and the structure or caregivers’ locations, the constraints related to the continuity of care, caregivers’ technical constraints, patients’ and caregivers’ preferences and finally the stress constraints and resources depletion (burnout), etc. This complexity axis was treated in the studies of (Blais et al. 2003; Lahrichi et al. 2006; Hertz et Lahrichi 2006; Benzarti et al. 2012). This one is not covered in this paper.

Indeed, the complexity of the care activities management in HCS is related to three distinct axes (cf. Fig 1). The first one is the number of patients (care activities) per caregiver ratio. This axis is the classical complexity dimension of the TSP problem, i.e., increasing the number of care activities per caregiver ratio increases the complexity of the routing of the caregivers in HCS. The simplest example is the ratio equal to one (one care activity per caregiver). These HCS use external resources to perform the care activities. This system relieves the home care structures from the management of the care rounds.

The temporal dependencies allow linking the caregivers’ rounds, and consequently lead to solving a more complex problem, i.e., the temporal dependencies rate constitutes a complexity axis of the care activities management in HCS.

Finally, the routing of the caregivers is more complex, while the covered area is large. The main studies on the environmental axis consist on the districting of the covered area into multiple districts. This districting decomposes the caregivers’ rounds on multiple independent groups of rounds. The main objective of the districting studies aim at creating independent districts, which reduce the complexity of the caregivers routing problem. For this, the realized works suggest optimizing the caregivers’ patient assignment. In our study, we assess that the assignment of patient to caregivers is considered as a tactical decision and we focus on designing an efficient model for solving the caregivers routing problem.

4 Heuristic approach for the routing of the caregivers in HCS

The alternative to the exact approaches is heuristics and/or meta-heuristics (tabou-search, genetic algorithms, etc.), adapted to the problem of the routing of caregivers in the HCS. In the remainder of this paper, we develop an adapted heuristic to obtain good quality solutions in a reasonable computational time. The Caregivers Routing Heuristic (CRH) is a two-stage heuristic.

4.1 Model definition

In this part, we define the model of the caregivers routing problem. Assuming that, there are multiple caregivers belonging to the HCS. Each one follows a route to visit a list of assigned patients. The assignment of patient to caregivers is considered as a tactical decision. Each patient is available into a given time window. Indeed, in the current practice of homecare, the patients may have many activities other than the care visits. Thus, the patients may impose their time availabilities. Each visit of a caregiver is characterized by a given care time. In our context, all the patients need multiple visits and some visits should be coordinated (the patient’s care should be performed in a defined order). For example, a blood test must be realized before the chemotherapy activities. Such temporal dependencies are imposed in the therapeutic project. Moreover, several cares should not be planned at the same time; no overlap is allowed between care visits. The main assumptions of this problem are:

  • The patients are allocated to caregivers,

  • Each patient requires more than one visit per day,

  • The caregivers’ tours begin and end at the HCS,

  • Care visits for the same patient can be performed in a predefined order (i.e., coordinated),

  • The travel time between patients are known,

  • The care durations for each patient are known and without preemption.

The main variables for the caregivers routing problem allow at a time, defining the caregivers’ start time for each patients, sequencing the caregivers’ and the patients’ visits. The objective of the caregivers routing problem is to minimize the unproductive times, i.e. the caregivers’ travelled and waited times.

4.2 General approach and pseudo-code for CRH

The CRH proceeds in two steps, the first step consists of building the optimal caregivers rounds (i.e., with the shortest travelling times) without patients’ coordination and sequencing constraints. In fact, the first step solves an m-TSP problem where each salesman problem is independent from the other. The second step integrates the relaxed constraints to build the final solution, while satisfying all the problems’ assumptions. The technique used in this step is similar to greedy algorithms, which allows building a solution by taking a series of decisions made at each stage according to a local criterion and without destroying the decisions already taken.

4.2.1 The first step

In this first step, optimal rounds are searched. This search is based on the assessment of all the possible rounds for the caregivers, and then the selection of the round with the shortest travel duration. It is possible to use an enumerative approach because caregivers never visit more than 7 or 8 patients per day. Following this approach, we can obtain an optimal round for each caregiver in terms of travel durations. Thus, the caregivers round solution can be defined as the theoretical lower boundary of the problem. Algorithm 1 illustrates the first step of the CRH. The aim of this step is to determine the shortest caregivers’ rounds.

4.2.2 The second step

The objective of the second step is the introduction of (1) the precedence constraints (sequencing of the care activities) and (2) the coordination constraints (the predefined order between the care activities). The inputs of this second step are the caregivers’ rounds obtained at the first step (the lower bound).

For each patient, the precedence and the coordination between the care activities are checked. If the precedence constraints are not satisfied (i.e. two care activities for a patient overlap) it will be necessary to slide an activity after the other to eliminate the overlap. The CRH proceeds by moving the second activity in the chronological order, and the starting time of this one is equal to the ending time of the first activity. While both activities have the same starting time, the overlap is eliminated while choosing randomly one activity to move.

Otherwise, while the coordination constraints are not satisfied, i.e. two care activities for a patient do not occur in the imposed order, it will be necessary to swap activities to respect the imposed order.

The operations cited above may impact (1) the feasibility of the caregivers’ tours, thus, each tour may be inspected and the care activities in this tour must be sequenced (respecting the care duration and the travel time between patients), and (2) the coordination constraints, thus the imposed order may be controlled and maintained after each operation. The Algorithm 2 illustrates the general approach of the second step of the CRH.

The aim of this step is to resolve overlap or coordination (temporal dependencies) conflicts, i.e. to introduce the precedence and the coordination constraints. This step will provide the patients with an effective planning while reducing his/her waiting times. Yet, this will result for the caregivers to swap their visits; which will eventually lead to produce changes in the caregivers’ rounds.

In the next examples, we illustrate the process of the CRH to eliminate conflicts and satisfy the constraints. Figure 2 details the process for eliminating the overlap between the activities for three patients (p1, p2 and p3) visited by four caregivers. The initial situation shows that there are overlaps “α” and “β” between the activities of the patient “p1” and three caregivers are implied (i.e., the caregivers CG11, CG12 and CG13).

Fig. 2
figure 2

Process to eliminate the overlap conflict between the caregivers’ activities

Full size image

The CRH proceeds firstly by eliminating the overlap “α” due to the conflict between the caregivers CG12 and CG11. Since the task of the caregiver CG11 is moved forward, this leads to spreading this movement for the patients of the caregiver CG11 (p2 and p3) to maintain a feasible round. Afterward, the CRH proceeds to eliminate the overlap “β” between the caregivers CG11 and CG13. This set of corrections leads to progressively create a set of other overlaps. The CRH loops until it obtains feasible rounds (feasible schedules).

The example shown in Fig. 2 does not consider the coordination between care activities (the predefined order between activities of a patient). Figure 3 illustrates the process for correcting the sequences of the patients’ activities and the caregivers’ rounds, while considering temporal dependencies (coordination) constraints.

Fig. 3
figure 3

Process to eliminate the temporal dependencies conflicts between caregivers’ activities

Full size image

In this example, the care task of the caregiver CG11 for the patient p1 must be performed before the care task of the caregiver 2. The CRH proceeds by swapping both care tasks to satisfy the imposed care activities order. This switch causes a disruption on the round of the caregiver 1, which will be corrected to maintain a feasible round. This series of corrections causes the overlap “α”, which will be eliminated using the procedure illustrated in the second step of the algorithm.

In Figs. 3 and 4 we present the process used by the CRH to eliminate the overlap and the temporal dependencies conflicts. The elimination of the conflicts by the CRH may lead to changes on the caregivers’ rounds (the order of the caregivers’ visits).

Fig. 4
figure 4

Impact of the process of eliminating the temporal dependencies conflicts

Full size image

In the example presented in Fig. 4, the caregiver CG21 has to perform his/her care activity before the caregiver CG11. A permutation is required in order to meet the therapeutic project; this process leads to changes in the caregivers’ rounds, i.e., these changes lead to a shift in the rounds of the caregiver 1 and changes the patients sequence for the caregiver 2.

Therefore, CRH proceeds by scanning sequentially every patient until all the overlap and the coordination problems are solved. The scanning process of the patients, impacts strongly on the quality of the caregivers’ rounds. To avoid this undesirable effect and to ensure generating a good quality solution, the second step will be repeated, as many times as there are combinations of sequence of choice for the patients. If there are “N” patients, “N!” experiences may be realized.

5 Computational tests

5.1 Lists of instances

The lists of instances used in this paper were extracted after collaboration with many home care structures. Throughout this collaboration, we have obtained many databases, which allowed us to develop a test generator. This application allowed us to generate travelled times between the set of patients and a random allocation of patients to the caregivers. Experts in the home care field validated the used instances.

The first instance generated represents a HCS with an internal staff of 10 caregivers and the number of patients that may be visited is 10. The number of patients per caregiver ratio is equal to 5. In the second instance we consider a HCS with 15 caregivers visiting 15 patients per day. The number of patients per caregiver ratio is equal to 5. Finally, in the third instance, we consider a HCS with an internal staff of 15 caregivers visiting 15 patients per day. The number of patients per caregiver ratio is equal to 8. Each instance represents respectively a small, a medium and a large structure.

In our experience, the variability of the care durations is not a complexity factor for the caregivers’ routing problem. Thus, all the care durations are set to 25 min. For every experiment, the patients are considered available for all the working day (the patients’ time windows are equal to the working day). The travel times are randomly generated between 15 and 50 min.

A temporal dependencies rate is set randomly from the number of possible combinations. For example, we select 3 care activities to perform for a patient, the number of the combinations (orders) possible is equal to 6 (i.e., 3!). If we set the temporal dependency rate to 0 %, then the three activities could be made in any order. If the temporal dependency rate is set to 100 %, the three activities should be performed in a predefined order. The work horizon is 1 day.

5.2 Numerical results

This experimentation aims at assessing the performance of CRH and at comparing these results with the m-TSPC model. As introduced previously, CRH is sensitive to the scanning process of the patients. In order to eliminate this bias it would be necessary to run the CRH “N!” time (“N” is the number of patients). Since this solutions generation is time consuming, we discuss the impact of the sample of run on the quality of the problem solution.

5.2.1 First instance (patients per caregiver ratio = 5; 10 patients; 10 caregivers)

For this first instance, the number of patients and caregivers are set to 10. The ratio of the number of patient per caregiver is set to 5. The CRH is run for different temporal dependencies rates between 0 to 100 %. For each of these instances, CRH has been run until obtaining the set of the possible solutions. Table 2 shows (1) the average and the standard deviation of the caregivers travelling and waiting times, and (2) the best round obtained (shortest travelling and waiting times).

Table 2 Results of the CRH-first instance
Full size table

The Table 2 illustrates the CRH results while varying the number of iterations. This table summarizes the average and standard deviation of the travelling and the waiting times for the set of experiences. It also summarizes the best rounds obtained (bold values). Simultaneously, the m-TSPC model was executed using the same instances. The computational time was limited at 08h30 (c.f. Table 3). For tests 1 and 2, the m-TSP model leads to optimal solutions. Unlike tests 3, 4, 5 and 6, the results are feasible (not optimal). Although, the CRH reaches a better solution compared to the m-TSP model, for obtaining this best solution CRH must be run N! times. This is possible when the number of patients is small, thus this is not conceivable for a large number of patients (the computational time growing exponentially with the patients’ number).

Table 3 m-TSPC results for 5 patients per caregiver (Redjem 2013)
Full size table

To address this issue, we study if the CRH may provide a good quality solution with a small number of iterations. In Table 2 (test 1), the CRH runs 3 min to obtain the best solution (1315 min, sum of travelling and waiting times). While the number of tests performed is decreased to 10 % of the N! iterations, the gap from the best solution is less than 3 %.

Before calculating the gap in percentage between the optimal or the best solution reached with the m-TSP approach and the best solution obtained by the CRH, we present in Table 3 the explosion of run times while using the m-TSPC approach using the first instance (10 patients; 10 caregivers; patients per caregiver ratio = 5). These results have been extracted from (Redjem 2013).

Table 4 illustrates the gap in percentage between the optimal or the best solution (after 08h30 of computational time) reached with the m-TSP model (cf. Redjem 2013) and the best solution obtained by CRH. For many tests, the CRH reaches better solutions than the m-TSP model (these results are displayed by an up arrow in Table 4).

Table 4 Gap between the CRH and the m-TSPC model
Full size table

Table 4 shows for every test that the CRH reaches very good solutions. For tests 1 and 2, when the m-TSP reaches the optimal solution, the CRH is close to the optimal solution with a gap less than 3 %. For tests 3–6, the CRH provides better solutions than those obtained by the m-TSPC model after 08h30 of computational time. Moreover, we noticed that the variation of the temporal dependencies rate has no impact on the computational time for CRH, contrary to the m-TSPC model.

In the second experience, the CRH is tested with a larger instance that consists of 15 patients and 15 caregivers. The number of patients per caregiver ratio for this instance is set at 5. For the third experience, the CRH is tested on a larger problem. This instance consists of 60 patients and 30 caregivers. The number of patients per caregiver ratio is set at 8. The aim of this study is, on one hand, to test the robustness and scalability of the CRH when the size of the instance increases to reach a real case and, on other hand, to confirm the results obtained in the first instance.

5.2.2 Second instance (patients per caregiver ratio = 5; 15 patients; 15 caregivers)

For 15 patients the number of iterations is very large (i.e., 15!); for that, we perform only a sample randomly generated from the iterations set. The Table 5 illustrates the results obtained using the CRH when the temporal dependencies rate increased from 0 to 100 %. We display a new double column in the Table 5, with the best solution of the first step of the CRH. As mentioned previously, this solution is the theoretical lower boundary of the problem, i.e., all the coordination constraints are relaxed. This lower boundary allows us to assess the quality of the best solution reached by the CRH (bold values).

Table 5 Results of the CRH-Second instance
Full size table

Table 5 shows that the CRH is very robust to solve the average instances. The CRH may generate a very large number of solutions. The previous experiences show that the CRH can deliver very satisfactory solutions using a sample of the set of all proposed solutions, i.e., the CRH may deliver satisfactory solutions using a limited number of iterations.

These tests show also the important degradation in the quality of solutions (lower bound) due to the constraints of the temporal dependencies. This degradation varies between 35 and 60 %. This proves that, the constraints of the temporal dependencies have an important impact on the solutions’ quality.

5.2.3 Third instance (patients per caregiver ratio = 8; 60 patients; 30 caregivers)

The number of iterations in this example takes a large value (i.e., 30!); for that, a sample of 100 iterations (solutions) will be randomly generated. In Table 6, we illustrate the results obtained using the CRH, while varying the temporal dependencies between 0 and 100 %. This instance was also used to evaluate the performance of the m-TSPC approach, which was executed during 24 h of computational time.

Table 6 CRH for 8 patients per caregiver
Full size table

This instance was used to test the m-TSPC approach. The m-TSPC model is not able to provide a feasible solution after 24 h of computational time. However, the CRH provided 100,000 solutions after 1:30 min using the same instance. Indeed, after 1:30 min the average caregiver’s travelled time is equal to 102 min (average travelled time per caregiver) and the average waiting times is equal to 33 min (average waiting time per caregiver). The results obtained by the CRH represent a very satisfactory solution.

Thus, the set of tests realized on the CRH shows that the complexity of the rounds generation through the CRH is independent of the complexity of the temporal dependencies. In contrast, the m-TSPC models were very sensitive to the complexity of the temporal dependencies (cf. Sect. 2).

The decision makers may generate good quality solutions for the routing problem within a considerable performance (calculating times), regardless the number of patients, the number of caregivers, the number of care activities per caregiver ratio as well as the complexity of the temporal dependencies.

6 Conclusion and perspectives

The operations management related to care activities in HCS is divided into two classes, i.e., (1) the districting of the covered area and allocation of human resources and (2) the allocation and scheduling of caregivers’ activities. This paper addressed the problem of the caregivers routing in HCS. Previous works on this problem have concluded that the MILP implementations are not able to reach optimal solutions for real size instances in a reasonable computational time. In order to solve this issue we have developed an adapted heuristic, called the Caregivers Routing Heuristic (CRH).

The first step of the CRH consists of building the optimal caregivers rounds (i.e., with the shortest travelling times) without patients’ coordination and sequencing constraints. The second step integrates the relaxed constraints to build the final solution, while satisfying all the problems’ assumptions. The CRH was tested using several instances, and the realized tests have proven its high performance to solve the real size instances. It is also worth mentioning that unlike the MILP approaches, the complexity of the CRH is not sensitive to the temporal dependencies’ rate.

Despite its performance, the CRH remains open for further improvements. On one side, the CRH offers a substantial number of solutions. However, it is crucial to develop an application that can extract the most suitable solution among a set of proposed solutions (those promoting solutions on others), which allow more flexibility to the policymakers to balance the caregivers’ work while respecting their constraints. On the other side, the proposed approach is not able to consider the variability on the demand of the home care. In fact, it is mandatory to recalculate all the caregivers’ tours, each time a patient is assigned to a caregiver or a patient leaves the care process during the working horizon. In another sense, the CRH is a centralized approach, i.e. all the care rounds begin and end in the HCS. Nonetheless, it can be more efficient to design a distributed approach that enables start and end the caregivers’ rounds freely.

The home care process is subject to uncertainties which may be in the caregivers’ travelled time, availability of material resources or care durations, etc. Nevertheless, the CRH is very sensitive to these uncertainties. In fact it would be interesting to develop approaches that take into account these environmental constraints.