帶任務(wù)順序約束的岸橋集卡集成調(diào)度約束規(guī)劃模型

秦天保，彭嘉瑤，沙梅

(上海海事大學(xué)交通運(yùn)輸學(xué)院，上海 201306)

0 引言

集裝箱碼頭運(yùn)營有許多調(diào)度問題，其中岸橋調(diào)度(Quay Crane Scheduling Problem，QCSP)和堆場內(nèi)集卡調(diào)度(Yard Truck Scheduling Problem，YTSP)是兩個互相聯(lián)系的調(diào)度問題.但是，現(xiàn)有文獻(xiàn)大多分開研究這兩個子問題.KIM等［1］針對QCSP提出一個考慮任務(wù)順序關(guān)系及岸橋沖突約束的混合整數(shù)規(guī)劃(Mixed Integer Programming，MIP)模型，并設(shè)計分支定界算法和貪婪隨機(jī)適應(yīng)性搜索算法求解.MOCCIA等［2］設(shè)計分支割算法求解QCSP，改進(jìn)解的質(zhì)量.SAMMARRA等［3］進(jìn)一步設(shè)計禁忌搜索(Tabu Search，TS)算法求解該問題，求解時間大大縮短，但解的質(zhì)量稍差.BIERWIRTH等［4］設(shè)計一個基于分支定界的單向調(diào)度啟發(fā)式算法求解QCSP，算例表明該算法能夠在更短時間內(nèi)產(chǎn)生比以往文獻(xiàn)中算法質(zhì)量更好的解.CHUNG等［5］設(shè)計一個改進(jìn)的遺傳算法求解QCSP，其質(zhì)量和效率未超過文獻(xiàn)［4］提出的算法.曾慶成等［6］將隨機(jī)貪婪適應(yīng)性搜索算法融入遺傳算法求解QCSP.董良才等［7］提出帶時間窗的岸橋調(diào)度MIP模型，并設(shè)計遺傳算法求解.針對YTSP，BISH等［8］提出貪婪算法研究集卡調(diào)派問題.NG 等［9］設(shè)計遺傳算法求解 YTSP.呂顯強(qiáng)［10］對集裝箱碼頭集卡分配問題建立整數(shù)規(guī)劃模型.康志敏等［11］提出集裝箱碼頭物流系統(tǒng)有色Petri網(wǎng)建模的基本構(gòu)架和一種新的遺傳算法編碼方式求解YTSP.

由于岸橋和集卡具有很強(qiáng)的交互作用，將二者進(jìn)行集成調(diào)度能夠得到更好的全局解，這就是岸橋與集卡集成調(diào)度問題(Integrated Quay Crane and Yard Truck Scheduling Problem，IQCYTSP)，但集成調(diào)度文獻(xiàn)較少.文獻(xiàn)［12］中建立的基于時間最短的集卡線路優(yōu)化模型，對岸橋的處理僅使用其作業(yè)時間，將所有岸橋作為一個整體考慮，沒有涉及到岸橋與集卡之間作業(yè)時間銜接的約束以及岸橋執(zhí)行各個任務(wù)的調(diào)度.CAO等［13］研究IQCYTSP，建立MIP模型、設(shè)計遺傳算法并改進(jìn)基于約翰遜規(guī)則的啟發(fā)式算法求解，但其只求解小規(guī)模的問題，而且未考慮岸橋卸載任務(wù)具有順序關(guān)系約束.

IQCYTSP問題是NP(Non-deterministic Polynomial)難題［13］，現(xiàn)有文獻(xiàn)基本上都是設(shè)計各種啟發(fā)式算法進(jìn)行求解.本文針對IQCYTSP建立一個考慮岸橋卸載任務(wù)順序關(guān)系的新的MIP模型和一個約束規(guī)劃(Constraint Programming，CP)模型(CP是計算機(jī)科學(xué)、人工智能和運(yùn)籌學(xué)的交叉技術(shù))，設(shè)計問題的下界，通過實驗驗證CP模型求解的高效性.

1 問題描述與MIP模型

集裝箱碼頭船舶裝卸有多種組織方式，其中作業(yè)線方式是一種較常見的組織方式.一組岸橋服務(wù)于一艘船，卸船先于裝船，本文只考慮卸船過程.船上的集裝箱依貝劃分為若干區(qū)域，一般情況下，每個區(qū)域配備一臺岸橋.在已知每臺岸橋所服務(wù)的集裝箱區(qū)域的情況下，只需考慮單臺岸橋的調(diào)度，所有岸橋調(diào)度結(jié)果是單臺岸橋調(diào)度結(jié)果的簡單綜合.一組固定的集卡服務(wù)一臺岸橋，稱為一條作業(yè)線.集卡在岸橋處裝載卸下的集裝箱，運(yùn)輸?shù)蕉褕鲋付ㄏ鋮^(qū)，由場橋卸下集裝箱，集卡再空載返回到岸橋處裝載下一個集裝箱.假設(shè)一個集裝箱為一個任務(wù)，岸橋執(zhí)行卸載任務(wù)，集卡執(zhí)行運(yùn)輸任務(wù).各集裝箱被岸橋卸載所用的時間不同.通常，靠近岸邊的集裝箱比遠(yuǎn)離岸邊的集裝箱卸載時間短，上面的集裝箱比下面的集裝箱卸載時間短.另外，碼頭實踐中，會事先安排好船上的集裝箱到堆場的某一特定位置，因此集卡運(yùn)輸不同集裝箱到堆場的時間不同.這樣，不同的集裝箱卸載次序和對集卡的不同任務(wù)分配會導(dǎo)致不同的完工時間，該問題需要尋求一個最優(yōu)的卸載次序以及集卡任務(wù)分配以使得總完工時間最短.

該問題的一個特點是岸橋從船上卸載一個集裝箱后，若下面無集卡(集卡可能還未返回)，則岸橋必須等待，即處于阻塞狀態(tài)，這一點模型中必須考慮，為此設(shè)計兩個決策變量為岸橋從船上提取集裝箱i并移動到陸側(cè)的時刻，本文稱之為岸橋卸載集裝箱i的結(jié)束時刻;di為岸橋放下集裝箱i到集卡上的時刻，也就是集裝箱離開岸橋的時刻.di－即為岸橋阻塞的時間.岸橋放下集裝箱到集卡上后才能開始一段過渡時間去卸載下一個集裝箱.另一個特點是岸橋卸載船上集裝箱時必須遵守一定的卸載順序，如上層的集裝箱必須先于下層集裝箱卸載.下面，先建立本問題的MIP模型.

1.1 模型參數(shù)

n為集裝箱數(shù)目;m為集卡數(shù)目;pi為岸橋卸載集裝箱i所需時間;ti為集卡運(yùn)輸集裝箱i到堆場的時間，也等于其返程時間;d為場橋從集卡卸載一個集裝箱到堆場所需時間;sij為岸橋?qū)⒓b箱i放到集卡上后，立即卸載集裝箱j的過渡時間;Φ為具有順序關(guān)系的岸橋卸載任務(wù)對集合，若任務(wù)(集裝箱)i必須在任務(wù)j前(不一定是緊前)卸載，則(i，j)∈Φ;M為一個足夠大的正整數(shù).

1.2 決策變量

1.3 MIP 模型

目標(biāo)函數(shù)(1)是最小化所有集裝箱由船舶卸載到堆場存放的完工時間.約束(2)保證總完工時間大于所有集裝箱運(yùn)到堆場并堆放完成的時間.約束(3)保證岸橋卸載集裝箱i時至少經(jīng)過一段卸載時間(不包含岸橋等待集卡的時間)才能完全卸載操作.約束(4)保證任一集裝箱只能分配給一輛集卡運(yùn)輸.約束(5)保證集裝箱i離開岸橋的時刻大于岸橋卸載集裝箱i的結(jié)束時刻.約束(6)保證集裝箱i離開岸橋的時刻等于集卡開始運(yùn)輸集裝箱i的時刻，該約束表達(dá)岸橋與集卡間的銜接關(guān)系.約束(7)和(8)保證岸橋卸載兩個不同集裝箱間要經(jīng)過一段過渡時間，約束(7)表示如果集裝箱j先于i被岸橋卸載(yij=0)，則j離開岸橋后至少經(jīng)過sji的過渡時間才能開始卸載i.約束(8)表示如果集裝箱i先于j被岸橋卸載(yij=1)，則i離開岸橋后至少經(jīng)過sij的過渡時間才能開始卸載j.約束(9)表示若集裝箱j先于i被同一集卡 k運(yùn)輸(yij=0，xik，xjk=1)，則運(yùn)輸并堆放j到堆場完成后，至少經(jīng)過tj的過渡時間(即返程時間)才能開始運(yùn)輸i.約束(10)表示若集裝箱i先于j被同一集卡k運(yùn)輸(yij=1，xik，xjk=1)，則運(yùn)輸并堆放i到堆場完成后，至少經(jīng)過ti的過渡時間(即返程時間)才能開始運(yùn)輸j.約束(11)是岸橋卸載任務(wù)順序約束，若(i，j)∈Φ，則任務(wù)(集裝箱)j的卸載開始時間必須大于或等于i的完成時間.式(12)和(13)是決策變量域約束.

2 約束規(guī)劃模型

2.1 模型特征

下面建立相應(yīng)的CP模型.CP模型在不同的CP系統(tǒng)中表示方法不同，表達(dá)方式也不一致.本文所建CP模型是用IBM ILOG CPLEX Optimization 12.4中的OPL 12.4語言實現(xiàn)的.OPL針對調(diào)度問題提出一種新的概念，即區(qū)間(決策)變量.區(qū)間變量概念是約束規(guī)劃在調(diào)度領(lǐng)域應(yīng)用的一個重要擴(kuò)展.LABORIE等［14］首次正式介紹CP中應(yīng)用區(qū)間變量的內(nèi)在機(jī)制.區(qū)間變量不同于一般MIP模型中的決策變量，區(qū)間變量具有起點、終點和長度(通常情況下，區(qū)間變量的長度等于終點與起點之間的長度)等內(nèi)在屬性，起點、終點都是整數(shù)，故以下的CP模型中，時間都被離散化為整數(shù).

區(qū)間變量經(jīng)常用于建模一段任務(wù)(活動)時間，起點為任務(wù)開始時刻，終點為任務(wù)結(jié)束時刻.本文提出的CP模型就是基于區(qū)間變量設(shè)計的.CP系統(tǒng)提供大量函數(shù)訪問區(qū)間變量的屬性和設(shè)置約束.為簡單起見，主要采用BAPTISTE等［15］和OPL中的符號表示法表示基于區(qū)間變量的CP模型，該文獻(xiàn)中提出的“活動”變量就是區(qū)間變量的雛形，提出的許多作用于活動變量的函數(shù)亦可用于區(qū)間變量，這些函數(shù)都是簡單自明的.如start(a)表示區(qū)間變量a的起點、end(a)表示區(qū)間變量a的終點、presence(a)表示區(qū)間變量a是否出現(xiàn)在最終調(diào)度中(即在最終調(diào)度中是否被執(zhí)行).文獻(xiàn)［15］中未提到的一些函數(shù)和構(gòu)造本文直接采用OPL中的構(gòu)造.采用這套表示法表達(dá)的CP模型很容易轉(zhuǎn)化成OPL語言實現(xiàn).

2.2 模型參數(shù)

CP模型中除sij外，其他參數(shù)定義與MIP模型中的定義相同.CP模型中的sij為岸橋卸載集裝箱i后立即卸載集裝箱 j的過渡時間(i=1，…，n;j=1，…，n+1)，其中 si，n+1=0 是虛擬過渡時間.

2.3 決策變量與約束條件

2.3.1 變量域約束

CP模型定義3組區(qū)間決策變量:xi，yi和zki.xi表示岸橋卸載集裝箱i的任務(wù)，其起點表示任務(wù)開始時刻，終點表示任務(wù)結(jié)束時刻，長度為卸載該集裝箱的持續(xù)時間.求解結(jié)果中將得出開始時刻、結(jié)束時刻.對xi的域限制約束:?1≤i≤n，

約束(14)限制岸橋卸載集裝箱i的開始時刻必須大于0.約束(15)限制岸橋卸載集裝箱i的結(jié)束時刻，這里給出一個簡單的上界，即所有任務(wù)串行執(zhí)行時完工時間的總和.約束(16)規(guī)定岸橋卸載集裝箱的所需時間為pi.約束(17)保證岸橋任務(wù)i必須出現(xiàn)在最終調(diào)度中，即必須被執(zhí)行.

區(qū)間變量yi表示集卡運(yùn)輸集裝箱i的任務(wù)(這里將運(yùn)輸任務(wù)執(zhí)行時長定義為集卡運(yùn)輸時間與場橋卸載時間之和)，對yi的域限制約束:?1≤i≤n，

約束(18)限制集卡運(yùn)輸集裝箱i的開始時刻必須大于0.約束(19)規(guī)定集卡運(yùn)輸集裝箱i的結(jié)束時刻上界.約束(20)規(guī)定集卡執(zhí)行任務(wù)的時間長度為ti+d.約束(21)保證任務(wù)必須被執(zhí)行.

二維區(qū)間變量zki表示集卡k運(yùn)輸集裝箱i的任務(wù)，它表示一個運(yùn)輸任務(wù)可能由任意一個集卡完成(最終會利用選擇約束(alternative約束)限制僅能由一輛集卡完成).因此，可以將zki理解為一種模式選擇區(qū)間變量，即一個任務(wù)可能有多種完成模式(一輛集卡為一個模式).?1≤i≤n，1≤k≤m，

約束(22)，(23)，(24)分別限制 zki的起點、終點和長度.對zki的約束中沒有presence約束，說明并非所有zki都必須被執(zhí)行，只有那些被選中的才會被執(zhí)行.

2.3.2 集卡任務(wù)選擇約束

yi和zki受限制于alternative約束，表示如果執(zhí)行運(yùn)輸任務(wù) yi，則所有的 zki(k=1，2，…，m)中只能有一個被執(zhí)行，且其起止時間與yi完全相同，這樣就能保證每個集裝箱只能由一輛集卡運(yùn)輸，即對一個運(yùn)輸任務(wù)yi要從多種執(zhí)行模式(集卡)zki中選擇一個來執(zhí)行.?1≤i≤n，1≤k≤m，

2.3.3 任務(wù)不重疊約束

所有的岸橋任務(wù)xi之間不能重疊，即岸橋只能一次一個、依次卸載集裝箱，而且岸橋執(zhí)行的前后任務(wù)之間還有一段過渡時間.為實現(xiàn)此約束，首先定義一個過渡函數(shù)transitionTimesQuay:{i|i=1，…，n}×{j|j=1，…，n}→{sij|i，j=1，…，n}，該函數(shù)用于定義岸橋卸載任務(wù)(集裝箱)i到j(luò)的過渡時間為sij.然后，定義一個序列變量q.一個序列變量是一組區(qū)間的集合，這里，利用式(26)定義序列變量q為所有岸橋任務(wù)的集合.式(27)為順序變量中的任務(wù)xi設(shè)置類型i，即任務(wù)類型就是任務(wù)(集裝箱)編號，后面的約束將使用這個類型.利用約束(28)保證該序列中的任務(wù)不重疊，且兩個相繼任務(wù)之間需要一段過渡時間，系統(tǒng)取得序列變量中任意兩個任務(wù)的類型，代入過渡函數(shù)transitionTimesQuay即可求得過渡時間.?1≤i≤n，

類似地，集卡k執(zhí)行的任務(wù)zki(i=1，2，…，n)也不能重疊，且集卡卸箱到堆場后，需要一段時間返回到岸橋，才能開始下一個運(yùn)輸任務(wù)，故集卡的兩個相繼運(yùn)輸任務(wù)之間有過渡時間，這個過渡時間就是返程時間.定義過渡函數(shù)transitionTimesTruck:{i|i=1，…，n}×{j|j=1，…，n}→{ti|i=1，…，n}，集卡任務(wù)i到j(luò)的過渡時間為ti.定義序列變量rk為集卡k的任務(wù)集合(見(29)).式(30)為順序變量中的任務(wù)zki設(shè)置類型i，即任務(wù)類型就是集裝箱編號.利用約束(31)保證集卡k的任務(wù)不重疊，且兩個相繼任務(wù)之間有一段過渡時間，系統(tǒng)取得序列變量中任意兩個任務(wù)的類型，代入過渡函數(shù)transition Times Truck即可求得過渡時間.?1≤i≤n，1≤k≤m，

2.3.4 岸橋與集卡任務(wù)順序約束

在卸船過程中，對任一集裝箱i，應(yīng)該先由岸橋卸載，再由集卡運(yùn)輸，此順序關(guān)系約束:?1≤i≤n，

2.3.5 岸橋與集卡任務(wù)銜接關(guān)系約束

岸橋任務(wù)與集卡任務(wù)之間有一個銜接關(guān)系，即當(dāng)岸橋卸載集裝箱i完成時，必須等待集卡開始運(yùn)輸集裝箱i，再經(jīng)過一段過渡時間，才能開始卸載下一個集裝箱j.

這個約束可以用蘊(yùn)含約束(33a)表示，約束(33a)雖然直觀易于理解，但是通過實驗發(fā)現(xiàn)其求解效率較低，因為它是meta約束(指整個約束式中還含有其他約束式)，不是直接約束，故約束傳播能力不強(qiáng).實驗發(fā)現(xiàn)采用OPL提供的startOfNext函數(shù)可得到更高的求解效率，故最終采用約束(33b)的形式.其中startOfNext函數(shù)返回的是q中xi緊后任務(wù)的開始時間.當(dāng) xi已經(jīng)是最后的任務(wù)時，start－OfNext返回M.該約束說明q中岸橋任務(wù)xi的緊后任務(wù)的開始時間大于集卡任務(wù)yi的開始時間加上一段過渡時間.這里特別要說明的是過渡時間si，typeOfNext(q，xi，n+1)腳標(biāo)的含義.要求得兩個相繼岸橋任務(wù)間的過渡時間，必須得到它們的任務(wù)編號(即任務(wù)類型).約束(33b)涉及兩個岸橋的相繼任務(wù)，前一個任務(wù)xi的編號是i，后一個任務(wù)的編號是typeOfNext(q，xi，n+1)，這里 typeOfNext函數(shù)返回 xi的緊后任務(wù)的類型，根據(jù)式(27)，岸橋任務(wù)類型等于其編號，故這兩個相繼任務(wù)的過渡時間為si，typeOfNext(q，xi，n+1).當(dāng) xi已經(jīng)是 q 中最后一個任務(wù)時，typeOfNext(q，xi，n+1)返回 n+1，這個 n+1 表示虛擬岸橋任務(wù)的編號，定義任何岸橋任務(wù)到虛擬任務(wù)的過渡時間都為 0.?1≤i，j≤n;i≠j，

2.3.6 岸橋卸載任務(wù)順序約束

約束(34)確保若(i，j)∈Φ，則任務(wù)(集裝箱)i的卸載完成時間必須早于任務(wù)j的開始時間.

2.3.7 資源約束

以上約束已經(jīng)可以完全描述本文提出的岸橋集卡集成調(diào)度問題，但為了進(jìn)一步提高CP引擎的求解效率，引入累積(cumulative)約束，它表示任一時刻所有任務(wù)消耗的資源總數(shù)不得超過設(shè)定值.這里將集卡作為資源，任一集卡任務(wù)yi執(zhí)行期間會消耗一輛集卡資源，任一時刻集卡總消耗量不得大于集卡總數(shù)m.累積約束是全局約束，因此非常有助于求解器進(jìn)行全局推理，從而提升求解效率.

約束(35)中pulse函數(shù)是OPL中的基本累積函數(shù)，其中的第一個參數(shù)表示消耗資源的區(qū)間變量，第二個參數(shù)表示區(qū)間變量在執(zhí)行過程中消耗的資源數(shù)(集卡數(shù)).基本累積函數(shù)求和后成為匯總累積函數(shù)，代表所有基本累積函數(shù)在執(zhí)行過程中消耗的資源總量.對匯總累積函數(shù)施加約束即為資源約束，這里運(yùn)輸任務(wù)消耗的集卡數(shù)不超過集卡總數(shù).

圖1 匯總累積函數(shù)

圖1表示匯總累積函數(shù)消耗資源的曲線，其中H是資源量限制，各個a是區(qū)間變量.可以看出，執(zhí)行每個區(qū)間變量時，匯總累積函數(shù)值增加，執(zhí)行完區(qū)間變量后，匯總累積函數(shù)值減少.對匯總累積函數(shù)上限施加的限制就是累積約束，也就是資源限制約束.

2.4 目標(biāo)函數(shù)

目標(biāo)函數(shù)(36)是最小化集卡任務(wù)的最晚完工時間，也就是整體完工時間:?1≤i≤n，

比較CP模型和混合整數(shù)線性規(guī)劃(Mixed Integer Linear Programming，MILP)模型，可以發(fā)現(xiàn) CP模型約束可以自然簡潔地表達(dá)邏輯約束，無須使用大量0-1變量.

2.5 搜索策略

為進(jìn)一步提升ILOG CP優(yōu)化器搜索本問題解空間的效率，可以對默認(rèn)搜索策略進(jìn)行調(diào)整.這里利用ILOG CP提供的搜索階段(search phase)機(jī)制干預(yù)搜索策略.通過搜索階段可以指定CP優(yōu)化器固定變量的次序，不同的次序可能會對搜索效率產(chǎn)生顯著影響.通過實驗嘗試幾個不同的次序，發(fā)現(xiàn)先固定順序變量數(shù)組r，再固定q的搜索效率最高.搜索階段用ILOG腳本定義如下:

3 下界分析

為評價CP模型的求解質(zhì)量，需要得到較緊的下界(即完成所有任務(wù)時間的下界).本節(jié)提出一個新的求解上述問題下界的方法，即:完工時間下界=最后一輛集卡出發(fā)時刻的下界+其后所需運(yùn)輸時間的下界.以下介紹具體求法.

首先引入符號，記a(k)表示一組數(shù)值A(chǔ)={ai|i=1，…，n}中第k小的元素，即把a(bǔ)i從小到大排序后第k個元素;b［k］表示一組數(shù)值 B={bi|i=1，…，n}中第k大的元素，即把bi從大到小排序后第k個元素.

(1)計算最后一輛集卡出發(fā)時刻的下界.卸船開始時，m輛集卡在岸橋下等待.卸船任務(wù)從開始到最后一輛集卡出發(fā)所經(jīng)歷的最小時間(即下界)可表示為式(37)，即m個任務(wù)已由岸橋卸載完畢，包括岸橋工作時間和相鄰兩個任務(wù)間的過渡時間.

式中:p(m)表示所有卸載任務(wù)按卸載時間從小到大排序后第m個卸載時間;s(m－1)表示所有過渡時間從小到大排序后第m－1個過渡時間.

(2)計算最后一輛集卡出發(fā)后所需運(yùn)輸時間的下界.最后一輛集卡出發(fā)后所需的運(yùn)輸時間下界=(所有任務(wù)運(yùn)輸時間－最后一輛集卡出發(fā)前已經(jīng)歷的運(yùn)輸時間－全部集卡最后一次最大返程時間總和)÷集卡數(shù)，其中所有任務(wù)的運(yùn)輸時間(包括集卡在堆場的卸載時間和返程時間)為

最后一輛集卡出發(fā)前其他所有集卡的運(yùn)輸時間可以集卡為對象進(jìn)行研究.第1輛集卡的運(yùn)輸時間為

第2輛集卡的運(yùn)輸時間為

第m－1輛集卡的運(yùn)輸時間為

累加上述式子得最后一輛集卡出發(fā)前已經(jīng)歷的運(yùn)輸時間為

全部集卡最后一次最大返程時間總和為

其中t［m］表示所有任務(wù)單程運(yùn)輸時間從大到小排序后第m個運(yùn)輸時間.故根據(jù)“最后一輛集卡出發(fā)后所需運(yùn)輸時間的下界”的計算公式以及式(38)，(39)和(40)，可得最后一輛集卡出發(fā)后所需運(yùn)輸時間的下界:

(3)完工時間下界.根據(jù)前面提出的完工時間下界計算公式，結(jié)合式(35)和(41)可得問題下界:

4 數(shù)值試驗

將以上CP模型用IBM ILOG CPLEX Optimization Studio 12.4中的OPL語言實現(xiàn)，并利用其中的CP優(yōu)化器求解.計算時采用默認(rèn)參數(shù)配置，測試硬件平臺為 Intel Core i5-24003.1 GHz CPU，2 GB內(nèi)存.

為了測試CP方法能否求解實際規(guī)模的例子，隨機(jī)生成7個不同規(guī)模的實例集，每個實例集含10個實例.各實例集裝箱數(shù)(即任務(wù)數(shù))分別為10，20，30，40，60，80 和100，集卡統(tǒng)一為 5 輛.生成數(shù)據(jù)時設(shè)置 pi服從［45，85］上的均勻分布，ti服從［180，600］上的均勻分布，sij服從［20，40］上的均勻分布，d為50.生成具有順序關(guān)系的岸橋任務(wù)對(i，j)的規(guī)則:將每個實例的集裝箱平均分為5組，前一組的集裝箱必須在后一組集裝箱之前卸載.

(1)小規(guī)模實例測試.對于10個任務(wù)5輛集卡的小規(guī)模實例，可用CPLEX求MIP模型得最優(yōu)解，CPLEX得到的最優(yōu)值與CP的求解結(jié)果的比較見表1.表1中“最優(yōu)值”是CPLEX求得的最優(yōu)目標(biāo)值，“時間”是CPLEX求得最優(yōu)解所用的時間，“CP值”是CP模型求得的最佳目標(biāo)值，“差距百分比”是CP值相對“最優(yōu)值”的差距百分比.觀察表1可知，CP方法幾秒內(nèi)都得到最優(yōu)解，說明CP的求解效率和求解質(zhì)量都很高.

表1 小規(guī)模實例結(jié)果比較

(2)中大規(guī)模實例測試.進(jìn)一步測試CP方法對中大規(guī)模實例的求解結(jié)果，求解時限為半小時(對這些實例，CPLEX無法求得最優(yōu)解，會發(fā)生內(nèi)存溢出).為了更加準(zhǔn)確地觀察求解收斂情況和解的質(zhì)量，分5 min，10 min，30 min等3個時間段統(tǒng)計實驗結(jié)果，結(jié)果見表2.表2中“下界”是每個實例集中10個實例的平均下界，“5 min內(nèi)目標(biāo)”是CP在5 min內(nèi)求得的最佳目標(biāo)值(為10個實例的平均值)，“時間1”是5 min內(nèi)求得最佳目標(biāo)的具體時間(為10個實例的平均值)，“差距1”是5 min內(nèi)最佳目標(biāo)相對下界的差距百分比(為10個實例的平均值)，其他以此類推.

表2 中大規(guī)模實例測試結(jié)果

觀察表2可以發(fā)現(xiàn)，不超過80個任務(wù)的實例集在5 min內(nèi)就可得到質(zhì)量較好的解，而100個任務(wù)的實例集也可在10 min內(nèi)得到質(zhì)量較好的解.在半小時內(nèi)所有實例都可得到質(zhì)量較好的解.

5 結(jié)束語

采用CP技術(shù)建模求解帶任務(wù)順序關(guān)系約束的岸橋與集卡聯(lián)合調(diào)度問題，在采用提高求解效率的累積約束及更加高效的約束表達(dá)式后，利用不同規(guī)模實例進(jìn)行測試，結(jié)果顯示CP具有很高的求解效率和求解質(zhì)量，能夠求解規(guī)模更大的問題.未來的一個研究方向是考慮將場橋調(diào)度也集成進(jìn)來，開發(fā)集成范圍更大的模型.

［1］KIM K H，PARK Y M.A crane scheduling method for port container terminals［J］.Eur J Operational Res，2004，156(3):752-768.

［2］MOCCIA L，CORDEAU JF，GAUDIOSO M，et al.A branch-and-cut algorithm for the quay crane scheduling problem in a container terminal［J］.Naval Res Logistics，2006，53(1):45-59.

［3］SAMMARRA M，CORDEAU J-F，LAPORTE G，et al.A tabu search heuristic for the quay crane scheduling problem［J］.J Scheduling，2007，10(4/5):327-336.

［4］BIERWIRTH C，MEISEL F.A fast heuristic for quay crane scheduling with interference constraints［J］.J Scheduling，2009，12(4):345-60.

［5］CHUNG S H，CHOY K L.A modified genetic algorithm for quay crane scheduling operations［J］.Expert Systems with Applications，2012，39(4):4213-4221.

［6］曾慶成，高宇.集裝箱碼頭裝卸橋調(diào)度優(yōu)化模型與算法［J］.計算機(jī)工程與應(yīng)用，2006，(32):7-219.

［7］董良才，丁以中，宓為建.基于時間窗的集裝箱裝卸橋調(diào)度［J］.上海海事大學(xué)學(xué)報，2011，32(1):1-7.

［8］BISH E K，CHEN F Y，LEONG Y T，et al.Dispatching vehicles in a mega container terminal［M］//Container Terminals ＆ Cargo Systems.Springer，2007:179-194.

［9］NG W C，MAK K L，ZHANG Y X.Scheduling trucks in container terminals using a genetic algorithm［J］.Eng Optimization，2007，39(1):33-47.

［10］呂顯強(qiáng).集裝箱碼頭分派車輛的整數(shù)規(guī)劃模型［J］.大連水產(chǎn)學(xué)院學(xué)報，2004，6(19):18-20.

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

［12］計明軍，靳志宏.集裝箱碼頭集卡與岸橋協(xié)調(diào)調(diào)度優(yōu)化［J］.復(fù)旦學(xué)報:自然科學(xué)版，2007，46(4):476-480.

［13］CAO J X，SHI Q X，LEE D H.Integrated quay crane and yard truck schedule problem in container terminals［J］.Tsinghua Sci＆ Technol，2010，15(4):467-474.

［14］LABORIE P，ROGERIE J.Reasoning with conditional time-intervals［C］//Proc 21st Int Florida Artificial Intelligence Research Society Conf Coconut Grove，USA，2008:555-560.

［15］BAPTISTE P，LABORIE P，PAPE C L，et al.Constraint-based scheduling and planning［M］//ROSSI F，van BEEK P，WALSH T.Handbook of Constraint Programming.Netherlands:Elsevier，2006:761-794.