集裝箱港口動(dòng)態(tài)泊位指派仿真優(yōu)化

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

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

0 引言

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

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

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

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

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

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

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

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

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

2.1 仿真分析

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

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

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

2.2 仿真建模

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

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

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

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

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

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

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

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

圖3 染色體表達(dá)實(shí)例

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

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

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

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

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

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

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

表2 本文方法與人工貪婪算法對(duì)比

5 結(jié)束語

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

當(dāng)然，集裝箱碼頭的作業(yè)系統(tǒng)非常復(fù)雜，泊位指派和分配問題除了離散泊位指派問題外還有連續(xù)泊位指派的問題.此外，實(shí)際操作中，泊位指派計(jì)劃制訂時(shí)還需要考慮岸橋計(jì)劃、堆場計(jì)劃等.進(jìn)一步研究可從以下3個(gè)方面展開:(1)研究在泊位分配的同時(shí)考慮船舶進(jìn)入泊位的順序;(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］王軍，李卓蓉.基于遺傳算法的動(dòng)態(tài)泊位分配問題優(yōu)化研究［J］.中國水運(yùn)，2011，11(1):63-65.

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

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

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

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

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

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