Dynamic daily scheduling of mobile care services that use time-dependent multimodal transportation
The aim of the project was to develop dynamic planning tools in order to support the daily scheduling of home health care (HHC) services. HHC services are of vital importance for today's society. With services ranging from qualified home nursing to assistance in leading the household, they allow old and frail people a self-determined living in their familiar environment. The current demographic and social developments induce a significant increase in their demand. Currently, the scheduling is usually done manually and because of its complexity, suitable decision support systems are highly welcomed.
We consider a real-world HHC problem, which is based on the demands of the Austrian Red Cross (ARC), one of the leading HHC service providers in Austria. It has a daily planning horizon and focuses on urban regions. Extending previous research we primary concentrate on the dynamic and stochastic aspects of the problem. Its objective consists of minimizing the total expected travel and waiting times of the nurses. The problem itself can be briefly summarized as follows:
A certain number of heterogeneous nurses, with different qualification levels and working times, has to visit a set of clients at least once during a day. Various assignment constraints (e.g., language skills, declined nurses, etc.) and hard time windows of these visits are considered. In HHC, it may happen several times a day that the estimated service time for treating a client is exceeded as it usually depends on the physical condition of the client. It may also happen that new clients show up who need last-minute services (e.g., due to dehospitalization) and thus, have to be inserted into the existing schedules. In practice, nurses use either cars or public transport, depending on the geographical region and the efficiency of the public transport system. As the project aims at urban operational areas with well-established public transport systems, time-dependent public transport is considered as the main choice of transport. Besides the fact that not each nurse owns a driving license, it is also more efficient for traveling in cities, if one takes traffic- and parking conditions into account. Therefore, for example, more than 90 % of the ARC-nurses in Vienna are using public transport.
Optimization in the field of HHC is a rather young but quickly evolving research area. However, routing with public transport is still hardly considered in literature. Stochastic programming has only been applied to the HHC assignment problem. This type of problem has a mid- to long-term perspective and aims at assigning clients to nurses based on their needs and skills. While the routing of the nurses is not considered, it usually addresses aspects like continuity of care or workload balancing.
The developed solution approach had to satisfy two main requirements. First, it should focus on computing robust schedules that are able to cope with smaller disturbances. Second, in case a certain extent is reached, it should provide tools for efficient rescheduling.
The algorithms have been tested with real-world based data from the ARC in Vienna. The solutions are compared with those obtained with deterministic service times, in order to evaluate the robustness of the computed schedules.
From a modelling point of view, the underlying problem can be seen as a time-dependent vehicle routing problem with stochastic service times and additional HHC-related constraints. First, a mathematical problem formulation has been stated, implemented and solved with the solver software Xpress 7.8. The developed mixed integer linear program is able to solve instances with up to 3 nurses and 15 Jobs to optimality within 24h of computation time.
The developed solution approach builds upon our previous time-dependent and multimodal routing algorithms and aims at computing robust schedules that are able to cope with disturbances up to a certain extent. Currently, it is assumed that the service times for treating a client follow a known probability distribution and are independent from each other. Nevertheless, due to the modelling of the uncertainty, various events (e.g. prolonged travel times or new jobs) with various distributions can be handled.
A discrete time approach has been chosen to model the time-dependency. To efficiently compute time-dependent travel time matrices out of the timetables from the public transport service providers, a dynamic programming approach has been implemented. It considers walking to nearby stations as well as waiting for later connections and complies with the first in - first out (FIFO) property, which is a natural assumption for time-dependent routing. To solve real-world sized instances within reasonable time, a time-dependent Tabu Search (TS) based algorithm has been developed and implemented in the programming language C++. Infeasible solutions are temporarily allowed and a dynamically adapted weighted evaluation function is used to guide the search process. To speed up the search, the developed TS dynamically changes the size of its neighborhood. For the rescheduling, a flexible discrete-event driven metaheuristic was developed. It iteratively generates promising solutions based on the occurrence of events over time. Multiple promising solutions are generated through the use of biased-randomisation techniques.
In order to incorporate the stochastic service times and to compute efficient robust schedules, a penalty formulation together with a chance-constraint is used. Thus, the objective function is extended by the expected costs for recourse actions. Recourse actions are needed in case a route gets infeasible because of the prolonged service times. In such a case, it is assumed that HHC service providers send out floaters, who step in and take over a certain number of clients in order to sustain the services of the subsequent clients in the route. In addition, the chance-constraint limits the probability that a route gets invalidated to a given threshold.
The solution approach has been tested with real-world data from the ARC in Vienna, with up to 202 jobs and 46 nurses. It has been revealed that most schedules ignoring uncertainty are actually infeasible if the scheduled service time is exceeded. Assuming a geometric distribution (p = 0.5), the average probability of the feasibility of the schedules increases from 75.5 % to 99.9 %. However, the minimum feasibility values increase from 51.6 % to 99.2 %, revealing that almost every route contains jobs where the service time must not be exceeded. Of course, this robustness comes at a price, which results in an average increase in traveling and waiting times of 9.7 %.