應用人工智慧法於居家照顧服務排程路徑規劃問題

Artificial Intelligence Approaches for the Home Care Scheduling Routing Problem

許正良(Cheng-Liang Hsu)

指導教授 ： 謝益智

國立虎尾科技大學/管理學院/工業工程與管理研究所/碩士(2013年)

摘要

本研究探討居家照護服務排程路徑規劃問題，此問題包含服務人員的安排以及週期性服務地點，問題的目標為以最小成本來選擇服務人員組合與服務地點之排程順序，因此此居家照護服務排程路徑規劃問題亦屬於週期性車輛路徑問題(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.

並列關鍵字

Periodic Vehicle Routing Problem ； Genetic Algorithm ； Immune Algorithm ； Particle Swarm Optimization ； home care scheduling routing problem

參考文獻

9. 林豐澤(2005)，「演化式計算下篇：基因演算法以及三種應用實例」，東北大學資訊科學與工程學院系統工程學報，3卷，2期，頁25-56。

10. 林雪華(2010)，應用粒子群最佳化演算法與免疫演算法為基之動態分群於顧客關係管理研究，台北科技大學工業工程與管理系碩士班，碩士論文。

12. 范姜智勇(2008)，基因演算法中交配與突變交互作用之研究，國立台北科技大學光電工程系碩士班，碩士論文。

13. 陳登銳(2009)，適應性基因演算法在主動噪音控制系統之應用，中原大學電機工程學系，碩士論文。

2. 台灣長期照護專業協會(2013)，http://www.ltcpa.org.tw/，引用日期：2013.05.12。