基于啟發(fā)式算法的集裝箱甩掛運(yùn)輸任務(wù)集調(diào)度優(yōu)化

王吉生，羅志勇

（1.南昌交通學(xué)院，南昌 330100；2.中國(guó)鐵路北京局集團(tuán)有限公司豐臺(tái)貨運(yùn)中心，北京 102300）

0 引言

甩掛運(yùn)輸是指在牽引車(chē)與掛車(chē)在自由搭配的環(huán)境中，牽引車(chē)拖帶掛車(chē)至目的地將掛車(chē)甩下后，拖掛新的掛車(chē)或者不掛任何掛車(chē)運(yùn)往另一個(gè)目的地的運(yùn)輸組織方式。甩掛運(yùn)輸充分發(fā)揮了并行工作的優(yōu)勢(shì)，大大縮短了牽引車(chē)等待貨物裝卸及在物流中心排隊(duì)的時(shí)間，從而使得牽引車(chē)的作業(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í)間緊迫度來(lái)優(yōu)化甩掛運(yùn)輸牽引車(chē)調(diào)度，利用啟發(fā)式算法求解在最短的時(shí)間內(nèi)完成已知任務(wù)的模型已知任務(wù)在最短時(shí)間能夠完成的目標(biāo)進(jìn)行求解。

1 問(wè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)即客戶(hù)節(jié)點(diǎn)。每天牽引車(chē)都需從圖中的0點(diǎn)即配送中心點(diǎn)出發(fā)，去取箱子或者是送箱子，這一任務(wù)稱(chēng)為取箱任務(wù)或者送箱任務(wù)。取箱任務(wù)為在1到n點(diǎn)有已經(jīng)裝滿(mǎn)好貨物的掛車(chē)，牽引車(chē)立刻過(guò)去把掛車(chē)掛上，把它運(yùn)回到0點(diǎn)甩掛中心。送箱任務(wù)為在1到n點(diǎn)有貨物需要裝載，牽引車(chē)馬上掛上空的掛車(chē)即空箱去需要裝載貨物的客戶(hù)點(diǎn)，放下空的掛車(chē)去下一個(gè)任務(wù)點(diǎn)完成其他的事情，當(dāng)這個(gè)需要裝載貨物的客戶(hù)點(diǎn)把貨物裝好后，那么這個(gè)客戶(hù)點(diǎn)就變成新的取箱點(diǎn)。

每一次執(zhí)行任務(wù)，牽引車(chē)的出發(fā)點(diǎn)都是不確定的[4]。若上次的任務(wù)是取箱，那么牽引車(chē)的出發(fā)點(diǎn)就是0點(diǎn)即甩掛中心；若上次的任務(wù)是送箱，那么牽引車(chē)的出發(fā)點(diǎn)就是在上次任務(wù)客戶(hù)點(diǎn)。

根據(jù)任務(wù)點(diǎn)的需求，在上一個(gè)任務(wù)和下一個(gè)任務(wù)的設(shè)置中，可以把牽引車(chē)的行駛路徑分為四類(lèi)：

1）上一任務(wù)是取箱任務(wù)，下一任務(wù)是取箱任務(wù)；

2）上一任務(wù)是取箱任務(wù)，下一任務(wù)是送箱任務(wù)；

3）上一任務(wù)是送箱任務(wù)，下一任務(wù)是取箱任務(wù)；

4）上一任務(wù)是送箱任務(wù)，下一任務(wù)是送箱任務(wù)。

這四類(lèi)路徑類(lèi)型如圖2所示。

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

圖2中，0為甩掛中心，1和2均為客戶(hù)需求點(diǎn)。實(shí)線箭頭為加入本次路程計(jì)算的路線，虛線箭頭為上（下）一個(gè)任務(wù)行駛路線，即不加入本次路程計(jì)算的路線。牽引車(chē)在途行進(jìn)的全程路線由該四種類(lèi)型路線連接而成[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í)間，再開(kāi)始安排所有的調(diào)度工作，現(xiàn)僅考慮用一輛牽引車(chē)行駛完成所有任務(wù)，求完成總時(shí)間最短的方案。

2 集裝箱甩掛運(yùn)輸任務(wù)集調(diào)度優(yōu)化的混合整數(shù)規(guī)劃模型

2.1 假設(shè)條件

根據(jù)物流園區(qū)實(shí)際運(yùn)轉(zhuǎn)情況，作出以下假設(shè):

1）所有牽引車(chē)和掛車(chē)都采用統(tǒng)一標(biāo)準(zhǔn)尺寸；

2）一輛牽引車(chē)一次只拖掛一輛掛車(chē)；

3）牽引車(chē)拖掛重箱和拖掛空箱的速度相同；

4）牽引車(chē)拖上掛車(chē)以及取下掛車(chē)的時(shí)間不計(jì)；

5）牽引車(chē)每天從甩掛中心出發(fā)，最后返回到甩掛中心。

2.2 符號(hào)定義

模型中的符號(hào)定義如下：m1表示第一種路徑類(lèi)型的任務(wù)數(shù)；m2表示第二種路徑類(lèi)型的任務(wù)數(shù)；m3表示第三種路徑類(lèi)型的任務(wù)數(shù)；m4表示第四種路徑類(lèi)型的任務(wù)數(shù)；M表示所有任務(wù)集合，且滿(mǎn)足M=m1∪m2∪m3∪m4；tij表示i到j(luò)的行駛時(shí)間與在j地的等待時(shí)間之和，則存在：

2.3 模型建立

目標(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約束。

3 基于時(shí)間緊迫度的啟發(fā)式算法

本文根據(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)化而來(lái)的取箱任務(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的最早開(kāi)始時(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ì)算出來(lái)，本文最早開(kāi)始時(shí)間設(shè)置為ETqm+i=任務(wù)next_m的執(zhí)行時(shí)間+裝卸時(shí)間，最晚開(kāi)始時(shí)間設(shè)置為L(zhǎng)Tqm+i=ETqm+i+1小時(shí)，否則不考慮該新的取箱任務(wù)，進(jìn)入Step4；

Step4:判斷確定L集合是否為空，如果為空，停止計(jì)算，輸出t和行駛路線，如果不為空則轉(zhuǎn)到Step2。

4 數(shù)值檢驗(yàn)

本文以蘇寧南昌物流中心為例，蘇寧南昌物流中心為F0，選定其輻射的五個(gè)客戶(hù)點(diǎn)F1、F2、F3、F4、F5提供服務(wù)。表1的數(shù)據(jù)表示客戶(hù)點(diǎn)與客戶(hù)點(diǎn)間的距離和牽引車(chē)到達(dá)各個(gè)客戶(hù)點(diǎn)所花費(fèi)的時(shí)間，具體如表1所示。假設(shè)牽引車(chē)在行駛的過(guò)程中是勻速的，且速度設(shè)為每10分鐘行駛的距離為5個(gè)單位距離。表2的數(shù)據(jù)表示各個(gè)客戶(hù)點(diǎn)需要牽引車(chē)完成的所有任務(wù)量，具體如表2所示。每項(xiàng)任務(wù)的時(shí)間窗口如表3所示。

表1 節(jié)點(diǎn)之間距離和車(chē)輛所用時(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衍生出來(lái)的，所以x2、x6、x9、x12時(shí)間窗均是不確定的。為方便計(jì)算，假設(shè)把在客戶(hù)點(diǎn)F1、F2、F3、F4、F5的進(jìn)行裝箱作業(yè)，8個(gè)小時(shí)均能完成，如果特殊情況，可延長(zhǎng)1個(gè)小時(shí)；在每天的運(yùn)輸行駛過(guò)程中，假設(shè)牽引車(chē)的運(yùn)輸作業(yè)時(shí)間是早上6點(diǎn)，排除車(chē)輛限行情況。由于客戶(hù)要求將從集裝箱x3和x8派生的取箱任務(wù)安排在第二天進(jìn)行運(yùn)輸，因此，從集裝箱 x3和x8派生的取箱任務(wù)在本研究中不予考慮。

牽引車(chē)途徑各點(diǎn)的時(shí)間統(tǒng)計(jì)結(jié)果如表4所示。

表4 牽引車(chē)途徑各點(diǎn)的時(shí)間

表5為每個(gè)任務(wù)的最優(yōu)形式路線、所屬類(lèi)型及其被完成的順序。表6為牽引車(chē)開(kāi)展送箱任務(wù)時(shí)派生出的取箱任務(wù)及其派生任務(wù)時(shí)間窗。表7為完成各項(xiàng)任務(wù)之后重新計(jì)算出來(lái)的所有任務(wù)的時(shí)間緊迫度，然后選取其中時(shí)間緊迫度最高的一項(xiàng)作為下一個(gè)馬上要執(zhí)行的任務(wù)。

表5 每個(gè)任務(wù)的所屬類(lèi)型及其被完成順序

表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)方式，且同樣牽引車(chē)每天從早上6點(diǎn)開(kāi)始發(fā)車(chē)，每個(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倍。

5 結(jié)語(yǔ)

本文以蘇寧物流中心為例，運(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)度的先后順序，通過(guò)數(shù)值檢驗(yàn)的方式，得出通過(guò)甩掛運(yùn)輸調(diào)度的方式，蘇寧物流中心的甩掛運(yùn)輸作業(yè)對(duì)任務(wù)集進(jìn)行調(diào)度優(yōu)化比原有的運(yùn)輸效率提高近3倍，減少了牽引車(chē)在各個(gè)客戶(hù)點(diǎn)完成裝卸的等待時(shí)間，同時(shí)也減緩了空車(chē)行駛的概率，為蘇寧物流公司的貨物運(yùn)輸提供一些更加科學(xué)合理的優(yōu)化調(diào)度方法，實(shí)現(xiàn)提高物流中心作業(yè)效率，降低成本的效果。