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

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

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

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

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

1 問題描述

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

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

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

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

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

2 模型建立

2.1 符號(hào)

為了便于建模，引入以下符號(hào):

(1)集合。U 為船舶待卸貝位集合，u∈U;V為船舶待裝貝位集合，v∈V;E 為堆場(chǎng)箱區(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 最多同時(shí)運(yùn)輸?shù)募〝?shù)，u∈U，e∈E;Nue為從貝位u 到箱區(qū)e 作業(yè)路線上最多作業(yè)次數(shù)，u∈U，e∈E;Mev為從箱區(qū)e 到貝位v 最多同時(shí)運(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)輸時(shí)間，u∈U，e∈E;tev為集卡從箱區(qū)e 裝箱運(yùn)輸?shù)截愇籿 的運(yùn)輸時(shí)間，e∈E，v∈V;tef為集卡在箱區(qū)間的空載運(yùn)輸時(shí)間，e、f∈E 且e≠f;toe為集卡船舶o 與箱區(qū)e 之間空載運(yùn)輸時(shí)間，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 集卡動(dòng)態(tài)調(diào)度模型

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

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

3 數(shù)值試驗(yàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

表13 優(yōu)化路線

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

4 結(jié)論

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

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

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

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

［4］ 王軍，許曉雷. 集裝箱碼頭集卡作業(yè)的路徑選擇［J］.大連海事大學(xué)學(xué)報(bào)，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ì)算機(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ì)的集裝箱龍門起重機(jī)生產(chǎn)率研究［J］.武漢理工大學(xué)學(xué)報(bào):信息與管理工程版，2009，31(1):161－164.

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