基于預(yù)約策略的港外集卡送取箱雙目標(biāo)優(yōu)化模型

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

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

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

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

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

1.1 問題描述

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

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

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

1.2 問題假設(shè)

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

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

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

4) 該時(shí)段的時(shí)間長度小于集卡從港外堆場到港口的行程時(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.3 參數(shù)定義

1.4 模型建立

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

(1)

1.4.2 約束條件 為滿足各碼頭堆場的送、取箱需求以及預(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ù)量兩者的較小值.式(8)表示所有集卡都從港外堆場出發(fā).式(9)表示所有集卡完成任務(wù)后都返回到港外堆場.式(10)表示集卡到達(dá)進(jìn)口箱區(qū)完成送箱任務(wù)必須在到達(dá)出口箱區(qū)之前.式(11)表示集卡從港外堆場出發(fā)到達(dá)出口箱區(qū)i的時(shí)刻.式(12)表示集卡從出口箱區(qū)i出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻.式(13)表示集卡從港外堆場出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻.式(14)確保集卡從港外堆場出發(fā)到達(dá)出口箱區(qū)i的時(shí)刻滿足該箱區(qū)的預(yù)約時(shí)間窗要求.式(15)確保集卡從出口箱區(qū)i出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻滿足該箱區(qū)j的預(yù)約時(shí)間窗要求.式(16)確保集卡從港外堆場出發(fā)到達(dá)進(jìn)口箱區(qū)j的時(shí)刻滿足該箱區(qū)的預(yù)約時(shí)間窗要求.

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

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

步驟1編碼與初始種群.

染色體的基因?yàn)楦鬟M(jìn)出口箱區(qū)的編號，每條染色體采用自然數(shù)編碼，并用自然數(shù)的大小表示進(jìn)出口箱區(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為進(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.為簡化編碼過程，可先不考慮港外堆場的編碼，將染色體直接表示成(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ù)后直接返回港外堆場，另外調(diào)配一輛空集卡來完成進(jìn)口箱區(qū)的取箱任務(wù).若港外集卡完成送箱任務(wù)后，還能滿足下一個(gè)進(jìn)口箱區(qū)對應(yīng)基因的時(shí)間窗，則該集卡繼續(xù)完成取箱任務(wù)，再返回港外堆場.每當(dāng)有集卡返回港外堆場就更新港外集卡數(shù)量和港外集卡消耗總時(shí)間：car_num=car_num+1，all_time=all_time+該集卡此次消耗時(shí)間.

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

通過對步驟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)象，故要對交叉后的染色體進(jìn)行消去沖突操作.并且染色體中的基因是由兩種類型交替排列的方式組成，因此，消去沖突時(shí)需要考慮基因的排列方式.具體交叉過程如圖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ù)自動調(diào)整.

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

步驟7終止條件.

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

3 算例分析

3.1 算例描述

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

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

3.2 結(jié)果分析

該算例實(shí)驗(yàn)在Anaconda下用Python編程求解，并在Intel 酷睿i5-4200u處理器，主頻1.6 GHz，內(nèi)存4 GB的計(jì)算機(jī)上運(yùn)行.經(jīng)過200次迭代與經(jīng)過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)配方案見表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é)果見表4.

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

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

為避免算例規(guī)模的單一性造成隨機(jī)性結(jié)果，將上述算法應(yīng)用于不同規(guī)模的算例進(jì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所示.對于30個(gè)箱區(qū)算例，港外集卡消耗總時(shí)間最優(yōu)值為2 176 min，調(diào)配的集卡數(shù)量為35輛，最小成本為39 260.對于50個(gè)箱區(qū)算例，港外集卡消耗總時(shí)間最優(yōu)值為3 200 min，調(diào)配的集卡數(shù)量為54輛，最小成本為59 000.兩種算例都得到了在預(yù)約窗口下的港外集卡最優(yōu)調(diào)度方案，從而證明該算法通過了隨機(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

4 結(jié)論

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