張 赫,邢江豪,閆建鑫,王 宇
(大連海事大學(xué)交通運(yùn)輸工程學(xué)院,遼寧 大連 116026)
隨著港口吞吐量的逐年增長(zhǎng),集卡調(diào)度在港口的集疏港作業(yè)中顯得越來(lái)越重要.在作業(yè)高峰時(shí)段,大量非平穩(wěn)到達(dá)的集卡從各公路系統(tǒng)匯集到港口,造成公路系統(tǒng)以及閘口和碼頭堆場(chǎng)的排隊(duì)擁堵[1-2].這不僅制約了港口貨物集疏運(yùn)速率,而且導(dǎo)致了集卡在碼頭的滯留,加重了二氧化碳等汽車尾氣對(duì)大氣造成的破壞.鑒于此,中外學(xué)者對(duì)預(yù)約機(jī)制下的港外集卡調(diào)度進(jìn)行了一系列探討和分析,得出了許多研究成果.曾慶成等[3]對(duì)集卡到達(dá)的規(guī)律使用非平穩(wěn)排隊(duì)模型,以遺傳算法(genetic algorithm,GA)與駐點(diǎn)固定流體近似算法確定最優(yōu)的預(yù)約份額.范厚明等[4]針對(duì)基于預(yù)約機(jī)制的送箱集卡多集裝箱碼頭調(diào)度問(wèn)題,以集卡數(shù)量最少化為目標(biāo)函數(shù)建立集卡調(diào)度模型,并用改進(jìn)的蟻群算法(ant colony optimization,ACO)求解.張赫等[5]將港口系統(tǒng)和公路運(yùn)輸系統(tǒng)進(jìn)行整體調(diào)度優(yōu)化,以最小化集卡工作時(shí)間為目標(biāo),將集卡調(diào)度運(yùn)作路徑進(jìn)行了優(yōu)化處理,增加了港公系統(tǒng)的運(yùn)作速率.Namboothiria等[6]通過(guò)將車隊(duì)運(yùn)輸費(fèi)用最優(yōu)化,來(lái)建立集卡調(diào)度模型,并指出了集卡車隊(duì)在考慮預(yù)約機(jī)制因素下調(diào)度的影響.Kim等[7]通過(guò)分析得出利用M/G/1排隊(duì)模型來(lái)建立集卡在堆場(chǎng)的排隊(duì)過(guò)程.Chen等[8]考慮了集卡抵達(dá)受時(shí)間影響的特點(diǎn),構(gòu)造了預(yù)約機(jī)制下集卡非平穩(wěn)排隊(duì)模型,提出了集卡抵達(dá)分布、高峰時(shí)段阻塞繳納費(fèi)用的集卡控制辦法.
綜上研究為預(yù)約機(jī)制下的港外集卡調(diào)度優(yōu)化提供了依據(jù),但目前的研究都是針對(duì)集卡到達(dá)港口完成送箱或取箱的問(wèn)題,而現(xiàn)實(shí)狀況下往往是集卡往返于單一港外堆場(chǎng)與多個(gè)碼頭堆場(chǎng)之間的同時(shí)進(jìn)行送取箱操作.本文在上述研究基礎(chǔ)上,提出了港外集卡在預(yù)約時(shí)間窗下到達(dá)港口堆場(chǎng)內(nèi)多個(gè)進(jìn)出口箱區(qū)的優(yōu)化調(diào)度問(wèn)題,使得該問(wèn)題的探討更符合現(xiàn)實(shí)情況.
現(xiàn)將堆場(chǎng)內(nèi)的箱區(qū)根據(jù)其目的地統(tǒng)一分為兩種,一種是存放從船上卸下集裝箱的進(jìn)口箱區(qū),另一種是存放等待裝船集裝箱的出口箱區(qū).港口通過(guò)獲取船舶到港時(shí)間以及集裝箱的裝卸量,并以此為依據(jù)為各進(jìn)、出口箱區(qū)設(shè)定港外集卡的預(yù)約時(shí)段和各時(shí)段的預(yù)約份額[9].所有港外集卡都從港外堆場(chǎng)出發(fā),首先,必須在預(yù)約時(shí)間窗下將港外堆場(chǎng)的集裝箱運(yùn)送至出口箱區(qū),然后再判斷是否滿足進(jìn)口箱區(qū)的預(yù)約時(shí)間窗與預(yù)約份額的限制,若滿足,則到達(dá)進(jìn)口箱區(qū)完成取箱操作,返回港外堆場(chǎng),完成一次送、取箱任務(wù).若不能滿足預(yù)約時(shí)間窗的限制,則由港外堆場(chǎng)單獨(dú)安排集卡完成任務(wù).問(wèn)題描述如圖1所示.
本文考慮在預(yù)約機(jī)制下,單一港外堆場(chǎng)與多個(gè)具有不同送取箱需求的進(jìn)、出口箱區(qū)的港外集卡調(diào)度問(wèn)題.在預(yù)約時(shí)間窗與預(yù)約份額確定的條件下,合理安排港外集卡,求得港外集卡數(shù)量與所有港外集卡送取箱總時(shí)間相對(duì)應(yīng)的成本最小值,以減少集、疏港過(guò)程中的資源消耗.
圖1 港外集卡送取箱示意圖Fig.1 Schematic diagram of the deliver and pickup container of the trucks
1) 由于在不同時(shí)間段內(nèi),船舶到達(dá)碼頭的數(shù)量不均衡以及受到其他非平穩(wěn)因素的影響,預(yù)約時(shí)間窗與預(yù)約份額在不同時(shí)段內(nèi)存在較大的波動(dòng),故只考慮一個(gè)時(shí)段內(nèi)的時(shí)間窗劃分.
2) 各進(jìn)出口箱區(qū)在該時(shí)段內(nèi)的預(yù)約時(shí)間窗連續(xù)且各時(shí)間窗長(zhǎng)度相同,預(yù)約份額確定.
3) 整個(gè)過(guò)程中,港外集卡的時(shí)間消耗主要是從港外堆場(chǎng)到港口的往返行程時(shí)間、閘口排隊(duì)時(shí)間、碼頭停車場(chǎng)等待時(shí)間、裝卸箱時(shí)間、進(jìn)與出口箱區(qū)間行程時(shí)間.集裝箱的裝卸時(shí)間由場(chǎng)橋的運(yùn)作時(shí)間決定并設(shè)為確定值.港外堆場(chǎng)到港口的往返時(shí)間與進(jìn)、出口箱區(qū)間的行程時(shí)間統(tǒng)一成為集裝箱運(yùn)輸時(shí)間,并由行程距離與港外集卡平均速度的比值確定.閘口排隊(duì)時(shí)間和碼頭停車場(chǎng)等待時(shí)間統(tǒng)一成港口排隊(duì)等待時(shí)間,并取各集卡等待時(shí)間的平均值[10-12].
4) 該時(shí)段的時(shí)間長(zhǎng)度小于集卡從港外堆場(chǎng)到港口的行程時(shí)間最小值的三倍.
5) 所有港外集卡的出發(fā)時(shí)刻相同,且不考慮集卡的不確定因素,即假設(shè)所有集卡都能準(zhǔn)時(shí)到達(dá)[13].
6) 各進(jìn)、出口箱區(qū)的取、送集裝箱數(shù)量必須在該時(shí)間段內(nèi)完成,該時(shí)段內(nèi)各進(jìn)、出口箱區(qū)的時(shí)間窗劃分確定且不可改變[14].
1.4.1 目標(biāo)函數(shù)的確定 目標(biāo)函數(shù)的公式為:
(1)
1.4.2 約束條件 為滿足各碼頭堆場(chǎng)的送、取箱需求以及預(yù)約時(shí)間窗限制,約束條件表示如下:
(2)
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
(11)
?i∈N,?j∈M,?l∈L;
(12)
(13)
(14)
(15)
(16)
在上述模型中,式(1)為目標(biāo)函數(shù),求得所有港外集卡完成集、疏港任務(wù)所消耗的總時(shí)間與調(diào)用集卡數(shù)量的成本最小值.式(2)、(3)與(4)表示一輛集卡單次最多到達(dá)兩個(gè)不同任務(wù)的箱區(qū)完成送、取箱任務(wù).式(5)表示到達(dá)出口箱區(qū)i的集卡數(shù)量必須滿足該箱區(qū)的送箱總量.式(6)表示到達(dá)進(jìn)口箱區(qū)j的集卡數(shù)量必須滿足該箱區(qū)的取箱總量.式(7)表示集卡單次到達(dá)兩個(gè)箱區(qū)完成送、取箱任務(wù)的數(shù)量,小于所有到達(dá)出口箱區(qū)的集卡數(shù)量與所有到達(dá)進(jìn)口箱區(qū)的集卡數(shù)量?jī)烧叩妮^小值.式(8)表示所有集卡都從港外堆場(chǎng)出發(fā).式(9)表示所有集卡完成任務(wù)后都返回到港外堆場(chǎng).式(10)表示集卡到達(dá)進(jìn)口箱區(qū)完成送箱任務(wù)必須在到達(dá)出口箱區(qū)之前.式(11)表示集卡從港外堆場(chǎng)出發(fā)到達(dá)出口箱區(qū)i的時(shí)刻.式(12)表示集卡從出口箱區(qū)i出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻.式(13)表示集卡從港外堆場(chǎng)出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻.式(14)確保集卡從港外堆場(chǎng)出發(fā)到達(dá)出口箱區(qū)i的時(shí)刻滿足該箱區(qū)的預(yù)約時(shí)間窗要求.式(15)確保集卡從出口箱區(qū)i出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻滿足該箱區(qū)j的預(yù)約時(shí)間窗要求.式(16)確保集卡從港外堆場(chǎng)出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻滿足該箱區(qū)的預(yù)約時(shí)間窗要求.
遺傳算法是一種應(yīng)用廣泛的啟發(fā)式算法,對(duì)于大規(guī)模優(yōu)化問(wèn)題的求解具有高效穩(wěn)定的特點(diǎn).本文采用改進(jìn)的遺傳算法對(duì)模型進(jìn)行求解,將港外集卡的調(diào)用數(shù)量與所有港外集卡所消耗的時(shí)間總和來(lái)構(gòu)造適應(yīng)度函數(shù),并通過(guò)直接保留精英染色體的方式加快算法的收斂速度.算法的具體步驟如下.
步驟1編碼與初始種群.
染色體的基因?yàn)楦鬟M(jìn)出口箱區(qū)的編號(hào),每條染色體采用自然數(shù)編碼,并用自然數(shù)的大小表示進(jìn)出口箱區(qū),其中0代表港外堆場(chǎng).例如(0 1 6 0 2 7 0 3 8 0 4 0 9 5 0 10 0)表示:自然數(shù)1至5為出口箱區(qū),自然數(shù)6至10為進(jìn)口箱區(qū),兩者相互交替排列.共調(diào)用6輛集卡,調(diào)度方案為0-1-6-0,0-2-7-0,0-3-8-0,0-4-0,0-9-5-0,0-10-0.為簡(jiǎn)化編碼過(guò)程,可先不考慮港外堆場(chǎng)的編碼,將染色體直接表示成(1 6 2 7 3 8 4 9 5 10).最后使用兩次隨機(jī)數(shù),在滿足交替排列的前提下,生成各進(jìn)、出口箱區(qū)獨(dú)立的自然數(shù)隨機(jī)排列,完成初始化種群.
步驟2港外集卡數(shù)量car_num與消耗總時(shí)間all_time的計(jì)算.
先為N個(gè)出口箱區(qū)安排一輛港外集卡,再按染色體中基因排列的順序調(diào)配港外集卡,若港外集卡只能滿足出口箱區(qū)的時(shí)間窗則該港外集卡完成送箱任務(wù)后直接返回港外堆場(chǎng),另外調(diào)配一輛空集卡來(lái)完成進(jìn)口箱區(qū)的取箱任務(wù).若港外集卡完成送箱任務(wù)后,還能滿足下一個(gè)進(jìn)口箱區(qū)對(duì)應(yīng)基因的時(shí)間窗,則該集卡繼續(xù)完成取箱任務(wù),再返回港外堆場(chǎng).每當(dāng)有集卡返回港外堆場(chǎng)就更新港外集卡數(shù)量和港外集卡消耗總時(shí)間:car_num=car_num+1,all_time=all_time+該集卡此次消耗時(shí)間.
步驟3適應(yīng)度函數(shù)計(jì)算.
通過(guò)對(duì)步驟2港外集卡數(shù)量car_num與消耗總時(shí)間all_time的加權(quán)求得整體總成本,并將其倒數(shù)作為個(gè)體的適應(yīng)度值.
步驟4選擇操作.
采用精英策略,直接保留父代中的最優(yōu)個(gè)體,并用輪盤賭算法從父代中選擇個(gè)體進(jìn)入子代交配池.
步驟5交叉操作.
由于兩個(gè)染色體的基因片段隨機(jī)交叉后容易出現(xiàn)基因重復(fù)的現(xiàn)象,故要對(duì)交叉后的染色體進(jìn)行消去沖突操作.并且染色體中的基因是由兩種類型交替排列的方式組成,因此,消去沖突時(shí)需要考慮基因的排列方式.具體交叉過(guò)程如圖2~圖4所示.
1) 隨機(jī)設(shè)定兩個(gè)交叉點(diǎn)——點(diǎn)1和點(diǎn)2(如圖2).
圖2 隨機(jī)設(shè)定交叉點(diǎn)
Fig.2 Randomly set the intersection
2) 染色體基因片段交叉(如圖3).
圖3 基因片段交叉Fig.3 Gene fragment cross
3) 消去沖突點(diǎn)——點(diǎn)3和點(diǎn)4(如圖4).
圖4 消去沖突Fig.4 Eliminate conflicts
步驟6變異操作.
按照非均勻的變異概率將染色體中的進(jìn)口碼頭基因與出口碼頭基因分別隨機(jī)交換.非均勻變異概率P由進(jìn)化代數(shù)自動(dòng)調(diào)整.
其中pmax,pmin為設(shè)定的初始變異概率,Tnow為當(dāng)前進(jìn)化代數(shù),Tmax最大進(jìn)化代數(shù).
步驟7終止條件.
迭代到設(shè)定次數(shù)時(shí)終止算法.
表1 各堆場(chǎng)間的行程時(shí)間表Tab.1 Itinerary schedule between terminal yards min
表2 各碼頭堆場(chǎng)集港信息Tab.2 Terminal yards information
該算例實(shí)驗(yàn)在Anaconda下用Python編程求解,并在Intel 酷睿i5-4200u處理器,主頻1.6 GHz,內(nèi)存4 GB的計(jì)算機(jī)上運(yùn)行.經(jīng)過(guò)200次迭代與經(jīng)過(guò)300次迭代,得到的收斂結(jié)果分別如圖5和圖6所示.
圖5 GA算法進(jìn)化200代的結(jié)果Fig.5 GA algorithm evolution 200 generation results
圖6 GA算法進(jìn)化300代的結(jié)果Fig.6 GA algorithm evolution 300 generation results
從圖中結(jié)果分析得出,隨著迭代次數(shù)的增加,種群中的染色體逐漸收斂穩(wěn)定于最優(yōu)值.當(dāng)進(jìn)化到300代時(shí),輸出的算例最優(yōu)值達(dá)到最小并且處于收斂狀態(tài),此時(shí)得出的港外集卡調(diào)配方案見(jiàn)表3.港外集卡消耗總時(shí)間最優(yōu)值為638 min,調(diào)配的集卡數(shù)量為10輛,最小成本為11 380.得到了在預(yù)約窗口下的港外集卡最優(yōu)調(diào)度方案,達(dá)到了節(jié)省系統(tǒng)作業(yè)成本的目的,從而證明該算法是有效的.
表3 港外集卡最優(yōu)調(diào)配方案表Tab.3 The optimal scheduling of trucks
運(yùn)用同樣的算例,在相同的設(shè)備下,采用蟻群算法求解,并與本文遺傳算法求解結(jié)果進(jìn)行比較,其結(jié)果見(jiàn)表4.
從表中可以看出,在相同算例下,兩種算法都得到了相同的最優(yōu)結(jié)果,但在不同迭代次數(shù)間,用遺傳算法求解的結(jié)果相對(duì)于蟻群算法更貼近于最優(yōu)結(jié)果,并且迭代的速度更快.
為避免算例規(guī)模的單一性造成隨機(jī)性結(jié)果,將上述算法應(yīng)用于不同規(guī)模的算例進(jìn)行分析,如將上述問(wèn)題擴(kuò)展為算例1和算例2.算例1:30個(gè)箱區(qū),其中 10個(gè)進(jìn)口箱區(qū),份額為20個(gè)集裝箱;20個(gè)出口箱區(qū),份額為32個(gè)集裝箱.算例2:50個(gè)箱區(qū),其中20個(gè)進(jìn)口箱區(qū),份額為40個(gè)集裝箱;30個(gè)出口箱區(qū),份額為40個(gè)集裝箱.
表4 ACO與GA結(jié)果比較Tab.4 Comparison of ACO and GA results
新增的兩個(gè)算例,在算法進(jìn)化200代后,收斂結(jié)果如圖7和圖8所示.對(duì)于30個(gè)箱區(qū)算例,港外集卡消耗總時(shí)間最優(yōu)值為2 176 min,調(diào)配的集卡數(shù)量為35輛,最小成本為39 260.對(duì)于50個(gè)箱區(qū)算例,港外集卡消耗總時(shí)間最優(yōu)值為3 200 min,調(diào)配的集卡數(shù)量為54輛,最小成本為59 000.兩種算例都得到了在預(yù)約窗口下的港外集卡最優(yōu)調(diào)度方案,從而證明該算法通過(guò)了隨機(jī)性驗(yàn)證,算法是有效的.
圖7 30個(gè)箱區(qū)GA算法進(jìn)化結(jié)果Fig.7 30 container block GA algorithm evolution results
圖8 50個(gè)箱區(qū)GA算法進(jìn)化結(jié)果Fig.8 50 container block GA algorithm evolution results
在港口與船舶以及港外堆場(chǎng)都建有預(yù)約機(jī)制的情況下,港方能夠獲取船舶靠港時(shí)間、裝卸箱數(shù)量等集、疏港信息,并以此為依據(jù),綜合考慮港外堆場(chǎng)的實(shí)際運(yùn)輸能力,制定合理的集卡送取箱預(yù)約計(jì)劃.將有效降低集卡非平穩(wěn)到達(dá)情況下造成的港口排隊(duì)擁堵,減少系統(tǒng)碳排放量,提高集疏港作業(yè)效率.本文針對(duì)預(yù)約時(shí)間窗下港外集卡多進(jìn)、出口箱區(qū)的調(diào)度問(wèn)題,建立了數(shù)學(xué)模型,并用改進(jìn)的遺傳算法求解.算例結(jié)果證實(shí)模型是有效的,設(shè)計(jì)的遺傳算法也能較快地收斂到全局最優(yōu)解.通過(guò)合理調(diào)配集卡在某時(shí)段內(nèi)到達(dá)的進(jìn)出口箱區(qū),能夠減少集卡數(shù)量與所有集卡的消耗時(shí)間,提高集卡的運(yùn)輸效率,降低港口設(shè)施空耗.這些優(yōu)化結(jié)果可以為將來(lái)的港外集卡送、取箱調(diào)度提供理論參考依據(jù).本文沒(méi)有將港外集卡在閘口和堆場(chǎng)處的實(shí)際排隊(duì)規(guī)律、時(shí)間窗滾動(dòng)分布、場(chǎng)橋作業(yè)規(guī)律等問(wèn)題構(gòu)建到模型中,因此需要對(duì)這些問(wèn)題做進(jìn)一步的綜合研究.