以最短路徑為基礎之派車演算法實作與模擬

前言
高架懸掛式運輸系統(Overhead hoist transport, OHT)經常應用於半導體產業中的自動化物料運載系統(Automatic material handling system, AMHS)，和其他的地面式物料運載系統比較例如無人搬運車(Automated guided vehicle, AGV)，OHT的運轉限制會稍微多一些。舉例來說，OHT上的載具-軌道導引車(Rail guided vehicle, RGV)，其運行方式為單向運行，所以OHT系統上的每一段軌道都是被設計為單行道，只能前進不能後退；再者，OHT系統上的RGV載具在變換軌道以及行進路線時需要藉助軌道交接處的轉轍器進行。因此，在多台RGV載具的OHT系統運作中，RGV的派送、路徑規劃以及排程管理相對複雜，不適當的派送法則及交通管理將會導致OHT系統運載過程中產生無效率的繞路，甚至是鎖死(Deadlock)進而造成系統當機。
OHT系統在過去的三十年中，除了在晶圓製造的場域內運轉並與後端的製造資訊系統加以整合，近年來也逐漸擴散至後段的封裝及測試場域內運用，因應此一趨勢，本文將針對OHT系統的路徑規劃以及派送策略做一個介紹，以期收到拋磚引玉之效。本文接下來將會對一般自動化物料運載系統常用路徑規劃以及派送策略的相關研究進行簡要的文獻回顧，並說明本文中運用的派送策略；接下來針對本文將會用到的最短路徑規劃法，A*演算法做一個扼要地介紹；最後將以一個多迴圈兩台RGV為主的OHT系統，以實際模擬說明本文介紹的路徑規劃以及派送策略。
文獻回顧與派送策略
1.文獻回顧
基於AMHS的路徑規劃以及派送策略自從上世紀的八十年代起就已經有相關的文獻及研究，Egbelu [1]提出兩種派送方式，分別是以工作站為主的派送方式(Work center initiated dispatching tasks)以及以車輛為主的派送方式(Vehicle initiated dispatching tasks)，並比較不同派送策略在特定製造場域配置下之效能，Co [2] 與Sinriech [3]則對派送的策略做了一個很好的彙整。Bozer [4]提出區域式無人搬運車系統能夠避免車輛碰撞及簡化交通控制，Tanchoco [5]亦針對AGV的派送法則做一全面概述，並將關於車輛派送之研究主要分為事前規劃(Preplaning)與事件驅動(Event-Driven)兩大類。Mantel [6]探討軌道佈局、無人搬運車的數量要求與運輸作業控制等三個方向，根據個案研究的結果，顯示其中軌道佈局和運輸作業控制是主要問題，並建議相關議題以利進一步的研究。Ross [7]針對區域式與傳統網路式的無人搬運車之表現，評估並比較其車輛平均使用時間、平均產出時間、平均延遲時間以及平均延遲百分比，Hwang [8]研究基於投標策略(Bidding concept)提出新的無人搬運車派送演算法。Ganesharaja [9]著重於無人搬運車的設計與作業流程，Aarab [10]的研究則描述針對無人搬運車設施規劃系統的單向模式(Unidirectional)之導引軌道設計配置。Qui [11]指出平行系統與分散式系統的相似度，並建議將其類比想法運用在無人搬運車的路線與排程。Vis [12]闡述最小流量演算法(Minimum flow algorithm)的發展，並描述如何去計算所需要的無人搬運車的數量。Qiu [13]著重於無人搬運車的系統，回顧無人搬運車的路線與排程文獻，將演算法分成通用拓撲路徑演算法、路徑網絡最佳化與特定拓撲路徑演算法等三大類。Tuan. [14]指出針對軌道設計問題，會因其每一軌道設計的不同而有對應的考量點，在此探討常用的傳統網路式(Conventional)、單迴圈(Single loop)及區域式(Tandem system) 軌道設計等三種軌道佈置。Reza [15]利用禁忌搜尋法(Tabu search)與基因演算法，針對區域式AGV最小化且其最大裝載量之系統。Jeon [16]建議在港口貨櫃的無人搬運車使用Q學習(Q-learning)，以利於找到一個最佳路徑規劃，並用實驗模擬案例佐證Q學習所呈現的路線是最短距離路線。Shaikh [17] 提出一種演算法(Dijkstra’s Algorithm)，藉由此演算法，可以針對數輛無人搬運車找出最短路徑，並且幫助減少移動時間和成本並增加其效率。Chang [18] 利用基於基因演算法的最佳化方法去解決派送問題，並建造出實驗性的晶圓生產驗證場域，數據顯示，與傳統單一派送方法相比，所提出的方法可以明顯改善整合運輸系統(Integrated delivery system)的表現。總結以往的研究已有提出一些實用的派送策略以及演算法，本文將參考部分的派送策略，並以最短路徑規劃為基礎，嘗試運用於以軌道導引為載具之高架懸掛式運輸系統的相關自動運載及車輛管理。
2.派送策略
基於上述的文獻回顧之說明，目前採用的派送策略部分參考Egbelu [1]提出的派送調度策略，在該研究之派送與交通管理規劃階段，派車方法之評估可分為以工作站為優先考慮的指派方式(Workcenter initiated task assignment problem)以及以車輛為優先考慮的指派方式(Vehicle initiated task assignment problem)，以下先說明這兩種派工調度策略並各別提出相近地派送方式，再針對本文中以最短路徑為基礎的演算法，選擇以最短距離為主的派送調度做為主要策略。
以工作站為優先考慮的指派方式為當多部車輛載具處於閒置狀態，而有一工件需被運送，此時選擇其中一台載具去承載此一工件。在此指派方式下，可能的派車法則有：
(1)隨機選取車輛法則 (Random vehicle rule, RV)
(2)距離最近之車輛法則 (Nearest idle vehicle rule, NIV)
(3)使用率最低之車輛法則 (Least utilized vehicle rule, LUV)
(4)先到先服務之法則(First come first serve rule, MFCFS)