運用資料探勘技術解決自動化設備傳送路徑壅塞問題

Abstract

在路徑規劃相關的研究議題中，大多皆以最短路徑成本(一般來說是距離成本)來作為主要的評估項目，但在實際的應用上，可能會因為路徑壅塞的因素，而導致最短路徑所得到的時間成本卻未必最短。目前在科技業所使用的自動化傳送設備的路徑規劃上，僅大多仰賴於供應商所提供的物流管理系統(Material Control System, MCS)來進行路徑規劃。 本論文將以實際的科技業廠房，建置一個自動化傳送的路徑路網，並以實際的動態路由路徑規劃演算法為實驗比較的基礎。將各筆傳送資料以代克斯托演算法(Dijkstra’s algorithm)找到最短路徑距離後，模擬實際行走的時間。最後以本論文所提出的資料探勘演算法，先以關聯法則(Association rule)探勘訓練資料集內擁有過高支持度的路徑，並將之視為壅塞路徑後，調高其路徑距離成本。再將驗證資料集以代克斯托演算法找到最短路徑距離後，模擬實際行走的時間。最終，以動態路由演算法、代克斯托演算法及資料探勘演算法三者來比較其路徑規劃優劣。由最後模擬出的結果可以得知，本論文所提出的方法確實可以達到較短傳送時間的目標

Existing research on issues associated with path planning generally base their evaluations on the costs of the shortest path (commonly referred to as distance costs). However, in practical application, the time costs of the shortest path may not be the lowest due to path congestion. For the path planning of their automation transferring systems, the technology industry often depends on the material control system (MCS) provided by their suppliers. This study developed a path network for automation transferring in an actual factory and compared the experiment results with the dynamic routing produced by an actual path planning algorithm. We employed Dijkstra’s algorithm to obtain the distance of the shortest path and then simulated the actual travel time. Using the data mining algorithm proposed in this paper, we then mined paths receiving overly high degrees of support in the training data based on the association rule and considered these paths to be congested before increasing their distance costs. Once the distance of the shortest path was identified from the verified data using Dijkstra’s algorithm, we simulated the actual travel time. We compared the results of the dynamic routing algorithm, Dijkstra’s algorithm, and the proposed data mining algorithm. The simulation results indicated that the proposed method can achieve shorter delivery times.