- 學位論文
以類免疫演算法應用於船席指派問題之研究
A Study On The Application Of Artificial Immune Algorithm On The Berth Allocation Problem
摘要
經營一個港埠，國家需投入大量的資金、設備與人力，而港埠設立後的各項設施、經營績效良窳，對國家經濟發展影響甚钜。船舶停泊作業為海運過程中首要作業，效率的好壞直接影響到後續作業的運作，而國內目前在停泊作業上，航商、代理行與港口船席調配小組以會議的方式進行，此種方式固然可以解決問題，但是能做出最佳決策，值得商榷。 本研究在模式構建上主要是以參予船席指派決策的航商、港埠當局為主，在考量航商在港時間最小化、港埠當局營運成本最小化來構建多目標模式，並以車輛繞徑的角度解釋船席指派問題。問題的求解則是以C語言自行撰寫類免疫演算法配合模糊理論進行求解。 以自行設計的小型範例配合窮舉法來確認模式的正確性，並利用此結果來進行演算法的證確性測試；演算法參數的選擇的上，則是利用了ANOVA檢定找出較佳的參數。此外，設計了不同規模、不同船舶到達型態範例，以禁忌搜尋法、類免疫演算法進行求解，比較兩者的求解品質。最後利用基隆港民國95年5月22日至5月28日船席指派紀錄作為實証資料、敏感度分析。 本研究將「船席」視為車輛繞徑中的「車輛」，「船舶」視為「需求點」，且假設需求點的作業時間、節線成本會因為車輛、需求點的不同而有所差異，以此方式解釋船席指派問題並構建多目標模式。 窮舉法的結果確認模式的正確性(有解)，而禁忌搜尋法、類免疫演算法都可以找到與窮舉法相同的觧，證實了演算法的正確性。不同類型的範例中，經過統計檢定兩種演算法的求解結果，發現類免疫演算法在大型範例中有較佳的求解品質；以基隆港過去船席指派紀錄與模式求解比較結果，本模式下兩個目標的隸屬函數值，均優於實務指派結果隸屬函數值；敏感度分析方面，經由多次的測試，發現船席服務的船舶數與服務時間、使用成本成反向變動，合乎一般的邏輯性，更可證明本模式正確性，具有應用價值，可以作為實務單位營運決策之參考。
並列摘要
Most of the import and export freights are transported by sea transportation in Taiwan. Berth Allocation Problem (BAP) is essential problem for the operation of the port authority. The time and location assignment of the berths to vessels is cricial to the efficiency of the port operation. In the current practice in Taiwan, this decision is made by port authority and shipowner in the daily berth allocation meeting, which may not be the best policy to be adopted. A series of academic researchs have devoted on the optimal BAP model for this problem. However, there is no model address this problem from the point of views of both port authority and shipowners, which is the focus of the model proposed in this study. In this research, we attempt to explore the application of the VRP (vehicle routing problem) concept on the BAP. With the focus of the interests of the port authority and shipowner, a multi-objective programming model is formulated in this study. There are two objectives in this model, i.e., the minimization of the total time in port of the shipowners, and the minimization of the working cost of the port authority. With the NP-Hard nautrre of the porposed model, it is harder to get the optimal solution when the size of problem increasing. Therefore, the artificial immune algorithm (IA) and Tabu Search algorithm (TA) are proposed as the main solution procedure of the study for its diversity search ability. In order to reduce subject judgements in the multiple- objective programming, a series of fuzzy functions for the objectives are developed for this study. Finally, to evaluate the propsed model and the algorithms developed in the study, a series of case studies include one data from Keelung harbor are tested in this study. The results of these numerical tests indicate that the IA performs better in large size problem. The solution of the proposed procedure provides better result than the conclusion of the daily berth meeting approach.