秦天保，彭嘉瑤，沙梅

(上海海事大學(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)是兩個(gè)互相聯(lián)系的調(diào)度問題.但是，現(xiàn)有文獻(xiàn)大多分開研究這兩個(gè)子問題.KIM等［1］針對QCSP提出一個(gè)考慮任務(wù)順序關(guān)系及岸橋沖突約束的混合整數(shù)規(guī)劃(Mixed Integer Programming，MIP)模型，并設(shè)計(jì)分支定界算法和貪婪隨機(jī)適應(yīng)性搜索算法求解.MOCCIA等［2］設(shè)計(jì)分支割算法求解QCSP，改進(jìn)解的質(zhì)量.SAMMARRA等［3］進(jìn)一步設(shè)計(jì)禁忌搜索(Tabu Search，TS)算法求解該問題，求解時(shí)間大大縮短，但解的質(zhì)量稍差.BIERWIRTH等［4］設(shè)計(jì)一個(gè)基于分支定界的單向調(diào)度啟發(fā)式算法求解QCSP，算例表明該算法能夠在更短時(shí)間內(nèi)產(chǎn)生比以往文獻(xiàn)中算法質(zhì)量更好的解.CHUNG等［5］設(shè)計(jì)一個(gè)改進(jìn)的遺傳算法求解QCSP，其質(zhì)量和效率未超過文獻(xiàn)［4］提出的算法.曾慶成等［6］將隨機(jī)貪婪適應(yīng)性搜索算法融入遺傳算法求解QCSP.董良才等［7］提出帶時(shí)間窗的岸橋調(diào)度MIP模型，并設(shè)計(jì)遺傳算法求解.針對YTSP，BISH等［8］提出貪婪算法研究集卡調(diào)派問題.NG 等［9］設(shè)計(jì)遺傳算法求解 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］中建立的基于時(shí)間最短的集卡線路優(yōu)化模型，對岸橋的處理僅使用其作業(yè)時(shí)間，將所有岸橋作為一個(gè)整體考慮，沒有涉及到岸橋與集卡之間作業(yè)時(shí)間銜接的約束以及岸橋執(zhí)行各個(gè)任務(wù)的調(diào)度.CAO等［13］研究IQCYTSP，建立MIP模型、設(shè)計(jì)遺傳算法并改進(jìn)基于約翰遜規(guī)則的啟發(fā)式算法求解，但其只求解小規(guī)模的問題，而且未考慮岸橋卸載任務(wù)具有順序關(guān)系約束.

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

1 問題描述與MIP模型

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

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

1.1 模型參數(shù)

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

1.2 決策變量

1.3 MIP 模型

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

2 約束規(guī)劃模型

2.1 模型特征

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

區(qū)間變量經(jīng)常用于建模一段任務(wù)(活動)時(shí)間，起點(diǎn)為任務(wù)開始時(shí)刻，終點(diǎn)為任務(wù)結(jié)束時(shí)刻.本文提出的CP模型就是基于區(qū)間變量設(shè)計(jì)的.CP系統(tǒng)提供大量函數(shù)訪問區(qū)間變量的屬性和設(shè)置約束.為簡單起見，主要采用BAPTISTE等［15］和OPL中的符號表示法表示基于區(qū)間變量的CP模型，該文獻(xiàn)中提出的“活動”變量就是區(qū)間變量的雛形，提出的許多作用于活動變量的函數(shù)亦可用于區(qū)間變量，這些函數(shù)都是簡單自明的.如start(a)表示區(qū)間變量a的起點(diǎn)、end(a)表示區(qū)間變量a的終點(diǎn)、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語言實(shí)現(xiàn).

2.2 模型參數(shù)

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

2.3 決策變量與約束條件

2.3.1 變量域約束

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.7 資源約束

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

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

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

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

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

目標(biāo)函數(shù)(36)是最小化集卡任務(wù)的最晚完工時(shí)間，也就是整體完工時(shí)間:?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)生顯著影響.通過實(shí)驗(yàn)嘗試幾個(gè)不同的次序，發(fā)現(xiàn)先固定順序變量數(shù)組r，再固定q的搜索效率最高.搜索階段用ILOG腳本定義如下:

3 下界分析

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)束語

采用CP技術(shù)建模求解帶任務(wù)順序關(guān)系約束的岸橋與集卡聯(lián)合調(diào)度問題，在采用提高求解效率的累積約束及更加高效的約束表達(dá)式后，利用不同規(guī)模實(shí)例進(jìn)行測試，結(jié)果顯示CP具有很高的求解效率和求解質(zhì)量，能夠求解規(guī)模更大的問題.未來的一個(gè)研究方向是考慮將場橋調(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ì)算機(jī)工程與應(yīng)用，2006，(32):7-219.

［7］董良才，丁以中，宓為建.基于時(shí)間窗的集裝箱裝卸橋調(diào)度［J］.上海海事大學(xué)學(xué)報(bào)，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é)報(bào)，2004，6(19):18-20.

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

［12］計(jì)明軍，靳志宏.集裝箱碼頭集卡與岸橋協(xié)調(diào)調(diào)度優(yōu)化［J］.復(fù)旦學(xué)報(bào):自然科學(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.