考慮照護人員與病人雙方媒合程度之家庭健康照護排程與繞境問題之研究

Home Health Care Rostering and Routing Problem with Matching Score of Caregivers and Caretakers

劉珮羽

指導教授 ： 林春成

國立交通大學/管理學院/工業工程與管理系所/碩士(2018年)

摘要

家庭健康照護服務(Home Health Care Service，HHCS)隨著社會的高齡化越來越被重視。近年來除了求解照護人員的排程(Rostering)與車程(Vehicle Routing)問題，越來越多研究在規劃照護人員排程時會考慮病人對照護人員的偏好(Preference)來提升病人滿意度。然而，過去研究在考慮病人對照護人員偏好時，缺乏考慮病人對照護人員之偏好項目間的重視程度之差異，使得最終雙方媒合結果無法確實表現出病人之偏好。因此，本研究提出照護人員與病人雙方媒合程度(Matching Score)之家庭健康照護排程與繞境問題(Joint Rostering and Routing Problem in HHCS)。本研究之排程過程考慮了病人對照護人員之偏好，且讓偏好項目間具有重視程度之差異，以此計算出病人與照護人員雙方的媒合程度，使越符合病人偏好的照護人員有越高的機率執行服務，進而使病人不滿意度降低。接著考慮照護人員之技能、HHCS之法規、以及車程上的限制，以最小化成本與病人不滿意度為目標，規劃出照護人員的一週班表與車程。由於此問題包含照護人員排班與有時間窗格的車輛繞境兩個子問題皆為NP-hard問題，因此適合以啟發式演算法求解。基因演算法在過去排程研究有優異的效能，而變動鄰域搜索法也被證實較其他演算法更適合求解車輛繞境問題。因此，本研究結合兩個演算法的長處，採用聯合基因演算法與變動鄰域演算法來求解，亦即利用基因演算法求解照護人員排班問題；變動鄰域搜索法求解有時間窗格的車輛繞境問題。實驗結果顯示，本研究所提出之病人與照護人員雙方媒合機制能夠有效降低病人不滿意度；而所提出之演算法在不同的問題實例中，皆能較其他演算法穩定求得較佳的結果。

關鍵字

家庭健康照護 ； 照護人員排程 ； 有時間窗格的車輛路徑問題 ； 基因演算法 ； 變動鄰域搜索法

並列摘要

As the era of population aging, the home health care problems have become more and more attention. In recent years, in addition to solving the Nurse rostering problem and vehicle routing problem, more and more studies have been conducted to improve patient satisfaction by considering the patient's preference for the home care worker. However, most of home care workers for schedule did not consider the lack of the difference in the degree of attention between the items of the patient's preference for the home care worker in the previous work. Therefore, this dissertation proposes Home Health Care Rostering and Routing Problem with Matching Score of Caregivers and Caretakers. Considering the patient’s preference for the home care worker and making the preference items have different levels of emphasis, and calculate the matching score between the patient and the home care worker. That the nurse who more in line with the patient's preferences has a higher probability to perform the task. The study is planning a weekly schedule for home care workers with the goal of minimizing costs and maximizing patient and home care worker satisfaction and caregiver satisfaction under constraints of skills qualifications, regulations, and link time. Because the home health care rostering and routing problem is the NP-hard problem，and the two sub-problems home care worker rostering and vehicle routing problems with time windows are also NP-hard problems. It is suitable to solve by heuristic algorithm. Due to the excellent performance of genetic algorithms (GA) in past scheduling studies, and the variable neighborhood search method (VNS) has also been proved to be more suitable for solving the vehicle routing problems with time windows than other algorithms, exactly the same with the two sub-problems of our problems. So this paper proposes a joint GA and VNS, divided the problem into two stages to solve. Using GA to solve the home care worker rostering, VNS to solve the vehicle routing problems with time windows. The experimental results show that the matching mechanism of patients and home care workers proposed in this study can effectively improve patient satisfaction; the combined GA and VNS can be obtained more stable and better results than other algorithms in different instances.

並列關鍵字

Home Health care problems ； home care worker rostering ； vehicle routing problems with time windows ； Genetic Algorithm ； Variable Neighborhood Search

參考文獻

H. Algethami, R. L. Pinheiro, and D. Landa-Silva, 2016. “A genetic algorithm for a workforce scheduling and routing problem,” in Proc. of 2016 IEEE Congress on Evolutionary Computation (CEC), IEEE Press, 2016.

M. Angelova, O. Roeva, and T. Pencheva, 2015. “InterCriteria analysis of crossover and mutation rates relations in simple genetic algorithm,” in Proc. of 2015 Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE, 2015, 419-424.

J. de Armas, E. Lalla-Ruiz, C. Expósito-Izquierdo, D. Landa-Silva, and B. Melián-Batista, 2015. “A hybrid GRASP-VNS for ship routing and scheduling problem with discretized time windows,” Engineering Applications of Artificial Intelligence, 45, 350-360.

A. Baniamerian, M. Bashiri and F. Zabihi, 2018. “A modified variable neighborhood search hybridized with genetic algorithm for vehicle routing problems with cross-docking,” Electronic Notes in Discrete Mathematics, 66, 143-150.

S. Belhaiza, P. Hansen, and G. Laporte, 2014. “A hybrid variable neighborhood tabu search heuristic for the vehicle routing problem with multiple time windows,” Computers & Operations Research, 52, 269-281.