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

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

0 引言

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

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

1 動態(tài)泊位指派問題的數(shù)學(xué)描述

為了便于描述泊位指派問題的數(shù)學(xué)模型，作如下假設(shè):

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

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

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

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

2 動態(tài)離散泊位系統(tǒng)仿真建模

2.1 仿真分析

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

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

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

2.2 仿真建模

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

圖1 離散泊位系統(tǒng)仿真流程

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

3 基于遺傳算法的離散泊位指派仿真優(yōu)化

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

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

圖2 基于GA 的離散泊位系統(tǒng)仿真優(yōu)化流程

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

圖3 染色體表達實例

4 離散泊位系統(tǒng)仿真優(yōu)化案例分析

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

表1 船舶泊位服務(wù)時間矩陣

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

圖4 離散泊位系統(tǒng)仿真模型

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

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

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

5 結(jié)束語

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

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

［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］王軍，李卓蓉.基于遺傳算法的動態(tài)泊位分配問題優(yōu)化研究［J］.中國水運，2011，11(1):63-65.

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

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

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

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

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

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