基于運(yùn)載能力的集裝箱碼頭集卡調(diào)度優(yōu)化方法研究

孔靈睿 計(jì)明軍 關(guān)云瀟 任 剛 郭興海

(大連海事大學(xué) 交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)

0 引言

集裝箱碼頭是集裝箱運(yùn)輸?shù)年P(guān)鍵節(jié)點(diǎn),在集裝箱運(yùn)輸體系中具有重要的地位。2019年全球前十大集裝箱碼頭總吞吐量已達(dá)到2.44億TEU,相比十年前增長37.1%。集裝箱碼頭吞吐量的不斷增長,對集裝箱碼頭的作業(yè)能力提出了更高的要求。集卡作為集裝箱碼頭水平運(yùn)輸系統(tǒng)中最為重要的機(jī)械,負(fù)責(zé)碼頭前沿至堆場,以及堆場內(nèi)各箱區(qū)之間的運(yùn)輸作業(yè)任務(wù)。對集卡的作業(yè)調(diào)度進(jìn)行優(yōu)化,使其與集裝箱碼頭其他作業(yè)環(huán)節(jié)相互配合,能夠有效提高碼頭的作業(yè)效率,縮短船舶在港作業(yè)時(shí)間,提升港口的競爭力。

國內(nèi)外對于集卡調(diào)度問題的研究,主要圍繞著優(yōu)化集卡行駛路徑[1-2]、減少空駛距離[3]、縮短作業(yè)時(shí)間[4]、降低運(yùn)營成本[5-6]、減少能源消耗[7]等目標(biāo)展開。集裝箱碼頭作業(yè)系統(tǒng)由諸多相互關(guān)聯(lián)的決策過程組成[8],其中,岸橋、集卡、場橋具有很強(qiáng)的交互性,若將其中二者或三者進(jìn)行集成調(diào)度能夠進(jìn)一步提升集裝箱碼頭的裝卸作業(yè)效率。因此,部分學(xué)者將集卡調(diào)度同碼頭的其他作業(yè)環(huán)節(jié)進(jìn)行聯(lián)合優(yōu)化。如集卡與岸橋的集成調(diào)度優(yōu)化[9-11],集卡與場橋的集成調(diào)度優(yōu)化[12-13],以及岸橋-集卡-場橋三者聯(lián)合的集成調(diào)度優(yōu)化[14-17]。然而,現(xiàn)有的研究均以單位集卡重載一個(gè)集裝箱為作業(yè)單元,即僅考慮了“一車一箱”的運(yùn)輸模式,缺乏對集卡實(shí)際運(yùn)輸能力的考慮。實(shí)際上,一個(gè)集卡最多可同時(shí)運(yùn)輸兩個(gè)20 ft集裝箱或一個(gè)40 ft集裝箱。由于集卡的數(shù)量有限,且具有一定的維護(hù)成本,在集裝箱碼頭的實(shí)際作業(yè)過程中,為了充分利用集卡的運(yùn)載能力,對于20 ft集裝箱往往采用“一車兩箱”的運(yùn)輸模式,即一個(gè)集卡同時(shí)運(yùn)輸兩個(gè)20 ft集裝箱,如圖1所示。

圖1 “一車兩箱”的運(yùn)輸模式Figure 1 The transport mode of “one truck, two containers”

以進(jìn)口箱卸箱過程為例,圖3和圖4分別展示了“一車一箱”與“一車兩箱”運(yùn)輸模式下某一集卡的運(yùn)輸過程。在“一車一箱”運(yùn)輸模式下,集卡在岸邊提取一個(gè)集裝箱后,將其直接運(yùn)輸至堆場的指定位置進(jìn)行卸箱,完成卸箱后即可返回岸邊繼續(xù)提箱(將該過程稱為集卡的一次作業(yè)循環(huán));而在“一車兩箱”運(yùn)輸模式下,集卡需要在岸邊依次提取兩個(gè)20 ft集裝箱,然后分別將兩個(gè)集裝箱運(yùn)輸至堆場的指定位置等待場橋卸箱,當(dāng)集卡所載集裝箱均被場橋卸下后方可返回岸邊繼續(xù)提箱。對比圖3和圖4可知,雖然在“一車兩箱”運(yùn)輸模式下,集卡的一次作業(yè)循環(huán)相比于“一車一箱”運(yùn)輸模式下的一次作業(yè)循環(huán)行駛了更長的時(shí)間,可能還會(huì)產(chǎn)生更多在岸橋和場橋的等待時(shí)間,但完成了“一車一箱”運(yùn)輸模式下需要進(jìn)行兩次作業(yè)循環(huán)才可以完成的任務(wù)。理論上,若是能夠協(xié)調(diào)好集卡與岸橋、場橋之間的相互等待關(guān)系,以及集卡同時(shí)運(yùn)輸?shù)膬蓚€(gè)集裝箱在堆場的卸箱位置,“一車兩箱”的運(yùn)輸模式能夠極大縮短整個(gè)卸箱作業(yè)的時(shí)間。

圖3 “一車一箱”運(yùn)輸模式下集卡作業(yè)示意圖Figure 3 The transport mode of “one truck, one container”

圖4 “一車兩箱”運(yùn)輸模式下集卡作業(yè)示意圖Figure 4 The transport mode of “one truck, two containers”

在以往僅考慮“一車一箱”運(yùn)輸模式的研究中,集卡調(diào)度問題只需對集卡的任務(wù)指派以及集卡的提箱順序進(jìn)行決策。而若同時(shí)考慮“一車兩箱”的運(yùn)輸模式,集卡作業(yè)過程中除了要進(jìn)行上述決策外,還應(yīng)對集裝箱的配對問題進(jìn)行決策,即某一集卡的某一作業(yè)循環(huán)是否同時(shí)運(yùn)輸兩個(gè)集裝箱,運(yùn)輸哪兩個(gè)集裝箱,以及配對后的兩個(gè)集裝箱在堆場中的先后配送順序。此外,在碼頭的實(shí)際作業(yè)過程中,岸橋吊具的可伸縮性允許岸橋卸箱作業(yè)存在如下三種情況:卸載一個(gè)20 ft集裝箱;同時(shí)卸載兩個(gè)20 ft集裝箱;卸載一個(gè)40 ft集裝箱。基于以上分析,考慮集卡的實(shí)際運(yùn)輸能力以及岸橋的三種作業(yè)情景,進(jìn)口箱卸箱過程中集卡的作業(yè)任務(wù)與所面臨的決策包括(如圖5所示):

圖5 基于實(shí)際運(yùn)載能力的集卡作業(yè)決策Figure 5 Decisions of the truck based on actual transportation capacity

(1)對于岸橋一次同時(shí)卸載兩個(gè)20 ft集裝箱的情況,集卡在岸邊應(yīng)當(dāng)同時(shí)完成這兩個(gè)20 ft集裝箱的裝載,如圖2所示。

圖2 岸橋同時(shí)卸載兩個(gè)20 ft集裝箱Figure 2 Two 20 ft containers being loaded by a quay crane simultaneously

(2)對于岸橋卸載一個(gè)20 ft集裝箱的情況,集卡在岸橋處裝載該20 ft集裝箱后,面臨三種不同的抉擇:1)直接運(yùn)輸當(dāng)前集裝箱至堆場;2)在原岸橋繼續(xù)等待裝載第二個(gè)20 ft集裝箱;3)行駛到其他岸橋裝載第二個(gè)20 ft集裝箱。在決策過程中需要對岸橋的空閑時(shí)間、集裝箱的堆場位置、集卡的運(yùn)輸、等待時(shí)間進(jìn)行協(xié)同考慮,做出最優(yōu)的配對決策,盡可能縮短岸橋的等待時(shí)間、減少集卡的運(yùn)輸與等待時(shí)間。

(3)對于岸橋卸載一個(gè)40 ft集裝箱的情況,集卡在岸橋處裝載該箱后,應(yīng)直接運(yùn)輸至堆場。

(4)集卡在完成岸邊裝載任務(wù)后應(yīng)將集裝箱運(yùn)輸至堆場的指定卸箱位置,對于“一車兩箱”的運(yùn)輸模式,同一次運(yùn)輸中配對的兩個(gè)集裝箱可能存放于不同箱區(qū)。因此需對集裝箱的堆場位置、集卡的運(yùn)輸時(shí)間以及作業(yè)場橋的空閑時(shí)間進(jìn)行協(xié)同考慮,決策配對集裝箱在堆場的先后配送順序,以縮短集卡的運(yùn)輸時(shí)間以及集卡在堆場的等待時(shí)間。

針對上述分析可知,若在傳統(tǒng)研究中“一車一箱”運(yùn)輸模式的基礎(chǔ)上,并行考慮“一車兩箱”的運(yùn)輸模式,需要更好的協(xié)調(diào)岸橋、集卡、場橋之間的作業(yè)關(guān)系,做出最優(yōu)的集裝箱配對決策,以期能夠進(jìn)一步發(fā)揮集卡的運(yùn)載能力,提升集卡作業(yè)效率,減少船舶的在港作業(yè)時(shí)間。本文基于集卡的實(shí)際運(yùn)載能力,對集裝箱碼頭進(jìn)口箱卸箱過程中的集卡調(diào)度問題進(jìn)行研究。研究涉及20 ft與40 ft兩種不同箱型,考慮了作業(yè)過程中集卡與岸橋和場橋的相互等待時(shí)間,以卸箱作業(yè)完成時(shí)間最小為目標(biāo),對集卡指派、提箱順序、集裝箱配對以及配對集裝箱的配送順序進(jìn)行協(xié)同優(yōu)化。

本文的貢獻(xiàn)是:基于集卡的實(shí)際運(yùn)載能力,提出了一個(gè)新的科學(xué)問題,即考慮“一車兩箱”運(yùn)輸模式的集卡調(diào)度問題,并證明了該問題是 NP完全的;理論上分析了“一車兩箱”運(yùn)輸模式相比于“一車一箱”運(yùn)輸模式的優(yōu)勢以及所涉及的更多的作業(yè)決策;針對問題的特征,設(shè)計(jì)了混合整數(shù)規(guī)劃模型與多起點(diǎn)自適應(yīng)鄰域搜索求解算法,算例實(shí)驗(yàn)結(jié)果驗(yàn)證了本文所提出方法的有效性,同時(shí)也表明本文的集卡調(diào)度方案能夠充分發(fā)揮集卡運(yùn)力,減少船舶在港作業(yè)時(shí)間,為集裝箱碼頭實(shí)際運(yùn)營過程中的集卡調(diào)度決策提供有益借鑒。

1 問題描述與模型構(gòu)建

1.1 問題描述

1.1.1 船舶到港口后的卸箱過程描述

本文研究集裝箱碼頭進(jìn)口箱卸箱作業(yè)過程中的集卡調(diào)度問題。通常,當(dāng)一艘集裝箱船靠港之前,其泊位位置以及相應(yīng)作業(yè)岸橋的指派與調(diào)度計(jì)劃已知。當(dāng)船舶靠泊后,岸橋按照相應(yīng)的作業(yè)計(jì)劃進(jìn)行卸箱操作。卸箱時(shí),岸橋?qū)⒓b箱從船舶直接卸至集卡上,若此時(shí)岸橋處無集卡,則岸橋需要等待直至集卡到達(dá);若集卡先到達(dá),則集卡需在岸邊等待岸橋完成其上一個(gè)作業(yè)任務(wù)。因此,集卡的調(diào)度計(jì)劃應(yīng)當(dāng)與岸橋作業(yè)計(jì)劃相互協(xié)調(diào),以縮短岸橋與集卡的相互等待時(shí)間。當(dāng)集卡在岸邊提箱后需要將所載集裝箱運(yùn)輸至堆場指定卸箱位置,通過場橋?qū)⒓ㄉ系募b箱卸下。若集卡到達(dá)時(shí),場橋未完成上一個(gè)作業(yè)任務(wù),集卡需要進(jìn)行等待。因此,集卡的調(diào)度計(jì)劃也應(yīng)當(dāng)與場橋的作業(yè)相互協(xié)調(diào),以減少集卡在堆場的等待時(shí)間。

對于進(jìn)口集裝箱,其在船上的位置已知,岸橋卸載每個(gè)集裝箱的時(shí)間由集裝箱在船上的位置決定(越靠近海側(cè)的集裝箱卸箱時(shí)間越長,層數(shù)越低的集裝箱卸箱時(shí)間越長;在設(shè)計(jì)算例時(shí)也考慮了岸橋按照其作業(yè)順序移動(dòng)到另一個(gè)貝繼續(xù)作業(yè)的移動(dòng)時(shí)間)。每個(gè)進(jìn)口集裝箱在堆場的堆存位置已知(有關(guān)進(jìn)口箱卸箱順序以及堆場堆存位置優(yōu)化的問題可參考Zhu等[18])。進(jìn)口箱包括20 ft與40 ft兩種箱型,對于40 ft集裝箱,僅可采用“一車一箱”的運(yùn)輸模式;對于20 ft集裝箱,可選擇“一車一箱”或“一車兩箱”的運(yùn)輸模式。

1.1.2 對于岸橋同時(shí)卸載兩個(gè)20ft集裝箱的描述

本文考慮了岸橋可以一次作業(yè)兩個(gè)20 ft集裝箱的情況(受岸橋的吊具結(jié)構(gòu)與作業(yè)能力限制,同一次作業(yè)的兩個(gè)20 ft集裝箱必須在船舶同一層、同一棧、相鄰兩個(gè)貝的箱位中)。如圖6所示,較長的長方形表示40 ft集裝箱,較短的長方形表示20 ft集裝箱,灰色表示不在本港口卸載的集裝箱。長方形內(nèi)的數(shù)字為集裝箱的編號,也表示岸橋1/岸橋2的作業(yè)順序。對于岸橋1來說,集裝箱5和集裝箱6可以在同一次作業(yè)循環(huán)中卸載,集裝箱7和集裝箱8也可以在同一次作業(yè)循環(huán)中卸載。同理對于岸橋2,集裝箱1和集裝箱2、集裝箱6和集裝箱7、集裝箱9和集裝箱10也分別可以被岸橋同時(shí)卸下。

圖6 岸橋卸箱順序示意圖Figure 6 The unloading sequence of the quay crane

為了記錄可被岸橋同時(shí)卸載的集裝箱,我們定義一個(gè)集合Ω。對于20 ft集裝箱i,如果其能夠與集裝箱i+1被岸橋同時(shí)卸載,則將i加至集合Ω中。若以符號(q,i)表示岸橋q的第i個(gè)集裝箱,則對于圖6來說,Ω={(1,5),(1,7),(2,1),(2,6),(2,9)}。為了充分發(fā)揮岸橋的作業(yè)效率,本文假定對于任意的(q,i)∈Ω,集裝箱(q,i)和(q,i+1)被岸橋同時(shí)卸載。如若某集卡被分配裝載集裝箱(q,i),且(q,i)∈Ω, 則集卡必須同時(shí)裝載集裝箱(q,i)與(q,i+1),進(jìn)行“一車兩箱”的運(yùn)輸。而當(dāng)集裝箱(q,i)?Ω時(shí),如圖5所示,集卡在提取集裝箱(q,i)后,需要進(jìn)行配對決策。

1.1.3 決策內(nèi)容與決策結(jié)果

本研究所涉及的決策內(nèi)容與決策結(jié)果如圖7所示,即對集卡指派、提箱順序、集裝箱配對、配對集裝箱在堆場的配送順序四個(gè)決策進(jìn)行協(xié)同優(yōu)化,得到最優(yōu)的集卡運(yùn)輸序列,以最小化整個(gè)卸箱作業(yè)結(jié)束的時(shí)間(最后一個(gè)集裝箱被運(yùn)至堆場并完成卸箱的時(shí)間)。

圖7 研究所涉及的決策內(nèi)容與決策結(jié)果Figure 7 Decisions and consequences of the study

1.2 模型構(gòu)建

參數(shù)設(shè)置

C:待卸船進(jìn)口集裝箱集合,(q,i)∈C表示岸橋q第i次作業(yè)的集裝箱;

C20:待卸船20 ft集裝箱集合;

C40:待卸船40 ft集裝箱集合;

B:場橋數(shù)量;

Q:岸橋數(shù)量;

S:集卡數(shù)量;

δ(q.i):岸橋卸載集裝箱(q,i)所需的時(shí)間;

β:場橋作業(yè)一個(gè)集裝箱所需的時(shí)間;

:場橋從集裝箱(q,i)的堆場位置移動(dòng)至集裝箱(l,j)的堆場位置所需的時(shí)間;

:集卡從集裝箱(q,i)的岸邊位置行駛至集裝箱(l,j)的岸邊位置所需的時(shí)間(某一集裝箱的岸邊位置是指為了提取該集裝箱,集卡應(yīng)到達(dá)的位置);

:集卡從集裝箱(q,i)的堆場位置行駛至集裝箱(l,j)的岸邊位置所需的時(shí)間;

:集卡從集裝箱(q,i)的堆場位置行駛至集裝箱(l,j)的堆場位置所需的時(shí)間;

O:虛擬起始任務(wù);

O′:虛擬結(jié)束任務(wù)。

變量設(shè)置

:0-1決策變量,若集裝箱(q,i)和(l,j)由同一輛集卡運(yùn)輸,且集裝箱(q,i)為集裝箱(l,j)的緊前作業(yè)(提箱過程),則否則

:0-1決策變量,若集裝箱(q,i)和(l,j)由同一場橋作業(yè),且集裝箱(q,i)為集裝箱(l,j)的緊前作業(yè),則,否則

:0-1決策變量,若集裝箱(q,i)和(l,j)由同一輛集卡同時(shí)運(yùn)輸(互為配對集裝箱),且集卡在堆場先配送集裝箱(q,i)后配送集裝箱(l,j),那么,否則

t(q,i):岸橋開始作業(yè)集裝箱(q,i)的時(shí)間;

T(q,i):場橋開始作業(yè)集裝箱(q,i)的時(shí)間;

F:卸箱作業(yè)結(jié)束的時(shí)間。

基于上述參數(shù)與變量定義,建立混合整數(shù)規(guī)劃模型如下:

模型的目標(biāo)函數(shù)如式(1)所示,表示為最小化卸箱作業(yè)結(jié)束的時(shí)間。

式(2)定義了卸箱作業(yè)結(jié)束的時(shí)間,即變量F。

式(3)和式(4)表示任一集卡的作業(yè)任務(wù)有且僅有一個(gè)緊前任務(wù)和一個(gè)緊后任務(wù);式(5)和式(6)表示任一場橋作業(yè)任務(wù)有且僅有一個(gè)緊前任務(wù)和一個(gè)緊后任務(wù)。

式(7)～(10)為集裝箱配對決策的相關(guān)約束:式(7)表示40 ft集裝箱只能由一輛集卡單獨(dú)運(yùn)送,不可與其他集裝箱進(jìn)行配對運(yùn)輸;式(8)表示若集裝箱(q,i)和(q,i+1)由岸橋同時(shí)卸下,那么他們一定互為配對箱;式(9)表示對于任意的20 ft集裝箱,最多只能有一個(gè)20 ft集裝箱與其配對;式(10)定義了決策變量y與m的關(guān)系,表示若兩個(gè)集裝箱為同一集卡同次運(yùn)輸?shù)膬蓚€(gè)配對箱,那么這兩個(gè)集裝箱一定互為該集卡的緊前緊后作業(yè)任務(wù)。

式(11)和(12)表示岸橋按照卸箱順序進(jìn)行連續(xù)作業(yè)的時(shí)間約束;其中,約束(11)表示若集裝箱(q,i)和(q,i+1)由岸橋同時(shí)卸載,那么岸橋開始作業(yè)這兩個(gè)集裝箱的時(shí)間相同;約束(12)表示,若集裝箱(q,i)和(q,i+1)不能被岸橋同時(shí)卸載,那么岸橋開始卸載集裝箱(q,i+1)的時(shí)間要大于岸橋開始卸載集裝箱(q,i)的時(shí)間加上卸載集裝箱(q,i)所需的時(shí)間,以保證岸橋的作業(yè)順序以及岸橋作業(yè)的連續(xù)性;式(13)為場橋連續(xù)作業(yè)的時(shí)間約束。

式(14)～(20)約束了集卡在各個(gè)點(diǎn)之間(堆場-岸邊、岸邊-岸邊、岸邊-堆場、堆場-堆場)的連續(xù)運(yùn)輸時(shí)間:式(14)約束了集卡從堆場行駛至岸邊時(shí)的連續(xù)運(yùn)輸時(shí)間;式(15)約束了如下特殊情況發(fā)生時(shí)集卡從堆場行駛至岸邊的連續(xù)運(yùn)輸時(shí)間:集卡從堆場出發(fā)去岸邊提取集裝箱(l,j),其緊前作業(yè)任務(wù)為集裝箱(q,i),集裝箱(q,i)與另一個(gè)集裝箱(h,k)為配對箱且集卡在堆場運(yùn)輸時(shí)先配送集裝箱(q,i)后配送集裝箱(h,k);若式(15)成立,由于兩邊(時(shí)間)之和大于第三邊(時(shí)間),式(15)可將式(14)覆蓋,若式(15)不成立,則式(14)發(fā)揮作用;式(16)約束當(dāng)兩個(gè)緊前緊后作業(yè)的集裝箱為配對箱時(shí),集卡從岸邊到岸邊的連續(xù)運(yùn)輸時(shí)間;式(17)～(19)表示集卡從岸邊運(yùn)輸集裝箱到堆場的時(shí)間約束;其中式(17)表示當(dāng)一個(gè)集裝箱不與任何其他集裝箱配對時(shí),集卡從岸邊運(yùn)輸該集裝箱至堆場情況;式(18)約束了集裝箱(q,i)是(l,j)的緊前作業(yè)集裝箱、集裝箱(q,i)和(l,j)為配對集裝箱并且在堆場先配送集裝箱(q,i)時(shí),集卡從岸邊到堆場的連續(xù)運(yùn)輸時(shí)間;式(19)約束了集裝箱(q,i)是(l,j)的緊前作業(yè)集裝箱、集裝箱(q,i)和(l,j)為配對集裝箱并且在堆場先配送集裝箱(l,j)時(shí),集卡從岸邊到堆場的連續(xù)運(yùn)輸時(shí)間;式(20)約束了當(dāng)兩個(gè)集裝箱為配對集裝箱時(shí),集卡從堆場到堆場的連續(xù)運(yùn)輸時(shí)間。

式(21)與(22)為集卡的數(shù)量約束;式(23)和式(24)為場橋的數(shù)量約束。

式(25)定義了變量的取值范圍。

2 問題復(fù)雜性

為表明問題求解時(shí)間的復(fù)雜性,本文提出如下定理并加以證明。

定理基于運(yùn)載能力的集裝箱碼頭集卡調(diào)度問題(以下簡稱為TSBTC問題)是NP完全問題。

證明:考慮如下特殊情況:集卡數(shù)量為1,岸橋與場橋的數(shù)量為無限,那么此時(shí)集卡在岸橋和場橋處不發(fā)生等待,且問題的目標(biāo)函數(shù)值等于該集卡的運(yùn)輸時(shí)間加上場橋作業(yè)一次的時(shí)間。圖8分別展示了當(dāng)有兩個(gè)待卸集裝箱時(shí),集卡進(jìn)行“一車兩箱”運(yùn)輸和“一車一箱”運(yùn)輸時(shí)的行駛路徑。由圖8可知,對于任意一種運(yùn)輸模式,集卡均需要行駛?cè)温窂?經(jīng)過四個(gè)節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)僅經(jīng)過一次,來完成卸箱任務(wù)。若集裝箱的數(shù)量為N,無論進(jìn)行配對運(yùn)輸?shù)募b箱的數(shù)量為多少,集卡均需要行駛2N-1段路徑,經(jīng)過2N個(gè)節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)僅經(jīng)過一次,來完成卸箱任務(wù)。由此可知,在該特殊情況下TSBTC問題同旅行商問題(TSP)的性質(zhì)類似,均為包含若干節(jié)點(diǎn)且每個(gè)節(jié)點(diǎn)僅訪問一次的路徑選擇問題。而TSP已被證明是NP完全問題[19],因此可以使用規(guī)約方法將TSP規(guī)約至本文所研究的TSBTC問題,并說明TSBTC問題為NP問題,即可證明TSBTC問題是NP完全問題。

圖8 集卡進(jìn)行“一車兩箱”運(yùn)輸和“一車一箱”運(yùn)輸時(shí)的行駛路徑Figure 8 The driving path of the truck in “one truck, two containers” and “one truck, one container” transportation

首先,可以很容易證明TSBTC問題為NP問題:給定一個(gè)集卡調(diào)度方案,可以在o(N3)時(shí)間內(nèi)驗(yàn)證方案的可行性(對應(yīng)模型中o(N3)個(gè)線性約束),即可以在多項(xiàng)式時(shí)間內(nèi)驗(yàn)證解的正確性,因此TSBTC問題為NP問題。

證明TSBTC問題能夠規(guī)約至TSP,首先需要基于TSP的參數(shù)構(gòu)造TSBTC問題實(shí)例。

TSP描述如下:給定n+1個(gè)節(jié)點(diǎn),求從起始點(diǎn)出發(fā)經(jīng)過所有其他點(diǎn)(各點(diǎn)僅經(jīng)過一次)并返回起始點(diǎn)的最短回路K(假定起始點(diǎn)到其他n個(gè)節(jié)點(diǎn)的距離相等,均為k)。

構(gòu)造TSBTC問題:共有n/2個(gè)待卸集裝箱,因此會(huì)產(chǎn)生n個(gè)節(jié)點(diǎn)(n/2個(gè)節(jié)點(diǎn)為集裝箱在船上的位置,n/2個(gè)節(jié)點(diǎn)為集裝箱在堆場的卸箱位置),各個(gè)節(jié)點(diǎn)之間的運(yùn)輸時(shí)間與其所對應(yīng)的TSP中各節(jié)點(diǎn)(除去起始點(diǎn)的n個(gè)節(jié)點(diǎn))之間的距離相等;集卡數(shù)量為1,岸橋與場橋數(shù)量為無限,問題的目標(biāo)為求得最小的卸箱作業(yè)完成時(shí)間F(場橋作業(yè)一個(gè)集裝箱的時(shí)間用β表示)。

在TSBTC問題的解中,集卡的行駛路徑可以看成是一個(gè)經(jīng)過n個(gè)節(jié)點(diǎn)的不閉合的哈密頓路徑,路徑的長度(該條路徑的運(yùn)輸時(shí)間/集卡的運(yùn)輸時(shí)間)即為F-β;為了同起始點(diǎn)形成閉合的回路,還需連接哈密頓路徑的兩個(gè)端點(diǎn)同起始點(diǎn)的兩條線段;由于假定起始點(diǎn)到任意其他n個(gè)節(jié)點(diǎn)的距離均為k,所以形成的閉合回路的長度為F-β+2×k。因此,若TSBTC所求得的最小卸箱作業(yè)完成時(shí)間為F,那么可說明TSP中存在總長度為F-β+2×k的回路。

反之,若TSP的最短回路為K,那么說明在TSBTC問題中,集卡的運(yùn)輸任務(wù)可以在K-2×k的時(shí)間內(nèi)完成,即卸箱作業(yè)可以在K-2×k+β時(shí)間內(nèi)完成。

綜上,TSP可以規(guī)約至TSBTC問題,又因TSBTC問題為NP問題,則可說明TSBTC問題是NP完全的。因此不存在有效的多項(xiàng)式算法可以對TSBTC問題進(jìn)行求解,除非P=NP。因而,本文針對問題的特點(diǎn),設(shè)計(jì)了啟發(fā)式算法進(jìn)行求解。

3 算法設(shè)計(jì)

3.1 基本思想

本文證明了基于運(yùn)載能力的集卡調(diào)度問題是NP完全問題,對于實(shí)際規(guī)模的算例,無法通過直接求解上述模型得到滿意解。因此針對問題的特點(diǎn),設(shè)計(jì)了多起點(diǎn)自適應(yīng)鄰域搜索算法(簡稱MS-ANS算法)對問題進(jìn)行求解。MSANS算法流程如圖9所示:(1)算法以多個(gè)初始可行解為起點(diǎn)進(jìn)行搜索以保證解的多樣性,避免過早收斂。為每個(gè)初始解賦予相同的初始權(quán)重,在每次迭代的過程中依據(jù)每個(gè)解的權(quán)重,使用輪盤賭選擇機(jī)制選擇一個(gè)解,對該解進(jìn)行鄰域搜索;(2)針對解的特點(diǎn)設(shè)計(jì)了多種鄰域動(dòng)作并賦予相同的初始權(quán)重,在每次進(jìn)行鄰域搜索之前,需要根據(jù)各個(gè)鄰域動(dòng)作的權(quán)重運(yùn)用輪盤賭選擇機(jī)制選擇一個(gè)鄰域動(dòng)作,再對當(dāng)前解進(jìn)行該鄰域動(dòng)作下的鄰域搜索;(3)搜索結(jié)束后需根據(jù)新解的質(zhì)量對當(dāng)前所使用的鄰域動(dòng)作的權(quán)重以及相應(yīng)解的權(quán)重進(jìn)行更新,然后進(jìn)行下一次迭代直至滿足算法的終止準(zhǔn)則。在迭代的過程中,為了進(jìn)一步避免解的過早收斂,陷入局部最優(yōu),采用了模擬退火算法中的Metropolis準(zhǔn)則作為鄰域搜索所產(chǎn)生的新解的接受準(zhǔn)則:若新解優(yōu)于當(dāng)前解,則接受新解作為當(dāng)前解,否則以一定的概率接受新解作為當(dāng)前解。

圖9 MS-ANS算法流程圖Figure 9 The framework of MS-ANS algorithm

3.2 解的編碼與解碼

本文采用三層編碼的方式來表示一個(gè)解的結(jié)構(gòu)。如圖10所示,編碼的第一層表示為所有集裝箱的編號;編碼的第二層為集卡編號;編碼的第三層表示集裝箱的配對情況,其中0表示所對應(yīng)第一層編碼的集裝箱不與其緊后集裝箱配對,1表示與緊后集裝箱配對且在堆場先配送其所對應(yīng)第一層編碼的集裝箱,2表示與緊后集裝箱配對且在堆場先配送緊后集裝箱。

編碼的前兩層決定了集卡的指派結(jié)果以及提箱順序。圖10中的編碼表示:共有9個(gè)待卸集裝箱,集裝箱(1,3)、(1,5)和(2,6)由集卡1運(yùn)輸,集裝箱(1,1)、(1,2)和(2,7)由集卡2運(yùn)輸,集裝箱(1,4)、(2,8)和(2,9)由集卡3運(yùn)輸,集卡提箱順序即為編碼第一層所表示的集裝箱從左到右排列的順序。編碼的第三層決定了集裝箱的配對結(jié)果以及配對集裝箱在堆場的先后配送順序。如圖10所示,集裝箱(1,1)所對應(yīng)的編碼第三層位置的數(shù)字為1,則表示集裝箱(1,1)與其緊后集裝箱,即集裝箱(1,2)進(jìn)行了配對,且集卡在堆場先配送集裝箱(1,1);集裝箱(1,3)所對應(yīng)的編碼第三層位置的數(shù)字為2,則表示集裝箱(1,3)與其緊后集裝箱,即集裝箱(1,5)進(jìn)行了配對,且集卡在堆場先配送集裝箱(1,5)。如上規(guī)則,圖10中編碼可以解碼成如圖11所示的解。

圖10 編碼結(jié)構(gòu)示意圖Figure 10 The structure of a code

圖11 圖10中編碼所對應(yīng)的解Figure 11 The solution related to the code in Figure 10

在集卡到達(dá)堆場指定位置后,按照集卡到達(dá)的先后順序由相應(yīng)最近的場橋?yàn)榧ㄐ断?。因此?dāng)集卡的指派、集卡提箱順序、集裝箱配對結(jié)果與配對集裝箱在堆場的配送順序確定后,場橋的作業(yè)順序也隨之確定。

為了保證解的可行性,即為了保證每個(gè)解均符合模型的約束條件,解的編碼需要滿足如下規(guī)則:

① 第一層編碼必須包含所有不重復(fù)的集裝箱編號,即保證每個(gè)集裝箱均被運(yùn)輸且僅被運(yùn)輸一次;

② 若某一集裝箱與另一集裝箱被岸橋同時(shí)卸下,那么它們一定為某一集卡的緊前緊后作業(yè)任務(wù);

③ 若某一集裝箱與另一集裝箱被岸橋同時(shí)卸下,那么它們必須配對;

④ 必須保證岸橋的作業(yè)順序:若集裝箱(1,4)和(1,5)由同一集卡運(yùn)輸,那么集卡不可以先提集裝箱(1,5),因?yàn)榇藭r(shí)集裝箱(1,4)還沒有被岸橋卸下,不可先卸載集裝箱(1,5);

⑤ 若某一集裝箱為40 ft集裝箱,則其不能與任何集裝箱進(jìn)行配對,如圖10,若集裝箱(2,8)為40 ft集裝箱,那么集裝箱(2,8)所對應(yīng)編碼第三層位置的數(shù)字必須為0,集裝箱(1,4)所對應(yīng)的編碼第三層位置的數(shù)字也必須為0;

⑥ 若某一集裝箱已與另一集裝箱配對,那么它不能再與任何其他集裝箱進(jìn)行配對,如圖10,集裝箱(1,1)已與集裝箱(1,2)進(jìn)行了配對,那么集裝箱(1,2)所對應(yīng)編碼第三層位置的數(shù)字必須為0。

3.3 鄰域動(dòng)作

針對解的編碼結(jié)構(gòu),設(shè)計(jì)了如下三種鄰域動(dòng)作:

(1) 交換編碼第一層的兩個(gè)集裝箱編號的位置

交換編碼第一層的兩個(gè)集裝箱編號的位置能夠調(diào)整集卡的指派結(jié)果以及提箱順序。如若交換圖10中編碼第一層集裝箱(2,7)和集裝箱(2,8)的位置,那么集卡2和集卡3的作業(yè)序列變?yōu)槿鐖D12所示。

圖12 交換編碼第一層兩個(gè)集裝箱編號的位置所得到的新解Figure 12 The new solution obtained by exchanging two numbers in the first tier of the code

理論上,若有N個(gè)待卸集裝箱,那么最多可以產(chǎn)生種交換結(jié)果,但為了滿足3.2中所描述的條件②與④,大部分交換均不可行。因此僅需評估滿足條件②④的可行交換所產(chǎn)生的解的目標(biāo)函數(shù)值(每次交換后須對解編碼的第三層進(jìn)行修正以滿足條件③⑤⑥,再得到目標(biāo)函數(shù)值),選取其中最優(yōu)的解作為此次鄰域搜索所得到的新解。

(2) 變換編碼第二層的一個(gè)集卡編號

變換編碼第二層的一個(gè)集卡編號同樣也能夠調(diào)整集卡的指派結(jié)果以及提箱順序。如把圖10編碼第二層第6個(gè)位置的集卡編號由1變?yōu)?,那么相當(dāng)于將集裝箱(2,6)從原本集卡1的運(yùn)輸序列中刪去并插入集卡2運(yùn)輸序列的指定位置,使得集卡2的作業(yè)序列變?yōu)槿鐖D13所示。

圖13 變換編碼第二層的集卡編號所得到的新解Figure 13 The new solution obtained by changing the number in the second tier

假設(shè)集卡數(shù)量為S,那么第二層任一位置的集卡編號可有S-1種變換可能(除去原本的編號)。因此,若有N個(gè)集裝箱,那么最多可以產(chǎn)生N×(S-1)種變換結(jié)果。為了滿足3.2中所描述的條件④,大部分變換均不可行,因此僅需評估滿足條件④的可行變換所產(chǎn)生的解的目標(biāo)函數(shù)值(每次變換后須先對解編碼的第二層進(jìn)行修正以滿足條件②,再對解編碼的第三層進(jìn)行修正以滿足條件③⑤⑥,最終得到目標(biāo)函數(shù)值),選取其中最優(yōu)的解作為此次鄰域搜索所得到的新解。

(3) 變換編碼第三層的一個(gè)數(shù)值

變換編碼第三層的一個(gè)數(shù)值可以改變集裝箱的配對結(jié)果,若將圖10中編碼第三層第一個(gè)位置的數(shù)值變?yōu)?,那么集裝箱(1,1)、(1,2)將先后由集卡2分兩次進(jìn)行運(yùn)輸,若將第三層第一個(gè)位置的數(shù)值變?yōu)?,那么集卡2的作業(yè)序列變?yōu)槿鐖D14所示。

圖14 變換編碼第三層的一個(gè)數(shù)值所得到的新解Figure 14 The new solution obtained by changing the number in the third tier

對于N個(gè)集裝箱,共可能產(chǎn)生2N種變換結(jié)果(由于可變換數(shù)字為0、1或2,且不能變換為其原本的數(shù)值)。僅需對滿足條件條件③⑤的可行變換進(jìn)行評估(每次變換后須對解編碼的第三層進(jìn)行修正以滿足條件⑥,再得到目標(biāo)函數(shù)值),選取其中最優(yōu)的解作為此次鄰域搜索所得到的新解。

為了加快求解速度,在進(jìn)行以上任意一種鄰域動(dòng)作下的鄰域搜索過程中,若某一次可行交換/變換所得到解的目標(biāo)函數(shù)值優(yōu)于當(dāng)前解的目標(biāo)函數(shù)值,則鄰域搜索停止,并將該交換/變換所得到的解作為鄰域搜索所得到的新解。

3.4 解的接受準(zhǔn)則

在鄰域搜索得到一個(gè)新解后,根據(jù)模擬退火算法中的Metropolis準(zhǔn)則來判斷是否接受新解xnew替換當(dāng)前解xcurrent,用f(xnew)表示新解的目標(biāo)函數(shù)值,f(xcurrent)表示當(dāng)前解的目標(biāo)函數(shù)值,那么接受新解xnew的概率可表示為:

Titer為第iter次迭代時(shí)的溫度值,Titer值隨著迭代次數(shù)的增加越來越低,可以保證接受劣解的概率隨著迭代次數(shù)的增加而下降。溫度值下降的函數(shù)表示為:

T0為算法的初始溫度,本文設(shè)置為T0=0.05×f(xinitial),f(xinitial)為初始可行解的平均目標(biāo)函數(shù)值;α為0-1之間的小數(shù),用來控制溫度下降的速度。

3.5 權(quán)重更新

當(dāng)鄰域搜索得到一個(gè)新解后,需要根據(jù)新解的好壞,對當(dāng)前解的權(quán)重以及當(dāng)前所使用的鄰域動(dòng)作的權(quán)重進(jìn)行更新。

式(28)為權(quán)重更新公式,f(xbest)為當(dāng)前所求得的最優(yōu)解的目標(biāo)函數(shù)值,μ為0-1之間的小數(shù),ω表示對新解的評估值,ω1＞ω2＞ω3＞0。式(28)可以保證新解越好,當(dāng)前解的權(quán)重值以及當(dāng)前所使用鄰域動(dòng)作的權(quán)重值就越高。本文將所有的初始權(quán)重值設(shè)為1,ω1為1.2,ω2為1.1,ω3為0.9。

3.6 終止規(guī)則

設(shè)置算法的終止規(guī)則為:總迭代次數(shù)到達(dá)指定值,算法終止。

4 實(shí)驗(yàn)分析

本節(jié)以待卸載集裝箱的數(shù)量為基礎(chǔ),設(shè)置不同規(guī)模的算例實(shí)驗(yàn),對MS-ANS算法的有效性以及本文的研究意義進(jìn)行驗(yàn)證。算例設(shè)置如下:20 ft集裝箱數(shù)量與40 ft集裝箱數(shù)量之比設(shè)定為4∶1;隨機(jī)生成集裝箱在船上的位置,每個(gè)集裝箱的卸箱時(shí)間與其在船上的位置有關(guān),取值范圍在1.5 min～2.5 min之間;定義岸橋的作業(yè)順序以一個(gè)偶數(shù)貝為單位,從陸側(cè)到海側(cè)、由上到下進(jìn)行卸箱,卸完一個(gè)偶數(shù)貝的集裝箱后再移動(dòng)到下一個(gè)偶數(shù)貝進(jìn)行卸箱;定義岸橋數(shù)量為2,盡量保證岸橋的作業(yè)任務(wù)量均衡;若兩個(gè)集裝箱屬于同一偶數(shù)貝且位于同一層同一棧,那么定義這兩個(gè)集裝箱被同時(shí)卸下;設(shè)置場橋數(shù)量為4,在一定范圍內(nèi)隨機(jī)生成每個(gè)集裝箱的堆場位置;定義場橋作業(yè)一個(gè)集裝箱的時(shí)間為1.5 min;定義集卡/場橋在任意兩點(diǎn)之間的運(yùn)輸/移動(dòng)時(shí)間由兩點(diǎn)之間的距離決定。

實(shí)驗(yàn)運(yùn)行在1.8 GHz Intel Core i5-8265M CPU和8GB內(nèi)存的計(jì)算機(jī)上;所有求解方式均通過Visual Studio 2017 中的C++語言進(jìn)行編碼并加以實(shí)現(xiàn),所調(diào)用規(guī)劃求解器的版本為Gurobi8.1.0;設(shè)置MS-ANS算法初始可行解的個(gè)數(shù)為20,算法執(zhí)行1000代停止;對于每個(gè)算例,MS-ANS算法運(yùn)行10次取平均值;Gurobi設(shè)置為最多運(yùn)行2小時(shí)停止并輸出當(dāng)前所求得的最優(yōu)解。

4.1 算法參數(shù)值確定

為更好的應(yīng)用MS-ANS算法進(jìn)行求解,首先需要確定合理的算法參數(shù)值,包括Metropolis準(zhǔn)則中參數(shù)α的值,以及權(quán)重更新參數(shù)μ的值。

為確定參數(shù)α的值,將參數(shù)μ的值固定(μ=0.9)并將參數(shù)α的值設(shè)置為0.80、0.85、0.90、0.95、0.99,分別對同一算例(集裝箱數(shù)量為50,集卡數(shù)量為4)進(jìn)行求解?；讦恋拿總€(gè)取值,算法運(yùn)行10次取平均值,平均目標(biāo)函數(shù)值隨迭代次數(shù)的變化如圖15(a)所示。由圖15(a)可知,當(dāng)參數(shù)α的值為0.99時(shí),算法的收斂性最差。分析原因如下:若α取值較大,在執(zhí)行MS-ANS算法中的Metropolis準(zhǔn)則時(shí),溫度下降較慢,鄰域搜索的過程中接受劣解的可能性更大,導(dǎo)致算法不易收斂,并且最終得到的解較差;而參數(shù)α其他的4個(gè)取值均可以使算法在1000代以內(nèi)收斂,驗(yàn)證了算法的收斂性;此外,當(dāng)α取值越小時(shí),算法的收斂速度越快,但可能使得算法過早收斂至較差的解;在5個(gè)取值中,當(dāng)α取值為0.90時(shí),盡管收斂速度不是最快,但可以使算法收斂至更優(yōu)的解,因此,在后續(xù)的實(shí)驗(yàn)中,將α的取值設(shè)置為0.90。

同理,為確定參數(shù)μ的取值,將參數(shù)α的值固定(設(shè)置α=0.90),將參數(shù)μ的值設(shè)置為0.8、0.85、0.9、0.95、1.0,分別對同一算例進(jìn)行求解?；讦痰拿總€(gè)取值,MS-ANS算法運(yùn)行10次取平均值,平均目標(biāo)函數(shù)值隨迭代次數(shù)的變化如圖15(b)所示。由圖15(b)可知,以上參數(shù)μ的5個(gè)取值均可使算法在1000代以內(nèi)收斂;其中,當(dāng)參數(shù)μ取值為0.95時(shí),算法的收斂速度較快,且得到的目標(biāo)函數(shù)值最小,因此在后續(xù)的計(jì)算中將參數(shù)μ的取值設(shè)定為0.95;當(dāng)μ取值為1時(shí),算法的收斂速度較慢,最終得到的解也劣于其他方案,一定程度上表明了MS-ANS算法中加入自適應(yīng)因素的作用。

圖15 不同參數(shù)下的算法迭代圖Figure 15 Algorithm iteration graph with different parameters

此外,本文算法為基于多起點(diǎn)的自適應(yīng)鄰域搜索算法,為驗(yàn)證設(shè)置多起點(diǎn)(初始可行解)的必要性以及確定合理的起點(diǎn)個(gè)數(shù),將初始可行解的個(gè)數(shù)分別設(shè)置為1、10、20、30和40?；诿恳粋€(gè)方案,MS-ANS算法運(yùn)行10次取平均值,平均目標(biāo)函數(shù)值隨迭代次數(shù)的變化如圖16所示。

圖16 初始可行解(起點(diǎn))的個(gè)數(shù)對算法收斂結(jié)果的影響Figure 16 The effect of the number of initial solutions on the convergence of the algorithm

由圖16可知,對于不同的初始解的個(gè)數(shù),算法均會(huì)在1000代以內(nèi)收斂;當(dāng)初始可行解個(gè)數(shù)為1時(shí),算法在450代左右收斂,但最終所得結(jié)果最差,驗(yàn)證了算法設(shè)置多起點(diǎn)的必要性;當(dāng)初始可行解個(gè)數(shù)為20、30或40時(shí),算法均會(huì)收斂至較優(yōu)的值,因此可設(shè)置MS-ANS算法的初始可行解個(gè)數(shù)為20。

4.2 算法有效性驗(yàn)證

基于集裝箱的數(shù)量N以及集卡的數(shù)量S,選取了16個(gè)小規(guī)模算例,分別使用規(guī)劃求解器Gurobi和MS-ANS算法進(jìn)行求解,對算法的有效性進(jìn)行驗(yàn)證。求解結(jié)果如表1所示,其中,

表1的實(shí)驗(yàn)結(jié)果表明,隨著問題規(guī)模變大,Gurobi求解時(shí)間明顯增加,當(dāng)集裝箱數(shù)量達(dá)到20及以上時(shí),Gurobi無法在2小時(shí)內(nèi)求得最優(yōu)解;對于算例13、14,Gurobi無法在2小時(shí)內(nèi)獲得問題的可行解。而MS-ANS算法對于以上算例均能在2 s內(nèi)求得近優(yōu)解,平均求解時(shí)間為0.81 s;且算法求得的近優(yōu)解與Gurobi所求精確解相差較小,平均相差0.7%,初步驗(yàn)證了MS-ANS算法的求解質(zhì)量與求解效率。

表1 Gurobi與MS-ANS算法求解結(jié)果對比Table 1 Comparison of results obtained by Gurobi and MS-ANS algorithm

4.3 方案對比分析

將允許“一車兩箱”運(yùn)輸模式的集卡調(diào)度方案同僅允許“一車一箱”運(yùn)輸模式的集卡調(diào)度方案進(jìn)行對比,驗(yàn)證本文所提出的集卡調(diào)度方案的有效性。為得到僅允許“一車一箱”運(yùn)輸模式的集卡調(diào)度方案,對MS-ANS算法進(jìn)行修改,使得算法中每個(gè)初始解編碼第三層的數(shù)值都為0;此外,在進(jìn)行鄰域搜索時(shí)僅可選擇前兩個(gè)鄰域動(dòng)作,不可選擇第三個(gè)鄰域動(dòng)作,可以保證集卡一次僅運(yùn)輸一個(gè)集裝箱。將修改后的MSANS算法稱為MS-ANS-Ⅰ算法,用來得到僅允許“一車一箱”運(yùn)輸模式的集卡調(diào)度方案。

選取了20個(gè)中等規(guī)模和大規(guī)模的算例,分別使用MSANS-Ⅰ算法和MS-ANS算法進(jìn)行求解,對于每個(gè)算例算法運(yùn)行10次取平均值。求解結(jié)果如表2所示,其中,由于運(yùn)行10次取平均值可能會(huì)使得平均集裝箱配對數(shù)量為小數(shù),表中“配對數(shù)量”列所展示的為平均集裝箱配對數(shù)量向下取整的值。

表2 MS-ANS-I算法與 MS-ANS算法求解結(jié)果對比Table 2 Comparison of results obtained by MS-ANS-I and MS-ANS algorithm

由表2中結(jié)果可知,在不同數(shù)量集裝箱以及不同數(shù)量集卡的作業(yè)條件下,允許“一車兩箱”運(yùn)輸模式的集卡調(diào)度方案均能夠大幅度降低進(jìn)口箱卸箱作業(yè)的完成時(shí)間,相比于僅允許“一車一箱”運(yùn)輸模式下的集卡調(diào)度方案平均減少了23.5%。觀察表2中“配對數(shù)量”和“Gap1”列可以發(fā)現(xiàn),當(dāng)集裝箱數(shù)量相同時(shí),集卡數(shù)量越少,就越傾向于進(jìn)行配對運(yùn)輸,兩個(gè)方案的卸箱作業(yè)完成時(shí)間的差值也越大。這說明集卡數(shù)量越有限,進(jìn)行“一車兩箱”的運(yùn)輸就越有優(yōu)勢。

圖17與18具體展示了集裝箱數(shù)量為50,集卡數(shù)量為6的算例某一次的求解結(jié)果。圖中矩形左邊所對應(yīng)的橫軸時(shí)刻為相應(yīng)集卡在岸邊提取矩形中集裝箱的時(shí)間,矩形右邊所對應(yīng)的橫軸時(shí)刻為集卡將矩形中集裝箱送至堆場后場橋開始卸箱的時(shí)間,灰色部分表示集卡在一個(gè)時(shí)段內(nèi)同時(shí)運(yùn)輸兩個(gè)集裝箱。例如圖17中集卡1的第一個(gè)矩形表示,集卡1在岸邊同時(shí)提取了集裝箱(1,3)和集裝箱(1,4)(集裝箱(1,3)和(1,4)被岸橋同時(shí)卸下),且在堆場先配送集裝箱(1,3)再配送集裝箱(1,4);集卡1的第三個(gè)矩形表示,集卡1首先在岸邊提取了集裝箱(1,10),然后行駛至另一個(gè)岸橋裝載了集裝箱(2,14)再返回堆場,在堆場先配送集裝箱(1,10)再配送集裝箱(2,14)。對比圖17和圖18可知,允許“一車兩箱”運(yùn)輸模式下的集卡調(diào)度方案充分利用了集卡的運(yùn)輸能力,能夠減少集卡的空駛時(shí)間,縮短船舶卸箱作業(yè)的完成時(shí)間。

圖17 允許“一車兩箱”運(yùn)輸模式的集卡調(diào)度方案Figure 17 The truck schedule under the transport mode of “one truck, two containers”

圖18 僅允許“一車一箱”運(yùn)輸模式的集卡調(diào)度方案Figure 18 The truck schedule under the transport mode of “one truck, one container”

此外,對于表2中等規(guī)模到大規(guī)模的所有算例,MS-ANS算法均能在400 s內(nèi)求得近優(yōu)解,平均求解時(shí)間為134.9 s,進(jìn)一步驗(yàn)證了MS-ANS算法的求解效率。

4.4 靈敏度分析

集卡在岸邊的等待時(shí)間以及集卡在堆場的運(yùn)輸時(shí)間,均有可能成為影響集裝箱配對決策的重要因素。其中,岸橋的數(shù)量是影響集卡在岸邊等待時(shí)間的主要因素,集裝箱在堆場的積載位置是影響集卡在堆場運(yùn)輸時(shí)間的主要因素。因此,在本部分對岸橋的數(shù)量以及集裝箱在堆場的分布情況進(jìn)行靈敏度分析,討論不同作業(yè)條件對于集卡調(diào)度方案的影響。為了描述集裝箱在堆場的分布情況,引入分散度(η)的概念,來表示集裝箱在堆場的分散程度。η的值越高,表示集裝箱在堆場越分散;η的值越低,表示集裝箱在堆場越集中。分散度η的計(jì)算公式如下:

式(29)中C為待卸集裝箱集合,N為集裝箱的總數(shù)量,為兩個(gè)集裝箱堆場位置之間的距離 (m)。

算例設(shè)置如下:設(shè)置集裝箱數(shù)量為100,集卡數(shù)量為6;岸橋的數(shù)量分別設(shè)置為1、2、3、4、5;η的取值分別設(shè)置為20、40、60、80。對于不同岸橋數(shù)量和η值的組合共生成20個(gè)算例,每個(gè)算例分別使用MS-ANS算法和MS-ANS-Ⅰ算法進(jìn)行求解。算法運(yùn)行10次取平均值,求解結(jié)果如圖19所示,其中,

圖19(a)(b)(c)(d)結(jié)果顯示,對于兩種運(yùn)輸方案均存在如下情況:當(dāng)岸橋數(shù)量越多,卸箱作業(yè)完成時(shí)間(目標(biāo)函數(shù)值)越小;當(dāng)集裝箱在堆場的分布越集中,卸箱作業(yè)完成時(shí)間越小。分析原因如下:當(dāng)岸橋數(shù)量越多時(shí),集卡在岸邊的等待時(shí)間越短,當(dāng)集裝箱分布越集中,集卡在堆場的運(yùn)輸時(shí)間越短,最終使得總卸箱時(shí)間越小,符合碼頭實(shí)際運(yùn)營情況,驗(yàn)證了算法的穩(wěn)定性。

圖19 岸橋數(shù)量和集裝箱堆場分布對于集卡調(diào)度方案的影響Figure 19 The impact of the number of quay cranes and the container distribution at the yard on the truck scheduling plan

此外,觀察圖19可知,對于η的所有取值,均存在如下情況:岸橋數(shù)量越多,兩種運(yùn)輸方案所對應(yīng)的目標(biāo)函數(shù)值相差(Gap2值)越大。 這是由于當(dāng)集卡在岸邊裝載一個(gè)20 ft集裝箱后,若是選擇繼續(xù)裝箱進(jìn)行配對運(yùn)輸,那么岸橋數(shù)量越多時(shí),集卡需要等待裝載第二個(gè)集裝箱的時(shí)間可能越短,因此越有利于“一車兩箱”的運(yùn)輸;此外,當(dāng)η的取值越小時(shí),即當(dāng)集裝箱在堆場分布越集中時(shí),兩種運(yùn)輸方案所對應(yīng)的目標(biāo)函數(shù)值相差越大。這是由于集裝箱在堆場的位置越集中,兩個(gè)有可能進(jìn)行配對的集裝箱在堆場的位置就越接近,因此,集卡進(jìn)行“一車兩箱”的運(yùn)輸時(shí)在堆場的送箱時(shí)間就越短,越有利于進(jìn)行“一車兩箱”的運(yùn)輸。

由靈敏度分析實(shí)驗(yàn)可知,岸橋數(shù)量與集裝箱在堆場的分布情況均會(huì)對集卡的調(diào)度結(jié)果產(chǎn)生影響。當(dāng)岸橋數(shù)量越多,且集裝箱在堆場分布越集中時(shí),越有利于集卡進(jìn)行“一車兩箱”的運(yùn)輸。允許“一車兩箱”運(yùn)輸模式的集卡調(diào)度方案相比于僅允許“一車一箱”運(yùn)輸模式的集卡調(diào)度方案,卸箱作業(yè)完成時(shí)間縮短了20%左右。

5 結(jié)論

本文考慮集卡對于20 ft集裝箱和40 ft集裝箱的實(shí)際運(yùn)載能力以及岸橋的多種作業(yè)模式,以進(jìn)口箱卸箱作業(yè)完成時(shí)間最小為目標(biāo)構(gòu)建混合整數(shù)規(guī)劃模型,對集卡指派、集卡提箱順序、集裝箱配對、配對集裝箱的堆場配送順序進(jìn)行協(xié)同優(yōu)化。隨后,證明了本文所研究的考慮運(yùn)載能力的集卡調(diào)度問題是NP完全問題。為求解實(shí)際規(guī)模的問題,設(shè)計(jì)了多起點(diǎn)自適應(yīng)鄰域搜索算法進(jìn)行求解,并通過不同規(guī)模的算例實(shí)驗(yàn)驗(yàn)證了啟發(fā)式算法的求解質(zhì)量與求解效率。最終研究結(jié)果表明,在傳統(tǒng)研究中“一車一箱”運(yùn)輸模式的基礎(chǔ)上同時(shí)考慮“一車兩箱”的運(yùn)輸,能夠進(jìn)一步提高集卡作業(yè)效率,縮短船舶在港作業(yè)時(shí)間。

本文的研究成果可為集裝箱碼頭實(shí)際運(yùn)營過程中的集卡調(diào)度決策提供理論支撐,能夠充分利用集卡的運(yùn)輸能力,提高集卡的作業(yè)效率,最終達(dá)到縮短船舶的在港作業(yè)時(shí)間的目的。目前,為了提高碼頭的裝卸作業(yè)效率,已有很多集裝箱碼頭實(shí)現(xiàn)了同裝同卸的作業(yè)工藝,因此今后的研究有必要同時(shí)考慮裝船和卸船的過程,對集裝箱碼頭裝船過程與卸船過程中的集卡調(diào)度問題進(jìn)行聯(lián)合優(yōu)化。此外,隨著自動(dòng)化碼頭的發(fā)展,水平運(yùn)輸設(shè)備AGV受到了廣泛的關(guān)注。因此,今后可針對自動(dòng)化碼頭的裝卸工藝,對多載AGV的調(diào)度優(yōu)化進(jìn)行討論和研究。