Résumé indisponible. / A healthcare network or health system consists of all organizations, actions and people who participate to promote, restore or maintain people’s health. The health care systems in many developed countries are facing increasing costs. The major reason is the changing age distribution of the population with more elderly people in need of support. Increasing healthcare costs has created new alternatives to traditional hospitalization in which one is Home Health Care (HHC). Home health care or domiciliary care is the provision of health care and assistance to people in their own homes, according to a formal assessment of their needs. HHC has attained a specific place in healthcare network. HHC programs have now been successfully implemented in many countries. The purpose of HHC is to provide the care and support needed to assist patients to live independently in their own homes. HHC is primarily performed by means of personal visitations of healthcare workers to patients in their homes, where they provide care assistance according to patients’ needs. In this thesis we have considered different aspects of planning problems for home health care services. The efficient use of resources is necessary in continuous healthcare services. To meet the increased demand of HHC, operation research specialist can play an important role by solving the various combinatorial optimization problems arising in HHC. These problems can be tactical, strategic or operational with respect to planning horizon. Strategic problems are those which help in attaining long term goals or objectives, e.g. higher level of quality for HHC patients and efficient use of resources. These strategic objectives can be achieved through tactical i.e. medium term panning and operational planning i.e. short term planning. The main purpose of our thesis is to identify these potential optimization problems and solve them via recent metaheuristics. HHC is an alternative to traditional hospitalization and has got a significant share in the organization of healthcare in developed countries. The change in aging demographics, recent development in technology and the increase in the demand of healthcare services are major reasons for this rapid growth. Some studies show HHC as a tool to reduce costs of care, which is a major preoccupation in developed countries. Some others reveal that it leads to the improvement of patients’ satisfaction without increasing the resources. Home health care, i.e. visiting and nursing patients in their homes, is a flourishing realm in the medical industry. The number of companies has grown largely both in public and private sectors. The staffing needs for HHC companies have been expanded as well. Also they face the problem of assigning geographically dispersed patients to home healthcare workers and preparing daily schedules for these workers. The challenge of this problem is to combine aspects of vehicle routing and staff rostering. Both of them are well known NP- hard combinatorial optimization problems, it means the amount of computational time required to find solution increases exponentially with problem size. Home healthcare workers scheduling problem is difficult to solve optimally due to presence of large number of constraints. These are two types of constraints: hard constraints and soft constraints. The hard constraints are the restrictions to be fulfilled for the schedules to be applicable and soft constraints are preferences to improve the quality of these schedules. (...)

Cette thèse comporte des résultats théoriques et pratiques sur deux métaheuristiques, la Recherche Dispersée et la Recherche Voisinage variable (RVV), ainsi que sur des Matheuristiques. Au niveau théorique, la contribution principale de cette thèse est la proposition d’un algorithme de recherche dispersée avec l’arrondi directionnel convergent pour les programmes en nombres entiers mixtes (0-1 MIP), avec une preuve de cette convergence en un nombre fini d’itérations. En se basant sur cet algorithme convergeant, deux implémentations et plusieurs heuristiques sont proposées et testées sur des instances de 0-1 MIP. Les versions testées reposent sur des implémentations non optimisées pour mettre en évidence la puissance des approches dans une forme simplifiée. Nos résultats démontrent l’efficacité de ces approches initiales, ce qui les rend attractives lorsque des solutions de très haute qualité sont recherchées avec un investissement approprié en termes d’effort de calcul. Cette thèse inclut également quelques nouvelles variantes de la métaheuristique Recherche Voisinage Variable telles qu’une recherche voisinage variable deux niveaux, une recherche voisinage variable imbriquée, une descente voisinage variable cyclique et une heuristique de plongée voisinage variable. En outre, plusieurs implémentations efficaces de ces algorithmes basés sur la recherche voisinage variable ont été appliquées avec succès à des problèmes NP-Difficiles apparaissant en transport, logistique, production d’énergie, ordonnancement, et segmentation. Les heuristiques proposées se sont avérées être les nouvelles heuristiques de référence sur tous les problèmes considérés. La dernière contribution de cette thèse repose sur la proposition de plusieurs matheuristiques pour résoudre le problème de Conception de Réseau Multi-flots avec Coût fixe (CRMC). Les performances de ces matheuristiques ont été évaluées sur un ensemble d’instances de référence du CRMC. Les résultats obtenus démontrent la compétitivité des approches proposées par rapport aux approches existantes de la littérature. / This thesis consists of results obtained studying Scatter Search, Variable Neighbourhood Search (VNS), and Matheuristics in both theoretical and practical context. Regarding theoretical results, one of the main contribution of this thesis is a convergent scatter search with directional rounding algorithm for 0-1 Mixed Integer Programs (MIP) with the proof of its finite convergence. Besides this, a convergent scatter search algorithm is accompanied by two variants of its implementation. Additionally, several scatter search based heuristics, stemming from a convergent scatter search algorithm have been proposed and tested on some instances of 0-1 MIP. The versions of the methods tested are first stage implementations to establish the power of the methods in a simplified form. Our findings demonstrate the efficacy of these first stage methods, which makes them attractive for use in situations where very high quality solutions are sought with an efficient investment of computational effort.This thesis also includes new variants of Variable Neighborhood Search metaheuristic such as a two-level variable neighborhood search, a nested variable neighborhood search, a cyclic variable neighborhood descent and a variable neighborhood diving. Additionally, several efficient implementation of those variable neighborhood search algorithms have been successfully applied for solving NP-Hard problems appearing in transportation, logistics, power generation, scheduling and clustering. On all tested problems, the proposed VNS heuristics turned out to be a new state-of-the art heuristics. The last contribution of this thesis consists of proposing several matheuristics for solving Fixed-Charge Multicommodity Network Design (MCND) problem. The performances of these matheuristics have been disclosed on benchmark instances for MCND. The obtained results demonstrate the competitiveness of the proposed matheuristics with other existing approaches in the literature.