羅志勇

(北京鐵路局豐臺(tái)貨運(yùn)中心,北京116026)

1 引言

甩掛運(yùn)輸利用并行工作的原理大大縮短了牽引車(chē)等待貨物裝卸及其在物流中心排隊(duì)的時(shí)間,提高了牽引車(chē)的作業(yè)效率。

國(guó)外關(guān)于甩掛作業(yè)調(diào)度的研究起步較早。Caris et al提出了基于插入法的兩階段啟發(fā)式算法,對(duì)具有時(shí)間窗約束的集裝箱甩掛運(yùn)輸作業(yè)調(diào)度問(wèn)題進(jìn)行求解。Lin et al應(yīng)用模擬退火算法來(lái)求解甩掛作業(yè)調(diào)度問(wèn)題,所獲得的基準(zhǔn)問(wèn)題求解結(jié)果優(yōu)于運(yùn)用禁忌搜索的求解結(jié)果。Lin et al構(gòu)建了放松車(chē)輛數(shù)量約束的甩掛作業(yè)調(diào)度數(shù)學(xué)模型,以從更大的鄰域內(nèi)搜索是否存在可進(jìn)一步減少運(yùn)送距離的可行解,并設(shè)計(jì)了模擬退火算法對(duì)其進(jìn)行求解。Derigs et al對(duì)于具有時(shí)間窗約束的甩掛作業(yè)調(diào)度問(wèn)題,提出了由局部搜索、大規(guī)模鄰域搜索和標(biāo)準(zhǔn)的泛?jiǎn)l(fā)式控制策略相結(jié)合的混合算法進(jìn)行求解。相比國(guó)外眾多研究成果,國(guó)內(nèi)關(guān)于甩掛運(yùn)輸調(diào)度優(yōu)化方面的研究則剛剛起步,研究成果較少。胡志華等建立了在集裝箱集散環(huán)境下空重箱循環(huán)甩掛的調(diào)度優(yōu)化模型,并設(shè)計(jì)兩階段優(yōu)化算法進(jìn)行求解。胡志華等為甩掛運(yùn)輸帶有子回路的新型路徑優(yōu)化問(wèn)題建立了0/1整數(shù)規(guī)劃模型,采用混合進(jìn)化算法進(jìn)行求解。

基于以上研究成果,本文在軸輻式網(wǎng)絡(luò)中的一點(diǎn)多線甩掛運(yùn)輸組織模式下,對(duì)任務(wù)的作業(yè)路徑進(jìn)行分類(lèi)轉(zhuǎn)換后建立了考慮多作業(yè)路徑的集裝箱甩掛運(yùn)輸牽引車(chē)調(diào)度優(yōu)化模型,并設(shè)計(jì)了啟發(fā)式算法的模擬退火算法求解。算例分析驗(yàn)證了模型與算法的有效性與實(shí)用性。

2 問(wèn)題描述

2.1 運(yùn)輸網(wǎng)絡(luò)描述

每個(gè)甩掛運(yùn)輸網(wǎng)絡(luò)由若干個(gè)軸輻式子網(wǎng)絡(luò)構(gòu)成,每個(gè)軸輻式子網(wǎng)絡(luò)的中心為甩掛運(yùn)輸中心,客戶(hù)點(diǎn)分布在甩掛中心周?chē)?。設(shè)軸輻式子網(wǎng)絡(luò)結(jié)構(gòu)圖G＝(V,A),其中,V＝{0,1,…,n},頂點(diǎn)0表示甩掛中心,頂點(diǎn)1,…,n表示客戶(hù)節(jié)點(diǎn),A表示頂點(diǎn)0,1,…,n之間距離弧的集合。圖1表示的是一個(gè)軸輻式子網(wǎng)絡(luò)圖。

在圖1中,0表示甩掛中心,1到n表示客戶(hù)節(jié)點(diǎn)。牽引車(chē)每天從甩掛中心出發(fā)去執(zhí)行取箱任務(wù)或送箱任務(wù),待所有任務(wù)執(zhí)行完之后返回甩掛中心。

2.2 任務(wù)路徑描述

圖1 軸輻式子網(wǎng)絡(luò)圖

取箱任務(wù)是指若某客戶(hù)點(diǎn)處有裝卸完畢的掛車(chē),牽引車(chē)到達(dá)該客戶(hù)點(diǎn)后立即掛上重箱后送回甩掛中心。送箱任務(wù)是指某客戶(hù)點(diǎn)處有貨物等待裝箱,牽引車(chē)拖帶一個(gè)空箱到達(dá)指定客戶(hù)點(diǎn)后甩下空箱即可去完成其它任務(wù),待該點(diǎn)集裝箱裝卸完畢后成為一個(gè)新的取箱任務(wù)。在執(zhí)行每個(gè)任務(wù)時(shí),牽引車(chē)的來(lái)源是不確定的,若上一個(gè)任務(wù)為取箱任務(wù)則牽引車(chē)的來(lái)源為甩掛中心;若上一個(gè)任務(wù)為送箱任務(wù),則牽引車(chē)的來(lái)源為上一個(gè)任務(wù)的客戶(hù)點(diǎn)。在途牽引車(chē)經(jīng)過(guò)的路徑根據(jù)前后任務(wù)節(jié)點(diǎn)可以歸為以下四類(lèi):(1)上一任務(wù)是取箱任務(wù),下一任務(wù)是取箱任務(wù);(2)上一任務(wù)是取箱任務(wù),下一任務(wù)是送箱任務(wù);(3)上一任務(wù)是送箱任務(wù),下一任務(wù)是取箱任務(wù);(4)上一任務(wù)是送箱任務(wù),下一任務(wù)是送箱任務(wù)。這四類(lèi)路徑可由圖2表示。

圖2 四種車(chē)輛路徑類(lèi)型

圖2中頂點(diǎn)0代表甩掛中心,頂點(diǎn)1、2表示客戶(hù)需求點(diǎn)。實(shí)線箭頭表示執(zhí)行當(dāng)前任務(wù)行駛路線,虛線箭頭表示執(zhí)行上(下)一個(gè)任務(wù)行駛路線。為便于求解,本文將每個(gè)任務(wù)的出發(fā)點(diǎn)和終到點(diǎn)結(jié)合成一點(diǎn),則圖2的四種車(chē)輛路徑類(lèi)型轉(zhuǎn)變?yōu)閳D3。

圖3 四種車(chē)輛路徑類(lèi)型轉(zhuǎn)換圖

在圖3中,1-0表示從客戶(hù)點(diǎn)1到甩掛中心的取箱任務(wù),0-0表示牽引車(chē)從甩掛中心到甩掛中心的虛擬行駛路徑。從圖3中的四種車(chē)輛路徑類(lèi)型可以看出,牽引車(chē)行駛路線如圖4所示。與傳統(tǒng)多重旅行商問(wèn)題不同的是,任務(wù)節(jié)點(diǎn)是由出發(fā)點(diǎn)和終到點(diǎn)結(jié)合后形成的一點(diǎn),且該牽引車(chē)行駛路線可能存在虛擬路徑。

圖4 牽引車(chē)行駛路線

3 混合整數(shù)規(guī)劃模型建立

3.1 假設(shè)條件

根據(jù)甩掛中心實(shí)際操作情況及解決實(shí)際問(wèn)題的需要,做出如下假設(shè):

(1)所有的任務(wù)在調(diào)度之前都已確定,中途不會(huì)增加其它任務(wù);(2)所有牽引車(chē)和掛車(chē)都采用統(tǒng)一標(biāo)準(zhǔn)尺寸;(3)一輛牽引車(chē)一次只拖掛一輛掛車(chē);(4)牽引車(chē)拖掛重箱和拖掛空箱的速度相同;(5)牽引車(chē)拖上掛車(chē)以及取下掛車(chē)的時(shí)間不計(jì);(6)牽引車(chē)每天從甩掛中心出發(fā),最后返回到甩掛中心。

3.2 參數(shù)說(shuō)明

M:任務(wù)的數(shù)量;K:牽引車(chē)的數(shù)量;tij:從任務(wù)i到任務(wù)j的時(shí)間;fi:執(zhí)行任務(wù)i所需的時(shí)間;wi:在執(zhí)行任務(wù)i時(shí)的等待時(shí)間;ti:到達(dá)任務(wù)i的對(duì)應(yīng)客戶(hù)點(diǎn)的時(shí)間;Rk:牽引車(chē)k的一天工作時(shí)間;[ETi,LTi]:表示任務(wù)i要求開(kāi)始的時(shí)間窗。

3.3 模型建立

目標(biāo)函數(shù):

式(1)為目標(biāo)函數(shù),表示使?fàn)恳?chē)的數(shù)量最少和總的行駛時(shí)間最短,C為一個(gè)足夠大的常數(shù),故保證了減少牽引車(chē)數(shù)量的優(yōu)先級(jí)高于總的行駛時(shí)間最短;式(2)表示從甩掛中心出發(fā)的牽引車(chē)數(shù)量不大于車(chē)輛總數(shù);式(3)表示每輛牽引車(chē)每天從甩掛中心出發(fā),執(zhí)行完一天任務(wù)后回到甩掛中心;式(4)表示每個(gè)任務(wù)僅且只被執(zhí)行一次;式(5)表示每輛牽引車(chē)的行駛時(shí)間不能超過(guò)其一天的工作時(shí)間;式(6)表示任務(wù)的被完成的先后順序約束;式(7)表示任務(wù)的開(kāi)始執(zhí)行時(shí)間必須在時(shí)間窗的范圍之內(nèi);式(8)表示決策變量。

3.4 懲罰成本函數(shù)

本文的時(shí)間窗采用軟時(shí)間窗。牽引車(chē)開(kāi)始執(zhí)行任務(wù)i的時(shí)間若在ti1之前或ti2之后,將付出較高的懲罰成本固定值M;若在[ti3,ti4]范圍內(nèi),懲罰成本為0;若在[ti1,ti3]范圍內(nèi),單位時(shí)間的懲罰成本為a;在[ti4,ti2]時(shí)間范圍內(nèi)到達(dá),單位時(shí)間的懲罰成本為b。圖5為第k輛牽引車(chē)執(zhí)行第i個(gè)任務(wù)所付出的懲罰成本函數(shù)圖像。式(9)為相應(yīng)的懲罰成本函數(shù)。

圖5 懲罰成本函數(shù)圖

4 基于啟發(fā)式規(guī)則的模擬退火算法求解

本文采用二維解矩陣的編碼方式進(jìn)行解的表示。在解的變換過(guò)程中,反復(fù)交換二維解矩陣中兩個(gè)不等于0的值以得到新解,這種解的反復(fù)變換過(guò)程類(lèi)似于模擬退火算法的加溫過(guò)程。圖6為基于啟發(fā)式規(guī)則的模擬退火算法流程圖。

圖6 基于啟發(fā)式規(guī)則的模擬退火算法流程圖

4.1 啟發(fā)式規(guī)則生成初始解

將n個(gè)任務(wù)按照可接受時(shí)間窗上限從早到晚進(jìn)行排序,形成任務(wù)集合M＝{1,2,…,n},將所有牽引車(chē)形成集合K＝{1,2,…,m}。設(shè)計(jì)啟發(fā)式規(guī)則生成初始解流程圖如圖7,具體實(shí)現(xiàn)步驟如下:

Step 1:設(shè)未完成任務(wù)集L＝M,任務(wù)i＝1(i∈M),牽引車(chē)j＝1(j∈K),進(jìn)入step 2;

Step 2:將任務(wù)集L按照時(shí)間窗順序進(jìn)行從小到大排序,進(jìn)入step 3;

Step 3:依次判斷任務(wù)i是否能加入到第j輛牽引車(chē)的任務(wù)集中,判斷依據(jù)為,是否滿(mǎn)足時(shí)間窗要求。若滿(mǎn)足,則L＝L/i,進(jìn)入step 4;否則,令j＝j(luò)＋1,重復(fù)執(zhí)行step 3;

Step 4:判斷L是否為空集,若是,則輸出初始解;否則令i＝i＋1,轉(zhuǎn)到Step 3。

圖7 啟發(fā)式算法流程圖

4.2 解的編碼方式

二維解矩陣中的值為任務(wù)編號(hào),每一行表示一輛牽引車(chē)的行駛路徑。圖8表示一個(gè)需使用4輛牽引車(chē),完成20個(gè)任務(wù)的甩掛運(yùn)輸方案,其中這四輛牽引車(chē)的行駛路徑分別為5-6-8-16-15;7-9-14-17-18;2-4-10-13-20;1-3-11-12-19。

圖8 解的編碼方式

但是,按照上述編碼方式,運(yùn)輸方案中的牽引車(chē)數(shù)量和每輛牽引車(chē)所完成的任務(wù)數(shù)是固定的,不利于保證解變換時(shí)搜索到全部可行解。為了擴(kuò)大解的搜索空間,對(duì)解矩陣進(jìn)行放大,每行每列增加足夠的0位。0并無(wú)實(shí)際意義,僅起到擴(kuò)大解的規(guī)模的作用。圖8的解矩陣擴(kuò)大規(guī)模后見(jiàn)圖9,此時(shí)該運(yùn)輸方案的牽引車(chē)數(shù)量由原來(lái)的4輛變?yōu)閇3,6]范圍內(nèi)的任一整數(shù)值,每輛牽引車(chē)完成的任務(wù)數(shù)也由原來(lái)的5個(gè)變?yōu)閇2,7]范圍內(nèi)的任一整數(shù)值,極大擴(kuò)大了可行解規(guī)模。

4.3 解變換

采用產(chǎn)生隨機(jī)數(shù)方法交換矩陣中的兩個(gè)數(shù),若生成的兩個(gè)數(shù)對(duì)應(yīng)在解矩陣中的值都是0,則重新產(chǎn)生兩個(gè)數(shù),直到不都為0為止,生成新解。在圖10中,解的規(guī)模是42,在[1,42]范圍內(nèi)隨機(jī)產(chǎn)生兩個(gè)整數(shù),確定兩個(gè)位置,在當(dāng)前解中將這兩個(gè)位置的數(shù)值進(jìn)行對(duì)換。假設(shè)產(chǎn)生的兩個(gè)數(shù)是9和18,則在解矩陣中,把第9個(gè)元素和第18個(gè)元素對(duì)調(diào),其對(duì)應(yīng)數(shù)值分別為9和13,對(duì)調(diào)9和13的位置產(chǎn)生新的解矩陣。

圖9 擴(kuò)大規(guī)模后的解

圖10 新解生成方法

5 算例分析

以某公司甩掛中心的運(yùn)營(yíng)數(shù)據(jù)為基礎(chǔ),對(duì)其每日的運(yùn)輸方案進(jìn)行優(yōu)化。為了保證算例分析的可重復(fù)性及其與實(shí)際分布規(guī)律的擬合程度,本文使用matlab中的unidrnd函數(shù)隨機(jī)生成客戶(hù)點(diǎn)的坐標(biāo),用unidrnd函數(shù)生成的隨機(jī)數(shù)呈離散均勻分布。二維均勻分布的函數(shù)為,x,y為自變量。設(shè)甩掛中心的坐標(biāo)為表1為某次隨機(jī)生成的客戶(hù)點(diǎn)坐標(biāo),此時(shí)a＝c＝0,b＝d＝30,甩掛中心的坐標(biāo)為(15,15)。

表1 客戶(hù)點(diǎn)位置

每個(gè)客戶(hù)點(diǎn)所包含的取箱任務(wù)量和送箱任務(wù)量為[0,a]內(nèi)的任意隨機(jī)整數(shù),可用matlab中的randpint函數(shù)實(shí)現(xiàn)。表2為表1中所有客戶(hù)隨機(jī)生成的任務(wù)數(shù)量。本文取a＝2。

表2 客戶(hù)點(diǎn)任務(wù)量

根據(jù)客戶(hù)時(shí)間窗的特性,使用unifrnd函數(shù)隨機(jī)生成每個(gè)任務(wù)的要求開(kāi)始時(shí)間,然后使用round函數(shù)保證生成的隨機(jī)數(shù)為整數(shù)。在每個(gè)任務(wù)的可接受時(shí)間窗等于要求的時(shí)間窗減去或加上一個(gè)固定的時(shí)間t0(t0≠0)。本文取t0＝30。表3為對(duì)表2中所有任務(wù)隨機(jī)生成的時(shí)間窗。

牽引車(chē)每天從甩掛中心開(kāi)始發(fā)車(chē)的時(shí)刻為6:00,平均以40km/h的速度行駛,甩掛中心與客戶(hù)點(diǎn)之間和客戶(hù)與客戶(hù)之間的歐氏距離等于坐標(biāo)距離的兩倍,牽引車(chē)早于任務(wù)的時(shí)間窗上限和晚于時(shí)間窗下限的懲罰系數(shù)為50。

表3 各任務(wù)對(duì)應(yīng)的時(shí)間窗

根據(jù)上述數(shù)據(jù),設(shè)計(jì)結(jié)合啟發(fā)式規(guī)則的模擬退火算法,對(duì)模型進(jìn)行求解。初始溫度T0＝1000,內(nèi)循環(huán)次數(shù)L＝500－T/4(T為當(dāng)前溫度),終止溫度Tend＝1,降溫速率α＝0.8。求得最優(yōu)解為:需要4輛牽引車(chē),執(zhí)行任務(wù)所需時(shí)間為6968,目標(biāo)函數(shù)的收斂情況如圖11。從圖11可以看出,算法在9000次左右收斂到極值點(diǎn)6986。收斂速度很快,而且算法比較穩(wěn)定。

圖11 模擬退火算法收斂圖

牽引車(chē)的最優(yōu)行駛路線如表4。

表4 牽引車(chē)執(zhí)行任務(wù)順序

數(shù)據(jù)結(jié)果表明,提出的模型和算法能夠?yàn)闋恳?chē)的調(diào)度提供最優(yōu)方案。

另外,在甩掛運(yùn)輸?shù)膶?shí)際調(diào)度規(guī)則用最多的是基于時(shí)間緊迫度的啟發(fā)式規(guī)則,即空的牽引車(chē)每次都去執(zhí)行時(shí)間上最緊迫的任務(wù)。使用matlab編程可得,實(shí)際調(diào)度規(guī)則得到的執(zhí)行任務(wù)所需時(shí)間為8642,牽引車(chē)的執(zhí)行任務(wù)順序如表5。

與實(shí)際調(diào)度規(guī)則進(jìn)行比較可知,本文的模型和算法從完成所有任務(wù)的時(shí)間最少上進(jìn)行考慮,得到的執(zhí)行任務(wù)時(shí)間比實(shí)際調(diào)度規(guī)則的執(zhí)行任務(wù)時(shí)間減少了19.37%。算例結(jié)果表明,本文的模型和求解算法對(duì)甩掛作業(yè)調(diào)度人員具有一定的實(shí)際指導(dǎo)意義。

表5 實(shí)際調(diào)度規(guī)則執(zhí)行任務(wù)順序

6 結(jié)論

本文在軸輻式網(wǎng)絡(luò)中的一點(diǎn)多線甩掛運(yùn)輸組織模式下,考慮了多作業(yè)路徑并進(jìn)行分類(lèi)轉(zhuǎn)換后建立集裝箱甩掛運(yùn)輸牽引車(chē)調(diào)度優(yōu)化模型,并設(shè)計(jì)了基于啟發(fā)式規(guī)則的模擬退火算法對(duì)模型進(jìn)行求解,借助matlab編程得以實(shí)現(xiàn)。通過(guò)算例分析與實(shí)際調(diào)度規(guī)則進(jìn)行比較,運(yùn)算結(jié)果證明了模型和算法的有效性和實(shí)用性。進(jìn)一步的研究將集中于甩掛運(yùn)輸任務(wù)集動(dòng)態(tài)調(diào)度優(yōu)化,即調(diào)度過(guò)程中可能增加其它任務(wù)。

[1]Caris A.,Janssens G.K.A local search heuristic for the pre-and end-haulage of intermodal container terminals[J].Computers&Operations Research,2009,36(10).

[2]Lin Shih Wei,Yu Vincent F,Chou Shuo Yan.Solving the truck and trailer routing problem based on a simulated annealing heuristic[J].Computers&Operations Research,2009,36(5).

[3]Lin Shih Wei,Yu Vincent F,Chou Shuo Yan.A note on the truck and trailer routing problem[J].Expert Systems with Applications,2010,37(1).

[4]Lin Shih Wei,Yu Vincent F,Lu Chung Cheng.A simulated annealing heuristic for the truck and trailer routing problem with time windows[J].Expert Systems With Applications,2011,38(12).

[5]Derigs Ulrich,Pullmann Markus,Vogel Ulrich.Truck and trailer routing-Problems,heuristics and computational experience[J].Computers&Operations Research,2013,40(2).

[6]胡志華等.集裝箱集散的空重箱循環(huán)甩掛調(diào)度方法[J].武漢理工大學(xué)學(xué)報(bào),2012,(10).

[7]胡志華.集裝箱碼頭間互拖的集卡甩掛運(yùn)輸調(diào)度問(wèn)題[J].重慶交通大學(xué)學(xué)報(bào),2013,32(2).

[8]胡志華等.基于混合進(jìn)化算法的甩掛配送問(wèn)題[J].公路交通科技,2013,30(5).