家庭健康照護服務之聯合排班、繞徑、與重排問題

Abstract

家庭健康照護問題是結合有時窗的車輛途程與護理人員排程的問題，由於兩個問題均是NP-hard問題，故過去許多研究將有時窗的車輛途程與護理人員排程問題分開解決。然而，有時窗的車輛途程與護理人員排程是互相影響且兩者目標可能相互有衝突，且過去在規劃家庭健康照護之護理人員排程問題時，護理人員對於班次的喜好與解決突發狀況是較缺乏討論的。因此，本文提出解決家庭健康照護服務之聯合排程與繞徑問題，並考量喜好、法規限制、資格限制與車程限制等多個限制下，安排護理人員服務所有的病人並至病人家提供服務以規劃出多數護理人員滿意度最大的班表；並提出當突發狀況發生時，解決家庭健康照護服務之聯合排程、繞徑、與重排問題，並多加考量重排限制下，重新安排護理人員服務所有的病人與去病人家的路線，有效規劃出與原班表差異最小化且符合多數護理人員滿意度最大的班表。而在過去研究中提及改良型和聲演算法在解決排程問題時，能比基因與和聲搜尋演算法更有效能，由於本文也是屬於排程問題，因此本文以改良型和聲演算法來搜尋最佳解，不僅修改演算法的調整機制，並加入移民和動態調整機制以提高求解效率。實驗方面則各別求解兩個實際案例，並將本研究方法與和聲演算法做相互比較，同時模擬不同需重排的動態情境，分析研究方法在不同問題與動態情境上的通用性。

The home health care problem is a combinatorial optimization problem that includes nurse rostering problem and vehicle routing problem with time windows, both of which are NP-hard. Most of the previous related works resolved them separately. However, optimization of those two subproblems affects each other and their objective functions may be in conflict with each other. Additionally, nurses’ preferred work shifts and unexpected situations were never considered in previous home health care problems. To meet more practical requirements, this paper proposes a home health care problem that jointly considering rostering, routing, in which an optimal nurse schedule under constraints of nurses’ preferences, qualifications, vehicle routing and lows is generated. Considering the constraint of rerostering, to rearrange nurses’ service and the route that nurse go to patient homes, effective planning new table with minimization of difference and maximize the nurse’ preferences, solve the home health care problem that jointly considering rostering, routing, and rerostering, when the emergency situation happened. Since the harmony search algorithm (HSA) has been shown to perform better for solving home health care problems, this paper proposes an improved HSA in which a crossover operator of genetic algorithm is applied to generate new solutions and the algorithm is adjusted to meet more problem-specific information and improve computational efficiency.