Home health care services have improved medical care allowing greater coverage of patients in their homes. In order to meet the demands of the service, monthly planning of caregiver’s shifts and daily routing of caregivers are addressed. Two optimization problems have mostly been discussed individually related with HHC: Nurse Scheduling problem (NSP) and Vehicle Routing. This study addresses an approach that considers the interaction of the two problems for an application in a case study in a private hospital, located in Bogotá, Colombia.  First a multi-objective mathematical model is developed for NSP using epsilon constraint. Thereafter, for solving the VRP, initially a mathematical model is proposed, then a Tabu Search metaheuristic is also implemented to find a solution in an acceptable computational time given the NP-hard complexity of the problem at hand. The impact of the proposed solution methods are demonstrated through the resolution of real size instances, outperforming the solutions implemented by the hospital´s decision planner. Obtained results show that proposed solution methods are able to reach near optimal solutions for both the NSP and VRP.