范厚明， 郭振峰， 李 陽

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

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

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

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

1.1 問題描述

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

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

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

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

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

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

1.2 問題假設(shè)

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

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

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

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

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

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

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

1.3 模型建立

目標(biāo)函數(shù)分為兩部分，K0表示堆場所調(diào)用集卡數(shù)量，E表示相應(yīng)集卡調(diào)度方案的總CO2排放量.目標(biāo)函數(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次送箱到達(dá)碼頭j后，在碼頭的等待時間；cil為集卡的怠速油耗，L·min-1；Dj為堆場到碼頭j的距離，km；chl為集卡重載油耗，為L·km-1；cll為集卡輕載油耗，L·km-1；eCO2為燃油CO2排放系數(shù)，kg·L-1.

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

式(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而不考慮其實(shí)際所處時段；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次送箱到達(dá)碼頭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è)計了改進(jìn)的蟻群算法，采用人工螞蟻來模擬堆場送箱集卡進(jìn)行調(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)度特點(diǎn),算法對其做了相應(yīng)改進(jìn)，以提高算法對最優(yōu)方案的搜索效率，保證集卡作業(yè)順序的合理性.

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

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

改進(jìn)的蟻群算法初始解路徑串由集卡編號、預(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后進(jìn)行第1時段的第1次送箱，送箱目標(biāo)為碼頭3；返回堆場的時刻為15，等待5后執(zhí)行第2時段的第1次送箱，送箱目標(biāo)為碼頭1；再次返回堆場的時刻為30，等待0后進(jìn)行第2時段的第2次送箱，送箱目標(biāo)為碼頭4.集卡全部路徑串即組成了港外堆場在多集裝箱碼頭間的總調(diào)度方案.

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

信息素更新規(guī)則主要包括集卡行駛后信息素更新時間及更新量.根據(jù)模型的特點(diǎn)，算法設(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ù)道路上遺留的信息素按照概率來進(jìn)行下一路段路徑的選擇，信息素濃度越高，路徑被選中的概率越大.因此需要設(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越大，集卡被選中前往的概率越?。沪艦橐粯O小的正數(shù);Jin,k表示螞蟻k在第i時段第n次送箱時能到達(dá)，且滿足時間窗及最大送箱量約束的碼頭集合.

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 算法步驟

改進(jìn)的蟻群算法流程如圖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；令當(dāng)前循環(huán)次數(shù)t=1.

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

圖2 改進(jìn)蟻群算法流程圖

Step 3 計算集卡k在第i時段第n次前往碼頭j之前，在堆場的等待時間tijn1,k和到達(dá)碼頭j的時刻Tijn,k(假設(shè)每輛集卡都希望盡早到達(dá)碼頭)，判定其可行性，即碼頭是否有集港需求，堆場在第i時段最大送箱量是否飽和，是否可以在時段i到達(dá)，是否有時間窗可以響應(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ù)約機(jī)制.碼頭將一天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進(jìn)行模型求解，在奔騰雙核處理器E5400，主頻2.7 GHz，內(nèi)存為3.00 GB的計算機(jī)上運(yùn)行.為了選擇較好的算法參數(shù)組合，令α、β、ρ在[1,2]、[1,3]、[0,1]中取值[16]，通過對算例進(jìn)行大量實(shí)驗驗證，確定所設(shè)計改進(jìn)蟻群算法的各項參數(shù)取值如下：信息素初始濃度設(shè)置為1，Kn=30，信息素?fù)]發(fā)系數(shù)ρ=0.5，相對重要度α=1，相對重要度β=2，螞蟻數(shù)量M=30，信息素增加常量Q=100.當(dāng)?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)定，當(dāng)算法迭代到400代時，所調(diào)用的集卡數(shù)量波動越來越小，目標(biāo)值趨于收斂.此時的送箱集卡最優(yōu)調(diào)度方案所使用的集卡數(shù)量為34，最優(yōu)方案中集卡調(diào)度順序及其作業(yè)情況如表3所示.在各集卡的路徑方案中，由1×5的數(shù)組來標(biāo)記其送箱及作業(yè)情況.數(shù)組中的5個數(shù)字依次為該集卡本次送箱的預(yù)約時段、本時段的送箱序數(shù)、送箱碼頭序號、前一次送箱完成后返回堆場的時刻、本次送箱在堆場的等待時間.表4中數(shù)據(jù)給出了表3各集卡及最終調(diào)度方案中運(yùn)輸里程、作業(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ù)約機(jī)制下最優(yōu)集卡調(diào)度方案作業(yè)信息表

3.3 算例對比分析

在通過改進(jìn)蟻群算法對預(yù)約機(jī)制下考慮碳排放的多碼頭集卡調(diào)度優(yōu)化方案進(jìn)行求解基礎(chǔ)上，表5、6中給出了以往傳統(tǒng)模式無預(yù)約機(jī)制下堆場面對同樣的多集裝箱碼頭集港任務(wù)時的集卡調(diào)度方案及相關(guān)的運(yù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ù)約機(jī)制最優(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ù)約機(jī)制的新調(diào)度模式僅為34臺，較傳統(tǒng)調(diào)度方案少5臺；傳統(tǒng)方案下CO2排放達(dá)73 662.19 kg，基于預(yù)約機(jī)制優(yōu)化方案CO2總排放量為72 155.91 kg，碳排放量減少了2.04%；預(yù)約機(jī)制下集卡總工作時間為37 387 min，較傳統(tǒng)模式減少18.92%(傳統(tǒng)模式下集卡工作總時間為46 114 min)；從等待時間方面來看，預(yù)約機(jī)制下集卡優(yōu)化調(diào)度與傳統(tǒng)模式最大的區(qū)別在于，預(yù)約機(jī)制下某集卡服務(wù)路徑中等待時間多是在堆場產(chǎn)生的，而傳統(tǒng)模式中集卡由于沒有預(yù)約信息的溝通，只能在完成上一次集港任務(wù)返回堆場后馬上出發(fā)，前往下一碼頭進(jìn)行集港，但往往其到達(dá)碼頭后由于碼頭方面種種原因需要在碼頭等待較長一段時間，怠速工況下增加了燃油消耗以及CO2排放量.

由此可見，在基于預(yù)約機(jī)制的單堆場多碼頭集卡優(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排放總量，最終減少堆場的運(yùn)營成本.

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

表5(續(xù))

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

表6(續(xù))

4 結(jié)論

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

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