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

王吉生，羅志勇

（1.南昌交通學院，南昌 330100；2.中國鐵路北京局集團有限公司豐臺貨運中心，北京 102300）

0 引言

甩掛運輸是指在牽引車與掛車在自由搭配的環(huán)境中，牽引車拖帶掛車至目的地將掛車甩下后，拖掛新的掛車或者不掛任何掛車運往另一個目的地的運輸組織方式。甩掛運輸充分發(fā)揮了并行工作的優(yōu)勢，大大縮短了牽引車等待貨物裝卸及在物流中心排隊的時間，從而使得牽引車的作業(yè)效率明顯提高。

目前，相關(guān)學者設(shè)計了許多關(guān)于甩掛運輸方面的研究成果。如王天予[1]等人分析了仿真技術(shù)實施甩掛運輸優(yōu)化。谷首更[2]在貪婪算法的基礎(chǔ)進行優(yōu)化改進，針對港口集裝箱的運輸需求，建立了對應的調(diào)度模型。王寶遠[3]分析甩箱運輸成本組成以及特點，選取甩箱運輸成本、時效性2個主要因素為研究對象，確定甩箱運輸模式配送成本最低的目標優(yōu)化模型。

然而，現(xiàn)有文獻中的優(yōu)化算法很少將任務(wù)的時間緊迫度考慮在內(nèi)。為此，本文以蘇寧物流中心為例，基于時間緊迫度來優(yōu)化甩掛運輸牽引車調(diào)度，利用啟發(fā)式算法求解在最短的時間內(nèi)完成已知任務(wù)的模型已知任務(wù)在最短時間能夠完成的目標進行求解。

1 問題描述

設(shè)軸輻式物流網(wǎng)絡(luò)圖G=(V,A)，其中，V={0,1,...,n}，點0為物流運輸?shù)乃熘行模?,...,n表示不同任務(wù)節(jié)點。A表示點1,...,n之間的距離弧集。具體的結(jié)構(gòu)圖如圖1所示。

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

圖1中，0為甩掛中心，1到n為與甩掛中心進行貨物運送銜接的點即客戶節(jié)點。每天牽引車都需從圖中的0點即配送中心點出發(fā)，去取箱子或者是送箱子，這一任務(wù)稱為取箱任務(wù)或者送箱任務(wù)。取箱任務(wù)為在1到n點有已經(jīng)裝滿好貨物的掛車，牽引車立刻過去把掛車掛上，把它運回到0點甩掛中心。送箱任務(wù)為在1到n點有貨物需要裝載，牽引車馬上掛上空的掛車即空箱去需要裝載貨物的客戶點，放下空的掛車去下一個任務(wù)點完成其他的事情，當這個需要裝載貨物的客戶點把貨物裝好后，那么這個客戶點就變成新的取箱點。

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

根據(jù)任務(wù)點的需求，在上一個任務(wù)和下一個任務(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均為客戶需求點。實線箭頭為加入本次路程計算的路線，虛線箭頭為上（下）一個任務(wù)行駛路線，即不加入本次路程計算的路線。牽引車在途行進的全程路線由該四種類型路線連接而成[5]。

本論文考慮甩掛運輸任務(wù)量均源于一個物流園區(qū)，所有的發(fā)貨貨物均需在甩掛中心集貨后再發(fā)往下一個途經(jīng)點，所有收貨貨物也均需先運到某城市的甩掛運輸中心后再分送到各個收貨點。假設(shè)先規(guī)定每個任務(wù)完成需要的時間，再開始安排所有的調(diào)度工作，現(xiàn)僅考慮用一輛牽引車行駛完成所有任務(wù)，求完成總時間最短的方案。

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

2.1 假設(shè)條件

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

1）所有牽引車和掛車都采用統(tǒng)一標準尺寸；

2）一輛牽引車一次只拖掛一輛掛車；

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

4）牽引車拖上掛車以及取下掛車的時間不計；

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

2.2 符號定義

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

2.3 模型建立

目標函數(shù)表示為：

約束條件表示為：

式中，t1表示完成從甩掛中心出發(fā)的取箱任務(wù)的所需時間；t2表示完成從甩掛中心出發(fā)的送箱任務(wù)所需的時間；t3表示完成從任務(wù)節(jié)點出發(fā)的取箱任務(wù)所需的時間；t4表示完成從任務(wù)節(jié)點出發(fā)的送箱任務(wù)所需的時間；mint表示完成總時間最短的目標函數(shù)；式(4)表示每個任務(wù)僅且只被完成一次；式(5)表示任務(wù)行駛路線決策變量的0～1約束。

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

本文根據(jù)每個任務(wù)的時間緊迫度選擇下個執(zhí)行任務(wù)，緊迫度Em由公式得出。在每執(zhí)行完一個任務(wù)之后都更新剩余未完成任務(wù)的時間緊迫度，在這些剩余未完成的任務(wù)中，優(yōu)先完成緊迫度最高的，圖3為算法流程圖。

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

具體實際操作步驟進行如下：

Step1：初始值：完成所有任務(wù)的總時間t=0，未完成任務(wù)集L=M，根據(jù)送箱任務(wù)轉(zhuǎn)化而來的取箱任務(wù)數(shù)i=1，進入step2；

Step2：計算所有未完成任務(wù)的時間緊迫度Em=a-(ETm-Tnow)，m∈L,其中a為一常數(shù)，在本文中將設(shè)a=10，ETm設(shè)置為任務(wù)m的最早開始時間，Tnow為當前時間，進入Step3；

Step3：選擇一個執(zhí)行任務(wù)next_m=max{Em,m∈M}。

Step3.1：如果next_m∈Q，把完成任務(wù)next_m所需的時間加入到t中，L=L/next_m，進入Step4；

Step3.2：如果next_m∈S，在t中加入完成任務(wù)next_m所需的時間，L=L/next_m，一個新的取箱任務(wù)qm+i將產(chǎn)生，然后再判斷此次取箱任務(wù)是否需要在當日完成，若是，則把qm+i的時間窗計算出來，本文最早開始時間設(shè)置為ETqm+i=任務(wù)next_m的執(zhí)行時間+裝卸時間，最晚開始時間設(shè)置為LTqm+i=ETqm+i+1小時，否則不考慮該新的取箱任務(wù)，進入Step4；

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

4 數(shù)值檢驗

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

表1 節(jié)點之間距離和車輛所用時間

表2 各節(jié)點作業(yè)量

表3 每個任務(wù)對應的時間窗

在所有集裝箱號的列表里，其中x2、x6、x9、x12是從送箱任務(wù)集裝箱號x1、x4、x7、x10衍生出來的，所以x2、x6、x9、x12時間窗均是不確定的。為方便計算，假設(shè)把在客戶點F1、F2、F3、F4、F5的進行裝箱作業(yè)，8個小時均能完成，如果特殊情況，可延長1個小時；在每天的運輸行駛過程中，假設(shè)牽引車的運輸作業(yè)時間是早上6點，排除車輛限行情況。由于客戶要求將從集裝箱x3和x8派生的取箱任務(wù)安排在第二天進行運輸，因此，從集裝箱 x3和x8派生的取箱任務(wù)在本研究中不予考慮。

牽引車途徑各點的時間統(tǒng)計結(jié)果如表4所示。

表4 牽引車途徑各點的時間

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

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

表6 派生任務(wù)及其時間窗

表7 每步的所有任務(wù)緊迫度

由此可得，若在甩掛運輸?shù)幕A(chǔ)上結(jié)合合理的運輸調(diào)度方式，從早上6點到晚上6點30分即可完成所有任務(wù)；反之用傳統(tǒng)方式，且同樣牽引車每天從早上6點開始發(fā)車，每個集裝箱的貨物裝載作業(yè)時間為7小時，那么每天最多能夠完成的運輸任務(wù)僅僅只有兩個。即本文的四個任務(wù)（兩個送箱任務(wù)和兩個取箱任務(wù)），而采用根據(jù)時間緊迫度的需求進行的甩掛運輸調(diào)度能夠使得十二個任務(wù)點得以完成。因此，合理的甩掛運輸作業(yè)調(diào)度比傳統(tǒng)的運輸效率提高近3倍。

5 結(jié)語

本文以蘇寧物流中心為例，運用軸輻式網(wǎng)絡(luò)集裝箱甩掛運輸結(jié)合每個任務(wù)的時間緊迫度性的要求，以完成所有任務(wù)的總時間最短為目標建立了優(yōu)化模型，設(shè)計了基于時間緊迫度的啟發(fā)式算法求解，對多個任務(wù)進行調(diào)度優(yōu)化，合理安排完成任務(wù)調(diào)度的先后順序，通過數(shù)值檢驗的方式，得出通過甩掛運輸調(diào)度的方式，蘇寧物流中心的甩掛運輸作業(yè)對任務(wù)集進行調(diào)度優(yōu)化比原有的運輸效率提高近3倍，減少了牽引車在各個客戶點完成裝卸的等待時間，同時也減緩了空車行駛的概率，為蘇寧物流公司的貨物運輸提供一些更加科學合理的優(yōu)化調(diào)度方法，實現(xiàn)提高物流中心作業(yè)效率，降低成本的效果。