Add to e-Shelf The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies
European Journal of Operational Research 219 (2012) 598–610
Contents lists available at SciVerse ScienceDirect
European Journal of Operational Research journal homepage: www.elsevier.com/locate/ejor
The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies
Matias Sevel Rasmussen 1, Tor Justesen 2, Anders Dohn 2, Jesper Larsen ⇑
Department of Management Engineering, Technical University of Denmark, Produktionstorvet, Building 424, DK-2800 Kgs. Lyngby, Denmark
a r t i c l e
i n f o
Article history:
Available online 10 November 2011
Keywords:
Home care
Crew scheduling
Vehicle routing
Generalised precedence constraints
Branch-and-price
Set partitioning
a b s t r a c t
In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.
We model the problem as a set partitioning problem with side constraints and develop an exact branch-and-price solution algorithm, as this method has previously given solid results for classical vehicle routing problems. Temporal dependencies are modelled as generalised precedence constraints and enforced through the branching. We introduce a novel visit clustering approach based on the soft preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss of quality for few
instances.
Contents lists available at SciVerse ScienceDirect
European Journal of Operational Research journal homepage: www.elsevier.com/locate/ejor
The Home Care Crew Scheduling Problem: Preference-based visit clustering and temporal dependencies
Matias Sevel Rasmussen 1, Tor Justesen 2, Anders Dohn 2, Jesper Larsen ⇑
Department of Management Engineering, Technical University of Denmark, Produktionstorvet, Building 424, DK-2800 Kgs. Lyngby, Denmark
a r t i c l e
i n f o
Article history:
Available online 10 November 2011
Keywords:
Home care
Crew scheduling
Vehicle routing
Generalised precedence constraints
Branch-and-price
Set partitioning
a b s t r a c t
In the Home Care Crew Scheduling Problem a staff of home carers has to be assigned a number of visits to patients’ homes, such that the overall service level is maximised. The problem is a generalisation of the vehicle routing problem with time windows. Required travel time between visits and time windows of the visits must be respected. The challenge when assigning visits to home carers lies in the existence of soft preference constraints and in temporal dependencies between the start times of visits.
We model the problem as a set partitioning problem with side constraints and develop an exact branch-and-price solution algorithm, as this method has previously given solid results for classical vehicle routing problems. Temporal dependencies are modelled as generalised precedence constraints and enforced through the branching. We introduce a novel visit clustering approach based on the soft preference constraints. The algorithm is tested both on real-life problem instances and on generated test instances inspired by realistic settings. The use of the specialised branching scheme on real-life problems is novel. The visit clustering decreases run times significantly, and only gives a loss of quality for few
instances.
References: Begur, S., Miller, D., Weaver, J., 1997. An integrated spatial dss for scheduling and routing home-health-care nurses Bertels, S., Fahle, T., 2006. A hybrid setup for a hybrid scenario: Combining heuristics for the home health care problem Research 33 (10), 2866–2890. Bredström, D., Rönnqvist, M. 2007. A branch and price algorithm for the combined vehicle routing and scheduling problem with synchronization constraints. Bredström, D., Rönnqvist, M., 2008. Combined vehicle routing and scheduling with temporal precedence and synchronization constraints Chabrier, A., 2006. Vehicle routing problem with elementary shortest path based column generation Cheng, E., Rich, J.L., 1998. A home health care routing and scheduling problem. Cordeau, J.-F., Desaulniers, G., Desrosiers, J., Solomon, M.M., Soumis, F., 2002. Vrp with time windows Dohn, A., Kolind, E., Clausen, J., 2009. The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach. Computers and Operations Research 36 (4), 1145–1157. Dohn, A., Rasmussen, M.S., Larsen, J., 2011. The vehicle routing problem with time windows and temporal dependencies Dror, M., 1994. Note on the complexity of the shortest path models for column generation in VRPTW Eveborn, P., Flisberg, P., Rönnqvist, M., 2006. Laps care—an operational system for staff planning of home care Feillet, D., Dejax, P., Gendreau, M., Gueguen, C., 2004. An exact algorithm for the elementary shortest path problem with resource constraints: Application to Foster, B.A., Ryan, D.M., 1976. An integer programming approach to the vehicle scheduling problem Garey, M., Johnson, D., 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness Gélinas, S., Desrochers, M., Desrosiers, J., Solomon, M., 1995. A new branching strategy for time constrained routing problems with application to backhauling. Ioachim, I., Desrosiers, J., Soumis, F., Bélanger, N., 1999. Fleet assignment and routing with schedule synchronization constraints Kallehauge, B., Larsen, J., Madsen, O.B., Solomon, M., 2005. The vehicle routing problem with time windows Lessel, C.R. 2007. Ruteplanlægning i hjemmeplejen. Master’s thesis, Informatics and Mathematical Modelling, Technical University of Denmark. Li, Y., Lim, A., Rodrigues, B., 2005. Manpower allocation with time windows and jobteaming constraints. Naval Research Logistics 52 (4), 302–311. Lim, A., Rodrigues, B., Song, L., 2004. Manpower allocation with time windows. Journal of the Operational Research Society 55 (11), 1178–1186. Lougee-Heimer, R., 2003. The common optimization interface for operations research: Promoting open-source software in the operations research Rezanova, N.J., Ryan, D.M., 2010. The train driver recovery problem – a set partitioning based model and solution method Ryan, D.M., Foster, B. 1981. An integer programming approach to scheduling. Thomsen, K. 2006. Optimization on home care. Master’s thesis, Informatics and Mathematical Modelling, Technical University of Denmark. van den Akker, J., Hoogeveen, J., van Kempen, J., 2006. Parallel machine scheduling through column generation: Minimax objective functions