本研究探討居家照護服務排程路徑規劃問題,此問題包含服務人員的安排以及週期性服務地點,問題的目標為以最小成本來選擇服務人員組合與服務地點之排程順序,因此此居家照護服務排程路徑規劃問題亦屬於週期性車輛路徑問題(PVRP)。由於週期性車輛路徑問題是屬於NP-hard問題,若利用傳統最佳化的方法,需花費冗時間求解,且無法得到趨近於最佳之解。因此,啟發式演算法(Heuristic)便成為另一個可行的方法,雖然不能保證求出來的解為最佳解,但其有求解快速且能求得近似最佳解的能力。 本研究應用三種啟發式演算法,其包括基因演算法(Genetic Algorithm)、免疫演算法(Immune Algorithm)與粒子群最佳化演算法(Particle Swarm Optimization),針對使用車輛配置的不同、服務人員成本與服務速度不同組合之變化以及服務地點基本時間設置的不同,來求解居家照護排程路徑規劃之最小成本,並將三種演算法做比較。實驗數值結果顯示,免疫演算法之結果較優於其他兩種演算法。
This thesis studies the home care scheduling routing problem which containes the arrangement of servers and periodic service locations. The objective of interest in this thesis is to minimize the total cost based upon the combination of types and number of servers and the service location scheduling. The home care scheduling routing problem is classified into the periodic vehicle routing problem (PVRP). Besides, due to the PVRP is essentially a NP-Hard problem, typical mathematical programming approaches are time consuming for finding the optimal solution of PVRP. Hence, In this study, heuristics are proposed to solve this home care scheduling routing problem. Although we cannot ensure to find the optimal solution, the proposed heuristics are able to obtain approximate optimal solutions fastly. In this study, we apply three heuristic algorithms, including Genetic Algorithm, Immune Algorithm and Particle Swarm Optimization. Based upon different service times, combinations of vehicles, speeds of service rate (SSR) and costs rate (SSC), we solve several home care scheduling routing problems and discuss the performance of these three heuristic algorithms. Numerical results indicate that the heuristic algorithms can find good solutions for the considered problems. In addition, numerical results also show that the proposed Immune Algorithm performs better than both Genetic Algorithm and Particle Swarm Optimization. Moreover, Genetic Algorithm is also performs better than Particle Swarm Optimization.