Recent planning approaches and mobility concepts for home health care services in Austria – A review

In 2015, about 16.4 million working hours were performed in home health care (HHC) and a total of 145,723 clients were visited in Austria (Statistik Austria, 2017a). HHC providers cover a wide range of services, leading from assistance in doing the housework to qualified home nursing. In Austria, HHC providers work independently from intramural care facilities like hospitals; the staff is not shared as it is sometimes the case in other countries like Italy (e.g., Cattafi et al., 2012) or Spain (e.g., Quintanilla et al., 2014). The demand for HHC services is expected to rise significantly during the next few years in industrialized countries (cf. Rest et al., 2012; Trautsamwieser and Hirsch, 2014; Sahin and Matta, 2015). Reasons for that are an increased life expectancy, changing family structures, and the trend to grow old at home. Depending on the region, it is estimated that HHC staff spends about 15—30% of its working time travelling from one client to the next one (e.g., Trautsamwieser et al., 2011). This portion can be even higher for the qualified nurses, who usually visit many more clients than the home helpers during the course of the day, or the HHC staff working in rural areas. The amount of time spent at the clients’ residences are dependent on their care needs and are fixed, but changing the assignment of the HHC staff to the clients and the sequence of visits may lead to major working time savings. Since many HHC service providers are faced with a high time pressure, this would relieve the situation essentially. Up to now, the scheduling of HHC services is still done manually by the senior HHC staff or the designated dispatchers in Austria, which leads to a high planning effort and makes it difficult to react quickly and efficiently to disturbances. HHC planning has to deal with different legal and organizational constraints that differ between countries and even organizations within one country. Hence, standard decision support systems (DSS) for routing and scheduling are not applicable and tailored solution approaches are needed.

This paper is based on the research on HHC of the author and his working group during the past 10 years and contains parts of the unpublished framework paper of the habilitation thesis of the author (Hirsch, 2016). The research was done in close cooperation with the Austrian Red Cross (ARC), one of the major providers of HHC services in Austria. Some of the developed ideas were implemented in a DSS that is currently used by a big HHC service provider in Vienna. Additionally, numerous international researchers built their work on the gathered knowledge. The aim of this paper is to provide the reader a comprehensive overview on logistical planning in HHC. In order to meet the future requirements, it is important to analyze different mobility concepts for HHC staff and to provide tailored solution approaches for routing and scheduling. The reader learns about the current HHC situation in Austria, logistical requirements for planning these services, possible mobility concepts for HHC staff, and potential threats for HHC operations. The developed solution methods are summarized; detailed mathematical model formulations and pseudo-codes of the algorithms can be found in the cited literature. The main findings are highlighted and discussed. The paper concludes with an outlook on potential future research paths in the area of HHC routing and scheduling.

The terms “home care” (e.g., Eveborn et al., 2006; Sahin and Matta, 2015) and “home health care” (e.g., Begur et al., 1997; Bertels and Fahle, 2006) are used synonymously in literature on optimizing the logistical planning of this service. Authors also rarely use the terms “mobile care” and “extramural health care”. The author’s papers use the term HHC, which is also done throughout this contribution. The Organization for Economic Co-operation and Development (OECD) stated that on average, across the OECD countries, the share of population aged 65 years and above is expected to be 27% in 2050; this is nearly twice as much as in 2010 (OECD, 2013). In 2014, women (men) at age 65 years could expect to live for another 21.6 (18.2) years on average in EU member states; the number of “healthy life years” that means disability free life expectancy, was 8.6 years for women and men (OECD/ EU, 2016). Changes in family structures can be observed in many industrialized countries. They lead to a decrease of the availability of informal care. Some examples are decreasing birth rates, higher job mobility, or the trend to live alone. OECD (2014) stated that the number of live births per 1,000 population and year decreased from 19 in 1960 to 10.5 in 2012 across the EU (unweighted average). The share of single households in Austria was 27.4% in 1985; this number rose to 37% in 2016 (Statistik Austria, 2017b). Rest et al. (2012) mentioned that the hours worked in HHC increased by 29.4% from 2000 to 2008 in Austria; Voegl (2015) stated that it is estimated that these hours increase by 36% from 2012 to 2020. In 2010, 11,500 full time equivalent employees worked in HHC in Austria; it is reckoned that this number rises to 18,300 in 2025 (Voegl, 2015).

The main advantages of HHC according to Rest et al. (2012) are:

Facilitation of care-dependent people to stay at home as long as possible

These facts underpin the need for an efficient logistical planning of HHC services. The exploration of decision support methodologies is a crucially important research area (Burke and Kendall, 2005). Due to the high complexity of many logistical planning situations in organizations, it is necessary to provide the management with suitable decision support techniques. Even though there are useful standard software tools available to assist decision makers, many real-world problems require innovative approaches in order to meet their specific objectives and constraints. This leads to an ongoing demand for the development and implementation of advanced mathematical model formulations and solution methods. Depending on the time range, the involved management level, the availability of deterministic data, and the impact of a decision on the economic well-being of an organization, different levels of decision making can be defined. McKinnon (2012) stated four levels of logistical decision making: strategic, commercial, operational, and functional decisions.

The logistical planning of HHC services can be seen as a part of humanitarian logistics. In general, humanitarian logistics is about delivering goods and/or services to vulnerable people. Common objectives are to minimize cost, to minimize resource use, or to maximize service levels. The demands can arise through disaster events (e.g., river floods, earthquakes, or pandemics) or through social and/ or medical requirements of people (e.g., the need for HHC or ambulance services). The International Federation of Red Cross and Red Crescent Societies (IFRC) defined the basic task of humanitarian logistics as follows: “…humanitarian logistics comprises acquiring and delivering requested supplies and services, at the places and times they are needed, whilst ensuring best value for money” (IFRC, s.a.). There are also some factors in humanitarian logistics that could make planning more difficult than in commercial logistics applications. Overstreet et al. (2011) listed unknowns, time, trained logisticians, media and funding, equipment and information technology, as well as human interference. Humanitarian logistics often faces the problem that it is difficult to obtain data, for example on the available traffic network after a disaster or the actual demands. Most of the operations are also very time-critical; failures can lead to serious consequences on human health. Table 1 states the differences between commercial and humanitarian logistics and is based on Larson (2014).

Table 1

Commercial logistics versus humanitarian logistics (cf. Larson, 2014)

Tabelle 1. Vergleich von kommerzieller und humanitärer Logistik (vgl. Larson, 2014)

Humanitarian logistics is an evolving research area. Tatham and Christopher (2014) mentioned that a recent review by Kunz and Reiner (2012) found that of 174 papers on humanitarian logistics, which appeared in the time span between 1995 and 2011, about 86% were published in the last five years between 2007 and 2011. Research on planning in HHC had increased tremendously during the last few years. The author and his working group had started to do research on this topic in 2008. At that time, only a few papers were available (e.g., Begur et al., 1997; Bertels and Fahle, 2006; Eveborn et al., 2006) and HHC service providers stated their need for suitable decision support, especially in the times of disasters. Trautsamwieser and Hirsch (2011) presented a model formulation and a metaheuristics solution approach based on Variable Neighborhood Search (VNS) for the daily scheduling of HHC workers in Austria. This work extended the vehicle routing problem (VRP) by additional constraints like working regulations (e.g., mandatory breaks) and used travel time as well as dissatisfaction criteria in the objective function. Trautsamwieser et al. (2011) modified the solution method and presented a real-world data based sensitivity analysis that showed how different natural disasters and flood scenarios influence HHC in three selected districts in Upper Austria. Rest et al. (2012) presented a comprehensive study of potential threats in rural and urban areas that influenced the HHC services and highlighted the importance of these services. The authors also presented a detailed real-world data based analysis of different flood scenarios. Trautsamwieser and Hirsch (2014) extended the planning horizon of HHC scheduling and proposed a VNS based method as well as an exact solution approach. Fikar and Hirsch (2015) imposed an innovative mobility concept for HHC services that used trip sharing of the staff in dedicated buses with employed drivers and facilitated walking on subroutes. Rest and Hirsch (2015) investigated the impact of potential threats on HHC in Vienna. They analyzed how blackouts, pandemics, and heat waves affect HHC. Fikar and Hirsch (2016) compared different mobility concepts for HHC staff with respect to travel time. They proposed metaheuristic algorithms that support the routing and scheduling of HHC staff with separate cars, trip sharing, and car sharing. Fikar et al. (2016) extended the research of Fikar and Hirsch (2015) to deal with a dynamic problem setting. Rest and Hirsch (2016) presented an exact solution method to compute the time-dependent travel times out of the timetables from public transport service providers. This served as a basis for three Tabu Search (TS) based solution methods to solve the daily scheduling of HHC workers that used public transport. Some of the findings of the stated research were also used to develop a DSS for an HHC service provider in Vienna (ingentus decision support, s.a.). Finally, Fikar and Hirsch (2017) provided a comprehensive review on worldwide research about HHC routing and scheduling. Figure 1 gives an overview on the publications of the author on HHC, their contents, and interrelations.

Figure 1

Other relevant research on HHC in Austria is presented by Hiermann et al. (2015), who introduced a general framework for solving a real-world multi-modal HHC scheduling problem from a major Austrian HHC provider. First results of the work of Hiermann et al. (2015) have been presented in Rendl et al. (2012). Braekers et al. (2016) based their numerical studies on the data provided by Hiermann et al. (2015); the authors considered the trade-off relationship between two competing objectives in HHC routing and scheduling.

This section defines the specific characteristics of HHC routing and scheduling. It presents possible transport modes for the HHC staff and the resulting optimization problems. Additionally, the impact of disasters on HHC planning is analyzed. In the following, a classification of the involved entities in daily HHC planning in Austria is presented.

Each client…

requires at least one job during the day.

Each job…

Each HHC worker…

starts her/his shift depending on the work contract

The main objective of HHC planning is to minimize the total travel times of HHC workers. These travel times include driving as well as waiting times. Trautsamwieser and Hirsch (2011) and Trautsamwieser et al. (2011) used a weighted objective function consisting of the main objective and penalties for:

overtime

Only the main objective is used for some numerical studies dealing with disaster situations in Trautsamwieser et al. (2011) as well as in Rest et al. (2012). The reason for that is the scarcity of workforce in disaster situations that compels HHC providers to neglect the violations of soft constraints.

The objective function is subject to:

Assignment constraints – for example, an HHC worker can only visit a client, if they do not reject each other, speak at least one common language, and if she/ he has (at least) the required qualification level for the job.

Trautsamwieser and Hirsch (2011), Trautsamwieser et al. (2011), and Rest et al. (2012) dealt with the daily planning problem of HHC. Trautsamwieser and Hirsch (2014) extended the planning horizon of HHC to one week. All these papers assumed that the HHC workers use individual cars. If the distances between clients are short, it is also common to walk or to use (e-)bikes or scooters. In these cases, the algorithms developed for individual car use can also be applied. The problem can be modeled as an extension of the VRP. Trautsamwieser and Hirsch (2014) developed an exact solution approach for the weekly HHC planning problem. To relax the problem, they used the objective of minimizing the total travel times of HHC workers and assumed that all of them start their shifts at the base of the HHC provider and end it there; else, they used the same hard constraints as in daily HHC planning and extended them by the following ones:

Each HHC worker has a maximum working time per week.

According to Rest et al. (2012), the vulnerable factors in HHC are staff, clients, communication, and transport. Especially during disaster events, the absence of staff is a major problem, since it can be affected by the disaster itself. The number of clients as well as the service time for treating them may increase significantly. Information and communication activities are important for almost all activities of HHC services. They are especially impaired during blackouts, which may also be a cascading effect of other disaster events. Transport may be affected by the closure of some connections, reduced speed on the traffic network, or a lack of fuel for the vehicles. Table 2, which is based on Rest et al. (2012), summarizes these findings for different disaster events. In case of extreme weather events, the focus is on a moderate climate zone as predominant in most parts of Europe. Hence, the impact of temperature on infrastructure is negligible.

Table 2

Impact of disaster events on HHC (cf. Rest et al., 2012)

Tabelle 2. Auswirkungen von Katastrophen auf die mobile Pflege (vgl. Rest et al., 2012)

The preferred transport mode of HHC staff changes depending on the area it operates in. In rural areas, individual car use is the prevalent transport mode, since the public transport network is usually sparse and the average distances between clients are longer. In urban areas, with a dense public transport network like Vienna, the (combined) use of train, tram, bus, and subway is common, which leads to new logistical challenges, since these transport modes operate based on timetables. Figure 2 presents a simplified example, considering only two possible paths between two clients; it shows how the shortest path changes depending on the time of the day. Rest and Hirsch (2016) presented TS based solution algorithms to solve this daily time-dependent HHC scheduling problem. They modified the model formulation presented in Trautsamwieser et al. (2011) and provided an exact solution approach to compute the time-dependent travel times out of the timetables from public transport service providers on a minute-basis.

Figure 2

Rest and Hirsch (2016) used a weighted objective function and aspiration levels to incorporate the satisfaction of HHC staff and clients. Moreover, they expanded the constraints by adding a minimum working time for the HHC staff. This minimum working time has to be guaranteed by the HHC service provider, if an employee starts a shift. To the best of the author’s knowledge, Rest and Hirsch (2016) is the first journal paper that deals with a time-dependent, multi-modal traffic network for HHC services. Hiermann et al. (2015), who also deal with multi-modal HHC routing and scheduling in Vienna, assume that HHC workers can either use cars or public transport. In contrast to Rest and Hirsch (2016), Hiermann et al. (2015) use a single estimate for each mode. Thus, they do not rely on the time tables, that is, the actual time of departure, of public transport modes. Moreover, Hiermann et al. (2015) deal with a relaxed version of the HHC formulation that was used, for example, in Trautsamwieser et al. (2011). Braekers et al. (2016) model the HHC routing and scheduling problem as a bi-objective problem and reveal that service providers face a considerable trade-off between costs and client convenience. The authors use randomly generated data that build on the test instances of Hiermann et al. (2015) and relax the HHC formulation too. Rest and Hirsch (2015) provided an analysis on the impact of disasters on HHC services, using the algorithms developed in Rest and Hirsch (2016). Fikar and Hirsch (2015) proposed the use of a dedicated bus service for HHC staff and developed a matheuristic method to solve the daily planning problem. The transport service delivers the HHC workers to the clients and picks them up after the completion of their services. In this approach, it is also possible to walk to the next client, if the distance is below a certain threshold. This leads to interdependencies in the problem, since changing the time of delivery results also in a change of the pickup time. Hence, it is necessary to synchronize the HHC staff and vehicles in this problem. Fikar and Hirsch (2015) defined the problem as an extended many-to-many multi-trip Dial-A-Ride Problem (DARP). They concentrated on minimizing the total travel times of the HHC staff and drivers, showing the trade-offs between these two groups of workers. The authors built on the constraints of daily HHC planning introduced in Trautsamwieser et al. (2011). The trip sharing concept presented by Fikar and Hirsch (2015) is not in practical use in Austria up to now; the author is also not aware of any scientific literature describing such a concept in other countries. Nevertheless, Austrian HHC service providers mention that it seems to be an interesting mobility concept and a future introduction should be considered especially in rural and sub-urban areas. Fikar et al. (2016) extended the static problem setting of Fikar and Hirsch (2015). In Fikar et al. (2016), not all information about visits to the clients is known beforehand at the beginning of the day. Hence, the developed discrete-event driven biased-randomized (BR) metaheuristic is able to deal with dynamic events as cancellations or new requests.

Fikar and Hirsch (2016) compared the trip and car sharing concepts in HHC to the traditional case of individual car use. They developed an event-driven BR heuristic, a post-optimization procedure, and a matheuristic to analyze routing with separate cars, car sharing, and trip sharing respectively. The authors consider different geographic distributions to identify which mobility concept for HHC staff fits best under certain circumstances.

Table 3 presents different mobility concepts for HHC staff and their underlying basic logistical problems that need to be extended as described at the start of this section to fit to the requirements of HHC; it is based on Voegl and Hirsch (2015). It is marked, if the problem formulations are based on the VRP or the DARP as well as if synchronization between HHC staff and the vehicle is needed due to the mobility concept.

Table 3

Mobility concepts in HHC and their underlying basic logistical problems (cf. Voegl and Hirsch, 2015)

Tabelle 3. Mobilitätskonzepte in der mobilen Pflege und ihre grundlegenden logistischen Problemformulierungen (vgl. Voegl und Hirsch, 2015)

Fikar and Hirsch (2017) provided an extensive review of the literature on HHC routing and scheduling. They focused on the considered problem settings that differ in the international context and the applied solution methods. Table 4 provides a categorization of the author’s papers on HHC.

Table 4

Categorization of the author’s publications on HHC

Tabelle 4. Kategorisierung der Publikationen des Autors über mobile Pflege

In order to solve the introduced planning problems, several tailored solution methods have been developed in the papers of the author and his working group. They are based on metaheuristics (TS, VNS, and BR), matheuristics, and exact methods. Only small problem instances in HHC can be tackled by implementing the mathematical model formulation in solver software. The general objective of using metaheuristics and matheuristics is to obtain near-optimal solutions in short computing times. Exact methods aim to find the global optimal solution of a planning problem; their computing times are usually much longer.

Glover and Kochenberger (2003) defined metaheuristics as “solution methods that orchestrate an interaction between local improvement procedures and higher-level strategies to create a process capable of escaping from local optima and performing a robust search of a solution space”. Gendreau and Potvin (2005) divided metaheuristics into two categories: “single-solution metaheuristics, where a single solution (and search trajectory) is considered at a time, and population metaheuristics, where a multiplicity of solutions evolves concurrently”. Gendreau and Potvin (2005) also distinguished between constructive metaheuristics, where a solution is built from scratch by adding new elements in each iteration step and improvement metaheuristics, which iteratively modify a solution. Other popular metaheuristics than TS and VNS are for example Simulated Annealing (SA), Evolutionary Algorithms (EA), or the Greedy Randomized Adaptive Search Procedure (GRASP). It is also common to develop hybrids of metaheuristics; this is done, for example, in Trautsamwieser et al. (2011), where the acceptance criterion in the VNS algorithm is based on the concept of SA. In the following, the basic concepts of the metaheuristics that were applied are explained in brief. Each metaheuristic stops after a predefined number of iteration steps, a fixed computing time, or if the solution value does not improve for a predefined number of iteration steps. The best-found solution during the computation is then used as output. For a detailed description of the implementations, the reader is referred to the respective publications of the author. The programming languages Java and C++ were applied in the publications on HHC of the author.

TS is a single-solution improvement metaheuristic that uses deterministic local search strategies. It is based on a short-term memory (tabu list) and on a long-term memory that allows the implementation of intensification- and diversification strategies to guide the search process. In each iteration step, the best solution in the neighborhood of the current solution is chosen as new current solution, even if the objective value gets worse. The tabu list stores recently visited solutions (or attributes of recently visited solutions) to avoid short-term cycling (Gendreau and Potvin, 2005). Hirsch (2011) stated that “the tabu duration can be fixed in the beginning of the algorithm or changed dynamically during the search process”. Moreover, TS uses rules known as aspiration criteria that allow using elements of the tabu list (Hirsch, 2011). Glover and Laguna (1997) described intensification strategies as a modification of “choice rules to encourage move combinations and solution features historically found good”; this may lead to a return to attractive regions to search them more thoroughly. Diversification strategies encourage the search process to examine unvisited regions and to generate solutions that differ in various significant ways from those seen before (Glover and Laguna, 1997). TS can be seen as a powerful approach to solve various variants of the VRP. This is underlined, for example, in Cordeau et al. (2002), who pointed out that “TS clearly stands out as the best metaheuristic for the VRP” or in Crevier et al. (2007), who stated that TS has proved to be highly effective for the solution of a wide range of classical VRPs. The author’s specific planning problems tackled with tailored TS variants cover extensions of the VRP and consider partly time-dependency as well as state-dependency; the undertaken numerical experiments prove the good applicability of these TS methods. TS is a very popular metaheuristic and a lot of variants can be found in literature. The TS variants used in the papers presented in this contribution are based on the ideas of Unified TS (see e.g., Cordeau et al., 2001). If applicable, the solution algorithms start with a method to reduce the solution space by excluding infeasible combinations before the solution procedure starts. After that, a heuristic constructs an initial solution for the problem. Then, the TS procedure starts. In brief, all the applied TS methods combine single task moves with local reoptimization, use fixed but problem-size dependent tabu durations, and aspiration criteria that are attribute-related (Hirsch, 2011). They allow for intermediate infeasible solutions that are assessed with adaptive weighting factors. Worsening candidate solutions are penalized by adding costs that are dependent on how often the attributes of a specific candidate solution were used in other solutions already. In some implementations, a post-optimization heuristic improves the solutions after each iteration step. Specific memory structures are used to avoid the repetition of computations that have already been made in previous iteration steps. The single TS variants differ in the applied neighborhood structure of a solution in each iteration step. These structures may change according to static rules that are defined before the algorithm starts or dynamically during its execution.

VNS is a single-solution improvement metaheuristic, with the basic idea of a systematic change of neighborhood within the local search. It combines deterministic and stochastic changes of the neighborhood (Hansen and Mladenović, 2003). VNS defines a set of neighborhood structures that are used in the search. Based on Hansen and Mladenović (2003), the fundamental solution process can be described as follows: The procedure starts from an initial solution and with the first neighborhood structure. In the shaking phase, a neighbor solution of the current one is chosen randomly. This neighbor solution is improved with a local search procedure until a local optimum is reached. If the solution is better than the incumbent, or if some acceptance criterion is met, this solution becomes the new current solution and the search continues in the same neighborhood structure. If the solution is not accepted, the search process moves to the next neighborhood structure. VNS is a very popular metaheuristic. It has proved to be a good choice for solving different variants of VRPs (Trautsamwieser et al., 2011). The VNS implementations in the author’s papers on HHC build on the definition of problem-specific and suitable neighborhood structures as well as on adequate local search strategies. The acceptance criterion uses a probability function that is based on SA.

The main idea behind BR techniques is to introduce randomness in a constructive heuristic procedure in such a way that more promising candidates receive higher probabilities of being selected (Juan et al., 2011). BR strategies are combined with heuristics or metaheuristics. The simple structure allows searching the solution space quickly.

Matheuristics combine heuristics or metaheuristics with mathematical programming. Archetti et al. (2015) stated that a combination of a heuristic or metaheuristic scheme with mixed integer linear programming models has been recently explored by several authors, but is denoted under different terms as “heuristics based on mathematical programming”, “hybrid heuristics”, or “matheuristics”. The author’s papers use the term matheuristics, since it becomes more and more common in literature. Fikar and Hirsch (2015) presented, for example, a two-stage solution approach for routing buses for HHC staff, which can also use walking routes for shorter distances. The authors start with solving a set-partitioning problem for the walking routes to optimality before the routing part starts with a biased-randomized savings heuristic as initial solution. After that, a TS based approach improves the solution iteratively. The TS uses a walking routes improvement operator to align the selected walking routes with HHC workers’ schedules and vehicles’ tours. Moreover, the start time optimization of tours is solved to optimality in each evaluation of a solution by using the solver software Xpress (FICO, s.a.).

There are many exact solution methods for combinatorial optimization problems in literature, including concepts like branch-and-bound, dynamic programming, or constraint programming. These approaches have to be customized to their specific application areas. Laporte (2007) mentioned that there are several families of exact algorithms that have been proposed for the VRP with a symmetric cost structure; these are based on integer linear programming, dynamic programming, and branch-and-bound. The success rate of exact methods in finding solutions for variants of the VRP is variable and the problem size is limited. This explains why most of the research effort has concentrated on heuristics, which tend to be considerably more flexible than exact algorithms and can be more readily adapted to deal with the diversity of variants arising in practice (Laporte, 2007). Nevertheless, research on exact algorithms is fundamental in order to provide sophisticated benchmarks for heuristic solutions. Trautsamwieser and Hirsch (2014) used a Branch-Price-and-Cut (BPC) approach to solve the medium-term HHC planning problem. Barnhart et al. (1998) presented an overview on the general methodology and stated that pricing and cutting are complementary procedures for tightening an LP relaxation. In Trautsamwieser and Hirsch (2014), the model formulation was decomposed by Dantzig-Wolfe decomposition; the result is a master problem and several subproblems. The solutions of the subproblems are added to the master problem as new columns in each iteration step. Then, the master problem is resolved, and its dual variables are used to obtain new solutions for the subproblems. This is repeated until the exact solution for the problem is found. For solving the subproblems, several concepts for tackling the Elementary Shortest Path Problem with Resource Constraints have been combined and adapted. Moreover, cuts are added to the master problem to strengthen the lower bound. The BPC approach can be started with any initial solution, but it could be advantageous to use a more sophisticated one, in order to have a good upper bound. Trautsamwieser and Hirsch (2014) introduced a VNS algorithm to compute the initial solution.

This section highlights and discusses the main findings of a selection of the presented papers. Representative numerical results are presented for the mobility concepts individual use of a car, bus service, and public transport. Moreover, the impact of a flood disaster on HHC services in rural and sub-urban areas in Upper Austria is shown. The results of the other presented papers are discussed in brief.

Trautsamwieser and Hirsch (2011) showed that even a complex problem like the daily routing of HHC services, which has a lot of properties to keep in mind, can be solved efficiently. The authors proposed a mathematical model formulation as well as a VNS based solution method for this problem. Table 5 compares the use of a weighted objective function (Λ₂) to the objective of minimizing the total travel time (Λ₁) for one small urban (r₁) and two rural regions (r₂ and r₃). If the HHC worker starts the tour from the base of the provider, this is denoted as D. H₁ means that the tour starts and ends at the home of the HHC worker; in case of H₂, the tour starts at the first client and ends at the last one. All these options are possible variations in the work contracts of the employees. The setting C considers a uniform distribution of the potential starting points of the HHC workers. The problem instances are real-world based and include 87/221/313 jobs, 87/196/277 clients, and 13/39/75 HHC workers for r₁/r₂/r₃. As stated in detail in Trautsamwieser and Hirsch (2011), the addresses of clients and HHC workers as well as the number of required jobs are known. Other information, as time windows of the jobs and actual starting points of the tours needed to be estimated. The weighting of Λ₂ was the result of a survey conducted with decision makers in HHC planning at the ARC. The used weighting factors are shown in Table 6.

Table 5

Solution values [min] for r1, r2, and r3 for different scenarios and the objective functions Λ1 and Λ2 (cf. Trautsamwieser and Hirsch, 2011)

Tabelle 5. Lösungswerte [min] für r1, r2, und r3 für unterschiedliche Szenarien und Zielfunktionen Λ1 und Λ2 (vgl. Trautsamwieser und Hirsch, 2011)

Table 6

Weighting of Λ₁ and Λ₂ (cf. Trautsamwieser and Hirsch, 2011)

Tabelle 6. Gewichtung von Λ₁ und Λ₂ (vgl. Trautsamwieser und Hirsch, 2011)

Moreover, Trautsamwieser and Hirsch (2011) compared the algorithmic results with a manually generated actual route plan in region r₃ and showed that the current total travel time of 3,703 minutes could be reduced by about 45.6% to 2,014 minutes. The authors also performed a sensitivity analysis where the number of time-critical jobs, the service times, and the number of jobs are increased gradually. Tighter time windows and longer service times lead to a higher satisfaction level of the clients, whereas an increase in the number of jobs improves the situation of the HHC provider as well as of the people, who are currently on the waiting list for HHC services. The analysis shows that these aims can be reached to a certain extent with the same number of HHC workers.

Trautsamwieser et al. (2011) studied the HHC services in the area of Upper Austria and used real-world data of a flood disaster in 2002 as well as standard flood scenarios, namely the 30, 100, and 200 year return period flood discharges (HQ30, HQ100, and HQ200), to depict their consequences on them. Moreover, they presented sensitivity analyses to estimate the impact of different natural disasters on the daily scheduling of HHC services. The results of the VNS based solution method were compared to the exact solutions obtained with the solver software Xpress for 20 small problem instances with 30 jobs, 30 clients, and 6 HHC workers. Both settings, Λ₁ and Λ₂, were tested. In the case of Λ₂, a slightly different weighting as in Trautsamwieser and Hirsch (2011) was selected, based on the suggestions of decision makers in Upper Austria. To compute the impact of the flood scenarios, setting Λ₁ was chosen, since the decision makers do not focus on the preferences of clients and HHC workers during disaster events. Real-world data from the three regions (θ₁, θ₂ and θ₃) were used to assess the impact on infrastructure of the different flood scenarios. This leads to HHC workers, who cannot leave their homes, inaccessible clients, detours due to blocked roads, or slower speeds on the available traffic network. Table 7 highlights the results for an “extreme day” in these three regions, which means that all possible jobs have to be performed.

Table 7

Solution values for an extreme day in three regions with different flood disaster scenarios (cf. Trautsamwieser et al., 2011)

Tabelle 7. Lösungswerte für einen Extremtag in den drei Regionen mit verschiedenen Flutszenarien (vgl. Trautsamwieser et al., 2011)

For HQ30 and HQ100, it is also possible to obtain feasible solutions for regions θ₁ and θ₂, but not for region θ₃. These results show that it is necessary to have additional HHC workers available in region θ₃ during flood events. Moreover, the decision makers need to know which clients cannot be accessed and have to be evacuated if necessary. The findings of Trautsamwieser et al. (2011) highlight the need to think about the risks that the HHC services face. The main results of Rest et al. (2012) are to reveal the potential threats that influence HHC. Based on the work of Trautsamwieser et al. (2011), an option to incorporate these threats into the planning of HHC services was proposed. The solution approach of Trautsamwieser et al. (2011) was used to carry out some additional real-world based numerical studies with flood data and to discuss the results with respect to their practicability. Furthermore, Rest et al. (2012) described the importance of HHC services for industrialized countries and outlined the differences between urban and rural HHC. Figure 3 and Figure 4 show exemplary for a small area within a test region in Upper Austria how the situation for an HHC provider changes if an HQ200 flood occurs. A “normal” day without a flood is depicted in Figure 3, whereas Figure 4 shows the impact of the HQ200 flood. Since some HHC workers have to visit the base of their employer (in this case the ARC) before they start their visits, many tours start and end there. Figure 3 and Figure 4 use the following representation: the circles mark the clients with their identifications, the rectangles show the homes of the single HHC workers, and the base is symbolized through a rectangle with a red cross.

Figure 3

Figure 4

In Figure 4, the flooded area is shaded and all the locations that are affected by the flood are crossed out. If a client is not located directly within the flooded area, but is surrounded by water and therefore not accessible by suitable HHC workers, her/his location is also crossed out. Rest et al. (2012) concluded that the HHC service providers need to face two challenges in future: an increased organizational effort due to the rising demand and the need for an anticipatory risk management.

Fikar and Hirsch (2015) provided a solution procedure for the daily HHC planning problem, if the HHC workers use a dedicated bus service combined with walking routes. The problem has a state-dependent nature, since the time of delivery of an HHC worker at a client determines her/ his pickup time at the same or a subsequent client. The authors used 30 problem instances based on real-world data to test the two variants of the TS based solution procedure, namely TS-SPBS and TS-GT. They investigated two geographic distributions of jobs, an urban (U) and a sub-urban (S) area. The problem instances have a size of 75/100/125 jobs and 24/32/40 HHC workers. In summary, there are six different instance sets consisting of five problem instances each. Each client is visited once and there are two vehicles with a seating capacity for five HHC workers on duty. A comparison between TS-SPBS and TS-GT showed the advantages of using TS-SPBS. Table 8 presents the average number of scheduled HHC workers for each instance set, the percentage savings of vehicles under the assumption that each HHC worker uses her/his own vehicle instead, the average number of pickups, and the percentage of the single components of the objective function.

Table 8

Average solution values for each instance set (cf. Fikar and Hirsch, 2015)

Tabelle 8. Durchschnittliche Lösungswerte für jede Testdatenmenge (vgl. Fikar und Hirsch, 2015)

The presented solution procedure was capable of analyzing the new mobility concept introduced in Fikar and Hirsch (2015). It can be applied to support decision makers at HHC service providers, who want to test an implementation of that concept. The results show that the number of required vehicles can be decreased substantially.

Rest and Hirsch (2016) presented a mathematical model formulation for the daily scheduling of HHC services, where HHC staff uses public transport with time-dependent travel times. The authors developed a dynamic programming approach to compute these time-dependent travel times out of the timetable data of the public transport service providers on a minute base. For solving the problem, three TS based metaheuristics were developed; they are denoted as TS, TSAS, and TSDYN. The authors tested their solution approaches with real-world data from the ARC in Vienna. In total, 20 problem instances with a size ranging from 106 to 202 jobs, 50 to 127 clients, and 16 to 46 HHC workers were evaluated. It was distinguished between two operational scenarios: In the first one, the dispatchers are bound to a predefined roster for the HHC workers; whereas in the second scenario, flexible working times are assumed. TS, TSAS, and TSDYN were compared to each other for all 20 problem instances and the two scenarios. The results show advantages for the TS in case of a predefined roster, whereas for flexible working times, TSDYN performs best. Prolonging the computing time from 10 minutes to 10 hours did not improve the solutions considerably, which proves that the TS based metaheuristics work well. Table 9 shows a comparison between the actual planning of the ARC and the results of TS, TSAS, and TSDYN after a computing time of 600 seconds. The savings obtained by the metaheuristics are given in percent for 12 problem instances and the two scenarios.

Table 9

Savings in travel time of HHC workers obtained by TS, TSAS, and TSDYN when compared to the actual planning of the ARC (cf. Rest and Hirsch, 2016)

Tabelle 9. Einsparungen in der Reisezeit von mobilen Pflegekräften bei Anwendung von TS, TSAS und TSDYN im Vergleich zur aktuellen Planung des Österreichischen Roten Kreuzes (vgl. Rest und Hirsch, 2016)

Table 9 shows that on average, savings of 41.5% with a given roster, and 51.1% with flexible working times are achievable through optimization. The algorithms presented in Rest and Hirsch (2016) are suitable to support the HHC service providers in their daily planning, if the HHC workers use time-dependent public transport; to the best of the author’s knowledge, this is a novelty in HHC planning. The algorithmic ideas of Rest and Hirsch (2016) are also used in a commercial DSS (ingentus, s.a.).

Trautsamwieser and Hirsch (2014) presented an exact solution method and a VNS based algorithm to solve the weekly HHC planning problem. The proposed BPC approach was capable to solve the real-world based test instances with up to 203 jobs, 45 clients, and 9 HHC workers per week to optimality within one hour of computing time. The BPC approach of Trautsamwieser and Hirsch (2014) can be used to generate exact solutions in smaller sized planning units. Moreover, its solutions or generated lower bounds can serve as a benchmark in the development of (mat-, meta-)heuristic approaches.

Rest and Hirsch (2015) carried out a sensitivity analysis that depicts the effects of various disasters in Vienna. The paper is based on real-world data of the ARC in Vienna and uses the algorithms presented in detail in Rest and Hirsch (2016). The results highlight in which areas the HHC workers would be overloaded if disasters occur.

Fikar et al. (2016) dealt with the dynamic case of Fikar and Hirsch (2015). Their computational experiments showed that the developed solution approach is fast and efficient. It can be applied to support real-world operations of trip sharing concepts by enabling rescheduling and rerouting. Fikar and Hirsch (2016) evaluated trip and car sharing concepts for HHC services. It is shown that the number of required vehicles can be reduced substantially if these concepts are used instead of individual cars. Trip sharing performs best if long service durations exist, long delays for parking occur and in urban as well as rural areas. Suburban areas seem to be less suitable for trip sharing systems.

Fikar and Hirsch (2017) studied and classified 44 international scientific journal publications on HHC routing and scheduling. They concluded that this research field is highly heterogeneous in terms of the different focus areas, objectives studied, and the considered regulative settings.

This paper provides a state-of-the-art review on HHC routing and scheduling in Austria. The reader gets a comprehensive overview on current developments and some future research paths can be identified. The importance of doing a research on the care services in Austria is underpinned by the author’s work as well as by other authors (e.g., Hiermann et al., 2015; Braekers et al., 2016; Jungmair and Meixner, 2016). Some alternative mobility concepts for HHC staff still need to be explored. These concepts combine different transport modes with each other and may lead to a more sustainable operation of HHC services, for example, through reduced emissions or less stress for the HHC staff. The solution methods for the planning of these alternative mobility concepts can build partially on the knowledge gathered in this paper. The conference paper of Voegl and Hirsch (2015) evaluated the sustainability criteria for the mobility of HHC staff and identified about 130 different criteria. As the next step, these criteria need to be assessed with suitable indicators and implemented in the planning algorithms. Another important issue in HHC planning is the extension of the planning horizon. Usually, the HHC service providers work with rosters that cover a certain time period, which is chosen by the organization. These rosters influence the degree of freedom of HHC planning considerably, as shown in Rest and Hirsch (2016). Hence, it is necessary to develop new models and algorithms to enable an integrated planning. This leads to additional constraints due to regulations like minimum rest times between single working periods. A first step in this direction was the extension of the planning horizon to one week in Trautsamwieser and Hirsch (2014). Except for one paper (Fikar et al., 2016), all the presented papers deal with a deterministic planning environment. This is an adequate assumption in HHC, since the planning can rely on quite static information. Nevertheless, it is important to extend research on HHC planning to deal efficiently with possible short-term changes during the planning horizon. One research direction concentrates on robust daily scheduling of HHC staff using public transport, which means that the feasibility of a schedule is guaranteed with a certain probability in case of disturbances. Ongoing work also extends the research on impacts of disasters on HHC services. Furthermore, from a methodological point of view, there are numerous possibilities to develop new algorithms and test them on the presented problem instances. In summary, a lot of research paths open up in the area of HHC planning. Some of them are related to other areas of research (e.g., stochastic VRPs) and can partially build on their findings, but others need to be investigated from scratch.