考量船隻選擇與時間窗之中期船席規劃問題

Abstract

本研究之核心為策略性的中期船席規劃問題，其目的為使有大量船舶停靠需求的擁擠港口能藉由此模式提供的指派資訊，決定是否接受該船停泊需求，並給予接受指派的船舶相應的指派船席。不同於過去短期的船席指派問題，本研究考慮之模式引入了循環週期長度，目的為安排船席模板(Berth Template)，使該模板能套用在中期的碼頭船席決策，做港口資源最佳化的利用。同時，本研究在模式考量航商偏好之時間窗，使船席配置規劃能深入顧客服務層面，此結果也能提供航商未來長期的船期排程參考。本研究嘗試將中期船席規劃問題建構出數學模式，並考量問題規模與求解時間和求解品質，將該類中期船席規劃問題轉換成常見的集合涵蓋問題，並參考圖形最大權重匹配之演算方式進行求解演算法之構建。在數值例題測試部分，該演算方式能在可接受時間內完成可行解之搜尋，並有良好的求解績效。本研究期藉由數學模式與演算方式能增進中期船席規劃問題之發展與應用，提升中期船席規劃問題的可行性與求解效率。

Under the context of a congested container terminal, solving the congested problem has become the most important issue to port operators. The study developed two mixed integer programming (MIP) models for the tactical berth template design problem. With the objective of cost minimization, the terminal operator determines the berth assignment and the service starting time of the potential calling ships on a cyclical basis with respect to a fixed length of planning horizon. The operator has the flexibility of denying a ship at the price of losing a ship-dependent revenue or berthing it within a specific time window. In particular, an early or late penalty cost is incurred, if the ship service starting time is deviated from the preferred target time. This study compared the performances of the two IP formulations, one directly using the binary variable to represent the decision of berth assignment and service sequencing and the other indirectly making use of the generalized set-partitioning model. It was found that the performance of the latter is much better. This study further designed a heuristic solution algorithm based on the classic maximum weighted matching problem with respect to the generalized set-partitioning formulation. Based on the numerical experiments, the model and the solution algorithm developed in this study are promising in enhancing the literature of the tactical planning of container terminals