王吉生,羅志勇
(1.南昌交通學(xué)院,南昌 330100;2.中國鐵路北京局集團(tuán)有限公司豐臺(tái)貨運(yùn)中心,北京 102300)
甩掛運(yùn)輸是指在牽引車與掛車在自由搭配的環(huán)境中,牽引車拖帶掛車至目的地將掛車甩下后,拖掛新的掛車或者不掛任何掛車運(yùn)往另一個(gè)目的地的運(yùn)輸組織方式。甩掛運(yùn)輸充分發(fā)揮了并行工作的優(yōu)勢(shì),大大縮短了牽引車等待貨物裝卸及在物流中心排隊(duì)的時(shí)間,從而使得牽引車的作業(yè)效率明顯提高。
目前,相關(guān)學(xué)者設(shè)計(jì)了許多關(guān)于甩掛運(yùn)輸方面的研究成果。如王天予[1]等人分析了仿真技術(shù)實(shí)施甩掛運(yùn)輸優(yōu)化。谷首更[2]在貪婪算法的基礎(chǔ)進(jìn)行優(yōu)化改進(jìn),針對(duì)港口集裝箱的運(yùn)輸需求,建立了對(duì)應(yīng)的調(diào)度模型。王寶遠(yuǎn)[3]分析甩箱運(yùn)輸成本組成以及特點(diǎn),選取甩箱運(yùn)輸成本、時(shí)效性2個(gè)主要因素為研究對(duì)象,確定甩箱運(yùn)輸模式配送成本最低的目標(biāo)優(yōu)化模型。
然而,現(xiàn)有文獻(xiàn)中的優(yōu)化算法很少將任務(wù)的時(shí)間緊迫度考慮在內(nèi)。為此,本文以蘇寧物流中心為例,基于時(shí)間緊迫度來優(yōu)化甩掛運(yùn)輸牽引車調(diào)度,利用啟發(fā)式算法求解在最短的時(shí)間內(nèi)完成已知任務(wù)的模型已知任務(wù)在最短時(shí)間能夠完成的目標(biāo)進(jìn)行求解。
設(shè)軸輻式物流網(wǎng)絡(luò)圖G=(V,A),其中,V={0,1,...,n},點(diǎn)0為物流運(yùn)輸?shù)乃熘行模?,...,n表示不同任務(wù)節(jié)點(diǎn)。A表示點(diǎn)1,...,n之間的距離弧集。具體的結(jié)構(gòu)圖如圖1所示。
圖1 軸輻射子網(wǎng)絡(luò)圖
圖1中,0為甩掛中心,1到n為與甩掛中心進(jìn)行貨物運(yùn)送銜接的點(diǎn)即客戶節(jié)點(diǎn)。每天牽引車都需從圖中的0點(diǎn)即配送中心點(diǎn)出發(fā),去取箱子或者是送箱子,這一任務(wù)稱為取箱任務(wù)或者送箱任務(wù)。取箱任務(wù)為在1到n點(diǎn)有已經(jīng)裝滿好貨物的掛車,牽引車立刻過去把掛車掛上,把它運(yùn)回到0點(diǎn)甩掛中心。送箱任務(wù)為在1到n點(diǎn)有貨物需要裝載,牽引車馬上掛上空的掛車即空箱去需要裝載貨物的客戶點(diǎn),放下空的掛車去下一個(gè)任務(wù)點(diǎn)完成其他的事情,當(dāng)這個(gè)需要裝載貨物的客戶點(diǎn)把貨物裝好后,那么這個(gè)客戶點(diǎn)就變成新的取箱點(diǎn)。
每一次執(zhí)行任務(wù),牽引車的出發(fā)點(diǎn)都是不確定的[4]。若上次的任務(wù)是取箱,那么牽引車的出發(fā)點(diǎn)就是0點(diǎn)即甩掛中心;若上次的任務(wù)是送箱,那么牽引車的出發(fā)點(diǎn)就是在上次任務(wù)客戶點(diǎn)。
根據(jù)任務(wù)點(diǎn)的需求,在上一個(gè)任務(wù)和下一個(gè)任務(wù)的設(shè)置中,可以把牽引車的行駛路徑分為四類:
1)上一任務(wù)是取箱任務(wù),下一任務(wù)是取箱任務(wù);
2)上一任務(wù)是取箱任務(wù),下一任務(wù)是送箱任務(wù);
3)上一任務(wù)是送箱任務(wù),下一任務(wù)是取箱任務(wù);
4)上一任務(wù)是送箱任務(wù),下一任務(wù)是送箱任務(wù)。
這四類路徑類型如圖2所示。
圖2 四種車輛路徑類型
圖2中,0為甩掛中心,1和2均為客戶需求點(diǎn)。實(shí)線箭頭為加入本次路程計(jì)算的路線,虛線箭頭為上(下)一個(gè)任務(wù)行駛路線,即不加入本次路程計(jì)算的路線。牽引車在途行進(jìn)的全程路線由該四種類型路線連接而成[5]。
本論文考慮甩掛運(yùn)輸任務(wù)量均源于一個(gè)物流園區(qū),所有的發(fā)貨貨物均需在甩掛中心集貨后再發(fā)往下一個(gè)途經(jīng)點(diǎn),所有收貨貨物也均需先運(yùn)到某城市的甩掛運(yùn)輸中心后再分送到各個(gè)收貨點(diǎn)。假設(shè)先規(guī)定每個(gè)任務(wù)完成需要的時(shí)間,再開始安排所有的調(diào)度工作,現(xiàn)僅考慮用一輛牽引車行駛完成所有任務(wù),求完成總時(shí)間最短的方案。
根據(jù)物流園區(qū)實(shí)際運(yùn)轉(zhuǎn)情況,作出以下假設(shè):
1)所有牽引車和掛車都采用統(tǒng)一標(biāo)準(zhǔn)尺寸;
2)一輛牽引車一次只拖掛一輛掛車;
3)牽引車拖掛重箱和拖掛空箱的速度相同;
4)牽引車拖上掛車以及取下掛車的時(shí)間不計(jì);
5)牽引車每天從甩掛中心出發(fā),最后返回到甩掛中心。
模型中的符號(hào)定義如下:m1表示第一種路徑類型的任務(wù)數(shù);m2表示第二種路徑類型的任務(wù)數(shù);m3表示第三種路徑類型的任務(wù)數(shù);m4表示第四種路徑類型的任務(wù)數(shù);M表示所有任務(wù)集合,且滿足M=m1∪m2∪m3∪m4;tij表示i到j(luò)的行駛時(shí)間與在j地的等待時(shí)間之和,則存在:
目標(biāo)函數(shù)表示為:
約束條件表示為:
式中,t1表示完成從甩掛中心出發(fā)的取箱任務(wù)的所需時(shí)間;t2表示完成從甩掛中心出發(fā)的送箱任務(wù)所需的時(shí)間;t3表示完成從任務(wù)節(jié)點(diǎn)出發(fā)的取箱任務(wù)所需的時(shí)間;t4表示完成從任務(wù)節(jié)點(diǎn)出發(fā)的送箱任務(wù)所需的時(shí)間;mint表示完成總時(shí)間最短的目標(biāo)函數(shù);式(4)表示每個(gè)任務(wù)僅且只被完成一次;式(5)表示任務(wù)行駛路線決策變量的0~1約束。
本文根據(jù)每個(gè)任務(wù)的時(shí)間緊迫度選擇下個(gè)執(zhí)行任務(wù),緊迫度Em由公式得出。在每執(zhí)行完一個(gè)任務(wù)之后都更新剩余未完成任務(wù)的時(shí)間緊迫度,在這些剩余未完成的任務(wù)中,優(yōu)先完成緊迫度最高的,圖3為算法流程圖。
圖3 啟發(fā)式算法流程圖
具體實(shí)際操作步驟進(jìn)行如下:
Step1:初始值:完成所有任務(wù)的總時(shí)間t=0,未完成任務(wù)集L=M,根據(jù)送箱任務(wù)轉(zhuǎn)化而來的取箱任務(wù)數(shù)i=1,進(jìn)入step2;
Step2:計(jì)算所有未完成任務(wù)的時(shí)間緊迫度Em=a-(ETm-Tnow),m∈L,其中a為一常數(shù),在本文中將設(shè)a=10,ETm設(shè)置為任務(wù)m的最早開始時(shí)間,Tnow為當(dāng)前時(shí)間,進(jìn)入Step3;
Step3:選擇一個(gè)執(zhí)行任務(wù)next_m=max{Em,m∈M}。
Step3.1:如果next_m∈Q,把完成任務(wù)next_m所需的時(shí)間加入到t中,L=L/next_m,進(jìn)入Step4;
Step3.2:如果next_m∈S,在t中加入完成任務(wù)next_m所需的時(shí)間,L=L/next_m,一個(gè)新的取箱任務(wù)qm+i將產(chǎn)生,然后再判斷此次取箱任務(wù)是否需要在當(dāng)日完成,若是,則把qm+i的時(shí)間窗計(jì)算出來,本文最早開始時(shí)間設(shè)置為ETqm+i=任務(wù)next_m的執(zhí)行時(shí)間+裝卸時(shí)間,最晚開始時(shí)間設(shè)置為L(zhǎng)Tqm+i=ETqm+i+1小時(shí),否則不考慮該新的取箱任務(wù),進(jìn)入Step4;
Step4:判斷確定L集合是否為空,如果為空,停止計(jì)算,輸出t和行駛路線,如果不為空則轉(zhuǎn)到Step2。
本文以蘇寧南昌物流中心為例,蘇寧南昌物流中心為F0,選定其輻射的五個(gè)客戶點(diǎn)F1、F2、F3、F4、F5提供服務(wù)。表1的數(shù)據(jù)表示客戶點(diǎn)與客戶點(diǎn)間的距離和牽引車到達(dá)各個(gè)客戶點(diǎn)所花費(fèi)的時(shí)間,具體如表1所示。假設(shè)牽引車在行駛的過程中是勻速的,且速度設(shè)為每10分鐘行駛的距離為5個(gè)單位距離。表2的數(shù)據(jù)表示各個(gè)客戶點(diǎn)需要牽引車完成的所有任務(wù)量,具體如表2所示。每項(xiàng)任務(wù)的時(shí)間窗口如表3所示。
表1 節(jié)點(diǎn)之間距離和車輛所用時(shí)間
表2 各節(jié)點(diǎn)作業(yè)量
表3 每個(gè)任務(wù)對(duì)應(yīng)的時(shí)間窗
在所有集裝箱號(hào)的列表里,其中x2、x6、x9、x12是從送箱任務(wù)集裝箱號(hào)x1、x4、x7、x10衍生出來的,所以x2、x6、x9、x12時(shí)間窗均是不確定的。為方便計(jì)算,假設(shè)把在客戶點(diǎn)F1、F2、F3、F4、F5的進(jìn)行裝箱作業(yè),8個(gè)小時(shí)均能完成,如果特殊情況,可延長(zhǎng)1個(gè)小時(shí);在每天的運(yùn)輸行駛過程中,假設(shè)牽引車的運(yùn)輸作業(yè)時(shí)間是早上6點(diǎn),排除車輛限行情況。由于客戶要求將從集裝箱x3和x8派生的取箱任務(wù)安排在第二天進(jìn)行運(yùn)輸,因此,從集裝箱 x3和x8派生的取箱任務(wù)在本研究中不予考慮。
牽引車途徑各點(diǎn)的時(shí)間統(tǒng)計(jì)結(jié)果如表4所示。
表4 牽引車途徑各點(diǎn)的時(shí)間
表5為每個(gè)任務(wù)的最優(yōu)形式路線、所屬類型及其被完成的順序。表6為牽引車開展送箱任務(wù)時(shí)派生出的取箱任務(wù)及其派生任務(wù)時(shí)間窗。表7為完成各項(xiàng)任務(wù)之后重新計(jì)算出來的所有任務(wù)的時(shí)間緊迫度,然后選取其中時(shí)間緊迫度最高的一項(xiàng)作為下一個(gè)馬上要執(zhí)行的任務(wù)。
表5 每個(gè)任務(wù)的所屬類型及其被完成順序
表6 派生任務(wù)及其時(shí)間窗
表7 每步的所有任務(wù)緊迫度
由此可得,若在甩掛運(yùn)輸?shù)幕A(chǔ)上結(jié)合合理的運(yùn)輸調(diào)度方式,從早上6點(diǎn)到晚上6點(diǎn)30分即可完成所有任務(wù);反之用傳統(tǒng)方式,且同樣牽引車每天從早上6點(diǎn)開始發(fā)車,每個(gè)集裝箱的貨物裝載作業(yè)時(shí)間為7小時(shí),那么每天最多能夠完成的運(yùn)輸任務(wù)僅僅只有兩個(gè)。即本文的四個(gè)任務(wù)(兩個(gè)送箱任務(wù)和兩個(gè)取箱任務(wù)),而采用根據(jù)時(shí)間緊迫度的需求進(jìn)行的甩掛運(yùn)輸調(diào)度能夠使得十二個(gè)任務(wù)點(diǎn)得以完成。因此,合理的甩掛運(yùn)輸作業(yè)調(diào)度比傳統(tǒng)的運(yùn)輸效率提高近3倍。
本文以蘇寧物流中心為例,運(yùn)用軸輻式網(wǎng)絡(luò)集裝箱甩掛運(yùn)輸結(jié)合每個(gè)任務(wù)的時(shí)間緊迫度性的要求,以完成所有任務(wù)的總時(shí)間最短為目標(biāo)建立了優(yōu)化模型,設(shè)計(jì)了基于時(shí)間緊迫度的啟發(fā)式算法求解,對(duì)多個(gè)任務(wù)進(jìn)行調(diào)度優(yōu)化,合理安排完成任務(wù)調(diào)度的先后順序,通過數(shù)值檢驗(yàn)的方式,得出通過甩掛運(yùn)輸調(diào)度的方式,蘇寧物流中心的甩掛運(yùn)輸作業(yè)對(duì)任務(wù)集進(jìn)行調(diào)度優(yōu)化比原有的運(yùn)輸效率提高近3倍,減少了牽引車在各個(gè)客戶點(diǎn)完成裝卸的等待時(shí)間,同時(shí)也減緩了空車行駛的概率,為蘇寧物流公司的貨物運(yùn)輸提供一些更加科學(xué)合理的優(yōu)化調(diào)度方法,實(shí)現(xiàn)提高物流中心作業(yè)效率,降低成本的效果。