| Designing rosters and building routes for travelling workers has long fascinated the mathematical community for the complexity and diversity of the problems related to them. Nurses of Home Health Care (HHC) in CLSC Cote-des-Neiges are good examples of these itinerant workers. Indeed, they have to travel daily to the homes of patients to provide them with the care they need. Whatever the occupation, the problem of these itinerant workers is the same: how to optimize routes of a fleet of vehicles in order to visit the greatest number of customers while minimizing travel time. In addition to minimizing the distance traveled, another objective related to the context of HHC emerges; balancing of workload among nurses.; Solving HHC problem consists to solve a Vehicle Routing Problem (VRP). Note that when the temporal aspect is taken into account, as is the case of HHC, this type of problem is called in the literature Vehicle Routing Problem with Time windows (VRPTW). It has been proved that the PTVFT is an NP-hard problem, and that finding a feasible solution to a PTVFT is a NP-complete problem. The complexity and difficulty of this kind of problem leads to the development and selection of a heuristic approach to the problem of HHC.; The development of appropriate models requires analysis of the organization of HHC services and nurses travel. Thus, we have developed an information system (IS) to collect strategic information related to the HHC services. The IS incorporates also nurses scheduling and routing algorithms.; As we mentioned earlier, these heuristics must minimize nurses' travel time, while balancing the workload between them. In literature, a number of studies have focused on the balance of workloads. However, the majority of researchers balance the workload according to the treatment duration or the service time. However, by analyzing the context of HHC, we note that several factors come into play in the calculation of the workload; the traveling time or the number of heavy patients are only a few examples of these criteria. So far, we are aware of no studies that have focused on balancing the workload considering several indicators.; The primary goal of this thesis is to conduct a comparative analysis of the eight scheduling and routing algorithms. The comparison of these methods is made through 18 indicators that measure the level of workload balancing.; The simulation results show the superiority of algorithms that take into account the balancing of workloads among nurses compared with those who ignore it. However, we find that they are improving as the number of customers increases and for the majority of indicators. Furthermore, we note that the best results are mainly provided by the algorithms that assign the customers depending on the of the smallest service time, namely heuristics 1 and 4. These methods gave very similar results for most indicators in the study. It should be noted that for small and medium instances, the algorithm 1 that groups the customers depending on their period, gives better results than the heuristic 4, which does not include. For large instances, the opposite applies. |
