集裝箱港口動態泊位指派仿真優化

樂美龍，陳雷雷，2，黃有方

(1.上海海事大學 科學研究院，上海 201306;2.上海海洋大學 工程學院，上海 201306)

0 引言

集裝箱是重要的物流單元，集裝箱運輸已成為最重要的運輸方式，在跨國、跨洲的長途運輸領域更是如此.集裝箱港口是當今最為重要的物流樞紐;泊位是集裝箱港口最為重要的資源.泊位指派合理與否，直接影響到集裝箱船舶在港口的停泊時間和港口的運營成本，是航運與港口企業能否高效率和高效益運作的關鍵之一.當今，大型集裝箱船的運輸和裝卸規模越來越大［1］，泊位指派的復雜性也隨之增加.

泊位指派可分為離散泊位指派和連續泊位指派.IMAI 等［2］研究多用戶港口系統的泊位指派問題，引入離散泊位動態指派的基本模型;此后又在其動態泊位指派模型的基礎上引入服務優先級和港口能力限制等因素，對其研究進一步豐富和補充［3-4］.LEE 等［5］探討連續泊位下的泊位計劃問題，給出臨域搜索啟發式算法，算法中考慮先到先服務以及船舶作業安全間距等實際規則.GOLIAS 等［6］研究顧客服務級別優先程度不同情況下的動態和離散泊位分派問題，建立多目標復合優化模型，并用遺傳算法求解.國內也有不少學者對集裝箱港口的泊位指派問題進行研究.王軍等［7］應用遺傳算法研究動態泊位的指派問題，一些學者［8-11］應用仿真方法對泊位服務系統進行仿真建模和分析.當前的研究對泊位指派中以船舶在港時間最短為目標時存在的非線性問題討論較少，而仿真研究中也缺乏對泊位分配方案的自動生成和優化.近年來，仿真優化作為新的研究領域逐漸被學者們所重視，其基本思想是用仿真模型模擬實際系統，且以仿真結果評估實際系統的性能和參數的優劣，并在上層設計優化算法對仿真結果進行優化，進而達到優化實際系統的目的.就泊位指派問題而言，以仿真技術結合現代智能優化算法探討泊位指派方案的生成和優化，有較高的研究價值和意義.

1 動態泊位指派問題的數學描述

為了便于描述泊位指派問題的數學模型，作如下假設:

(2)B為泊位的集合，i為該集合中第i個元素，即泊位i，i=1，2，…，I;

(4)優化目標為船舶在港時間最小，船舶在港時間包含船舶的裝卸作業時間和等待時間;

(5)不考慮由于天氣等意外因素引起的船舶延遲離港，船舶到港時間已知.

式(3)確保每艘船均接受一次裝卸服務，而式(4)確定泊位一次最多服務一艘船.此外，由于船舶在特定泊位接受服務的順序k是連續排序的，當第k-1 序號無船舶接受服務時，第k 序號應當也無船舶接受服務，式(5)正是該邏輯的約束.式(6)則保證集裝箱船只有在到達泊位后才能開始進行裝卸服務.

2 動態離散泊位系統仿真建模

2.1 仿真分析

通過以上分析可知，如果應用數學規劃模型對泊位指派問題進行求解，其目標函數存在非線性，且隨著船舶數量的增長和泊位數量的增加，問題的規模會急劇擴大，因此用求解混合整數規劃模型的分支定界法、割平面法等常規求解方法難以求解.仿真技術建立在相似性原理之上，通過對現有真實系統的描述和模擬能夠使得真實系統在計算機里再現.越來越多的建模與仿真技術被成功應用于集裝箱碼頭的規劃設計和營運管理上［12］.應用仿真方法能夠有效解決目標函數非線性問題，在此基礎上的泊位指派優化更為高效和精確.

仿真系統可以分為時間推動和事件推動兩種類型.在時間推動的仿真系統框架下，系統能夠記錄仿真實現每一個事件發生的時間點.就離散泊位指派問題而言，不管是靜態的還是動態的，其目標函數均為所有船只的在港時間.在仿真的框架下其目標函數即可以表示為

此外，在仿真模型中，約束條件大多由仿真系統的結構保證.在離散泊位指派問題中，式(3)和(4)可通過設置相應仿真元素的容量實現，而式(8)則無須特別考慮，因為在仿真系統中只有主動實體到達才會有相應的仿真事件發生.

2.2 仿真建模

作為集裝箱港口的一個子系統，離散泊位系統的主要組成部分有集裝箱船舶、泊位、錨地等待區等.根據集裝箱船舶靠港的一般過程，泊位指派過程中主要發生的事務依次有:(1)船舶到達;(2)泊位分配;(3)排隊等待;(4)裝卸服務;(5)船舶離港.具體流程見圖1.

圖1 離散泊位系統仿真流程

根據離散泊位系統的基本理論可知，不論是在靜態還是動態情景下船舶到達港口的時間都是已知的，所以每艘船舶的到達時間構成船舶到達計劃表.在仿真過程中，船舶以此為依據到達港口.泊位分配，則是將所有到達船舶分為若干個子集，每一個子集對應一個具體泊位.每艘船舶和其對應的泊位分配編號構成泊位分配表.仿真過程中，船舶根據泊位分配表進入相應的等待隊列，隊列內的排隊規則為先到先服務.船舶靠泊后，泊位橋吊對船舶進行裝卸作業.不同泊位服務不同船只的時間各不相同，于是，相應船舶和對應泊位的裝卸服務時間構成船舶泊位服務時間矩陣，以表格的形式體現在仿真系統中.仿真過程中，船舶靠泊后具體服務時間由船舶編號和泊位編號兩個量決定.在服務時間矩陣中確定每一次裝卸作業的具體服務時間.

3 基于遺傳算法的離散泊位指派仿真優化

遺傳算法(Genetic Algorithm，GA)［13］是一種借鑒生物界的進化規律(適者生存，優勝劣汰遺傳機制)演化而來的隨機搜索方法，由美國的HOLLAND教授1975 年首先提出.其主要特點是直接對結構對象進行操作，不存在求導和函數連續性的限定;具有內在的并行性和更好的全局尋優能力;采用概率化的尋優方法，能自動獲取和指導優化的搜索空間，自適應地調整搜索方向，不需要確定的規則.由于GA的這些性質，它已被廣泛應用于組合優化、機器學習、信號處理、自適應控制和人工生命等領域.

GA 對染色體的選擇和淘汰的主要標準為適應度函數.而在仿真框架下離散泊位系統的在港時間為每次仿真實驗后得到的在港時間值.基于GA 的仿真優化流程見圖2.

圖2 基于GA 的離散泊位系統仿真優化流程

與傳統的二進制編碼方式不同，仿真優化中可采用每位編碼的序號對應相應的船舶，編碼的內容為分配的泊位編號，編碼的取值范圍為集合B，即{1，2，…，I}.以8 艘船、3個泊位為例，其染色體表達見圖3，一個染色體個體對應一種泊位分配方案:

圖3 染色體表達實例

4 離散泊位系統仿真優化案例分析

某港口擁有4個泊位，某日有8 艘船舶要求靠泊碼頭進行裝卸服務.8 艘船舶的到達時間和各船舶對應泊位的服務時間見表1.要求確定當日的最佳泊位分配方案，以使得船舶在港總時間最短.

表1 船舶泊位服務時間矩陣

根據該港口實際情況，仿真總體框架見圖4.在集裝箱船舶進入系統時記錄到達時間tAj，在船舶完成作業離開系統時記錄離開時間tLj，仿真結束時計算總體等待時間.

圖4 離散泊位系統仿真模型

在eM-plant 提供的GA 模塊中以總體等待時間最短為優化目標，以{1，2，3，4}為解集分別對應4個泊位，定義決策變量集{K1，K2，K3，K4，K5，K6，K7，K8}，其中的元素對應于染色體上相應編碼位的值，并將優化迭代得到的結果作為仿真模型的泊位指派指令.選擇交叉概率為0.8，變異概率為0.1.設置種群大小為30，迭代次數為30.模型經過30 代遺傳求解，算法的適應度值收斂過程見圖5.船舶在港時間最短為2 080 min，最佳分配方案為{3，4，1，2，4，3，1，3}，即1 號船進入3 號泊位，2 號船進入4 號泊位，以此類推，見圖6.

港口泊位計劃人員在泊位指派過程中一般按照先到先服務的原則，根據貪婪算法安排泊位(人工貪婪算法)，如船舶1 到達時泊位全部空閑則安排至裝卸時間最短的泊位3，而船舶2 到達時則安排在泊位4，若泊位全部被占用則船舶等待，若有泊位空閑則安排先到船舶靠泊進行裝卸服務.根據該日8 艘船的到達信息及在各泊位的裝卸時間，其泊位安排見表2中人工貪婪算法部分.由表2 計算可知，在本案例中用本文提出的基于GA 的仿真優化指派的船舶總體在港時間比人工貪婪算法指派的減少170 min，而且隨著到港船舶數量的增加其優勢會進一步顯現.

表2 本文方法與人工貪婪算法對比

5 結束語

隨著經濟的發展和集裝箱運輸在物流領域的廣泛應用，各大港口集裝箱的吞吐量也隨之增長.面對日益增長的集裝箱運輸需求，港口間競爭的日益激烈，合理配置資源以提高港口運作效率和效益是必由之路.本文通過建立動態離散泊位指派的數學模型，并在此基礎上，提出離散泊位指派的仿真模型和基于GA 的仿真優化方法.運用仿真優化方法，不僅可以很好地解決數學分析中存在的目標函數非線性問題，而且可以通過仿真模型的結構控制取代數學模型中的約束條件.本方法不僅可以提高分析的準確性，而且可以在很大程度上簡化求解過程，可用于集裝箱港口泊位資源的配置和調度.

當然，集裝箱碼頭的作業系統非常復雜，泊位指派和分配問題除了離散泊位指派問題外還有連續泊位指派的問題.此外，實際操作中，泊位指派計劃制訂時還需要考慮岸橋計劃、堆場計劃等.進一步研究可從以下3個方面展開:(1)研究在泊位分配的同時考慮船舶進入泊位的順序;(2)探索連續泊位指派的仿真優化方法;(3)結合岸橋調度研究泊位指派的仿真優化問題.

［1］VACCA I，BIERLAIRE M，SALANI M.Optimization at container terminals:status，trends，and perspectives［C］// Proc the Swiss Transport Res Conf.Monte Verita/Ascona，2007:1-21.

［2］IMAI A，NISHIMURA E，PAPADIMITRIOU S.The dynamic berth allocation problem for a container port［J］.Transportation Res:Part B，2001，35(4):401-417.

［3］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berth allocation with service priority［J］.Transportation Res:Part B，2003，37(5):437-457.

［4］IMAI A，NISHIMURA E，PAPADIMITRIOU S.Berthing ships at multi-user container terminal with a limited quay capacity［J］.Transportation Res:Part E，2008，44(1):136-151.

［5］LEE Yusin，CHEN Chuen-Yih.An optimization heuristic for the berth scheduling problem［J］.Eur J Operational Res，2009，196(2):500-508.

［6］GOLIAS M M，BOILE M，THEOFANIS S.Berth scheduling by customer service differentiation:a multi-objective approach［J］.Transportation Res:Part E，2009，45(6):878-892.

［7］王軍，李卓蓉.基于遺傳算法的動態泊位分配問題優化研究［J］.中國水運，2011，11(1):63-65.

［8］何軍良，宓為建，謝塵，等.基于分布式混合遺傳算法的動態泊位分配策略與仿真［J］.上海海事大學學報，2008，29(2):53-57.

［9］曾慶成，張倩.集裝箱泊位分配干擾管理仿真優化模型與算法［J］.中國科技論文在線，2009，4(10):742-746.

［10］王紅湘，嚴偉.基于啟發式算法和仿真優化的岸壁線長度泊位分配策略［J］.上海海事大學學報，2008，29(1):19-22.

［11］張靜，劉翠蓮.港口泊位服務系統的影響因素及其仿真［J］.大連海事大學學報:社會科學版，2008，7(6):110-112.

［12］沙梅.集裝箱碼頭物流系統建模與仿真綜述［J］.上海海事大學學報，2005，26(1):6-12.

［13］馬小姝，李宇龍，嚴浪.傳統多目標優化方法和多目標遺傳算法的比較綜述［J］.電氣傳動自動化，2010，32(3):48-50.