范厚明， 郭振峰， 李 陽

(1． 大連海事大學(xué) 交通運輸工程學(xué)院， 遼寧 大連 116026; 2． 大連海事大學(xué) 戰(zhàn)略管理與系統(tǒng)規(guī)劃研究所， 遼寧 大連 116026)

國際貿(mào)易量的快速增長和集裝箱船舶的大型化趨勢，對集裝箱碼頭的集港效率和服務(wù)能力提出了更高的要求.一方面，大型集裝箱船掛靠的碼頭作業(yè)量和作業(yè)強度增大，另一方面，大量送箱集卡高峰時間集中在集裝箱碼頭閘口及堆場排隊等待作業(yè)，消耗了大量的能源，排放了大量的CO2及污染氣體，迫切需要應(yīng)對和解決.服務(wù)于集港作業(yè)的送箱集卡調(diào)度一直是集裝箱碼頭集港作業(yè)流程的關(guān)鍵環(huán)節(jié)，合理優(yōu)化送箱集卡調(diào)度方案對提高車輛資源配置效率、節(jié)約能耗、減少碳排放等有直接的影響.目前有關(guān)集卡調(diào)度的研究多集中于港口碼頭內(nèi)集卡的研究，對港外集卡進港提送箱作業(yè)的相關(guān)研究較少.相對于港口碼頭內(nèi)集卡而言，外集卡服務(wù)多個碼頭且運輸距離更遠，碼頭調(diào)度方案對其等待時間的影響更大，同時由于外集卡資源數(shù)量也同樣有限，其等待時間過長勢必將降低集卡整體周轉(zhuǎn)效率.由于大型集裝箱船舶對掛靠港口的停泊時間有嚴格要求，碼頭集港時間較短，且集港量大；同時集裝箱碼頭往往服務(wù)的航線多、掛靠的船舶多，使得碼頭作業(yè)高峰期有大量集卡在同一時段到達港口進行操作，容易使碼頭閘口、堆場和作業(yè)線路的內(nèi)外集卡產(chǎn)生排隊、擁堵等諸多問題.這一方面是對碼頭及堆場核心資源的浪費，另一方面也增加了集卡在等待過程中的能耗及CO2排放，提高了運營成本.針對這些問題，一些港口從建立碼頭預(yù)約機制著手，嘗試使送箱集卡在可控的規(guī)定預(yù)約時段內(nèi)到港，以緩解作業(yè)高峰時段碼頭集卡的擁堵問題，降低堆場碼頭作業(yè)能耗，減少其總碳排放量，提高碼頭的服務(wù)效率和質(zhì)量.

從1999年加拿大溫哥華首先實施預(yù)約集港以來，長灘、洛杉磯、新加坡和天津等港口引入了集卡預(yù)約系統(tǒng).一些學(xué)者針對預(yù)約集港及預(yù)約機制下送箱集卡調(diào)度進行了研究.曾慶成等[1]利用Baskett-Chandy-Muntz-Palacios排隊網(wǎng)絡(luò)優(yōu)化了每個時段的預(yù)約份額，其可以有效地減少集卡在碼頭的周轉(zhuǎn)時間，較好地處理到達過程不平穩(wěn)的排隊問題.Namboothiria等[2]以降低車隊運輸成本為目標構(gòu)建了集卡調(diào)度模型，研究集卡預(yù)約系統(tǒng)對提高周轉(zhuǎn)效率的影響.蔣美仙等[3]提出了基于Poisson過程的港口碼頭集卡預(yù)約調(diào)度模型，根據(jù)到港船舶船期表和預(yù)出口集裝箱數(shù)目,模型對每艘到港船舶進行了預(yù)約時間段和各時間段計劃預(yù)約集裝箱數(shù)量分配.Huynh等[4]模擬了集卡在堆場的作業(yè)過程，利用數(shù)學(xué)模型求解了每個時間段最多可接受的預(yù)約份額.邵乾虔等[5]構(gòu)建了碼頭集疏港聯(lián)動預(yù)約模式，以時間殘值矩陣為核心的線性仿真數(shù)學(xué)模型驗證了聯(lián)動預(yù)約模式的有效性.許巧莉等[6]研究了非平穩(wěn)到達情況下的集卡預(yù)約優(yōu)化問題.Guan等[7]基于M/Ek/c排隊模型(顧客到達間隔時間分布為M負指數(shù)分布，Ek表示服務(wù)時間分布為k階愛爾蘭分布，服務(wù)臺數(shù)目為c)建立了集卡預(yù)約優(yōu)化模型.Chen等[8]建立了預(yù)約機制下集卡服務(wù)非穩(wěn)態(tài)排隊模型，在此基礎(chǔ)上設(shè)計了包括集卡到達優(yōu)化、擁堵收費設(shè)計的兩階段碼頭外部集卡管理方法.此外，曾慶成等[9]研究了集裝箱碼頭裝卸過程中集卡調(diào)度問題，建立了集卡調(diào)度動態(tài)模型，應(yīng)用Q學(xué)習(xí)算法(Q-learning algorithm，一種強化學(xué)習(xí)算法)進行了求解.丁一等[10]以橋吊調(diào)度計劃為依據(jù)，通過給定輪胎吊和集卡關(guān)聯(lián)任務(wù)集與作業(yè)要求時間，研究了輪胎吊-集卡的調(diào)度問題特性.Phan等[11]、Zhang等[12]及Chen等[13]對具有能源約束、集卡到達時間、時間窗限制的集裝箱碼頭集卡調(diào)度優(yōu)化問題進行了分析求解.綜上，目前的相關(guān)研究多是對單一外堆場與單一碼頭間的集卡調(diào)度問題，而現(xiàn)實中的港外堆場服務(wù)能力較強，一般同時為多個碼頭執(zhí)行集港服務(wù).本文在考慮堆場、碼頭節(jié)能減排發(fā)展要求的基礎(chǔ)上，從碳排放和預(yù)約機制的視角出發(fā)，對單一港外堆場服務(wù)多碼頭的送箱集卡調(diào)度問題進行研究，通過合理安排堆場集卡的送箱作業(yè)順序，降低調(diào)用集卡數(shù)量，提高集卡作業(yè)效率，減少其在碼頭的作業(yè)等待時間，從而降低集卡多碼頭調(diào)度作業(yè)CO2總排放量，提升堆場與碼頭的協(xié)作水平.

1 送箱集卡調(diào)度模型

1.1 問題描述

在傳統(tǒng)集裝箱碼頭針對遠洋運輸?shù)募蹣I(yè)務(wù)流程中，船方會在船舶到港前一段時間(如前96 h)向碼頭預(yù)報船期，并在船舶到港前24 h還會有船期確報，集裝箱碼頭根據(jù)船期以及碼頭的出口箱量、碼頭閘口和場內(nèi)機械的作業(yè)效率確定每條船舶的集港時間.港外堆場根據(jù)各碼頭公布的各集裝箱對應(yīng)船舶的集港時間、對應(yīng)碼頭的集港箱量大小、集港時間緊迫程度等信息，考慮自身的運力配置情況，制定集卡調(diào)度方案將集裝箱運抵集裝箱碼頭.

由于船舶集中到達、碼頭場橋和岸橋等核心調(diào)度資源能力不足、碼頭閘口擁擠等原因，這種傳統(tǒng)的集卡調(diào)度方案容易產(chǎn)生集卡資源過度占用，在碼頭閘口、港內(nèi)堆場等待時間過長等問題，因此傳統(tǒng)集卡調(diào)度在制定方案時需要堆場保持一定數(shù)量的集卡來應(yīng)付各種突發(fā)需求.由于堆場集卡保有量較高，集卡在作業(yè)過程中怠速等待時間過長，導(dǎo)致車輛能耗及CO2總排放量較高大，堆場運營成本較高.

依托現(xiàn)代信息和網(wǎng)絡(luò)通信技術(shù)有效建立碼頭和堆場之間的聯(lián)系.集裝箱碼頭根據(jù)船期以及碼頭的出口箱量、碼頭閘口和場內(nèi)機械的作業(yè)效率確定每條船舶的集港時間.碼頭將集港時間平均分成若干時間間隔相同的預(yù)約時段.堆場根據(jù)自身運力情況選擇合適的預(yù)約時段，并給出該時段的集港箱量.碼頭經(jīng)過平衡確定最終的集港計劃，并通知各個堆場，堆場按照具體的集港計劃來安排自身運力并進行集港工作.

圖1顯示了單一港外堆場向多個集裝箱碼頭的送箱集卡作業(yè)流程.在碼頭預(yù)約機制下，為了讓集卡可以在其所預(yù)約時段到達閘口，碼頭需要保證一定長度的預(yù)約時段.碼頭一般將24 h劃分為12個預(yù)約時段(每時段2 h)，每個時段碼頭給各個堆場一定的預(yù)約份額，堆場可根據(jù)各個碼頭的集港計劃以及自身實時運力情況選擇預(yù)約時段.碼頭根據(jù)各堆場所提交的預(yù)約時段及相應(yīng)預(yù)約箱量確定最終的堆場集港計劃.堆場按照最終的碼頭集港計劃制定集卡調(diào)度計劃方案.

圖1 單港外堆場對多碼頭的送箱集卡作業(yè)流程示意圖

由于碼頭在預(yù)約時段內(nèi)的集卡預(yù)約份額是有限的，碼頭不允許堆場在全天12個時段均申請集港作業(yè).在預(yù)約機制下各碼頭提前通知堆場其船舶集港計劃(一般提前24 h)，碼頭會按照計劃為堆場分配相應(yīng)的送箱時間窗(即可接受其集港的預(yù)約時段區(qū)間).堆場與碼頭最終確定集港作業(yè)計劃.一般船舶在本港的裝箱量決定了碼頭的集港箱量，不同碼頭船舶的出口箱集港時間對堆場而言可能在預(yù)約時段上有所重疊，在該時間窗內(nèi)堆場運抵碼頭的集裝箱數(shù)量必須滿足碼頭集港計劃要求.因此本文研究的是在堆場現(xiàn)有集卡資源基礎(chǔ)上，在碼頭預(yù)約機制下，單一港外堆場向多集裝箱碼頭的送箱集卡調(diào)度的優(yōu)化問題，滿足碼頭預(yù)約時段有限集卡預(yù)約份額要求，使堆場最終調(diào)用的集卡數(shù)量最少的同時節(jié)約能耗，減少集卡調(diào)度方案中CO2的總排放量，提高堆場的運營效率和效益.

1.2 問題假設(shè)

(1) 預(yù)約機制下碼頭將每天劃分為12個預(yù)約時段(每時段2h)，各碼頭時段劃分一致.

(2) 預(yù)約機制下堆場所調(diào)用集卡從1時段0時刻開始計時，其作業(yè)時間主要包括裝卸箱時間、運輸時間、等待時間.在堆場的裝箱時間主要由其場橋決定，一般取平均值；碼頭內(nèi)卸箱時間及運輸時間可統(tǒng)一為碼頭的集卡操作時間，一般取平均值，各碼頭操作時間各異；運輸時間與堆場和碼頭間的距離直接相關(guān)；等待時間包括堆場等待時間、碼頭等待時間及閘口排隊時間，堆場及碼頭的等待時間與集卡調(diào)度方案有關(guān)，碼頭閘口排隊等待時間與碼頭相關(guān)，各碼頭一般根據(jù)其情況取平均值.

(3) 假設(shè)多集裝箱碼頭所需要的總箱量一定，集卡從單一堆場對多碼頭進行送箱作業(yè)時其總的路程是不變的，但不同優(yōu)化方案的碼頭作業(yè)順序會對堆場集卡調(diào)用數(shù)量以及由于怠速等待運行造成的碳排放量有直接的影響.

(4) 集卡從堆場出發(fā)時僅能裝載一個集裝箱，在相應(yīng)碼頭完成卸箱操作后應(yīng)返回始發(fā)堆場等待繼續(xù)調(diào)度，集卡在碼頭等待及裝卸箱作業(yè)時怠速運行，在堆場等待調(diào)度時無能耗.

(5) 堆場集卡型號相同，行駛速度、油耗等性能相同，可在一個預(yù)約時段內(nèi)多次往返堆場碼頭完成集港任務(wù).

(6) 在預(yù)約機制下，集卡能準時到達集港作業(yè)計劃碼頭，不考慮其他干擾因素對集卡的影響.

(7) 預(yù)約機制下，碼頭會為堆場分配集港時間窗，時間窗所包括的預(yù)約時段和預(yù)約份額由碼頭給定，碼頭堆場共同制定集港作業(yè)計劃后，堆場出口集裝箱必須在碼頭集港時間窗內(nèi)到達港口.

1.3 模型建立

目標函數(shù)分為兩部分，K0表示堆場所調(diào)用集卡數(shù)量，E表示相應(yīng)集卡調(diào)度方案的總CO2排放量.目標函數(shù)如下：

(1)

式中：i為預(yù)約時段，將24 h決策期等分為I個預(yù)約時段,i=1,2,…,I；j為集裝箱碼頭編號，j=1,2,…,J；n為集卡在某一時段的第n次送箱，n=1,2,…,N；k為堆場集卡編號，k=1,2,…,K；yi,k為決策變量，表示集卡k在預(yù)約時段i是否參與過送箱，若是則其值為1，否則為0；yijn,k為決策變量，若集卡k在i時段的第n次送箱至碼頭j，則yijn,k=1，否則yijn,k=0；tj2為集卡在碼頭j閘口的平均等待時間；tj3為集卡在碼頭j的平均操作時間；tijn2,k為集卡k在i時段第n次送箱到達碼頭j后，在碼頭的等待時間；cil為集卡的怠速油耗，L·min-1；Dj為堆場到碼頭j的距離，km；chl為集卡重載油耗，為L·km-1；cll為集卡輕載油耗，L·km-1；eCO2為燃油CO2排放系數(shù)，kg·L-1.

目標函數(shù)計算時應(yīng)首先確定各時段堆場調(diào)用的集卡數(shù)量，再從中取最大值作為堆場總集卡調(diào)用量，取其最大值堆場能保證每個時段各個碼頭的送箱要求都能得到滿足，且未調(diào)用集卡可在堆場熄火等待，減少碳排放.其相應(yīng)集卡調(diào)度方案總的碳排放量與集卡調(diào)度方案中集卡行駛距離、作業(yè)及怠速等待時間直接相關(guān)，目標函數(shù)優(yōu)化目標是使兩個目標都盡可能達到最優(yōu)，保證最終的優(yōu)化調(diào)度方案較少占用堆場集卡，減少總碳排放量.

約束條件表示如下：

(1) 數(shù)量約束

(2)

(3)

xij≤hij,?i=1,2,…,I, ?j=1,2,…,J

(4)

yijn,k∈0,1,?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(5)

yi,k∈0,1, ?i=1,2,…,I,?k=1,2,…,K

(6)

式 (2)～(6)中：xij為堆場在預(yù)約時段i送達碼頭j的箱量；Qj為碼頭j需要的集港總箱量；hij為預(yù)約時段i碼頭j允許堆場運送的最大送箱量.

式(2)表示在碼頭j的預(yù)約送箱時間窗內(nèi)，堆場各時段總的送箱量應(yīng)滿足碼頭j的要求.式(3)表示i預(yù)約時段下從堆場送往碼頭j的總箱量.式(4)表示預(yù)約時段i內(nèi)堆場到碼頭j的送箱量要滿足其在該時段內(nèi)最大送箱量的約束.式(5)、(6)為決策變量屬性.

(2) 時間約束

Tijn,k=Tidn,k+tj1

?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(7)

Tirn,k=Tijn,k+tj2+tj3+tj1

?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(8)

Tid1,k=T(i-1)rn,k+tij11,k+t0

?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(9)

Tidn,k=Tir(n-1),k+tijn1,k+t0

?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(10)

Ts+(i-1)L≤Tijn,k≤Ts+iL

?i=1,2,…,I,?j=1,2,…,J,

?n=1,2,…,N,?k=1,2,…,K

(11)

式(7)～(11)中：Tijn,k為集卡k在i時段第n次送箱至碼頭j的時刻，若Tijn,k處于時段i，則Tidn,k,Tirn,k計入時段i而不考慮其實際所處時段；Tidn,k為集卡k在i時段第n次離開堆場的時刻；Tirn,k為集卡k在i時段第n次返回堆場的時刻；tj1為集卡從堆場到碼頭j的行駛時間；t0為集卡在堆場的裝箱時間，min；L為每個預(yù)約時段長度，min；Ts為第一個預(yù)約時段開始時刻；tijn1,k為集卡k在i時段第n次送箱至碼頭j前，在堆場的等待時間.

式(7)表示集卡k第i時段第n次送箱到達碼頭j的時刻.式(8)表示集卡k第i時段第n次回到堆場的時刻.式(9)表示集卡在第i時段第1次送箱離開堆場的時刻，式中T(i-1)rn,k表示集卡k在第i-1時段最后一次返回堆場的時刻，tij11,k表示集卡k第i時段第1次離開堆場前在堆場內(nèi)的等待時間.式(10)表示集卡k第i時段第n(n≥2)次離開堆場送箱的時刻，式中Tir(n-1),k表示集卡k第i時段第n-1次送箱返回堆場的時刻.式(11)保證在預(yù)約時段i送往碼頭j的集裝箱要滿足其預(yù)約時段i的時間限制.模型中相關(guān)的數(shù)量及時間約束能保證堆場集卡在預(yù)約時間段內(nèi)滿足各個碼頭的送箱要求.

2 算法設(shè)計

本文設(shè)計了改進的蟻群算法，采用人工螞蟻來模擬堆場送箱集卡進行調(diào)度優(yōu)化[14].在每次循環(huán)中，每只螞蟻分別模擬K輛集卡，K即為本次循環(huán)中堆場所調(diào)用的集卡數(shù)量.在所設(shè)計算法中，狀態(tài)轉(zhuǎn)移規(guī)則和信息素更新規(guī)則是集卡調(diào)度模擬的2個重要的規(guī)則，直接決定了螞蟻的搜索狀態(tài)，結(jié)合集卡調(diào)度特點,算法對其做了相應(yīng)改進，以提高算法對最優(yōu)方案的搜索效率，保證集卡作業(yè)順序的合理性.

2.1 解的結(jié)構(gòu)設(shè)計

針對所構(gòu)建集卡調(diào)度模型的特點，本文首先在基本蟻群算法中加入時間窗和分割配送的設(shè)計[15].時間窗設(shè)置能使螞蟻有效地判別碼頭不同預(yù)約時段內(nèi)的送箱需求，進而合理安排最適合的集卡執(zhí)行相應(yīng)配送.與車輛路徑問題及旅行商問題等不同，在集卡調(diào)度問題中車輛往往需要在堆場和各集裝箱碼頭間執(zhí)行多行程反復(fù)配送，因此結(jié)合其多行程的調(diào)度特點，算法引入了分割配送設(shè)計，當螞蟻在時間窗和運量約束下完成第1輛集卡調(diào)度后，從其開始的預(yù)約時段對第2輛集卡進行模擬直到所有任務(wù)都被完成，以每輛集卡的路徑串序列代表部分解方案，所有螞蟻所模擬集卡路徑及時間過程即為完整的求解方案.

改進的蟻群算法初始解路徑串由集卡編號、預(yù)約時段、送箱序數(shù)、送箱碼頭、前一次送箱完成后返回堆場時刻、堆場等待時間等元素組成，例如(1,1,1,3,0,0)→(1,2,1,1,15,5)→(1,2,2,4,30,0)表示1號集卡的全部調(diào)度過程，集卡從0開始，在等待0后進行第1時段的第1次送箱，送箱目標為碼頭3；返回堆場的時刻為15，等待5后執(zhí)行第2時段的第1次送箱，送箱目標為碼頭1；再次返回堆場的時刻為30，等待0后進行第2時段的第2次送箱，送箱目標為碼頭4.集卡全部路徑串即組成了港外堆場在多集裝箱碼頭間的總調(diào)度方案.

2.2 信息素更新規(guī)則

信息素更新規(guī)則主要包括集卡行駛后信息素更新時間及更新量.根據(jù)模型的特點，算法設(shè)定在所有螞蟻均都遍歷一次循環(huán)后更新信息素，對每只螞蟻m，更新規(guī)則如下：

τijn,k(t+1)=(1-ρ)τijn,k(t)+Δτ(t)yijn,k

(12)

2.3 狀態(tài)轉(zhuǎn)移規(guī)則

算法在求解過程螞蟻會根據(jù)道路上遺留的信息素按照概率來進行下一路段路徑的選擇，信息素濃度越高，路徑被選中的概率越大.因此需要設(shè)定狀態(tài)轉(zhuǎn)移規(guī)則來計算路徑被選中的概率，完成集卡路徑的構(gòu)造.在蟻群算法中，螞蟻對于路徑的選擇主要是由信息素濃度和啟發(fā)函數(shù)決定的，狀態(tài)轉(zhuǎn)移規(guī)則如式(13)所示.

(13)

式中：pijn,k(t)表示第t次循環(huán)時集卡k在第i時段第n次前往碼頭j的概率；τijn,k(t)表示第t次循環(huán)時集卡k在第i時段第n次送箱前往碼頭j的路徑上的信息素濃度；ηijn,k(t)表示第t次循環(huán)時集卡k在第i時段第n次送箱前往碼頭j的啟發(fā)函數(shù)；α、β分別表示集卡調(diào)度過程中信息素濃度和啟發(fā)函數(shù)的相對重要度；Jin,k表示集卡k第i時段第n次送箱所允許前往的碼頭集合.

2.3.1啟發(fā)函數(shù)的構(gòu)造

在基本蟻群算法中，啟發(fā)函數(shù)主要與路段的路徑長度有關(guān)，路徑越短其被選中概率越高，由于本問題集卡送箱量是固定的，其送箱與否與路徑長度無關(guān)，因此在構(gòu)建啟發(fā)函數(shù)時主要考慮集卡在堆場的等待時間，保證集卡能在各碼頭間高效周轉(zhuǎn).集卡相應(yīng)的啟發(fā)函數(shù)如式(14)、(15)所示.

ηijn,k(t)=wijn,k

(14)

(15)

式(14)、(15)中：wijn,k表示集卡在選擇下一前往的碼頭時能否被選中的概率，與其在堆場的等待時間tijn1,k直接相關(guān)，以有等待時間的集卡1和無等待時間的集卡2為例，由于tijn1,1>0使wijn,1<1，tijn1,2=0使wijn,2=1，因此集卡2被選中概率大于集卡1，tijn1,k越大，集卡被選中前往的概率越??；ε為一極小的正數(shù);Jin,k表示螞蟻k在第i時段第n次送箱時能到達，且滿足時間窗及最大送箱量約束的碼頭集合.

2.3.2禁忌表設(shè)計

在滿足堆場碼頭時間窗、預(yù)約時段碼頭最大預(yù)約份額以及碼頭總集港箱量約束下，集卡調(diào)度問題并不限制每輛集卡訪問某碼頭的次數(shù).碼頭禁忌表設(shè)計如下：設(shè)螞蟻k在堆場空閑，可以接受任務(wù).若Jin,k=?，則表明集卡k在第i時段的送箱任務(wù)全部完成；Jin,k≠?，則計算碼頭集合J中的轉(zhuǎn)移概率pijn,k(t).

2.4 算法步驟

改進的蟻群算法流程如圖2所示.

算法步驟如下：

Step 1 輸入碼頭初始信息J、I，碼頭送箱時間窗[Tj,s,Tj,f]，其中Tj,s和Tj,f分別表示碼頭開始接箱時間和碼頭終止接箱時間，Qj，hij，各時間信息t0、tj1、tj2、tj3，螞蟻數(shù)量M，堆場集卡總量K；設(shè)置初始信息素濃度τijn,k(0)、Q、ρ，相對重要度α、β，最大迭代次數(shù)N；令當前循環(huán)次數(shù)t=1.

Step 2 令當前集卡數(shù)量km=1，i=1，n=1,xij=0,qj=0,T1r0,k設(shè)置為第1預(yù)約時段開始時刻(qj表示碼頭j已完成的送箱量，km表示螞蟻m模擬的集卡數(shù)量).

圖2 改進蟻群算法流程圖

Step 3 計算集卡k在第i時段第n次前往碼頭j之前，在堆場的等待時間tijn1,k和到達碼頭j的時刻Tijn,k(假設(shè)每輛集卡都希望盡早到達碼頭)，判定其可行性，即碼頭是否有集港需求，堆場在第i時段最大送箱量是否飽和，是否可以在時段i到達，是否有時間窗可以響應(yīng).遍歷結(jié)束后，產(chǎn)生可行的碼頭集合Jin,k.若Jin,k=?，則轉(zhuǎn)入Step 5；若Jin,k≠?，則轉(zhuǎn)入Step 4.

Step 4 對Jin,k中的碼頭，按式(13)計算第t次循環(huán)螞蟻m在第i時段第n次前往的碼頭j的概率，決定本次前往的碼頭，計算返回堆場的時刻Tirn,k，將該元素加入路徑串序列.令yijn,k=1,n=n+1,xij=xij+1，qj=qj+1，記錄螞蟻m模擬集卡調(diào)度的解，返回Step 3.

Step 5i=i+1.若i≤12，則令n=1，返回Step 3.若i>12，判斷所有碼頭的集港需求是否得到滿足，若是則kbest=minkm，記錄最優(yōu)解，轉(zhuǎn)Step 6；若不是，則km=km+1，i=1，n=1，T1r0,k=T1,s，返回Step 3.

Step 6 若t

3 算例分析

3.1 算例描述

某堆場擁有100輛可調(diào)度的集卡，堆場與港口的7個碼頭建立了相應(yīng)的預(yù)約機制.碼頭將一天24 h劃分為12個預(yù)約時段，每個預(yù)約時段長度為2 h.集卡平均行駛速度為60 km· h-1，其重載油耗為1.2 L·km-1，輕載油耗為0.8 L·km-1，怠速狀態(tài)下油耗為2.5 L·h-1，燃油的CO2排放系數(shù)為2.65 kg·L-1，集卡在堆場的平均裝箱時間t0為3 min.堆場與各碼頭間的距離lj，碼頭集港箱量Qj，碼頭送箱時間窗信息Tj,s、Tj,f，集卡在各碼頭閘口的平均等待時間tj2，在碼頭平均操作時間tj3等信息如表1所示，不同預(yù)約時段碼頭對堆場的最大預(yù)約份額如表2所示.為了便于計算，案例中的時間單位在計算時都用分鐘表示.

表1 各碼頭集港信息

3.2 算例求解

為檢驗本文調(diào)度模型及算法的適用性，算法采用MATLAB2012進行模型求解，在奔騰雙核處理器E5400，主頻2.7 GHz，內(nèi)存為3.00 GB的計算機上運行.為了選擇較好的算法參數(shù)組合，令α、β、ρ在[1,2]、[1,3]、[0,1]中取值[16]，通過對算例進行大量實驗驗證，確定所設(shè)計改進蟻群算法的各項參數(shù)取值如下：信息素初始濃度設(shè)置為1，Kn=30，信息素揮發(fā)系數(shù)ρ=0.5，相對重要度α=1，相對重要度β=2，螞蟻數(shù)量M=30，信息素增加常量Q=100.當?shù)螖?shù)設(shè)為500時，算法可在迭代次數(shù)內(nèi)找到較優(yōu)的解，調(diào)度結(jié)果如圖3所示.

表2各碼頭預(yù)約時段允許堆場的最大送箱量

Tab.2Maximumdeliveryvolumeofcontainerallowedineachterminalatappointmentperiods箱

由圖3可知，隨著迭代次數(shù)的增加，最優(yōu)調(diào)度方案中集卡數(shù)量漸漸趨于穩(wěn)定，當算法迭代到400代時，所調(diào)用的集卡數(shù)量波動越來越小，目標值趨于收斂.此時的送箱集卡最優(yōu)調(diào)度方案所使用的集卡數(shù)量為34，最優(yōu)方案中集卡調(diào)度順序及其作業(yè)情況如表3所示.在各集卡的路徑方案中，由1×5的數(shù)組來標記其送箱及作業(yè)情況.數(shù)組中的5個數(shù)字依次為該集卡本次送箱的預(yù)約時段、本時段的送箱序數(shù)、送箱碼頭序號、前一次送箱完成后返回堆場的時刻、本次送箱在堆場的等待時間.表4中數(shù)據(jù)給出了表3各集卡及最終調(diào)度方案中運輸里程、作業(yè)時間及CO2排放量等信息.

圖3 算法迭代500次優(yōu)化結(jié)果

集卡編號送箱服務(wù)次序123456789101112131415161(1,1,2,0,0)(2,1,2,94,0)(2,2,2,188,0)(3,1,1,282,0)(4,1,3,401,0)(5,1,1,495,0)(6,1,5,614,0)(6,2,5,668,0)(7,1,5,722,0)(7,2,5,776,0)(8,1,4,830,0)(8,2,4,902,0)(9,1,4,974,0)(9,2,4,1 046,0)(10,1,7,1 118,0)(11,1,7,1 213,0)2(1,1,2,0,0)(2,1,2,94,0)(2,2,2,188,0)(3,1,2,282,0)(4,1,1,376,0)(5,1,1,495,0)(6,1,7,614,0)(7,1,6,709,0)(7,2,5,787,0)(8,1,4,841,0)(8,2,4,913,0)(9,1,4,985,0)(10,1,7,1 057,0)(10,2,7,1 152,0)(11,1,7,1 247,0)3(1,1,2,0,0)(2,1,1,94,0)(3,1,2,213,0)(3,2,2,307,0)(4,1,1,401,0)(5,1,5,520,0)(5,2,5,574,0)(6,1,5,628,0)(6,2,5,682,0)(7,1,5,736,0)(7,2,5,790,0)(8,1,6,844,0)(9,1,6,994,0)(10,1,7,1 072,0)(11,1,7,1 167,0)(11,2,7,1 262,0)4(1,1,2,0,0)(2,1,2,94,0)(2,2,2,188,0)(3,1,2,282,0)(4,1,2,376,0)(5,1,3,470,0)(5,2,5,564,0)(6,1,1,618,0)(7,1,5,737,0)(7,2,5,791,0)(8,1,4,845,0)(8,2,6,917,0)(9,1,7,972,0)(10,1,7,1 090,0)(11,1,7,1 185,0)5(1,1,2,0,0)(2,1,1,94,0)(2,2,2,188,0)(3,1,2,282,0)(4,1,2,376,0)(5,1,3,470,0)(5,2,5,564,0)(6,1,4,618,0)(6,2,5,690,0)(7,1,6,744,0)(8,1,6,822,0)(8,2,4,900,0)(9,1,7,995,0)(10,1,7,1 067,0)(11,1,7,1 162,0)(11,2,7,1 257,0)6(1,1,2,0,0)(2,1,1,94,0)(3,1,3,213,0)(3,2,2,307,0)(4,1,2,401,0)(5,1,1,495,0)(6,1,3,614,0)(7,1,4,708,0)(7,2,6,780,0)(8,1,6,858,0)(9,1,7,936,0)(9,2,6,1 031,0)(10,1,7,1 109,0)(11,1,7,1 204,0)7(1,1,2,0,0,)(2,1,1,94,0)(3,1,1,213,0)(4,1,1,332,0)(4,2,5,451,0)(5,1,3,505,0)(6,1,4,599,0)(6,2,5,671,0)(7,1,1,725,0)(8,1,4,844,0)(8,2,6,916,0)(9,1,7,994,0)(10,1,7,1 089,0)(11,1,7,1 184,9)8(1,1,2,0,0)(2,1,1,94,0)(3,1,1,213,0)(3,2,2,307,0)(4,1,2,332,0)(4,2,5,426,0)(5,1,1,480,0)(6,1,4,599,0)(7,1,4,725,0)(7,2,5,797,0)(8,1,4,851,0)(8,2,4,923,0)(9,1,7,995,0)9(1,1,2,0,0)(2,1,1,94,0)(3,1,1,213,0)(4,1,1,332,0)(4,2,5,451,0)(5,1,4,505,0)(6,1,4,577,0)(6,2,5,649,0)(7,1,7,703,0)(7,2,6,798,0)(8,1,1,876,0)(9,1,4,995,0)10(1,1,2,0,0)(2,1,1,94,0)(3,1,3,213,0)(3,2,3,307,0)(4,1,2,401,0)(5,1,3,495,0)(6,1,1,589,0)(7,1,4,708,0)(7,2,6,780,0)(8,1,7,858,0)(9,1,4,953,0)(10,1,2,1 025,0)11(1,1,2,0,0)(2,1,1,94,0)(3,1,1,213,0)(4,1,2,332,0)(4,2,5,426,0)(5,1,1,480,0)(6,1,4,599,0)(6,2,5,671,0)(7,1,1,725,0)(8,1,7,820,0)(8,2,6,915,0)(9,1,4,993,0)12(1,1,2,0,0)(2,1,1,94,0)(3,1,1,213,0)(4,1,3,332,0)(4,2,5,426,0)(5,1,1,480,0)(6,1,7,599,0)(6,2,5,694,0)(7,1,7,748,0)(8,1,4,843,0)(8,2,4,915,0)(9,1,4,987,0)

表3(續(xù))

表4 預(yù)約機制下最優(yōu)集卡調(diào)度方案作業(yè)信息表

3.3 算例對比分析

在通過改進蟻群算法對預(yù)約機制下考慮碳排放的多碼頭集卡調(diào)度優(yōu)化方案進行求解基礎(chǔ)上，表5、6中給出了以往傳統(tǒng)模式無預(yù)約機制下堆場面對同樣的多集裝箱碼頭集港任務(wù)時的集卡調(diào)度方案及相關(guān)的運輸距離、作業(yè)時間、碳排放等數(shù)據(jù).同樣的多碼頭集港需求，傳統(tǒng)模式下調(diào)度方案需要堆場保有39輛集卡，其集卡最多集港次數(shù)為11次，單車最長行駛里程為820 km，其平均堆場等待時間為0 min，平均碼頭等待時間為403.33 min，其最終返回堆場的平均時間為1 182.41 min，集卡平均CO2排放量為1 888.77 kg.由表4預(yù)約機制最優(yōu)集卡調(diào)度優(yōu)化方案數(shù)據(jù)可知，其需求集卡保有量僅為34輛，調(diào)度方案中集卡最多服務(wù)次數(shù)為16次，單車最長行駛里程為1 140 km，堆場平均等待時間為145.26 min，碼頭平均等待時間為61.65 min，集卡最終返回堆場的平均時間為1 099.62 min，集卡平均CO2排放量為2 122.23 kg.

從調(diào)度方案中集卡數(shù)量來看，考慮預(yù)約機制的新調(diào)度模式僅為34臺，較傳統(tǒng)調(diào)度方案少5臺；傳統(tǒng)方案下CO2排放達73 662.19 kg，基于預(yù)約機制優(yōu)化方案CO2總排放量為72 155.91 kg，碳排放量減少了2.04%；預(yù)約機制下集卡總工作時間為37 387 min，較傳統(tǒng)模式減少18.92%(傳統(tǒng)模式下集卡工作總時間為46 114 min)；從等待時間方面來看，預(yù)約機制下集卡優(yōu)化調(diào)度與傳統(tǒng)模式最大的區(qū)別在于，預(yù)約機制下某集卡服務(wù)路徑中等待時間多是在堆場產(chǎn)生的，而傳統(tǒng)模式中集卡由于沒有預(yù)約信息的溝通，只能在完成上一次集港任務(wù)返回堆場后馬上出發(fā)，前往下一碼頭進行集港，但往往其到達碼頭后由于碼頭方面種種原因需要在碼頭等待較長一段時間，怠速工況下增加了燃油消耗以及CO2排放量.

由此可見，在基于預(yù)約機制的單堆場多碼頭集卡優(yōu)化調(diào)度模式中，由于有對碼頭集港時間窗及各預(yù)約時段最大預(yù)約份額等預(yù)約信息的溝通，堆場在安排集卡集港服務(wù)路徑時可以更加方便地安排集卡的服務(wù)次序及作業(yè)流程，合理規(guī)避碼頭集港作業(yè)的高峰時段，避免碼頭閘口或港內(nèi)堆場的過長等待.與傳統(tǒng)集卡調(diào)度模式相比，本文所構(gòu)建的調(diào)度優(yōu)化方案能降低堆場對集卡數(shù)量的要求，提高集卡集港作業(yè)效率，有效減少能源消耗，降低集港作業(yè)過程中的CO2排放總量，最終減少堆場的運營成本.

表5 傳統(tǒng)模式送箱集卡調(diào)度方案

表5(續(xù))

表6 傳統(tǒng)模式下集卡調(diào)度方案作業(yè)信息表

表6(續(xù))

4 結(jié)論

在考慮集卡碳排放和碼頭預(yù)約機制的基礎(chǔ)上合理調(diào)度集卡車隊，完成各碼頭最終確定的各預(yù)約時段及其預(yù)約份額的集港任務(wù)，可以有效降低堆場集卡的調(diào)用數(shù)量，提高其運營效率，減少燃油消耗和CO2排放，降低堆場運營成本.本文針對預(yù)約機制下單一堆場多集裝箱碼頭間送箱集卡優(yōu)化調(diào)度問題，在考慮碳排放基礎(chǔ)上構(gòu)建了相應(yīng)的優(yōu)化模型，設(shè)計了改進的蟻群算法對其進行求解.算例求解及對比分析表明了本文所構(gòu)建模型及算法的有效性.研究成果拓展了堆場、碼頭相關(guān)的理論研究，為堆場企業(yè)的集卡調(diào)度優(yōu)化決策和低碳港口建設(shè)的相關(guān)決策提供了一定參考.

應(yīng)該指出，由于船舶集港所涉及的各個環(huán)節(jié)和影響因素較為復(fù)雜，在求解分析過程中本文沒有考慮集港過程中的集卡在港的排隊規(guī)律、相關(guān)干擾因素以及集卡失約等問題，這些都有待于未來繼續(xù)研究.