Home care services are an alternative answer to hospitalization, and play an important role in reducing the healthcare costs for governments and healthcare practitioners. To find a valid plan for these services, an optimization problem called the home healthcare routing and scheduling problem is motivated to perform the logistics of the home care services. Although most studies mainly focus on minimizing the total cost of logistics activities, no study, as far as we know, has treated the patients’ satisfaction as an objective function under uncertainty. To make this problem more practical, this study proposes a bi-objective optimization methodology to model a multi-period and multi-depot home healthcare routing and scheduling problem in a fuzzy environment. With regards to a group of uncertain parameters such as the time of travel and services as well as patients’ satisfaction, a fuzzy approach named as the Jimenez’s method, is also utilized. To address the proposed home healthcare problem, new and well-established metaheuristics are obtained. Although the social engineering optimizer (SEO) has been applied to several optimization problems, it has not yet been applied in the healthcare routing and scheduling area. Another innovation is to develop a new modified multi-objective version of SEO by using an adaptive memory strategy, so-called AMSEO. Finally, a comprehensive discussion is provided by comparing the algorithms based on multi-objective metrics and sensitivity analyses. The practicality and efficiency of the AMSEO in this context lends weight to the development and application of the approach more broadly.