Program > By speaker > Cissé Mohamed

We focus on Home Health Care Routing Problem (HHCRP). HHCRP consists in designing routes followed by a team of home care workers to care a group of patients living in a given geographical area. For this scheduling stage, the decision maker has to take into account many constraints : time windows, qualification requirements, synchronization, temporal dependencies, continuity of care. HHCRP is then an extension of Vehicle Routing Problem (VRP) augmented by many unusual size-constraints coming from Home Care context. In this study, we propose an extension of the so-called Split Tour for HHCRP. Split Tour is the kernel of many successful heuristics for VRP. Given a fixed sequence of services to schedule, which represents a giant tour of services without trip delimiters, we propose a label setting algorithm in order to extract the optimal solution based on this fixed sequence. This algorithm takes into account the constraints of HHCRP. Valid inequalities has been added in order to reduce the labels generated thus decreasing the computational time. Due to the fact that the algorithm is exponential in theory, many suboptimal approaches has been implemented leading to faster algorithms : limiting the number of labels for each node, limit the number of total labels generated, relaxing synchronization constraints. Computational experiments has been conducted on randomly generated sequences and optimal sequences from instances of literature. We compare the results of the algorithm to those of CPLEX. Finally, some research perspectives are outlined.