基于啟發式算法的集裝箱甩掛運輸任務集調度優化

王吉生，羅志勇

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

0 引言

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

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

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

1 問題描述

設軸輻式物流網絡圖G=(V,A)，其中，V={0,1,...,n}，點0為物流運輸的甩掛中心，1,...,n表示不同任務節點。A表示點1,...,n之間的距離弧集。具體的結構圖如圖1所示。

圖1 軸輻射子網絡圖

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

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

根據任務點的需求，在上一個任務和下一個任務的設置中，可以把牽引車的行駛路徑分為四類：

1）上一任務是取箱任務，下一任務是取箱任務；

2）上一任務是取箱任務，下一任務是送箱任務；

3）上一任務是送箱任務，下一任務是取箱任務；

4）上一任務是送箱任務，下一任務是送箱任務。

這四類路徑類型如圖2所示。

圖2 四種車輛路徑類型

圖2中，0為甩掛中心，1和2均為客戶需求點。實線箭頭為加入本次路程計算的路線，虛線箭頭為上（下）一個任務行駛路線，即不加入本次路程計算的路線。牽引車在途行進的全程路線由該四種類型路線連接而成[5]。

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

2 集裝箱甩掛運輸任務集調度優化的混合整數規劃模型

2.1 假設條件

根據物流園區實際運轉情況，作出以下假設:

1）所有牽引車和掛車都采用統一標準尺寸；

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

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

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

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

2.2 符號定義

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

2.3 模型建立

目標函數表示為：

約束條件表示為：

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

3 基于時間緊迫度的啟發式算法

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

圖3 啟發式算法流程圖

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

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

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

Step3：選擇一個執行任務next_m=max{Em,m∈M}。

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

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

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

4 數值檢驗

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

表1 節點之間距離和車輛所用時間

表2 各節點作業量

表3 每個任務對應的時間窗

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

牽引車途徑各點的時間統計結果如表4所示。

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

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

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

表6 派生任務及其時間窗

表7 每步的所有任務緊迫度

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

5 結語

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