Beta 1

Title The Home Care Crew Scheduling Problem
Author Justesen, Tor
Rasmussen, Matias Sevel (Operations Research, Department of Management Engineering, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Supervisor Larsen, Jesper (Operations Research, Department of Management Engineering, Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark)
Institution Technical University of Denmark, DTU, DK-2800 Kgs. Lyngby, Denmark
Thesis level Master's thesis
Year 2008
Abstract In the Home Care Crew Scheduling Problem (HCCSP) a staff of caretakers has to be assigned a number of tasks, such that the total number of assigned tasks is maximised. The tasks have different locations and positions in time, and travelling time and time windows must be respected. The challenge when assigning tasks to caretakers lies in the existence of several soft constraints and indeed also in timewise constraints connecting the tasks. Preferably all of these constraints are satisfied, however for different reasons, this is not always possible. We call a solution to the problem home care optimal, if it satisfies all soft constraints. The problem originates from the scheduling of tasks in the home care sector and has many similarities with the well-studied Vehicle Routing Problem with Time Windows (VRPTW) and the Crew Scheduling Problem with Time Windows (CSPTW). Former approaches to solving the HCCSP involve the use of heuristic methods. In this thesis, we will show that by using an exact algorithm as the basis and then modifying this intelligently, it is possible to generate home care optimal solutions which are in general better than the solutions found by the use of heuristics. The thesis constitutes a proof-of-concept and only focuses on the efficiency of the algorithm to some extent. The developed exact algorithm is based on a branch-and-price approach using column generation. The algorithm is tested on real-life problem instances supplied by the Danish company Zealand Care and we obtain solutions that are near to home care optimal in most cases. The problem is decomposed into a master and a subproblem. We model a very general precedence constraint that captures all timewise constraints from real-life, and we handle precedence constraints in the branching, which we have not seen elsewhere in the literature. We devise an exact label setting algorithm for solving the Elementary Shortest Path Problem with Resource Constraints (ESPPRC) subproblem. Solving the subproblem constitutes a substantial impact on the overall running time of the branch-and-price algorithm. To counteract this, intelligent reductions of the ESPPRC networks are introduced. When reducing the ESPPRC networks, the number of unassigned tasks may increase, hence the branch-and-price algorithm is extended to handle tasks that are unassigned as a consequence of the reductions of the ESPPRC networks. The reductions in the ESPPRC networks and the changes to the branchand-price algorithm result in improvements of both the quality of the solutions, many of which are close to being home care optimal, and the overall efficiency of the algorithm.
Imprint DTU Informatics : Kgs. Lyngby
Series IMM-M.Sc.-2008-22
Original PDF ep08_22_ej_fortrolig.pdf (1.17 MB)
Admin Creation date: 2008-03-06    Update date: 2010-03-08    Source: dtu    ID: 211533    Original MXD