應用人工智慧法於最佳消毒作業之時窗限制車輛途程問題

Artificial Intelligence Approaches for the Optimal Disinfection Operations of Vehicle Routing Problem with Time Windows

鄧宗倫(Zong-Lun Deng)

指導教授 ： 謝益智

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

摘要

時窗限制車輛途程問題(Vehicle Routing Problem with Time Windows, VRPTW)是車輛途程問題(Vehicle Routing Problem, VRP)的延伸，現實生活中常被應用在物流配送問題上，在近幾年中，已成為一項重要的研究與應用領域。本研究探討消毒作業排程問題，此問題包含了車輛的藥劑載重以及各消毒地點的時窗限制，問題目的為以最小的總成本來安排消毒排程的路徑，因此亦屬於時窗限制車輛途程的問題。一般傳統的時窗限制車輛途程問題的時窗限制均設定必須在某給定之時間段內完成服務，且各服務點皆為單次服務，然而本研究探討的消毒作業排程問題不同於傳統的時窗限制車輛途程問題，其中各個服務點的需求為多重服務(即噴灑多種消毒藥劑)，除此之外，為了噴灑安全時窗限制的條件是各服務點每一次的消毒，必須與該服務點上一個消毒作業間隔某段時間以上，才能再接受下一次服務。
由於時窗限制車輛途程問題之求解複雜度很高，屬於NP-hard問題，以傳統最佳化方法求解時，須花費冗長的運算時間亦無法獲得最佳解。因此啟發式演算法(heuristic)便成為一個較可行之途徑，雖不能保證求得整體最佳解，但其具有求解快速且能求得最佳解之近似解的優點。
本研究之主要目的為提出三種啟發式演算法，其包括免疫演算法(Immune Algorithm, IA)、遺傳演算法(Genetic Algorithm, GA)及粒子群最佳化(Particle Swarm Optimization, PSO)，本研究以虎尾科技大學為例，針對單車型及雙車合作型等不同之消毒策略，求解消毒排程的路徑以最小化總成本。實驗數值結果顯示，免疫演算法之結果較優於其他兩種演算法。

關鍵字

時窗限制車輛途程問題 ； 免疫演算法 ； 遺傳演算法 ； 粒子群最佳化 ； 消毒作業排程

並列摘要

The Vehicle Routing Problem with Time Windows (VRPTW) is an extension of the Vehicle Routing Problem (VRP). It has become an important research and the application field in recent years. This thesis studies the optimal disinfection operations problem which is similar to the well known contained vehicle capacity with time windows. This problem is arranged an optimal route with minimal cost. The studied disinfection operations problem is one of the vehicle routing problems with time windows, however, it is different to the traditional VRPTW since each node of the studied disinfection operations problem has to receive multiple various services (various liquid medicines) to disinfect various insects and bacteria. In addition, for safety, the interval times of spray of different liquid medicines should be up to given periods.
Due to its high computational complexity, VRPTW is a NP-hard problem. Typical mathematical programming approaches are time expensive for finding the optimal solution of VRPTW. Therefore, in practice, heuristics are proposed to solve VRPTW.
These main purposes of this thesis are multiple. Firstly, we propose three heuristic algorithms, including Immune Algorithm, Genetic Algorithm and Particle Swarm Optimization for solving the proposed disinfection operations problem. Secondly, based upon NFU campus, we solve for the optimal disinfection strategy and routs with single vehicle and multiple vehicles, respectively. Numerical results show that Immune Algorithm performs better than Genetic Algorithm and Particle Swarm Optimization.

並列關鍵字

Vehicle Routing Problem ； Time Window ； Immune Algorithm ； Genetic Algorithm ； Particle Swarm Optimization ； Disinfection Operation

參考文獻

15.郭惠梋 (2004)，物流派車管理之研究，靜宜大學資訊管理研究所，碩士論文。

7.李佳蓮 (2006)，車輛排程問題的廣域搜尋解法，國立成功大學土木工程研究所，碩士論文。

20.Alvarenga, G.B., Mateus, G.R. & Tomi, G.de (2007). “A genetic and set partitioning two-phase approach for the vehicle routing problem with time windows”, Computers & Operations Research, Vol.34, No.6, pp.1561-1584.

21.Angelelli, E. & Speranza, M.G. (2002). “The periodic vehicle routing problem with intermediate facilities”, European Journal of Operational Research, Vol.137, No.2, pp.233-247.

22.Bachem, A., Hochstattler, W. & Malich, M. (1996). “The simulated trading heuristic for solving vehicle routing problems”, Discrete Applied Mathematics, Vol.65, No.1-3, pp.47-72.