轉運限制下的冷藏集裝箱多式聯運路徑優化

劉 松 邵毅明 彭 勇

1(重慶交通大學交通運輸學院 重慶 400074)2(山地城市交通系統與安全實驗室 重慶 400074)

0 引 言

冷藏集裝箱多式聯運起步較晚，2016年3月，大連港創新冷藏集裝箱多式聯運，相關溫度指標等才達國際標準[1]。隨著“一帶一路”倡議，中新戰略性互聯互通項目的深入實施和人們生活水平的不斷提高，跨國貿易更加頻繁，東盟、歐洲的水果和乳制品等冷藏品不斷通過冷藏集裝箱進行運輸，冷藏集裝箱多式聯運需求越來越大。2017年商務部發布的《商貿物流發展“十三五”規劃》指出要鼓勵應用專業冷藏運輸、推動冷鏈物流發展。同年，交通運輸部發布的《交通運輸部等十八個部門關于進一步鼓勵開展多式聯運工作的通知》提出加快多式聯運發展，構建高效順暢的多式聯運系統。

多式聯運由多種運輸方式構成，相較于單一運輸方式，還需要考慮不同運輸方式之間的轉運以及鐵路、水路運輸發班時刻表等的影響，使其運輸路徑選擇比單一運輸方式下的路徑選擇更為困難，近年來引起了學者的廣泛關注。盧欣等[2]對帶時間窗約束的多式聯運路徑選擇問題進行了研究。張燕等[3]考慮運輸費用和運輸時間對海鐵聯運進行了研究。雷定猷等[4]以最小運輸時間、里程與費用為目標函數，以線路限界、橋梁承載能力、起重設備的起重能力為約束條件，建立了長大貨物多式聯運路徑優化模型,并設計了求解算法。Assadipour等[5]綜合考慮運輸成本和風險，對危險品公鐵聯運進行了研究。呂學偉等[6]從低碳的角度研究了多式聯運最優路徑選擇問題。曹歡等[7]考慮決策者風險規避程度對危險品公鐵聯運路徑選擇進行了研究。李珺等[8]對速度服從隨機分布時的綠色多式聯運路徑優化問題進行了研究。趙志文等[9]研究了危險品多式聯運路徑優化問題。于雪嶠等[10]從運量不確定視角，建立了以總費用為目標的多式聯運路徑優化模型。劉杰等[11]研究了以運輸總成本和碳排放為目標的多式聯運路徑優化問題。甄遠迪等[12]研究了運輸時間和碳排放量不確定下的多目標多式聯運路徑優化，并設計了粒子群算法。姬曉嶺等[13]研究了地下集裝箱的多式聯運問題。成耀榮等[14]從多式聯運經營人的角度，建立考慮碳排放的多任務多式聯運路徑優化模型，并設計了算法。萬杰等[15]考慮運輸成本、時間和物流服務質量研究了多目標多式聯運路徑選擇問題。李萍等[16]以總成本和風險為目標研究了由多個路徑期組成的危險品公鐵聯運網絡擴張問題。

已有文獻對普通貨物、危險品及長大貨物多式聯運路徑選擇問題進行了研究。由于冷藏集裝箱多式聯運起步較晚，對冷藏集裝箱多式聯運路徑選擇問題研究較少，而冷藏集裝箱多式聯運和前文所述的危險品、長大貨物多式聯運路徑選擇問題類似，相較于普通集裝箱運輸有其自身的運輸特點，還需要考慮如制冷費用、運輸時限以及為減少貨損貨差通常會限制冷藏集裝箱在運輸過程中不同運輸方式之間的轉運次數等特點對優化結果的影響。劉璘等[17]研究了以制冷成本、運輸成本、轉運成本在內的總成本最小為目標的冷藏集裝箱海鐵聯運運輸路徑優化，但沒有考慮實際多式聯運中鐵路、水路等運輸方式發班時刻對路徑優化的影響。由于受發班時刻的影響，冷藏集裝箱運輸所需的時間和費用與出發時刻有很大的關系，將導致運輸成本呈現出動態變化的特征。不同出發時刻所需的出行時間不同，出行費用也不同，從而得到的優化路徑不同。

另外，由于冷藏集裝箱運輸還需要考慮貨損貨差，時效性要求高，通常貨主會對轉運次數限制和運抵目的地有時間窗要求，而該問題又是典型的NP(Non-deterministic Polynomial)難題[18]，對該類問題的求解一直以來都受到學者的高度關注。Assadipour等[19]設計了啟發式算法求解多式聯運路徑問題。劉帥等[20]設計了動態規劃法求解隨機時變路網環境下的運輸路徑選擇問題。

綜上所述，現有文獻中少有同時考慮實際冷藏集裝箱多式聯運中鐵路、水路等運輸方式發班時刻對路徑優化的影響以及貨主對轉運次數的限制和時間窗要求。基于此，本文針對該問題建立以運輸費用、中轉費用和冷藏費用最少為目標的優化模型，并針對所求問題的NP難特點設計求解算法。該算法具有一定的理論意義及實際應用價值。

1 問題描述與建模

1.1 問題描述

在如圖1所示的多式聯運網絡示意圖中，現需要將冷藏集裝箱由起點1運輸到終點7，其中，鐵路和水路運輸方式按照發班時刻表發班，多式聯運托運人對冷藏集裝箱有轉運次數限制和到達目的地時間窗要求，求以運輸成本、轉運成本和冷藏成本最低為目標的運輸路徑。

圖1 多式聯運示意圖

1.2 模型建立

1) 參數定義：

V—多式聯運網絡節點集合i,j∈V；

M—運輸方式集合,m,n∈M；

E—所有邊的集合；

s—貨物運輸的起點；

d—貨物運輸的終點；

c—冷藏集裝箱的單位冷藏費用；

G—轉運次數上限值；

to—貨物離開起點的時刻；

2) 決策變量：

3) 目標函數及約束條件：

(1) 目標函數。冷藏集裝箱多式聯運過程產生的費用主要包括運輸成本、轉運成本以及冷藏成本。因此，目標函數如下：

(1)

式(1)共包含三部分。第一部分表示貨物的運輸成本；第二部分為不同運輸方式間的轉運成本；第三部分為貨物的冷藏成本。

(2) 約束條件。流量守恒約束，即起點凈流量為1，終點凈流量為-1，其他節點流量守恒。

(2)

集裝箱在相鄰兩節點間進行運輸時，只能選擇一種運輸方式:

(3)

運輸的連續性約束:

(4)

到達目的地的時間限制:

(5)

冷藏集裝箱運輸須滿足轉運次數限制:

(6)

決策變量只能取整數0或者1:

(7)

(8)

集裝箱在節點處只能轉運一次:

(9)

變量非負約束:

(10)

2 問題求解

針對所求問題的NP難特點，本文設計遺傳算法進行求解。

2.1 編碼與初始種群的生成

2.1.1編 碼

由于最短路徑經過的節點無法提前知道，路徑具有變長的情況，因此染色體長度應是不固定的,本文采用可變長的路徑編碼方法。針對多式聯運網絡節點間有多種運輸方式的特點，對染色體分兩段編碼，前一段為路徑節點，后一段為節點間的運輸方式。如圖2所示，染色體的路徑節點部分p=(1,3,6,7),表示圖1中從節點1到節點7的一條路徑。在交叉、變異操作時，把第二段運輸方式插入第一段的空隙中。圖2中，H表示公路，R表示鐵路運輸，W表示水路運輸。

圖2 染色體編碼

2.1.2初始種群的生成

本文利用如下方法生成初始種群：

步驟1由多式聯運網絡生成連通矩陣，即兩點間只要存在一種運輸方式連通，則表示連通，矩陣邊的權值取各連通運輸方式邊的權值的最小值。

步驟2利用動態規劃法生成染色體的第一段編碼，然后隨機選擇節點間的運輸方式生成第二段編碼，得到一條初始染色體。

步驟3若種群數量已達要求，則終止；否則隨機生成0～1之間的小數乘以該路徑各弧段的權值，并更新多式聯運網絡權值，返回步驟2。

2.2 適應度評估與約束條件判斷

采用目標函數的倒數為適應度函數F：

F=Z-1

(11)

優化模型包括轉運次數不超過要求的最多運行轉運次數和時間窗要求，但在算法的進化中,有些個體的轉運次數和時間窗會超過要求。因此,采取以下方法進行調整:

1) 求個體的總轉運次數和運輸總時間；

2) 判斷每個個體所示方案的轉運次數或者運輸總時間是否超過要求，若超過，則以一定的概率刪除；

3) 如果有q個個體被刪除,就在余下群體中隨機復制q個個體。

2.3 遺傳操作

步驟1選擇。采用輪盤賭策略進行選擇操作。

步驟2交叉。本文對染色體的第一段路徑節點部分采用兩點交叉法來進行交叉操作。另外，交叉操作中可能會產生非法個體，采取以下方法對非法染色體進行修復。

第一個交叉節點到起點可能存在沒有通路的情況，如果沒有連通，則利用動態規劃法尋找第一個交叉節點與相鄰的上一節點的有效路徑替代，如無法找到有效路徑，則查找再上一節點，如此往復直到找到有連通的路徑為止。同樣地，第二個交叉節點到終點可能存在沒有通路的情況，如果沒有連通，則利用動態規劃法尋找第二個交叉節點與相鄰的下一節點的有效路徑替代，如無法找到有效路徑，則查找再下一節點，如此往復直到找到有連通的路徑為止。

另外，需要注意的是，交叉后可能會出現環路，即在路徑編碼中出現了相同的節點，若出現環路，則刪除環路，去除環路中間節點，保留一個相同節點。如圖3所示的染色體，其中節點3出現了兩次，形成了閉環，則去掉環，得新的節點1、3、6、7。完善上述操作后，對于未發生變化的基因片段，保留其第二段編碼中的運輸方式，對于染色體第一段編碼發生變化的基因片段，隨機選擇節點間的運輸方式生成對應的第二段編碼。

圖3 環路處理

步驟3變異。本文采用改進的散射變異方法進行變異操作，給多式聯運網絡弧段隨機賦值，利用動態規劃法生成染色體的第一段節點編碼。然后隨機選擇節點間的運輸方式生成第二段編碼，進而得到變異后的染色體，并采用式(12)調整變異概率，在迭代后期增強種群的最優解搜索能力。

(12)

式中：I為迭代次數。

2.4 精英保留與終止策略

采用精英保留策略進行全局最優解更新。采用最大迭代次數作為終止條件，算法求解流程如圖4所示。

圖4 遺傳算法求解流程

3 算例設計與結果分析

3.1 算例設計

為驗證模型和算法的有效性，采用前期研究[21]的網絡，如圖5所示。以節點1為起點，節點25為終點，由于班期限制下的冷藏集裝箱多式聯運路徑優化問題是一個相對較新的問題，沒有標準的測試實例庫，需要自己構造測試數據。構造數據的方法一般有兩種，一種是隨機，另一種是在已有實例上修改。本文在Solomon[22]實例基礎上修改得到，選取Solomon中R101的前25個點依次對應圖5中的節點，并將Solomon中節點間的歐幾里得距離擴大10倍(km)。不同運輸方式之間的轉運時間及轉運成本如表1所示，各種運輸方式的運輸速度、運輸成本以及發班時間如表2所示。冷藏集裝箱的冷藏成本為12元/h，設現需要將冷藏集裝箱在07:30由起點1出發運輸到終點25，要求最多轉運5次，并在50 h內到達目的地，求所需總成本最低的運輸方案。

圖5 多式聯運網絡

表1 不同運輸方式之間的轉運時間和成本

表2 各運輸方式的運輸速度、成本及班期

3.2 結果分析

設置種群規模為300，交叉概率為0.8，變異概率為0.5，最大進化代數為100，采用MATLAB 2014a編程實現算法，運行平臺為Intel(R)Core (TM)i5-6300U 2.40 GHz CPU 4.0 G內存。運行程序35 s后獲得最優解。算法求解進化過程如圖6所示，適應值逐步減小，最后收斂，算法在達到一定迭代次數后穩定在最優解保持不變。

圖6 目標函數求解進化過程

所需總運輸成本為4 081元，所需要的運輸時間為2 640 min，即44 h，共需中轉5次，滿足中轉次數和到達時間窗要求。具體運輸方案如下：

冷藏集裝箱從節點1出發后，通過水路運輸到節點6，轉鐵路運輸到節點7并繼續通過鐵路到達節點12，轉公路到達節點17轉鐵路到達節點22后繼續通過鐵路到達節點23，轉公路運輸到節點24后，轉水路運輸到達終點。

為了驗證本文所建模型和算法的有效性，引入蟻群算法進行對比，使用設計的遺傳算法與蟻群算法在不同迭代次數條件下的求解結果如表3所示。可以看出，蟻群算法和遺傳算法都能夠在有限迭代次數限制條件下求出滿意解，其中遺傳算法所求得的滿意解比蟻群算法更低。

表3 遺傳算法與蟻群算法成本比較

4 結 語

考慮轉運次數限制和鐵路、水路運輸方式具有發車時間限制以及到達時間限制特點下的冷藏集裝箱多式聯運對于減少貨損貨差、降低運輸成本具有重要意義。本文構建了運輸總成本最少的優化模型，不僅考慮了運輸費用和節點換裝費用，還考慮了受鐵路、水路發班時間限制影響而波動較大的冷藏費用以及轉運次數限制。實驗結果表明，該算法收斂性較好，能有效求解該問題。