以導引式螞蟻演算法求解運輸與運籌領域之排序問題

Abstract

運輸(Transportation)與運籌(Logistics)屬於作業密集(Operation-intensive)的產業，其中許 多問題牽涉到排序(Sequencing)的決策。此類問題的複雜度隨著問題規模的上升是以階 層(Factorial)的方式增加，因此在考量產業經營的實際情況時，稍具實務意涵的問題在求 解上都有極高的挑戰性，而發展有效的啟發式解法就具備了相當的必要性。對於排序相 關問題，相較於其他各種巨集式啟發式演算法(Meta-heuristics)，例如基因演算法(Genetic Algorithm)、模擬退火演算法(Simulated Annealing)、禁忌搜尋法(Tabu Search)等，螞蟻演 算法(Ant Colony Optimization, ACO)有一些本質上的優勢，因為它搜尋與建立解答的過 程，基本上就是一個循序的架構。基於此種結構上的特性，螞蟻演算法也已經被廣泛應 用在各種排序相關的問題上。本研究發現在運輸與運籌領域裡，有兩個相當重要的問題 類型與排序決策有極大的關連性，一是港口作業的「船席指派問題(Berth Allocation Problem, BAP)」，另一個是製造或物流作業的「駁運式排程(Cross-Docking Scheduling, CDS)」。然而，螞蟻演算法固然在架構上很合適求解排序相關問題，但是其搜尋空間仍 然非常可觀。因此，本研究將嘗試利用其他等求解技巧，發展一個導引(Guide)螞蟻的機 制，以有效限縮螞蟻搜尋的空間、縮短對應的求解時間，並提升求解品質。最後，本研 究將以能反映實際運作情形的例題進行數值測試，以驗證所發展演算法的可用性。

Transportation and logistics are operation-intensive industries, and there are many problems involving the decisions about sequencing. The complexity of this type of problems increases in the factorial way when the problem size increases. When dealing with the real situations, it is challenging to solve any problem with significant practical implication. Therefore, it is usually required to develop an efficient heuristic algorithm. For the sequencing related problems, Ant Colony Optimization (ACO) has some inherited advantages over the other meta-heuristics, such as Genetic Algorithm (GA), Simulated Annealing (SA), and Tabu Search (TS), as the searching process or the solution building procedure basically has a sequential framework. Based on this structural feature, the ACO algorithms have been applied to many problems involving the sequencing decisions. This study identifies two important sequencing-related decision problems in the fields of transportation and logistics. One is the Berth Allocation Problem (BAP) for the sea port operations, and the other is the Cross-Docking Scheduling (CDS) for the manufacturing or logistics operations. Although the ACO algorithms are suitable for the sequencing problems, the search space for the ants is still considerably large. Therefore, this study plans to make use of various solution techniques to develop that mechanism that can guide the ants for searching so as to limit the space needed to explore, shorten the computation time, and improve the solution quality. Finally, the numerical experiments that can reflect to real operation in the field will be performed to validate the applicability of the developed solution algorithms.