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

Implementation and Simulation of Dispatching Algorithm Based on the Shortest Path Planning

孫彥碩 ； 劉喬溫

《機械工業雜誌》 461期 (2021/08) Pp. 83-90

摘要

自動化物料搬運系統（AMHS）已被廣泛運用於各個產業，特別是在半導體的製程中的高架懸掛式運輸系統（Overhead hoist transport, OHT）。該自動化物料搬運系統的控制中最重要的議題就是如何決定每一個運載任務的最短路徑以利縮短運送時間並增加產能，本篇內容主要即為針對特定生產場域中每一個任意點對點的運載任務提出一個以最短路徑為主的路徑規劃，而A*演算法在本文中被引用並以兩台軌道導引搬運車（Rail guided vehicles, RGVs）在特定簡單路線配置為自動化物料搬運系統來驗證其可行性。

關鍵字

自動化物料搬運系統 ； 高架懸掛式運輸系統 ； 軌道導引搬運車 ； 派送系統 ； A*演算法

並列摘要

Automatic Material Handling System (AMHS) has been widely applied in industry, especially for overhead hoist transport (OHT) in semiconductor manufacturing processes. The most important issue in the OHT based AHMS control system is how to determine the shortest path for each transportation task. This paper presents an optimal path planning based on minimization of travelling distance of arbitrary starting location and destination in a specific layout of a production line. The A-star algorithm is utilized to solve the problem in the paper, and an example of two rail guided vehicles (RGVs) as OHT with specific operation conditions are examined under a simple routing layout configuration.

並列關鍵字

AMHS (Automated material handling system) ； OHT (Overhead hoist transport) ； RGV (Rail guided vehicle) ； Dispatching system ； A-star algorithm

參考文獻

Egbelu, Pius J.,Tanchoco, Jose M. A.(1984).Characterization of automatic guided vehicle dispatching rules.Int. J. PROD. RES..22(3),359-374.

Co, Christine G.,Tanchoco, J.M.A.(1991).A review of research on AGVS vehicle management.Engineering Costs and Production Economics.21,35-42.

Sinriech, D.,Tanchoco, J.M.A.(1995).An introduction to the segmented flow approach for discrete material flow systems.Int. J. Prod. Res..33(12),3381-3410.

Bozer, Yanvuz A.,Srinivasan, Mandyam M.(1988).Tandem Configurations for Automated Guided Vehicle Systems and the Analysis of Single Vehicle Loops.,::Department of Industrial and Operations Engineering The University of Michigan.

Tanchoco, J. M. A.,Co, C. G.(1994).Material Flow Systems in Manufacturing.Springer.