考慮不確定性的岸橋與集卡集成調(diào)度

張 思，孫啟峰

（上海大學(xué) 管理學(xué)院，上海200444）

0 引言

航運(yùn)貿(mào)易的繁榮使全世界港口的集裝箱吞吐量不斷增長，以全世界最大的港口——上海港為例，如圖1所示，集裝箱吞吐量10年來一直保持穩(wěn)定增長：2010年的集裝箱吞吐量為2 906.9萬TEU，2017年突破4 000萬大關(guān)達(dá)到4 023萬TEU，2019已達(dá)到4 330萬TEU。預(yù)計(jì)上海港未來集裝箱吞吐量仍將保持中低增長趨勢，集裝箱碼頭能力適應(yīng)度問題將會日趨嚴(yán)峻[1-2]。

很多港口對現(xiàn)有的作業(yè)設(shè)備進(jìn)行調(diào)度優(yōu)化，以提高作業(yè)效率，緩解持續(xù)增長的集裝箱吞吐量帶來的作業(yè)壓力。其中，岸橋與集卡的集成調(diào)度是研究的重點(diǎn)之一。

圖1 上海港集裝箱吞吐量

部分學(xué)者研究了裝船與卸船作業(yè)同時(shí)進(jìn)行的雙向流問題。曾慶成，等[3]構(gòu)建上層調(diào)度岸橋、下層優(yōu)化集卡路徑的雙層模型以實(shí)現(xiàn)協(xié)調(diào)優(yōu)化，并設(shè)計(jì)遺傳算法求解。為協(xié)調(diào)岸橋調(diào)度與集卡路線，計(jì)明軍，等[4]使用進(jìn)化算法求解研究。馬超，等[5]設(shè)計(jì)雙層遺傳算法，通過主層調(diào)度岸橋，子層基于岸橋作業(yè)來調(diào)度集卡。Chen，等[6]加入場橋調(diào)度并設(shè)計(jì)三階段算法求解，并與其設(shè)計(jì)的禁忌搜索算法[7]相比較，證明了三階段算法的優(yōu)越性。Tang，等[8]協(xié)調(diào)岸橋與集卡以減少二者的空閑時(shí)間，設(shè)計(jì)粒子群算法求解。Behjati，等[9]考慮岸橋不交叉和船舶可變靠泊時(shí)間等因素，力求最小化船舶完工時(shí)間，并采用帝國主義競爭算法進(jìn)行求解。

雙向流問題的流程復(fù)雜，模型難以兼顧某些實(shí)際約束，有些學(xué)者僅研究裝船作業(yè)[10]或卸船作業(yè)[11-14]，以更清楚地描述作業(yè)流程。Cao，等[10]研究最小化裝船作業(yè)的完工時(shí)間，采用遺傳算法和基于約翰遜規(guī)則的啟發(fā)式算法求解模型。樂美龍，等[11]考慮岸橋共享集卡車隊(duì)來提升集卡的利用率，使卸船過程的完工時(shí)間最小化，采用禁忌搜索算法求解。Kaveshgar，等[12]考慮了任務(wù)的優(yōu)先級、岸橋間的干擾等因素，將岸橋與集卡類比為混合流水車間調(diào)度問題，設(shè)計(jì)遺傳算法與貪心算法相結(jié)合求解模型。Zhen，等[13]進(jìn)一步綜合調(diào)度岸橋與集卡，使二者的作業(yè)時(shí)間協(xié)調(diào)最優(yōu)，采用粒子群算法求解。梁承姬，等[14]對于該問題設(shè)計(jì)遺傳算法求解，取得了較好的效果。

以上文獻(xiàn)都是研究靜態(tài)或確定情況下的集成調(diào)度問題，隨著研究的逐步深入，動態(tài)或不確定因素下的集成調(diào)度問題將成為研究的重點(diǎn)[15]。港口作業(yè)的不確定性主要體現(xiàn)在對設(shè)備操作時(shí)間的影響上。大多數(shù)研究是以任務(wù)為視角定義操作時(shí)間，即任務(wù)不同，設(shè)備的操作時(shí)間不同，這適用于將任務(wù)定義為集裝箱組的研究。張思，等[16]考慮了岸橋處理集裝箱組時(shí)的操作時(shí)間具有不確定性，建立岸橋調(diào)度模型，分別設(shè)計(jì)粒子群算法與禁忌搜索算法求解。在岸橋與集卡的集成調(diào)度模型中，任務(wù)定義為單個(gè)集裝箱，操作時(shí)間更多地是取決于設(shè)備的不同，而非任務(wù)。有些學(xué)者以設(shè)備為視角定義任務(wù)的操作時(shí)間，研究了岸橋與集卡集成調(diào)度中的不確定性。樊陸彬，等[17]考慮了岸橋與集卡運(yùn)行參數(shù)的不確定，采用學(xué)科變量耦合優(yōu)化設(shè)計(jì)的方法建立模型。Lu，等[18]考慮了集卡運(yùn)行速度和岸橋操作時(shí)間這兩個(gè)不確定因素，采用粒子群算法求解模型。Noura，等[19]考慮了岸橋與跨運(yùn)車操作時(shí)間的不確定性，提出一種基于仿真的遺傳算法生成質(zhì)量控制計(jì)劃。

1 問題描述及數(shù)學(xué)模型

1.1 問題描述

本文研究卸船作業(yè)的岸橋與集卡的集成調(diào)度問題：船舶到港后，岸橋?qū)⑦M(jìn)口箱從船上卸載到集卡上，由集卡運(yùn)輸至指定的箱區(qū)堆存，而后集卡返回岸邊運(yùn)載下一個(gè)進(jìn)口箱。

在理想情況下，設(shè)備的效率被認(rèn)為是固定的值，且每臺設(shè)備的效率相同。但在實(shí)際情況下，設(shè)備狀況、天氣條件、人為因素等會給設(shè)備效率帶來不確定性，使其在某個(gè)取值區(qū)間內(nèi)波動。若忽略這些不確定性，將會導(dǎo)致調(diào)度計(jì)劃無法應(yīng)對突發(fā)狀況。本文以設(shè)備為視角定義操作時(shí)間，考慮岸橋與集卡在作業(yè)過程中受到不確定因素影響所帶來的效率差異，使調(diào)度計(jì)劃能夠更加穩(wěn)健。

1.2 模型假設(shè)

在構(gòu)建模型前，本文做出如下假設(shè)：

（1）任務(wù)均為40英尺標(biāo)準(zhǔn)集裝箱且信息已知；

（2）所有集卡默認(rèn)選擇其最佳路徑完成任務(wù)；

（3）場橋資源充足，集卡在堆場無需等待。

1.3 符號說明與數(shù)學(xué)模型

1.3.1 參數(shù)與集合

s-場景集合，s={1,2,...,|s|}，場景總數(shù)為|s|；

Ps-場景s發(fā)生的概率；

Ω-任務(wù)集合，Ω={1,2,...,|Ω|}，任務(wù)總數(shù)為

ΩO-ΩO=Ω?{O}，O為虛擬開始任務(wù)；

ΩF-ΩF=Ω?{F}，F(xiàn)為虛擬結(jié)束任務(wù)；

Q-岸橋集合，Q={1,2,...,|Q|}，岸橋總數(shù)為||Q；

K-集卡集合，K={1,2,...,|K|}，集卡總數(shù)為||K；

M-充分大的數(shù)；

Eq-岸橋q的最早工作時(shí)間；

lq-岸橋q的初始貝位；

Li-任務(wù)i所在的貝位；在場景s下岸橋q在每個(gè)貝位的移動時(shí)間；在場景s下岸橋q卸載集裝箱的時(shí)間；在場景s下集卡k的行駛速度；di-集卡由船舶到集裝箱i的指定堆場的往返距離；

φ-具有優(yōu)先級的任務(wù)集合，若(i,j)∈φ，則任務(wù)i先于任務(wù)j完成。

1.3.2 決策變量

Xijq-若岸橋q處理完任務(wù)i后立即處理任務(wù)j(Li≤Lj)則為1，否則為0；

xiq-若岸橋q處理任務(wù)i則為1，否則為0；

Yijk-若集卡k處理完任務(wù)i后立即處理任務(wù)j則為1，否則為0；

Zij-若岸橋在任務(wù)j的開始前完成任務(wù)i則為1，否則為0；在場景s下岸橋卸載任務(wù)i的完成時(shí)刻；在場景s下的岸邊最大完工時(shí)刻。

1.3.3 數(shù)學(xué)模型

s.t.

式（1）表示最小化所有場景的岸邊完工時(shí)間的加權(quán)和；式（2）和式（3）分別保證岸橋調(diào)度從虛擬任務(wù)O開始，在虛擬任務(wù)F結(jié)束；式（4）保證每個(gè)岸橋處理的任務(wù)有且僅有一個(gè)緊前任務(wù)和一個(gè)緊后任務(wù)；式（5）保證每個(gè)任務(wù)有且僅有一個(gè)岸橋處理；式（6）表示變量之間的關(guān)系；式（7）表示編號較大的岸橋處理的第一個(gè)任務(wù)的貝位號也是較大的，保證在初始階段岸橋不會產(chǎn)生初始堵塞問題；式（8）-式（11）表示集卡約束，分別對應(yīng)岸橋約束式（2）-式（5）；式（12）表示任務(wù)j與任務(wù)i位于同一或相鄰貝位，或者有優(yōu)先級要求時(shí)，不能被岸橋同時(shí)處理，必有先后順序；式（13）表示若任務(wù)i與任務(wù)j同時(shí)被處理，則處理較大貝位號任務(wù)的岸橋的編號也較大，保證岸橋間不能跨越；式（14）表示岸橋完成第一個(gè)任務(wù)的時(shí)刻；式（15）表示岸橋完成任務(wù)i后，移動到下一個(gè)任務(wù)j的貝位，卸載該任務(wù)的完成時(shí)刻；式（16）表示待運(yùn)載任務(wù)j的集卡就位后，岸橋才能完成任務(wù)j的卸載；式（17）和式（18）表示若任務(wù)i先于任務(wù)j處理，則在任務(wù)j開始前任務(wù)i已經(jīng)完成；式（19）定義了在場景s下的岸邊最大完工時(shí)間，此時(shí)岸橋已處理完所有任務(wù)，集卡正將最后一個(gè)任務(wù)運(yùn)載到堆場；式（20）和式（21）表示變量的取值范圍。

1.4 模型驗(yàn)證

1.4.1 驗(yàn)證岸橋作業(yè)模式。由于岸橋與集卡的集成調(diào)度是一個(gè)強(qiáng)NP-Hard問題[13]，本身求解難度很大，多場景進(jìn)一步加大了求解難度。為簡化問題，本文在定義變量Xijq時(shí)設(shè)定Li≤Lj，將岸橋設(shè)定為沿貝位編號由小到大方向進(jìn)行單向移動的作業(yè)模式。

一方面，岸橋單向移動的作業(yè)模式操作簡單、可實(shí)現(xiàn)性強(qiáng)，而且減少了雙向往返時(shí)的能源消耗，因此很多港口在實(shí)際作業(yè)中廣泛采用岸橋單向移動的作業(yè)模式。另一方面，本文通過CPLEX進(jìn)行算例實(shí)驗(yàn)，對比岸橋兩種作業(yè)模式的求解時(shí)間和結(jié)果，進(jìn)一步驗(yàn)證岸橋單向移動模式的效果，見表1。

表1 岸橋的作業(yè)模式對比

實(shí)驗(yàn)結(jié)果表明，岸橋單向移動模式的求解時(shí)間一直少于雙向移動模式，在求解2個(gè)岸橋和4輛集卡處理14個(gè)任務(wù)的算例時(shí)，雙向移動模式已達(dá)到1 239s，單向移動模式僅為3.5s。加入多場景后，岸橋雙向移動模式的求解難度會呈指數(shù)暴漲，將不具備求解的可行性。在求解質(zhì)量方面，岸橋單向移動模式最優(yōu)值與雙向移動模式最優(yōu)值的平均gap為0.30%，說明將岸橋的作業(yè)模式設(shè)定為單向移動，在簡化求解難度的同時(shí)，并未影響求解質(zhì)量。

1.4.2 驗(yàn)證模型的正確性。在進(jìn)行數(shù)據(jù)實(shí)驗(yàn)前，本文需要通過簡單算例對模型的正確性進(jìn)行驗(yàn)證，數(shù)據(jù)見表2，最優(yōu)調(diào)度方案如圖2所示。

表2 模型驗(yàn)證算例數(shù)據(jù)

圖2 顯示：在場景1中，岸橋1依次處理任務(wù)1→2→4，岸橋2依次處理任務(wù)5→6→3，集卡1依次處理任務(wù)5→6→4，集卡2依次處理任務(wù)1→2→3，最優(yōu)值為392；在場景2中，岸橋1依次處理任務(wù)1→5→4→6，岸橋2依次處理任務(wù)2→3，集卡1依次處理任務(wù)1→4，集卡2依次處理任務(wù)2→5→3→6，最優(yōu)值為396。

圖2 場景1(左)與場景2(右)最優(yōu)調(diào)度方案

將場景1的最優(yōu)調(diào)度方案應(yīng)用到場景2中，得到的目標(biāo)值為438，與原最優(yōu)解差距為10.61%，表現(xiàn)較差，可見作業(yè)過程中的不確定性給設(shè)備帶來的效率變化會影響調(diào)度計(jì)劃的質(zhì)量。而本文模型計(jì)算的最優(yōu)值為403，與兩個(gè)原最優(yōu)值的差距分別為2.81%、1.77%，較好地削弱了不確定性給港口調(diào)度帶來的影響。

2 求解方法

目前粒子群算法（PSO）是求解岸橋與集卡集成調(diào)度的主流方法之一[13]，禁忌搜索算法（TS）也被較多地應(yīng)用于求解該問題[6,11]和岸橋調(diào)度問題[20-23]。其中，PSO易實(shí)現(xiàn)、收斂快，其群體優(yōu)勢使其具有較強(qiáng)的全局開發(fā)能力，但當(dāng)問題規(guī)模增大時(shí)會出現(xiàn)維數(shù)障礙，使算法早熟收斂；TS具有較強(qiáng)的局部搜索能力，但難以形成有效率的尋優(yōu)路線，全局搜索能力較弱，因此，通常利用其它算法為其生成一個(gè)靠近全局最優(yōu)的初始解以增加搜索到全局最優(yōu)的概率。

兩種算法結(jié)合可以使全局搜索能力與局部搜索能力形成互補(bǔ)，本文設(shè)計(jì)粒子群禁忌搜索混合算法（PSO+TS），利用PSO的群體優(yōu)勢全局搜索，若群體最優(yōu)值連續(xù)m次迭代不更新，則認(rèn)為PSO早熟收斂，此時(shí)依靠TS的局部搜索能力跳出，若n次迭代內(nèi)找到更優(yōu)解，則返回PSO繼續(xù)尋優(yōu)，否則結(jié)束算法?；究蚣苋鐖D3所示。

圖3 禁忌粒子群混合算法

2.1 初始解設(shè)計(jì)

PSO要求隨機(jī)生成初始解以保持粒子的分散性，而隨機(jī)初始解的質(zhì)量可能不高，高質(zhì)量的初始解可以提升算法效率。本文在保證隨機(jī)性的同時(shí)對初始解進(jìn)行優(yōu)化：

（1）通常各岸橋均分任務(wù)的方案更靠近最優(yōu)解，本文將任務(wù)隨機(jī)且均分給各岸橋。

（2）不同的任務(wù)需要被運(yùn)輸至不同的箱區(qū)，使得集卡的行駛里程不同，本文隨機(jī)分配任務(wù)給集卡并保證各集卡的行駛里程均衡。

（3）使岸橋盡可能都處于工作狀態(tài)的方案往往更優(yōu)，考慮到岸橋之間不可跨越，本文將貝位編號小的任務(wù)分配給隊(duì)尾的岸橋處理，避免由于初始堵塞造成隊(duì)尾的岸橋閑置。

（4）若兩個(gè)岸橋處理的任務(wù)在同一貝位內(nèi)，根據(jù)同一貝位任務(wù)的優(yōu)先級要求，則由隊(duì)列在前的岸橋處理優(yōu)先級較高的任務(wù)，避免岸橋間的干擾等待。

2.2 粒子群算法設(shè)計(jì)

PSO是一種模擬鳥群覓食行為的進(jìn)化算法，通過個(gè)體與群體共享最優(yōu)信息，追蹤群體最優(yōu)值和個(gè)體最優(yōu)值來更新粒子的速度和位置，不斷向最優(yōu)解靠攏，使鳥群逐漸從無序到有序地趨向最優(yōu)位置?；究蚣苋鐖D4所示。

圖4 粒子群算法

PSO的尋優(yōu)規(guī)則使粒子的運(yùn)動過程不趨向劣解，即劣解粒子不具有引導(dǎo)運(yùn)動方向的作用。本文設(shè)置不計(jì)算劣解以加快運(yùn)行速度，不值得計(jì)算的劣解有兩種：

（1）在岸橋與集卡的作業(yè)中，集卡的數(shù)量多于岸橋數(shù)量，所以若兩個(gè)岸橋的初始任務(wù)由同一集卡處理，則在初始階段會出現(xiàn)岸橋等待和集卡閑置。

（2）若兩個(gè)岸橋處理的任務(wù)位于同一貝位，則隊(duì)列在后岸橋處理高優(yōu)先級的任務(wù)會造成兩個(gè)岸橋的相互等待。

當(dāng)PSO的群體最優(yōu)值連續(xù)多次不更新時(shí)，群體中多數(shù)粒子可能靠攏到局部最優(yōu)解處，使其無力跳出，此時(shí)進(jìn)入TS。

2.3 禁忌搜索算法設(shè)計(jì)

TS通過設(shè)置禁忌表模仿人類的記憶功能，記錄的解在一定迭代次數(shù)內(nèi)不再出現(xiàn)以防止迂回搜索，從而跳出局部最優(yōu)。它從一個(gè)初始可行解出發(fā)，按照一定的規(guī)則進(jìn)行鄰域搜索?；究蚣苋鐖D5所示。

圖5 禁忌搜索算法

本文設(shè)置插入、適配、隨機(jī)三種規(guī)則進(jìn)行鄰域搜索：

（1）插入。將某一岸橋的任務(wù)隨機(jī)插入另一岸橋的作業(yè)序列中，集卡的插入規(guī)則同理。

（2）適配。岸橋與集卡的調(diào)度計(jì)劃難以相互匹配，使調(diào)度計(jì)劃質(zhì)量不高，本文在鄰域搜索時(shí)調(diào)度集卡以適配岸橋的調(diào)度計(jì)劃，或使岸橋適配集卡。

（3）隨機(jī)。隨機(jī)生成一個(gè)新的方案以保持方案的多樣性。

TS鄰域搜索時(shí)接受劣解作為當(dāng)前最優(yōu)解，如此迭代難以形成有效率的尋優(yōu)路線，若TS找到優(yōu)于PSO群體最優(yōu)值的更優(yōu)解，由于優(yōu)質(zhì)解的稀少性，TS可能陷入劣解的盲目迭代，此時(shí)則返回PSO繼續(xù)尋優(yōu)。

2.4 算法交互設(shè)計(jì)

本文建立PSO與TS的聯(lián)系，使兩種算法進(jìn)行交互。

（1）運(yùn)行PSO時(shí)，將每次迭代的最優(yōu)粒子記錄到禁忌表中，當(dāng)PSO停止時(shí)，禁忌表中記錄的解為局部最優(yōu)附近處的解，一定程度上避免了TS在局部最優(yōu)處徘徊，增強(qiáng)了TS在初始階段的局部搜索能力。

（2）PSO陷入局部最優(yōu)后，最優(yōu)粒子已失去引導(dǎo)群體尋找到更優(yōu)解的能力，并且使其他粒子向其聚攏，失去多樣性。所以當(dāng)返回PSO時(shí)，本文將搜索到的更優(yōu)解替換掉最優(yōu)粒子，并將TS禁忌表中記錄的解對PSO中的部分粒子進(jìn)行替換，使其脫離聚集狀態(tài)，增強(qiáng)粒子群的多樣性與分散性。

（3）隨著迭代次數(shù)的增大，PSO愈容易陷入局部收斂，TS也獲得了優(yōu)質(zhì)的初始解，逐漸克服了自身的障礙。本文設(shè)置算法資源逐漸向TS傾斜：當(dāng)PSO變換到TS時(shí)，將PSO的迭代停止限度逐漸賦予TS，使TS迭代更多次。

3 數(shù)據(jù)實(shí)驗(yàn)

本文根據(jù)歷史數(shù)據(jù)，假設(shè)每臺設(shè)備的效率服從均勻分布，以體現(xiàn)作業(yè)過程中的隨機(jī)不確定性，其中，岸橋移動時(shí)間服從均勻分布U[4,6]（單位：s），岸橋卸箱時(shí)間服從均勻分布U[80,120]（單位：s），集卡行駛速度服從均勻分布U[8,12]（單位：m/s）。實(shí)驗(yàn)平臺CPU為intel core i5 2.3Ghz，采用CPLEX 12.6.1求解，代碼在Visual Studio 2013的C#中實(shí)現(xiàn)。

3.1 小規(guī)模算例實(shí)驗(yàn)

在小規(guī)模算例中，設(shè)置CPLEX與PSO+TS分別求解，通過比較來驗(yàn)證算法的性能，見表3。

表3 小規(guī)模算例：CPLEX與PSO+TS對比

小規(guī)模算例結(jié)果顯示，同等數(shù)量的任務(wù)-岸橋-集卡的算例，隨著場景數(shù)量的增加，CPLEX和PSO+TS的求解時(shí)間均迅速增加，說明多場景會增加求解難度，進(jìn)一步驗(yàn)證了本文設(shè)定岸橋單向移動作業(yè)模式的必要性。

隨著算例規(guī)模增大，CPLEX求解時(shí)迅速增加，對于規(guī)模為50個(gè)場景下2個(gè)岸橋和4輛集卡處理14個(gè)任務(wù)的算例，其求解時(shí)間已達(dá)到8 535s，而PSO+TS為299s，具有時(shí)間優(yōu)勢。在求解質(zhì)量方面，PSO+TS幾乎都能找到最優(yōu)解，與CPLEX的平均gap為0.13%，可以找到滿意解。

3.2 大規(guī)模算例實(shí)驗(yàn)

CPLEX的求解已超過2h，不再適用求解大規(guī)模算例，故采用PSO+TS分別與PSO、TS進(jìn)行對比（見表4），驗(yàn)證算法的效果。

大規(guī)模算例結(jié)果顯示，PSO的求解時(shí)間具備優(yōu)勢，說明趨向群體最優(yōu)的運(yùn)動方式可以有效提升尋優(yōu)速度。但PSO與PSO+TS的平均gap為11.44%，說明算法后期粒子集中在同一區(qū)域難以跳出，造成了PSO早熟收斂。

TS與PSO+TS的平均gap為7.00%，說明其禁忌功能避免了陷入局部最優(yōu)，但尋優(yōu)質(zhì)量尚可提高，而且TS求解時(shí)間更長，說明通過接受劣解來迭代增加了尋優(yōu)時(shí)間。

表4 大規(guī)模算例：PSO+TS分別與PSO、TS對比

PSO+TS的求解質(zhì)量更優(yōu)，說明TS在全局尋優(yōu)時(shí)未能充分地搜索全局空間，使其沒有搜索到全局最優(yōu)，結(jié)合PSO的群體優(yōu)勢后，提高了求解方案落到距離全局最優(yōu)附近的概率，提升了算法的速度與求解質(zhì)量。因此，將PSO與TS進(jìn)行有效結(jié)合，可以較好地均衡局部搜索能力與全局搜索能力，優(yōu)化求解精度。

4 結(jié)語

針對岸橋與集卡在作業(yè)過程中出現(xiàn)的不確定性情況，本文建立混合整數(shù)規(guī)劃模型，使調(diào)度計(jì)劃在發(fā)生突發(fā)狀況時(shí)保持穩(wěn)健性。本文將粒子群算法與禁忌搜索算法相結(jié)合，設(shè)計(jì)粒子群禁忌搜索混合算法求解模型，通過小規(guī)模算例驗(yàn)證了該算法的求解效率，通過大規(guī)模算例證明該算法可以有效地避免陷入局部最優(yōu)，并增加了搜索到全局最優(yōu)的概率。

在未來的研究中，可以研究同時(shí)裝卸作業(yè)的岸橋與集卡的集成調(diào)度問題，也可以嘗試將場橋調(diào)度納入集裝箱卸船作業(yè)中，研究集成岸橋、集卡、場橋的調(diào)度問題。另外，隨著港口自動化程度加深，探究自動化設(shè)備在港口作業(yè)的調(diào)度問題會成為未來的重點(diǎn)。