徐遠(yuǎn)琴，韓曉龍

(上海海事大學(xué) 物流研究中心，上海201306)

集卡是連接船舶和堆場的水平運(yùn)輸工具，在港口運(yùn)作中起著至關(guān)重要的作用。隨著我國港口貨物吞吐量的迅速增加，如何提高集裝箱碼頭作業(yè)效率、減少集卡作業(yè)時間已經(jīng)成為港口面臨的重要問題。集卡動態(tài)調(diào)度可以減少其運(yùn)作時間，提高碼頭作業(yè)的效率。

目前國內(nèi)外許多專家學(xué)者對集卡動態(tài)調(diào)度問題進(jìn)行了研究。徐承軍等［1］分析了傳統(tǒng)集卡調(diào)度模式的不足，提出了一種新的面向作業(yè)面的動態(tài)集卡調(diào)度模式，并且運(yùn)用多目標(biāo)模糊決策算法和層次分析法對單集卡多作業(yè)路徑問題進(jìn)行了研究。曾慶成等［2］針對集卡調(diào)度問題建立了集卡等待時間最小的調(diào)度動態(tài)模型，設(shè)計了Q 學(xué)習(xí)算法來求解模型。葛盼盼等［3］分析了集裝箱碼頭作業(yè)流程及其傳統(tǒng)作業(yè)工藝，建立了以集卡到達(dá)目的地距離最短為目標(biāo)的優(yōu)化模型，并使用蟻群算法求解。王軍等［4］對不同船舶裝船作業(yè)和卸船作業(yè)同時進(jìn)行的前提下集裝箱碼頭集卡作業(yè)路徑選擇問題進(jìn)行了分析，建立了基于時間最短的集卡調(diào)度模型，并進(jìn)行了數(shù)值仿真?？抵久舻龋?］通過對兩種調(diào)度模式的比較，總結(jié)了現(xiàn)代集卡調(diào)度系統(tǒng)的優(yōu)點，并提出了集裝箱碼頭物流系統(tǒng)有色Petri 網(wǎng)建模的基本構(gòu)架和一種新的遺傳算法調(diào)度編碼方式。樂美龍［6］等同時考慮龍門吊與集卡的協(xié)同調(diào)度，首次對實際作業(yè)中存在的一些約束，如多臺龍門吊在同一箱區(qū)作業(yè)時由于共享一個雙向軌道而存在的龍門吊不能相互跨越的約束等，建立了以集卡與龍門吊聯(lián)合調(diào)度完工時間最短為目標(biāo)函數(shù)的優(yōu)化模型。CAO 等［7］研究分析了集卡調(diào)度與配置問題，并由此建立了集卡等待時間最短的整數(shù)規(guī)劃模型，分別使用遺傳算法和啟發(fā)式算法求解優(yōu)化模型，最后得出啟發(fā)式算法更適合求解所建模型的結(jié)論。CAO 等［8］建立的集卡與場橋集成調(diào)度混合整數(shù)規(guī)劃模型，以集卡與場橋同步化完工時間最小為目標(biāo)函數(shù)，分別用Cplex 及傳統(tǒng)的Benders 分支法和新組合的Benders 分支法求解模型，比較各自優(yōu)劣。

筆者主要研究集卡的動態(tài)調(diào)度問題，首先對該問題進(jìn)行了描述，建立了集卡動態(tài)調(diào)度模型，求出集卡的最小運(yùn)作時間，最后驗證了模型的有效性。筆者的創(chuàng)新之處在對模型約束進(jìn)行創(chuàng)新的基礎(chǔ)上，考慮了特定集裝箱卸載到特定的箱區(qū)和從船舶到箱區(qū)運(yùn)行路徑上的集卡數(shù)量限制等現(xiàn)實約束，使得模型更具有現(xiàn)實意義。

1 問題描述

集卡是連通船舶和堆場的樞紐，如果集卡的運(yùn)輸能夠快速有效地組織，將會極大提高碼頭的裝卸作業(yè)效率。集卡作業(yè)過程如下:船舶到達(dá)泊位，通過裝卸橋卸箱到集卡，集卡運(yùn)箱到堆場，然后返回泊位或者到下一個堆場取箱返回泊位，此過程構(gòu)成一個集卡行走路徑。如何使得集卡行走時間最短就是集卡調(diào)度優(yōu)化問題。

動態(tài)調(diào)度方式是指集卡并不固定地服務(wù)于一臺裝卸橋，而是按照整體優(yōu)化調(diào)度的結(jié)果來完成集裝箱的裝卸任務(wù)。動態(tài)調(diào)度模型基于以下假設(shè):

(1)集卡能夠及時服務(wù)于裝卸橋、龍門吊且不出現(xiàn)交通擁堵情況，這一狀態(tài)即為理想狀態(tài)，在這種狀態(tài)下，需限定船舶貝位u 與箱區(qū)e 間最多能同時運(yùn)行的集卡數(shù)，以減少和避免交通擁堵。同時，為了堆場內(nèi)各箱區(qū)堆箱分派均勻合理，需限定貝位u 與箱區(qū)e 作業(yè)路線上最多作業(yè)次數(shù)。

(2)集卡每次可以裝載一個集裝箱。

(3)集卡獨立運(yùn)行，不相互干擾。

2 模型建立

2.1 符號

為了便于建模，引入以下符號:

(1)集合。U 為船舶待卸貝位集合，u∈U;V為船舶待裝貝位集合，v∈V;E 為堆場箱區(qū)集合，e∈E;O 為船舶集合，o∈O。

(2)參數(shù)。Ou為船舶待卸貝位要卸載的集裝箱數(shù)，u∈U;Cv為船舶待裝貝位的容量，v∈V;Pe為箱區(qū)要被裝船的箱量，e∈E;Ce為箱區(qū)的容量，e∈E;Ωue為船舶待卸貝位上的集裝箱必須卸到指定箱區(qū)的數(shù)量，u∈U，e∈E;Rev為出口集裝箱必須卸到指定貝位的數(shù)量，e∈E，v∈V;Mue為從船舶貝位u 到箱區(qū)e 最多同時運(yùn)輸?shù)募〝?shù)，u∈U，e∈E;Nue為從貝位u 到箱區(qū)e 作業(yè)路線上最多作業(yè)次數(shù)，u∈U，e∈E;Mev為從箱區(qū)e 到貝位v 最多同時運(yùn)輸?shù)募〝?shù)，e∈E，v∈V;Nev為從箱區(qū)e 到貝位v 作業(yè)路線上最多作業(yè)次數(shù)，e∈E，v∈V;tue為集卡從貝位u 裝箱運(yùn)輸?shù)较鋮^(qū)e 的運(yùn)輸時間，u∈U，e∈E;tev為集卡從箱區(qū)e 裝箱運(yùn)輸?shù)截愇籿 的運(yùn)輸時間，e∈E，v∈V;tef為集卡在箱區(qū)間的空載運(yùn)輸時間，e、f∈E 且e≠f;toe為集卡船舶o 與箱區(qū)e 之間空載運(yùn)輸時間，e∈E，o∈O。

(3)決策變量定義。xue為集卡從待卸船貝位u 裝箱重載運(yùn)輸?shù)较鋮^(qū)e 的次數(shù)，u∈U，e∈E;yev為集卡從箱區(qū)e 重載回到待裝船貝位v 的次數(shù)，e∈E，v∈V;zef為集卡從箱區(qū)e 運(yùn)輸?shù)较鋮^(qū)f 的次數(shù)，e、f∈E 且e≠f;xoe為集卡從船舶o 空載至箱區(qū)e 進(jìn)行裝船任務(wù)的次數(shù)，e∈E，o∈O;yeo為集卡從箱區(qū)e 空箱返回至船舶o 的次數(shù)，e∈E，o∈O。

2.2 集卡動態(tài)調(diào)度模型

基于集卡調(diào)度優(yōu)化的考慮，建立以集卡運(yùn)輸時間最小為目標(biāo)的集卡調(diào)度模型。

上式中，式(1)代表集卡的運(yùn)輸時間最小;約束條件式(2)表示集卡從貝位裝箱然后運(yùn)輸?shù)礁鱾€箱區(qū)的次數(shù)和等于該貝位的卸箱量;式(3)表示集卡從各個貝位裝箱然后運(yùn)輸?shù)较鋮^(qū)的次數(shù)和不能超過該箱區(qū)的容量;式(4)表示集卡從箱區(qū)裝箱然后運(yùn)輸?shù)酱b船各個貝位的次數(shù)和等于該箱區(qū)的裝箱量;式(5)表示集卡從箱區(qū)裝箱然后運(yùn)輸?shù)酱b船各個貝位的次數(shù)和不能超過該貝位的容量;式(6)表示集卡在船舶與箱區(qū)之間運(yùn)行的次數(shù)關(guān)系;式(7)表示集卡在船舶與箱區(qū)之間空載運(yùn)輸次數(shù)可同時為0 或有且僅有一個為0;式(8)、式(9)表示特定的集裝箱必須卸到特定的箱區(qū)，特定的集裝箱必須裝往特定的貝位;式(10)、式(11)為作業(yè)任務(wù)次數(shù)約束。

3 數(shù)值試驗

在某一時間段內(nèi)集裝箱碼頭有110 個進(jìn)口集裝箱需要進(jìn)行卸船作業(yè)，100 個出口集裝箱需要進(jìn)行裝船作業(yè)［9］，有4 個箱區(qū)可供其堆存。Ω31=34，表示從待卸船舶貝位3 上必須卸載34 個集裝箱到箱區(qū)1。集卡每次只能運(yùn)送一個集裝箱且其作業(yè)開始時均位于岸邊。具體數(shù)據(jù)如表1 ～表12 所示。

表1 待卸船舶各貝位的卸箱量國際標(biāo)準(zhǔn)箱

表2 待裝船舶各貝位的容量 國際標(biāo)準(zhǔn)箱

表3 各個箱區(qū)容量 國際標(biāo)準(zhǔn)箱

表4 各個箱區(qū)裝箱量 國際標(biāo)準(zhǔn)箱

表5 從各個貝位到各個箱區(qū)的運(yùn)輸時間 min

表6 從各個箱區(qū)到各個貝位的運(yùn)輸時間 min

表7 從箱區(qū)e 到箱區(qū)f 集卡的運(yùn)輸時間 min

表8 船舶與箱區(qū)間的運(yùn)輸時間 min

表9 從各個貝位到箱區(qū)的Mue 個

表10 從各個貝位到箱區(qū)的Nue 次

表11 從各個箱區(qū)到貝位的Mev 個

表12 從各個箱區(qū)到貝位的Nev 次

把以上數(shù)據(jù)代入所建模型中，利用遺傳算法思想及Lingo 求解工具［10］，可求出最小運(yùn)輸時間及集卡行走優(yōu)化路線，如表13 所示。

表13 優(yōu)化路線

數(shù)據(jù)結(jié)果表明，所提出的模型能夠為集卡運(yùn)輸提供最優(yōu)線路，節(jié)省集卡運(yùn)輸時間。

4 結(jié)論

集卡調(diào)度優(yōu)化直接影響集裝箱碼頭的作業(yè)效率。筆者據(jù)此建立了集卡動態(tài)調(diào)度優(yōu)化模型，對特定集裝箱卸載到特定箱區(qū)的問題，從船舶到箱區(qū)運(yùn)行路徑上的集卡數(shù)量有限等現(xiàn)實約束方面考慮，并首次將集卡任務(wù)次數(shù)的限制加以研究。建立了以集卡運(yùn)輸時間最短為目標(biāo)的動態(tài)調(diào)度優(yōu)化模型，利用遺傳算法求得了最優(yōu)解，算例結(jié)果表明了該模型的有效性和實用性。

［1］ 徐承軍，陶德馨. 基于多目標(biāo)模糊決策的集卡動態(tài)調(diào)度方法研究［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2007，29(4):57－59.

［2］ 曾慶成，楊忠振.集裝箱碼頭集卡調(diào)度模型與Q 學(xué)習(xí)算法［J］.哈爾濱工程大學(xué)學(xué)報，2008，29(1):1－4.

［3］ 葛盼盼，王繼榮，李軍，等.基于蟻群算法的碼頭集裝箱卡車路徑優(yōu)化研究［J］. 物流科技，2008(12):26－28.

［4］ 王軍，許曉雷. 集裝箱碼頭集卡作業(yè)的路徑選擇［J］.大連海事大學(xué)學(xué)報，2011，37(2):25－34.

［5］ 康志敏，吳洪明. 港口集裝箱碼頭集卡優(yōu)化調(diào)度研究［J］.物流工程與管理，2011，33(2):59－61.

［6］ 樂美龍，包節(jié)，范志強(qiáng).龍門吊與集卡協(xié)調(diào)調(diào)度問題研究［J］.計算機(jī)工程與應(yīng)用，2012，48(14):241－248.

［7］ CAO J X，SHI Q X，LEE D H. A decision support method for truck scheduling and storage allocation problem at container［J］. Tsinghua Science and Technology，2008，13(10):211－216.

［8］ CAO J X，LEE D H，CHEN J H，et al. The integrated yard truck and yard crane scheduling problem:benders' decomposition－based methods ［J］. Transportation Research Part E，2010(46):344－353.

［9］ 郭燕，趙謹(jǐn). 基于概率統(tǒng)計的集裝箱龍門起重機(jī)生產(chǎn)率研究［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2009，31(1):161－164.

［10］王里付，朱新平.基于Petri 網(wǎng)和遺傳算法的飛行訓(xùn)練計劃優(yōu)化編排［J］.武漢理工大學(xué)學(xué)報:信息與管理工程版，2012，34(2):197－201.