基于約束規(guī)劃的岸橋與集卡集成調(diào)度

秦天保，彭嘉瑤，沙 梅

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

基于約束規(guī)劃的岸橋與集卡集成調(diào)度

秦天保，彭嘉瑤，沙 梅

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

針對(duì)進(jìn)口集裝箱卸船的岸橋與集卡集成調(diào)度問題，分別提出混合整數(shù)規(guī)劃(MIP)模型和約束規(guī)劃(CP)模型，目標(biāo)是使得卸船完工時(shí)間最短，該問題是NP難題。通過OPL語言設(shè)計(jì)約束規(guī)劃模型，利用其為調(diào)度問題提供的特殊構(gòu)造，如區(qū)間變量、序列變量等進(jìn)行建模，并采用“擴(kuò)展操作任務(wù)”的概念來定義區(qū)間變量以提升求解效率。為評(píng)價(jià)解的質(zhì)量，設(shè)計(jì)一個(gè)新的下界求解方法。使用不同規(guī)模的實(shí)例對(duì)約束規(guī)劃模型和MIP模型進(jìn)行測(cè)試，結(jié)果表明，在小規(guī)模實(shí)例中，CP模型求解性能略差于MIP模型，但對(duì)于中大規(guī)模實(shí)例，MIP模型無法在設(shè)定時(shí)限內(nèi)找到解，而CP模型則能以較快的收斂速度得到高質(zhì)量的解，目標(biāo)距離下界的差距控制在2.19%～8.28%。

岸橋調(diào)度；集卡調(diào)度；約束規(guī)劃；集裝箱碼頭；最優(yōu)化；啟發(fā)式算法；混合整數(shù)規(guī)劃

1 概述

岸橋調(diào)度問題(Quay Crane Scheduling Problem, QCSP)和碼頭堆場內(nèi)部集卡調(diào)度問題(Yard Truck Scheduling Problem, YTSP)是集裝箱碼頭作業(yè)系統(tǒng)2個(gè)重要的子問題，指為岸橋和集卡制定工作計(jì)劃，使得某個(gè)目標(biāo)最優(yōu)(通常為完工時(shí)間最短)。

現(xiàn)有文獻(xiàn)大多分開研究這2個(gè)子問題。針對(duì)岸橋調(diào)度問題，文獻(xiàn)[1]建立了混合線性整數(shù)規(guī)劃(Mixed Integer Linear Programming, MILP)模型，并提出分支定界算法(B&B)求解；文獻(xiàn)[2]設(shè)計(jì)了一種禁忌搜索算法求解該問題；文獻(xiàn)[3]將隨機(jī)貪婪適應(yīng)性搜索算法融入遺傳算法求解岸橋調(diào)度；文獻(xiàn)[4]提出了帶時(shí)間窗的岸橋調(diào)度混合整數(shù)規(guī)劃(Mixed Integer Programming, MIP)模型，并設(shè)計(jì)了遺傳算法求解。針對(duì)集卡調(diào)度問題，文獻(xiàn)[5]提出了貪婪算法研究集卡調(diào)派問題；文獻(xiàn)[6]設(shè)計(jì)了遺傳算法求解集卡調(diào)度問題；文獻(xiàn)[7]對(duì)集裝箱碼頭集卡分配問題建立了整數(shù)規(guī)劃模型；文獻(xiàn)[8]設(shè)計(jì)了現(xiàn)代集裝箱碼頭集卡調(diào)度系統(tǒng)，提出了集裝箱碼頭物流系統(tǒng)有色Petri網(wǎng)建模的基本構(gòu)架和一種新的遺傳算法調(diào)度編碼方式。文獻(xiàn)[9]針對(duì)集卡調(diào)度，提出了基于能力約束判斷的資源協(xié)作模型，并設(shè)計(jì)了改進(jìn)的量子遺傳算法進(jìn)行求解。文獻(xiàn)[10]提出一種面向整個(gè)碼頭作業(yè)面的動(dòng)態(tài)蟻群算法來動(dòng)態(tài)優(yōu)化集卡調(diào)度路徑。

由于岸橋和集卡具有很強(qiáng)的交互作用，將兩者進(jìn)行集成調(diào)度能夠得到更好的全局解，這就是岸橋與集卡集成調(diào)度問題(Integrated Quay Crane and Yard Truck Schedule Problem, IQCYTSP)。但集成調(diào)度文獻(xiàn)較少，文獻(xiàn)[11]研究了該問題，但該文實(shí)際上是基于時(shí)間最短的集卡線路優(yōu)化模型，對(duì)岸橋的處理僅使用了其作業(yè)時(shí)間，將所有岸橋作為一個(gè)整體考慮，沒有涉及到岸橋和集卡之間作業(yè)時(shí)間銜接的約束以及岸橋執(zhí)行各個(gè)任務(wù)的調(diào)度。文獻(xiàn)[12]研究了集卡與岸橋聯(lián)合調(diào)度問題，建立了混合整數(shù)規(guī)劃MIP模型，并設(shè)計(jì)了遺傳算法和修訂的基于約翰遜規(guī)則的啟發(fā)式算法求解，但其只求了小規(guī)模的問題。

IQCYTSP問題是NP難題[12]，現(xiàn)有研究基本上都是設(shè)計(jì)各種啟發(fā)式算法進(jìn)行求解。本文建立一個(gè)新的規(guī)范化MIP模型和一個(gè)約束規(guī)劃(Constraint Programming, CP)模型，設(shè)計(jì)新的下界，對(duì)該問題進(jìn)行實(shí)驗(yàn)求解。一方面，通過實(shí)驗(yàn)判斷約束規(guī)劃技術(shù)應(yīng)用于本問題的適用性；另一方面，為學(xué)術(shù)界求解此類問題提供一個(gè)新的思路。

2 問題描述與MIP模型

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

該問題還有一個(gè)特點(diǎn)，即岸橋從船上卸載一個(gè)箱子后，若下面無集卡(集卡可能還未返回)，則岸橋必須等待，即處于阻塞狀態(tài)，這一點(diǎn)模型中必須考慮，為此，設(shè)計(jì)2個(gè)決策變量，為岸橋從船上提箱i并移動(dòng)到陸側(cè)的時(shí)間，本文稱之為岸橋卸載箱子i的結(jié)束時(shí)間，di為岸橋放下箱子i到集卡的時(shí)間，也就是箱子離開岸橋的時(shí)間，即為岸橋阻塞的時(shí)間。岸橋放下箱子到集卡上后才能開始一段過渡時(shí)間去卸下一個(gè)箱子。下面首先提出一個(gè)針對(duì)此問題的MIP模型。

2.1 模型參數(shù)

MIP模型各參數(shù)如下：

n：箱子數(shù)目；

m：集卡數(shù)目；

pi：岸橋卸載箱子i需要的時(shí)間

ti：集卡運(yùn)輸箱子i到堆場的時(shí)間，也等于其返程時(shí)間

d：場橋從集卡卸載一個(gè)集裝箱到堆場所需時(shí)間；

sij：岸橋放下箱子i到集卡上后，立即卸載箱子j的過渡時(shí)間

M：一個(gè)足夠大的正數(shù)。

2.2 決策變量

決策變量如下：

Cmax：所有任務(wù)完成的時(shí)間，即所有集裝箱經(jīng)過岸橋卸船、集卡運(yùn)輸、場橋卸載到堆場的結(jié)束時(shí)間；

di：岸橋卸下箱子i并放到集卡上的時(shí)間點(diǎn)，即箱子離開岸橋的時(shí)間

xik：如果箱子i分配給集卡k運(yùn)輸，取1，其他取0

yij：如果箱子i在箱子j之前卸載或運(yùn)輸，取1，其他取

2.3 MIP模型

MIP模型描述如下：

目標(biāo)函數(shù)式(1)是最小化所有箱子由船舶卸載到堆場存放的完工時(shí)間；約束式(2)定義總完工時(shí)間，要求其大于所有箱子運(yùn)到堆場并堆放完成的時(shí)間；約束式(3)保證岸橋卸載箱子i的結(jié)束時(shí)間大于卸載時(shí)間(不包含岸橋等待集卡的時(shí)間)；約束式(4)保證任一箱子只能分配給一輛集卡運(yùn)輸；約束式(5)保證箱子i離開岸橋的時(shí)間大于岸橋卸載箱子i的結(jié)束時(shí)間；約束式(6)保證箱子i離開岸橋的時(shí)間等于集卡開始運(yùn)輸i的時(shí)間，該約束表達(dá)了岸橋和集卡間的銜接關(guān)系；約束式(7)和式(8)保證岸橋卸載2個(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)和式(10)保證分配給同一集卡的2個(gè)箱子運(yùn)輸任務(wù)間至少要經(jīng)過一段過渡時(shí)間；約束式(9)表示若箱子j先于i被同一集卡k運(yùn)輸(yij=0，xik、xjk=1)，則j運(yùn)輸并堆放到堆場完成后，至少經(jīng)過tj的過渡時(shí)間(即返程時(shí)間)才能開始運(yùn)輸i；約束式(10)表示若箱子i先于j被同一集卡k運(yùn)輸(yij=1，xik、xjk=1)，則i運(yùn)輸并堆放到堆場完成后，至少經(jīng)過ti的過渡時(shí)間(即返程時(shí)間)才能開始運(yùn)輸j；式(11)和式(12)是決策變量域約束。

由于該問題是NP難題[10]，對(duì)大規(guī)模問題，MIP模型會(huì)難于求解(下文第4節(jié)的實(shí)驗(yàn)也驗(yàn)證了這一點(diǎn))，為此，本文在第3節(jié)提出針對(duì)此問題的一個(gè)CP模型，并測(cè)試和評(píng)價(jià)其求解效率。

3 約束規(guī)劃模型

3.1 模型特點(diǎn)

下面建立相應(yīng)的CP模型。CP模型在不同CP系統(tǒng)中表示方法不同，其表達(dá)方式也未達(dá)成一致。本文所建CP模型是用IBM ILOG CPLEX Optimization 12.4中的OPL 12.4語言實(shí)現(xiàn)的。OPL針對(duì)調(diào)度問題提出了一種新的概念，即區(qū)間(決策)變量，區(qū)間變量概念是對(duì)約束規(guī)劃在調(diào)度領(lǐng)域應(yīng)用的一個(gè)重要擴(kuò)展。文獻(xiàn)[13]介紹了約束規(guī)劃中應(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ù)，故以下的約束規(guī)劃模型中，時(shí)間都被離散化為整數(shù)。

區(qū)間變量經(jīng)常用于建模一段任務(wù)(活動(dòng))時(shí)間，起點(diǎn)為任務(wù)開始時(shí)間，終點(diǎn)為任務(wù)結(jié)束時(shí)間。本文提出的CP模型就是基于區(qū)間變量設(shè)計(jì)的。約束規(guī)劃系統(tǒng)提供大量函數(shù)訪問區(qū)間變量的屬性和設(shè)置約束。為簡單起見，主要采用文獻(xiàn)[13] 和OPL中的符號(hào)表示法來表示基于區(qū)間變量的約束規(guī)劃模型，該文獻(xiàn)中提出的“活動(dòng)”變量就是區(qū)間變量的雛形，其提出的許多作用于活動(dòng)變量的函數(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í)行)。文中采用的一些函數(shù)和構(gòu)造若文獻(xiàn)[14]中沒有，則直接采用OPL中的構(gòu)造，這些函數(shù)和構(gòu)造將在下面模型中出現(xiàn)時(shí)再解釋。采用這套表示法表達(dá)的約束規(guī)劃模型很容易轉(zhuǎn)化成OPL語言實(shí)現(xiàn)。

本文建立的CP模型有一個(gè)特色，就是對(duì)區(qū)間變量所代表的操作任務(wù)有不同的定義。傳統(tǒng)上，一個(gè)操作任務(wù)就是設(shè)備完成一個(gè)集裝箱操作所需的時(shí)間，它不包含設(shè)備阻塞的時(shí)間（比如岸橋卸箱時(shí)等待集卡的時(shí)間），本文把這樣定義的操作任務(wù)稱為“基本操作任務(wù)”，在前面的MIP模型中，對(duì)操作任務(wù)即采用此定義。

本文建立過一個(gè)將區(qū)間變量定義為基本操作任務(wù)的CP模型，通過實(shí)驗(yàn)發(fā)現(xiàn)求解效率不夠高。為此，筆者引入了一個(gè)新的任務(wù)定義，即在CP模型中，將設(shè)備操作任務(wù)定義為包含阻塞時(shí)間的操作任務(wù)，將包含阻塞時(shí)間的操作任務(wù)稱為“擴(kuò)展操作任務(wù)”。例如，岸橋卸載箱子的擴(kuò)展操作任務(wù)包含岸橋吊具從岸邊移到船上提箱，送到岸邊，再加上等待集卡的時(shí)間。筆者發(fā)現(xiàn)，將區(qū)間變量定義為擴(kuò)展操作任務(wù)所建立的CP模型，求解效率會(huì)提高很多，因此，以下CP模型中區(qū)間變量即采用擴(kuò)展操作任務(wù)的定義。

3.2 模型參數(shù)

3.3 決策變量與約束條件

3.3.1 區(qū)間決策變量

本CP模型定義了3組區(qū)間決策變量：qtasksi, ytasksi和ytTaskski。qtasksi表示岸橋卸載箱子i的擴(kuò)展任務(wù)，其域?yàn)閇0, H]。其起點(diǎn)表示任務(wù)開始時(shí)間，終點(diǎn)表示任務(wù)結(jié)束時(shí)間，長度即為卸載該箱子的持續(xù)時(shí)間（包含阻塞時(shí)間）。

約束式(13)規(guī)定岸橋的集裝箱操作任務(wù)(擴(kuò)展操作任務(wù))時(shí)間長度不小于相應(yīng)的基本操作任務(wù)時(shí)間pi，因?yàn)槿缜八?，CP模型中的定義的任務(wù)時(shí)間包含阻塞時(shí)間，所以長于實(shí)際的操作時(shí)間。

區(qū)間變量ytasksi表示集卡運(yùn)輸箱子i的任務(wù)(注：這里將運(yùn)輸任務(wù)執(zhí)行時(shí)長定義為集卡運(yùn)輸時(shí)間加上場橋卸載時(shí)間)，其域?yàn)閇0, H]。以下給出對(duì)該區(qū)間變量ytasksi的限制約束：

二維區(qū)間變量ytTaskski表示集卡k運(yùn)輸箱子i的任務(wù)，定義為可選(optional)區(qū)間變量，其域?yàn)閇0, H]。它表示一個(gè)運(yùn)輸任務(wù)可能由任意一個(gè)集卡完成，最終會(huì)利用選擇約束約束)來限制僅能由一輛集卡完成。因此，可以將ytTaskski理解為一種模式選擇區(qū)間變量，即一個(gè)任務(wù)可能有多種完成模式(一輛集卡為一個(gè)模式)。要間隔一段過渡時(shí)間。為實(shí)現(xiàn)這個(gè)約束，首先定義一個(gè)過渡函數(shù)：

ytTaskski定義為OPL可選變量，說明并非所有ytTaskski都必須執(zhí)行，只有那些被選中的才會(huì)被執(zhí)行。

3.3.2 集卡任務(wù)分配

ytasksi和ytTaskski受限制于選擇(alternative)約束式(16)，表示如果運(yùn)輸任務(wù)ytasksi執(zhí)行，則所有的ytTaskski(k=1, 2,…, m)中只能有一個(gè)執(zhí)行(其他不執(zhí)行，也就是其present狀態(tài)為0)，且其起止時(shí)間與ytasksi完全相同，這樣就能保證每個(gè)箱子只能由一輛集卡來運(yùn)輸，即將任務(wù)分配給特定的集卡。

該函數(shù)用于定義岸橋卸載任務(wù)(箱子)i到j(luò)的過渡時(shí)間為sij。然后定義一個(gè)序列變量qsequence：

為序列變量中的任務(wù)分配類型：

任務(wù)類型就是任務(wù)(箱子)編號(hào)。利用noOverlap(不重疊)約束式(18)來保證該序列中的任務(wù)不能重疊，且2個(gè)相繼任務(wù)之間需要一段過渡時(shí)間。

3.3.4 無緩沖約束

在卸船的過程中，對(duì)任一箱子i，岸橋卸載的擴(kuò)展操作任務(wù)結(jié)束時(shí)間要等于集卡運(yùn)輸?shù)拈_始時(shí)間，2個(gè)階段間沒有緩沖區(qū)。約束式(19)表達(dá)了岸橋和集卡間這種無緩沖的銜接關(guān)系。

3.3.3 任務(wù)排序約束

每一個(gè)集卡k執(zhí)行自己的運(yùn)輸任務(wù)ytTaskski(i=1,2,…,n)互相不能重疊，即集卡只能一次一個(gè)依次運(yùn)輸箱子，因此，需要確定任務(wù)在集卡上執(zhí)行的排序。集卡卸箱到堆場后，需要一段返程時(shí)間回到岸橋，才能開始下一個(gè)運(yùn)輸任務(wù)，故集卡的2個(gè)相繼運(yùn)輸任務(wù)之間有過渡時(shí)間，這個(gè)過渡時(shí)間就是返程時(shí)間，本文假設(shè)集卡運(yùn)輸集裝箱i的返程時(shí)間也是ti。OPL提供了序列變量這一新型決策變量來高效建模排序約束。首先，定義過渡函數(shù)：

3.3.5 資源消耗限制約束

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

該函數(shù)定義了集卡任務(wù)i到j(luò)的過渡時(shí)間為ti(如果返程時(shí)間不是ti，則修改過渡函數(shù)中的參數(shù)ti為實(shí)際返程時(shí)間即可)。在集卡k執(zhí)行的任務(wù)集合上定義序列變量ysequencek，其域?yàn)椋?/p>

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

圖1表示了匯總累積函數(shù)消耗資源的曲線，其中，H表示資源量限制，各個(gè)a是區(qū)間變量?？梢钥闯?，每個(gè)區(qū)間變量執(zhí)行時(shí)，使得匯總累積函數(shù)曲線增加，區(qū)間變量執(zhí)行完后，使得匯總累積函數(shù)減少。對(duì)匯總累積函數(shù)上限施加的限制就是累積約束，也就是資源限制約束。

可見序列變量可能的取值為一組區(qū)間變量的所有排序。可以對(duì)序列變量中各個(gè)任務(wù)分配一個(gè)類型，如：

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

類似地，所有的岸橋任務(wù)qtasksi也互相不能重疊，即岸橋只能一次一個(gè)依次卸載箱子，因此，需要確定任務(wù)在岸橋上執(zhí)行的排序，而且岸橋執(zhí)行2個(gè)相繼任務(wù)之間還需

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

目標(biāo)函數(shù)式(21)是最小化最晚完工的集卡任務(wù)的完工時(shí)間，即整體完工時(shí)間。

通過比較CP模型和MILP模型，可以發(fā)現(xiàn)CP模型約束表達(dá)自然簡潔，由于可以自然地表達(dá)邏輯約束，無需使用大量0-1變量。

3.5 搜索策略

為進(jìn)一步提升ILOG CP優(yōu)化器搜索本問題解空間的搜索效率，可以對(duì)其默認(rèn)搜索策略進(jìn)行調(diào)整，搜索策略包含多方面的內(nèi)容，這里要調(diào)整的是搜索變量的次序，和為變量賦值的次序(例如從小到大還是從大到小賦值)，研究發(fā)現(xiàn)，這些次序有時(shí)會(huì)極大地影響搜索效率。本文利用ILOG CP提供的搜索階段機(jī)制來干預(yù)其搜索策略。通過搜索階段可以指定CP優(yōu)化器搜索時(shí)固定變量的次序，筆者通過實(shí)驗(yàn)嘗試了不同的次序，發(fā)現(xiàn)先固定序列變量ysequence，再固定qsequence的搜索效率最高(變量賦值的次序采用系統(tǒng)默認(rèn)次序)。搜索階段用ILOG腳本定義如下：cp.setSearch Phases (f.searchPhase(ysequence), f.searchPhase(qsequence))。

4 下界分析

下文分別對(duì)LB1和LB2進(jìn)行分析。

4.1 LB1分析

以此類推，首次行程中最后一輛集卡的出發(fā)時(shí)間下界LB1為：

4.2 LB2分析

令T1為運(yùn)完所有集裝箱需要的所有集卡總運(yùn)輸時(shí)間，這個(gè)時(shí)間包括集卡堆場卸載和返程時(shí)間，但不包括集卡在岸橋下等待的時(shí)間，并且假設(shè)包含各集卡最后一次運(yùn)輸?shù)姆党虝r(shí)間，則有：

令T2為最后一輛集卡首次行程出發(fā)前其他集卡已完成的總運(yùn)輸時(shí)間上界，T3為各集卡最后一次運(yùn)輸所對(duì)應(yīng)的總返程時(shí)間上界(由于是最后一次運(yùn)輸，因此實(shí)際上無需返程)，則有：

為了評(píng)價(jià)CP模型的求解質(zhì)量，需要得到較緊的下界，本節(jié)提出一個(gè)新的求解上述問題下界的方法。為了定義該下界，本文首先定義2個(gè)要用于下界計(jì)算的算符。

定義定義min[k]為取一列數(shù)值中第k小的數(shù)，max[k]為取一列數(shù)值中第k大的數(shù)。

例如，給定一列數(shù)值S={10, 3, 6, 6, 7, 9 }，則：

也就是說首次行程中最后一輛集卡出發(fā)后剩下的集裝箱需要的總運(yùn)輸時(shí)間(包括集卡堆場卸載時(shí)間和返程時(shí)間)的下界LB2等于所有集裝箱需要的總運(yùn)輸時(shí)間T1減去該集卡出發(fā)前其他集卡已完成的總運(yùn)輸時(shí)間上界(因?yàn)檫@些時(shí)間已被用掉)T2，再減去各集卡最后一次運(yùn)輸所對(duì)應(yīng)的總返程時(shí)間上界(因?yàn)樽詈笠淮螣o需返程)T3。

為計(jì)算T2，考慮首次行程中共有m個(gè)箱子需要卸載。在最后一輛集卡出發(fā)前，第1輛集卡消耗的運(yùn)輸時(shí)間為岸橋卸載后m–1個(gè)箱子的時(shí)間及必要的過渡時(shí)間，這個(gè)時(shí)間的上界為：

注意，將這列數(shù)值先排序后會(huì)更加容易看出算符的操作結(jié)果，另外，允許這一列數(shù)值中有重復(fù)的數(shù)。

定理假設(shè)有m輛集卡運(yùn)輸m個(gè)集裝箱，1臺(tái)岸橋，則該IQYSP問題的下界LB可由下式求得：

證明：令LB1為首次行程中最后一輛集卡的出發(fā)時(shí)間的下界。首次行程指各集卡第一次運(yùn)輸箱子的行程，最后一輛集卡的出發(fā)時(shí)間即一開始排在最后的那輛集卡接受岸橋卸下箱子開始運(yùn)輸?shù)臅r(shí)間。令LB2為首次行程中最后一輛集卡出發(fā)后剩下的集裝箱需要的總運(yùn)輸時(shí)間(包括集卡堆場卸載時(shí)間和返程時(shí)間，但不包括集卡在岸橋下等待的時(shí)間)下界。則容易看出，下式成立：

同理，第2輛集卡消耗的運(yùn)輸時(shí)間為岸橋卸載后m–2個(gè)箱子的時(shí)間及必要的過渡時(shí)間，這個(gè)時(shí)間的上界為：

以此類推，可求得首次行程中前m–1輛集卡消耗的運(yùn)輸時(shí)間上界，把它們相加，即得到T2：

T3比較簡單，可由下式得到：

將式(25)、式(27)、式(28)中的T1，T2，T3代入式(26)，再將式(26)和式(24)代入式(23)，即可得到式(22)，定理得證。

5 數(shù)值實(shí)驗(yàn)

本節(jié)報(bào)告數(shù)值實(shí)驗(yàn)結(jié)果，將以上約束規(guī)劃模型用IBM ILOG CPLEX Optimization Studio 12.6中的OPL語言實(shí)現(xiàn)，并利用其中的CP優(yōu)化器求解。計(jì)算時(shí)將系統(tǒng)參數(shù)Sequence InferenceLevel和NoOverlapInferenceLevel都設(shè)為5，Workers參數(shù)設(shè)為1。測(cè)試硬件平臺(tái)為4核Intel Xeon E3 3.7 GHz CPU，8 GB內(nèi)存。

為了測(cè)試CP方法能否求解實(shí)際規(guī)模的實(shí)例，隨機(jī)生成了7個(gè)不同規(guī)模的實(shí)例集，每個(gè)實(shí)例集含5個(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。

5.1 小規(guī)模實(shí)例測(cè)試

對(duì)于10個(gè)任務(wù)5輛集卡的小規(guī)模實(shí)例，利用數(shù)學(xué)規(guī)劃求解軟件Gurobi 5.01求MIP模型，可得最優(yōu)解，本文比較了64位的Gurobi得到的最優(yōu)目標(biāo)值和CP的求解結(jié)果(CP求解時(shí)限設(shè)為5 min)，見表1。其中，“Gurobi”列是Gurobi求得的最優(yōu)目標(biāo)值和求解時(shí)間；“CP”列是CP模型1 min內(nèi)求得的最佳目標(biāo)值和求得該值的時(shí)間；“差距”列是CP目標(biāo)值相對(duì)最優(yōu)目標(biāo)的百分比差距。可以看見，CP方法在2 s以內(nèi)全部求到最優(yōu)解，說明CP的求解效率和求解質(zhì)量都很高。

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

5.2 中大規(guī)模實(shí)例測(cè)試

本節(jié)進(jìn)一步測(cè)試CP方法對(duì)中大規(guī)模實(shí)例的求解結(jié)果，求解時(shí)限為半小時(shí)(Gurobi無法在半小時(shí)時(shí)限內(nèi)求解這些實(shí)例)。為更準(zhǔn)確地觀察求解收斂情況與解的質(zhì)量，本文分3個(gè)時(shí)間段統(tǒng)計(jì)了實(shí)驗(yàn)結(jié)果，分別設(shè)定為1 min、2 min、5 min，表2統(tǒng)計(jì)了6個(gè)實(shí)例集(每個(gè)實(shí)例集含5個(gè)實(shí)例)的平均計(jì)算結(jié)果，其中，“下界”列表示每個(gè)實(shí)例集中5個(gè)實(shí)例的平均下界；“目標(biāo)”列是CP在相應(yīng)時(shí)段內(nèi)求得的每個(gè)實(shí)例集中5個(gè)實(shí)例的最佳目標(biāo)值的平均值；“時(shí)間”列是求得實(shí)例集中各實(shí)例最佳目標(biāo)的時(shí)間的平均值；“差距”列是實(shí)例集中各實(shí)例最佳目標(biāo)相對(duì)下界的百分比差距的平均值?？梢钥闯?，CP求解的收斂速度很快，在1 min內(nèi)就能得到較好的解，各實(shí)例集求解的平均目標(biāo)距離下界的差距在5%以內(nèi)，這種快速收斂的特性非常有利于碼頭實(shí)時(shí)調(diào)度。

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

圖2展示了一個(gè)100個(gè)任務(wù)的實(shí)例(實(shí)例100_1)求解收斂過程，可以看出早期收斂是非常快的，在最初1 min內(nèi)就收斂到下界附近了。

以上測(cè)試考察了集裝箱數(shù)量對(duì)裝卸時(shí)間的影響，為考察集卡數(shù)量對(duì)裝卸時(shí)間和求解性能的的影響，本文對(duì)100個(gè)任務(wù)的實(shí)例集分別測(cè)試5輛、8輛和10輛集卡的情況，求解時(shí)限設(shè)為5 min，在5 min內(nèi)求得的最佳目標(biāo)值(完工時(shí)間)見表3?？梢钥闯?，集卡數(shù)目對(duì)目標(biāo)值影響很大，集卡從5輛增加到10輛，裝卸完工時(shí)間平均可減少40%以上(假設(shè)場橋總是可用)。

圖2 100個(gè)任務(wù)的實(shí)例求解收斂過程

表3 不同集卡數(shù)量時(shí)的測(cè)試結(jié)果

6 結(jié)束語

本文采用CP技術(shù)建模求解岸橋與集卡聯(lián)合調(diào)度問題，在采用了提高求解效率的累積約束以及更高效的約束表達(dá)式后，利用不同規(guī)模實(shí)例進(jìn)行測(cè)試，實(shí)驗(yàn)結(jié)果顯示CP具有很高的求解效率和求解質(zhì)量，能夠求解規(guī)模更大的問題。CP的另一個(gè)重要優(yōu)勢(shì)是可以采用高級(jí)建模語言以聲明性語法(本文采用OPL語言)建模，這使得模型清晰易懂，便于根據(jù)實(shí)際情況隨時(shí)修訂約束。而其他文獻(xiàn)多采用啟發(fā)式算法求解問題，由于沒有清晰的模型表達(dá)機(jī)制，使得修改約束較為麻煩。CP技術(shù)兼具靈活性和效率的特點(diǎn)使其成為求解碼頭運(yùn)營問題的有效工具。未來可考慮擴(kuò)展模型，將場橋調(diào)度也集成進(jìn)來，形成岸橋、集卡和場橋集成調(diào)度模型。

[1] Kim K H, Park Y M. A Crane Scheduling Method for Port Container Terminals[J]. European Journal of Operational Research, 2004, 156(3): 752-768.

[2] Sammarra M, Cordeau J F, Laporte G, et al. A Tabu Search Heuristic for the Quay Crane Scheduling Problem[J]. Journal of Scheduling, 2007, 10(4/5): 327-336.

[3] 曾慶成, 高 宇. 集裝箱碼頭裝卸橋調(diào)度優(yōu)化模型與算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2006, 42(32): 217-219.

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

[5] Bish E K, Chen F Y, Leong Y T, et al. Dispatching Vehicles in a Mega Container Terminal[J]. OR Spectrum, 2005, 27(4): 491-506.

[6] Ng W C, Mak K L, Zhang Y X. Scheduling Trucks in Container Terminals Using a Genetic Algorithm[J]. Engineering Optimization, 2007, 39(1): 33-47.

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

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

[9] 丁榮濤. 基于協(xié)作能力約束的港口集卡調(diào)度優(yōu)化策略[J].清華大學(xué)學(xué)報(bào): 自然科學(xué)版, 2012, 52(8): 1158-1164.

[10] 李廣儒, 楊大奔, 任大偉. 集卡動(dòng)態(tài)調(diào)度路徑優(yōu)化算法[J].交通運(yùn)輸工程學(xué)報(bào), 2012, 12(3): 86-91.

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

[12] Cao Jinxin, Shi Qinxin, Lee D H. Integrated Quay Crane and Yard Truck Schedule Problem in Container Terminals[J]. Tsinghua Science and Technology, 2010, 15(4): 467-474.

[13] Laborie P, Rogerie J. Reasoning with Conditional Timeintervals[C]//Proc. of the 21st International Conference of the Florida Artificial Intelligence Research Society. Coconut Grove, USA: Florida AI Research Society, 2008: 555-560.

[14] Baptiste P, Laborie P, le Pape C, et al. Constraint-based Scheduling and Planning[M]//Rossi F, van Beek P, Walsh T. Handbook of Constraint Programming. [S. l.]: Elsevier, 2006: 761-794.

編輯 金胡考

Integrated Quay Crane and Yard Truck Scheduling Based on Constraint Programming

QIN Tian-bao, PENG Jia-yao, SHA Mei

(College of Transport & Communications, Shanghai Maritime University, Shanghai 200135, China)

A Mixed Integer Programming(MIP) model and a Constraint Programming(CP) model to tackle the integrated quay crane and yard truck scheduling problem for inbound containers are proposed, which aims to minimize the makespan of unloading process. The CP model is developed with OPL modeling language and employs OPL’s special constructs designed for scheduling problems, e.g., interval variables sequence variable etc. To improve solving efficiency, a special concept called extended operation task is proposed which is used to define interval variables. Besides, a new lower bound is given to evaluate the quality of solutions. Computational experiments on varied scales of instances are carried out to test the CP model and the MIP model. The results indicate that the CP model does not outperform the MIP model for small instances. For medium and large instances, the MIP model can not be solved within time limit, whereas the CP model is effective for finding high-quality solutions and can efficiently solve large problems with fast convergence rate. On average, the gap between the objective values of the CP model and the lower bounds is 2.19%～8.28%.

quay crane scheduling; yard truck scheduling; Constraint Programming(CP); container terminal; optimization; heuristic algorithm; Mixed Integer Programming(MIP)

10.3969/j.issn.1000-3428.2014.05.041

國家自然科學(xué)基金資助項(xiàng)目(71172076)；交通部應(yīng)用基礎(chǔ)研究基金資助項(xiàng)目(2011-329-810-450)；上海市科委地方院校專項(xiàng)基金資助項(xiàng)目(11510501800)；上海市教委科研創(chuàng)新基金資助項(xiàng)目(11YZ135)；上海市重點(diǎn)學(xué)科建設(shè)基金資助項(xiàng)目(S30601)。

秦天保(1971－)，男，副教授、博士，主研方向：港口與航運(yùn)系統(tǒng)智能優(yōu)化；彭嘉瑤，碩士研究生；沙 梅，教授、博士。

2013-03-11

2013-06-03E-mail：qtbgo@163.com

1000-3428(2014)05-0196-07

A

TP18