Abstract: The decline in fertility and the increase in average life expectancy have led to the rapid aging of the global population. In 2019, the proportion of the global people aged 65 and older reached 11%, and it is expected to increase to 16% by 2050. China is one of the countries with the most serious aging population. The results of the 7th Chinese census in 2020 show that the population aged 65 and older accounted for 13.5%, which is close to the deep aging level of 14%.To improve the community pension system and meet the demands of most patients for long-term and continuous health care services in China, family doctor contract services are developed by the government at the grassroots level. In this service, doctors can provide medical services to patients at their home, such as medical tests, wound care, therapy services, and care visits. It is especially suitable for the “key population” such as elderly, pregnant women, and patients with chronic diseases.It has become an important way to safeguard people’s health in China.
Home health care routing and scheduling problem (HHCRSP) is constructing routes for doctors to provide the patients’ services, which directly determines the scheduling activities and is generally modeled as an extension of the vehicle routing problem. According to the scheduling time horizon, HHCRSP can be categorized as either a single period (such as a single day) optimization problem or a multi-period (such as a week or a month) optimization problem. By analyzing related existing studies, it can be found that: (1) Most existing studies have focused on the single-period HHCRSP,while few studies have related to periodic scheduling problem. (2) Most existing studies assume that patients’ service days are fixed. However, in practice, patients are not willing toreceive service on each day, and every patient may have different preference satisfaction for the different days. (3) In the multi-period HHCRSPs, most studies have considered the patients’ preference satisfaction from the service continuity, which are captured by minimizing the total number of different doctors visiting the same patient during the planning horizon, or minimizing the relative frequency of patients receiving services between the current and last visit. No research has considered patients’ preference satisfaction from the perspective of service continuity between different days. Therefore, this paper introduces a periodic HHCRSP with the consideration of patient preference on time windows. The main contributions are as follows:
First, this paper assumes patients have fixed service frequencies but have different preference satisfaction for different time windows to accept services. By considering constraints about the skill requirements of patients, time windows, patients’ service date regulations and doctors’ working regulations, the problem is formulated as a mixed-integer linear programming model to minimize the total travel costs and maximize the patients’ preference satisfaction.The patients’ preference satisfaction captures the served time window, and service continuity between different days.
Second, since our problem is NP-hard and the exact method can only get the optimal solution of small instances, this paper chooses tabu search as the backbone and proposes a tailored hybrid tabu search (HTS) to get the approximate solution of more instances in a reasonable computation time. In this algorithm, a tailored initial solution construction procedure and a new solution generation method are designed. A shake procedure is also embedded to improve and diversify the search.
Finally, by numerical experiments,this paper analyzes the problem properties and parameter sensitivities, and tests the performance of HTS. The results demonstrates that: (1) The travel cost and objective function value decrease when the maximum skill deviation increases. (2) With the increase of time window preference weight and doctor-patient matching preference weight, the travel cost increases and the objective value decreases. (3) The shake procedure and neighborhoods can effectively improve the efficiency of HTS, and the proposed HTS can effectively solve instances of various scales.
The research conclusion has practical guiding significance for the scheduling decision of doctors in family doctor contract service. Under the medical resources in short situation, to some extent this paper can promote the development and improvement of family doctor contract service. In the future, the problem can be extended to more realistic dynamic situations (e.g., some patient requests are suddenly canceled or added, or the time window for patients to receive service is modified suddenly, etc.).

Key words: periodic home health care routing and scheduling problem, patient preference, multiple time windows, vehicle routing problem, Tabu search

摘要： 针对周期性家庭医护人员调度问题,研究了病人接受医疗服务的频次固定,但对不同接受服务的时间窗有不同偏好的情形。以最小化运营成本、最大化病人偏好满意度为目标建立了混合整数规划线性模型,设计了混合禁忌搜索算法进行求解。数值实验表明:医护人员的最大降级数越大,路径成本和目标函数值越小;病人对时间窗偏好的权重和医患匹配偏好权重越大,路径成本越大但目标函数值越小;混合禁忌搜索算法能有效求解各种规模的算例。

关键词: 周期性家庭医护人员调度, 病人偏好, 多时间窗, 车辆路径问题, 禁忌搜索