## 1 Introduction  
Home Healthcare (HHC) aims at supporting people with different degrees of dependencies to remain at home instead of receiving long-term care at a traditional medical institution. It encompasses a large variety of care provided at hospitals and gives rise to challenging planning and coordination problems. HHC is set to become an increasingly important issue in the years ahead with the longer human life expectancy. Research on these emerging problems has the intent to establish a fine coordination of human and material resources to provide an optimized planning that maximizes the quality of home healthcare while controlling logistics costs. Therefore, effective organization of HHC structures requires the use of optimization methods and decision support tools. The aim in our study is to determine the routes to be performed by a fleet of vehicles (associated with a group of caregivers) available to serve a set of geographically-dispersed customers (corresponding to the patients), who have preferences associated with caregivers, and so that the activity is planned in the most effective way. The specificities rely on the fact that a home healthcare service must often be performed in a given time window and may require the intervention of several caregivers simultaneously. In addition, sometimes a patient needs several types of care linked by precedence constraints. These timing constraints impose the coordination of several caregivers. This problem is hence modeled as a variant of the vehicle routing problem called _VRPTW-SP_ for the Vehicle Routing Problem with Time Windows, Synchronization, and Precedence constraints. In a previous work ([PERSON] et al. [1]), the minimization of the traveling cost and the sum of non-preferences related to customers were considered as a single-objective function. The obtained results showed the conflicting nature of these criteria, which is why, we are particularly interested in solving the bi-objective version of _VRPTW-SP_. The problem at hand is an extension of the Vehicle Routing Problem (VRP), which is one of the most-studied combinatorial optimization problems. First introduced by [PERSON] and [PERSON] [2], the aim of this NP-hard problem is to determine a set of minimal cost routes in which a set of customers is to be served by a fleet of vehicles based at a depot node. A detailed survey can be found in [PERSON] and [PERSON] [3]. Currently, one of the most effective metaheuristics for the VRP is the hybrid genetic algorithm introduced by [PERSON] [4], which was latter generalized to solve more than 26 VRP variants. Among the different classes of VRP, the VRP with Time Windows (VRPTW) stands as the basis variant of our studied problem. Heuristic and metaheuristic approaches have been widely used to solve the VRPTW such as those proposed by [PERSON] and [PERSON] [5], [PERSON] [6], [PERSON] [7], and [PERSON] et al. [8]. In the field of healthcare, most problems are modeled as a VRPTW. In fact, the origin of vehicle routing problems in HHC systems may be linked to the door-to-door-transportation of elderly or disabled persons (Dial A Ride Problems (DARP)) proposed by [PERSON] and [PERSON] [9]. A few years later, this variant was extended to the Home Healthcare (HHC) problem by [PERSON] and [PERSON] [10], where caregivers are assigned to patient homes to provide specific care. A mixed integer mathematical model was proposed, and a heuristic approach was developed. At this stage, the numerical results were given for only four caregivers and 10 patients. Since then, many other studies were carried out, and they are classified in this paper according to: (1) optimization criterion, (2) constraints, and (3) solution approaches. For a more exhaustive review, see for instance [11; 12]. Table 1 provides a classification of the main types of tackled objectives. Note that each category involves a broad class of possible objective functions. Table 2 summaries the criteria considered in the reviewed papers, these last being listed in Column 1.