Home Health Care (HHC) services have emerged as a result of the need to provide care to patients/people who cannot be treated in hospital due to their special conditions and/or need home care. The care and treatment processes provided by this service have been appreciated by researchers as they can be less expensive and just as effective than care provided by a hospital or a skilled care facility. HHC gains importance due to the increasing epidemic disease cases, the increase in the elderly population, etc. In this study, it is aimed to provide high quality service as well as minimizing travel costs by considering the constraints related to travel balancing and type of transportation vehicle. So, environmental and economic factors could be included in the model. The proposed Home Health Care Routing Problem with Health Team Skill Level (HTSL-HHCRP) model was coded in GAMS 24.2.1 software. A new hybrid method named as Genetic Algorithm Simulated Annealing-Marine Predators Algorithm (GASA-MPA) has been developed to solve the large dimensions of the problem. In hybrid approach, SA has been used with an initial point obtained by GA. On the other hand, feasibility of the neighborhood solutions is guaranteed by solving a constraint satisfaction problem via MPA. Test problems’ performance was analyzed using the Relative Deviation Index (RDI) evaluation criteria. In addition, the sensitivity of the results according to some parameters selected by scenario analysis was examined. Results confirm the efficiency of the GASA-MPA algorithm in terms of time and objective function. Furthermore, by addressing skill levels of the healthcare team, it is shown that the proposed algorithm performs better than more traditional evolutionary algorithms in HHCRP. The comparisons show that the proposed method outperformed the classical methods not only in terms of best solution, but also the Gap (%) and RDI values.