張 赫，邢江豪，閆建鑫，王 宇

(大連海事大學(xué)交通運輸工程學(xué)院，遼寧 大連 116026)

隨著港口吞吐量的逐年增長，集卡調(diào)度在港口的集疏港作業(yè)中顯得越來越重要.在作業(yè)高峰時段，大量非平穩(wěn)到達的集卡從各公路系統(tǒng)匯集到港口，造成公路系統(tǒng)以及閘口和碼頭堆場的排隊擁堵[1-2].這不僅制約了港口貨物集疏運速率，而且導(dǎo)致了集卡在碼頭的滯留，加重了二氧化碳等汽車尾氣對大氣造成的破壞.鑒于此，中外學(xué)者對預(yù)約機制下的港外集卡調(diào)度進行了一系列探討和分析，得出了許多研究成果.曾慶成等[3]對集卡到達的規(guī)律使用非平穩(wěn)排隊模型，以遺傳算法(genetic algorithm，GA)與駐點固定流體近似算法確定最優(yōu)的預(yù)約份額.范厚明等[4]針對基于預(yù)約機制的送箱集卡多集裝箱碼頭調(diào)度問題，以集卡數(shù)量最少化為目標(biāo)函數(shù)建立集卡調(diào)度模型，并用改進的蟻群算法(ant colony optimization，ACO)求解.張赫等[5]將港口系統(tǒng)和公路運輸系統(tǒng)進行整體調(diào)度優(yōu)化，以最小化集卡工作時間為目標(biāo)，將集卡調(diào)度運作路徑進行了優(yōu)化處理，增加了港公系統(tǒng)的運作速率.Namboothiria等[6]通過將車隊運輸費用最優(yōu)化，來建立集卡調(diào)度模型，并指出了集卡車隊在考慮預(yù)約機制因素下調(diào)度的影響.Kim等[7]通過分析得出利用M/G/1排隊模型來建立集卡在堆場的排隊過程.Chen等[8]考慮了集卡抵達受時間影響的特點，構(gòu)造了預(yù)約機制下集卡非平穩(wěn)排隊模型，提出了集卡抵達分布、高峰時段阻塞繳納費用的集卡控制辦法.

綜上研究為預(yù)約機制下的港外集卡調(diào)度優(yōu)化提供了依據(jù)，但目前的研究都是針對集卡到達港口完成送箱或取箱的問題，而現(xiàn)實狀況下往往是集卡往返于單一港外堆場與多個碼頭堆場之間的同時進行送取箱操作.本文在上述研究基礎(chǔ)上，提出了港外集卡在預(yù)約時間窗下到達港口堆場內(nèi)多個進出口箱區(qū)的優(yōu)化調(diào)度問題，使得該問題的探討更符合現(xiàn)實情況.

1 預(yù)約時間窗下集卡送取箱優(yōu)化模型

1.1 問題描述

現(xiàn)將堆場內(nèi)的箱區(qū)根據(jù)其目的地統(tǒng)一分為兩種，一種是存放從船上卸下集裝箱的進口箱區(qū)，另一種是存放等待裝船集裝箱的出口箱區(qū).港口通過獲取船舶到港時間以及集裝箱的裝卸量，并以此為依據(jù)為各進、出口箱區(qū)設(shè)定港外集卡的預(yù)約時段和各時段的預(yù)約份額[9].所有港外集卡都從港外堆場出發(fā)，首先，必須在預(yù)約時間窗下將港外堆場的集裝箱運送至出口箱區(qū)，然后再判斷是否滿足進口箱區(qū)的預(yù)約時間窗與預(yù)約份額的限制，若滿足，則到達進口箱區(qū)完成取箱操作，返回港外堆場，完成一次送、取箱任務(wù).若不能滿足預(yù)約時間窗的限制，則由港外堆場單獨安排集卡完成任務(wù).問題描述如圖1所示.

本文考慮在預(yù)約機制下，單一港外堆場與多個具有不同送取箱需求的進、出口箱區(qū)的港外集卡調(diào)度問題.在預(yù)約時間窗與預(yù)約份額確定的條件下，合理安排港外集卡，求得港外集卡數(shù)量與所有港外集卡送取箱總時間相對應(yīng)的成本最小值，以減少集、疏港過程中的資源消耗.

圖1 港外集卡送取箱示意圖Fig.1 Schematic diagram of the deliver and pickup container of the trucks

1.2 問題假設(shè)

1) 由于在不同時間段內(nèi)，船舶到達碼頭的數(shù)量不均衡以及受到其他非平穩(wěn)因素的影響，預(yù)約時間窗與預(yù)約份額在不同時段內(nèi)存在較大的波動，故只考慮一個時段內(nèi)的時間窗劃分.

2) 各進出口箱區(qū)在該時段內(nèi)的預(yù)約時間窗連續(xù)且各時間窗長度相同，預(yù)約份額確定.

3) 整個過程中，港外集卡的時間消耗主要是從港外堆場到港口的往返行程時間、閘口排隊時間、碼頭停車場等待時間、裝卸箱時間、進與出口箱區(qū)間行程時間.集裝箱的裝卸時間由場橋的運作時間決定并設(shè)為確定值.港外堆場到港口的往返時間與進、出口箱區(qū)間的行程時間統(tǒng)一成為集裝箱運輸時間，并由行程距離與港外集卡平均速度的比值確定.閘口排隊時間和碼頭停車場等待時間統(tǒng)一成港口排隊等待時間，并取各集卡等待時間的平均值[10-12].

4) 該時段的時間長度小于集卡從港外堆場到港口的行程時間最小值的三倍.

5) 所有港外集卡的出發(fā)時刻相同，且不考慮集卡的不確定因素，即假設(shè)所有集卡都能準(zhǔn)時到達[13].

6) 各進、出口箱區(qū)的取、送集裝箱數(shù)量必須在該時間段內(nèi)完成，該時段內(nèi)各進、出口箱區(qū)的時間窗劃分確定且不可改變[14].

1.3 參數(shù)定義

1.4 模型建立

1.4.1 目標(biāo)函數(shù)的確定 目標(biāo)函數(shù)的公式為：

(1)

1.4.2 約束條件 為滿足各碼頭堆場的送、取箱需求以及預(yù)約時間窗限制，約束條件表示如下：

(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ù)所消耗的總時間與調(diào)用集卡數(shù)量的成本最小值.式(2)、(3)與(4)表示一輛集卡單次最多到達兩個不同任務(wù)的箱區(qū)完成送、取箱任務(wù).式(5)表示到達出口箱區(qū)i的集卡數(shù)量必須滿足該箱區(qū)的送箱總量.式(6)表示到達進口箱區(qū)j的集卡數(shù)量必須滿足該箱區(qū)的取箱總量.式(7)表示集卡單次到達兩個箱區(qū)完成送、取箱任務(wù)的數(shù)量，小于所有到達出口箱區(qū)的集卡數(shù)量與所有到達進口箱區(qū)的集卡數(shù)量兩者的較小值.式(8)表示所有集卡都從港外堆場出發(fā).式(9)表示所有集卡完成任務(wù)后都返回到港外堆場.式(10)表示集卡到達進口箱區(qū)完成送箱任務(wù)必須在到達出口箱區(qū)之前.式(11)表示集卡從港外堆場出發(fā)到達出口箱區(qū)i的時刻.式(12)表示集卡從出口箱區(qū)i出發(fā)到達進口箱區(qū)j的時刻.式(13)表示集卡從港外堆場出發(fā)到達進口箱區(qū)j的時刻.式(14)確保集卡從港外堆場出發(fā)到達出口箱區(qū)i的時刻滿足該箱區(qū)的預(yù)約時間窗要求.式(15)確保集卡從出口箱區(qū)i出發(fā)到達進口箱區(qū)j的時刻滿足該箱區(qū)j的預(yù)約時間窗要求.式(16)確保集卡從港外堆場出發(fā)到達進口箱區(qū)j的時刻滿足該箱區(qū)的預(yù)約時間窗要求.

2 算法設(shè)計

遺傳算法是一種應(yīng)用廣泛的啟發(fā)式算法，對于大規(guī)模優(yōu)化問題的求解具有高效穩(wěn)定的特點.本文采用改進的遺傳算法對模型進行求解，將港外集卡的調(diào)用數(shù)量與所有港外集卡所消耗的時間總和來構(gòu)造適應(yīng)度函數(shù)，并通過直接保留精英染色體的方式加快算法的收斂速度.算法的具體步驟如下.

步驟1編碼與初始種群.

染色體的基因為各進出口箱區(qū)的編號，每條染色體采用自然數(shù)編碼，并用自然數(shù)的大小表示進出口箱區(qū)，其中0代表港外堆場.例如(0 1 6 0 2 7 0 3 8 0 4 0 9 5 0 10 0)表示：自然數(shù)1至5為出口箱區(qū)，自然數(shù)6至10為進口箱區(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.為簡化編碼過程，可先不考慮港外堆場的編碼，將染色體直接表示成(1 6 2 7 3 8 4 9 5 10).最后使用兩次隨機數(shù)，在滿足交替排列的前提下，生成各進、出口箱區(qū)獨立的自然數(shù)隨機排列，完成初始化種群.

步驟2港外集卡數(shù)量car_num與消耗總時間all_time的計算.

先為N個出口箱區(qū)安排一輛港外集卡，再按染色體中基因排列的順序調(diào)配港外集卡，若港外集卡只能滿足出口箱區(qū)的時間窗則該港外集卡完成送箱任務(wù)后直接返回港外堆場，另外調(diào)配一輛空集卡來完成進口箱區(qū)的取箱任務(wù).若港外集卡完成送箱任務(wù)后，還能滿足下一個進口箱區(qū)對應(yīng)基因的時間窗，則該集卡繼續(xù)完成取箱任務(wù)，再返回港外堆場.每當(dāng)有集卡返回港外堆場就更新港外集卡數(shù)量和港外集卡消耗總時間：car_num=car_num+1，all_time=all_time+該集卡此次消耗時間.

步驟3適應(yīng)度函數(shù)計算.

通過對步驟2港外集卡數(shù)量car_num與消耗總時間all_time的加權(quán)求得整體總成本，并將其倒數(shù)作為個體的適應(yīng)度值.

步驟4選擇操作.

采用精英策略，直接保留父代中的最優(yōu)個體，并用輪盤賭算法從父代中選擇個體進入子代交配池.

步驟5交叉操作.

由于兩個染色體的基因片段隨機交叉后容易出現(xiàn)基因重復(fù)的現(xiàn)象，故要對交叉后的染色體進行消去沖突操作.并且染色體中的基因是由兩種類型交替排列的方式組成，因此，消去沖突時需要考慮基因的排列方式.具體交叉過程如圖2～圖4所示.

1) 隨機設(shè)定兩個交叉點——點1和點2(如圖2).

圖2 隨機設(shè)定交叉點
Fig.2 Randomly set the intersection

2) 染色體基因片段交叉(如圖3).

圖3 基因片段交叉Fig.3 Gene fragment cross

3) 消去沖突點——點3和點4(如圖4).

圖4 消去沖突Fig.4 Eliminate conflicts

步驟6變異操作.

按照非均勻的變異概率將染色體中的進口碼頭基因與出口碼頭基因分別隨機交換.非均勻變異概率P由進化代數(shù)自動調(diào)整.

其中pmax，pmin為設(shè)定的初始變異概率，Tnow為當(dāng)前進化代數(shù)，Tmax最大進化代數(shù).

步驟7終止條件.

迭代到設(shè)定次數(shù)時終止算法.

3 算例分析

3.1 算例描述

表1 各堆場間的行程時間表Tab.1 Itinerary schedule between terminal yards min

表2 各碼頭堆場集港信息Tab.2 Terminal yards information

3.2 結(jié)果分析

該算例實驗在Anaconda下用Python編程求解，并在Intel 酷睿i5-4200u處理器，主頻1.6 GHz，內(nèi)存4 GB的計算機上運行.經(jīng)過200次迭代與經(jīng)過300次迭代，得到的收斂結(jié)果分別如圖5和圖6所示.

圖5 GA算法進化200代的結(jié)果Fig.5 GA algorithm evolution 200 generation results

圖6 GA算法進化300代的結(jié)果Fig.6 GA algorithm evolution 300 generation results

從圖中結(jié)果分析得出，隨著迭代次數(shù)的增加，種群中的染色體逐漸收斂穩(wěn)定于最優(yōu)值.當(dāng)進化到300代時，輸出的算例最優(yōu)值達到最小并且處于收斂狀態(tài)，此時得出的港外集卡調(diào)配方案見表3.港外集卡消耗總時間最優(yōu)值為638 min，調(diào)配的集卡數(shù)量為10輛，最小成本為11 380.得到了在預(yù)約窗口下的港外集卡最優(yōu)調(diào)度方案，達到了節(jié)省系統(tǒng)作業(yè)成本的目的，從而證明該算法是有效的.

表3 港外集卡最優(yōu)調(diào)配方案表Tab.3 The optimal scheduling of trucks

運用同樣的算例，在相同的設(shè)備下，采用蟻群算法求解，并與本文遺傳算法求解結(jié)果進行比較，其結(jié)果見表4.

從表中可以看出，在相同算例下，兩種算法都得到了相同的最優(yōu)結(jié)果，但在不同迭代次數(shù)間，用遺傳算法求解的結(jié)果相對于蟻群算法更貼近于最優(yōu)結(jié)果，并且迭代的速度更快.

3.3 算例規(guī)模隨機性分析

為避免算例規(guī)模的單一性造成隨機性結(jié)果，將上述算法應(yīng)用于不同規(guī)模的算例進行分析，如將上述問題擴展為算例1和算例2.算例1：30個箱區(qū)，其中 10個進口箱區(qū)，份額為20個集裝箱；20個出口箱區(qū)，份額為32個集裝箱.算例2：50個箱區(qū)，其中20個進口箱區(qū)，份額為40個集裝箱；30個出口箱區(qū)，份額為40個集裝箱.

表4 ACO與GA結(jié)果比較Tab.4 Comparison of ACO and GA results

新增的兩個算例，在算法進化200代后，收斂結(jié)果如圖7和圖8所示.對于30個箱區(qū)算例，港外集卡消耗總時間最優(yōu)值為2 176 min，調(diào)配的集卡數(shù)量為35輛，最小成本為39 260.對于50個箱區(qū)算例，港外集卡消耗總時間最優(yōu)值為3 200 min，調(diào)配的集卡數(shù)量為54輛，最小成本為59 000.兩種算例都得到了在預(yù)約窗口下的港外集卡最優(yōu)調(diào)度方案，從而證明該算法通過了隨機性驗證，算法是有效的.

圖7 30個箱區(qū)GA算法進化結(jié)果Fig.7 30 container block GA algorithm evolution results

圖8 50個箱區(qū)GA算法進化結(jié)果Fig.8 50 container block GA algorithm evolution results

4 結(jié)論

在港口與船舶以及港外堆場都建有預(yù)約機制的情況下，港方能夠獲取船舶靠港時間、裝卸箱數(shù)量等集、疏港信息，并以此為依據(jù)，綜合考慮港外堆場的實際運輸能力，制定合理的集卡送取箱預(yù)約計劃.將有效降低集卡非平穩(wěn)到達情況下造成的港口排隊擁堵，減少系統(tǒng)碳排放量，提高集疏港作業(yè)效率.本文針對預(yù)約時間窗下港外集卡多進、出口箱區(qū)的調(diào)度問題，建立了數(shù)學(xué)模型，并用改進的遺傳算法求解.算例結(jié)果證實模型是有效的，設(shè)計的遺傳算法也能較快地收斂到全局最優(yōu)解.通過合理調(diào)配集卡在某時段內(nèi)到達的進出口箱區(qū)，能夠減少集卡數(shù)量與所有集卡的消耗時間，提高集卡的運輸效率，降低港口設(shè)施空耗.這些優(yōu)化結(jié)果可以為將來的港外集卡送、取箱調(diào)度提供理論參考依據(jù).本文沒有將港外集卡在閘口和堆場處的實際排隊規(guī)律、時間窗滾動分布、場橋作業(yè)規(guī)律等問題構(gòu)建到模型中，因此需要對這些問題做進一步的綜合研究.