基于遺傳算法的甩掛運輸路徑優化研究

張涵悅 劉 松 岳海亮

（1．重慶交通大學交通運輸學院，重慶 400074；2．山地城市交通系統與安全重點實驗室，重慶 400074）

隨著物流業的發展，配送車輛的路徑優化問題也越來越重要，如何在滿足客戶需求的情況下實現高效節能的配送成為現代物流業一個重要的問題。其中，公路運輸在配送過程中使用卡車加掛車形成的甩掛車進行配送任務，能在同等運輸條件下，提高運輸效能。車輛示意圖如圖1所示，車隊是由兩種不同車型組成，卡車（帶有1節車廂）和甩掛車（帶有2節可卸車廂），網絡還包含一類特殊的點，稱之為甩掛點。在甩掛點，車輛可以停放、裝卸以及改變裝載順序。甩掛運輸是指特定的卡車加上掛車，按照預定好的方案在甩掛點甩下或掛上指定的掛車，繼續配送的一種運輸組織方式，能在同等條件下，最大限度地利用牽引力，加速車輛周轉率，提高運輸效能，是一種節能減排、降低運輸成本的先進道路運輸組織方式。

圖1 卡車與甩掛車車型示意圖

甩掛運輸作為一種新型高效的運輸方式，國內外學者已有一定的進展。邊展[1]等研究了帶時間窗的甩掛運輸路徑優化問題，建立了駕駛時間為目標函數構建模型。李紅啟[2]等以貨運噸公里碳排放量為目標函數，構建了混合整數規劃模型，實現了良好的節能減排效果。楊珍花[3]等建立了混合模式下的多車型交叉甩掛調度模型并設計了混合模擬退火算法來求解模型，結果體現了良好的節約成本作用。

1 模型的建立

1.1 問題描述

SB-VRP是在VRP基礎上加入甩掛車的概念，解決的是確定一個滿足客戶需求的允許甩掛的車輛路線規劃，目的是求得最優的配送路徑以實現最少的配送費用。小型SB-VRP的大致配送流程如圖2所示。

圖2 小型SB-VRP實例

圖2 中，靈活點表示既允許卡車配送也允許甩掛車配送的客戶點；限制點表示只允許卡車配送不允許甩掛車配送的客戶點；已選甩掛點表示經算法運行被用于進行甩掛操作的中轉點。本文研究的SB-VRP可歸納為：利用卡車和甩掛車，在車輛最大裝載能力內，對配送范圍內的客戶點進行配送任務，以滿足各個客戶點的需求量。

1.2 模型建立

在對SB-MVRP建模的開始要先進行如下假設：

（1）每輛車都要從物流配送中心出發，完成配送任務后回到配送中心；

（2）允許甩掛運輸的路徑在配送過程中只允許一次甩掛操作；

（3）限制點客戶只允許卡車進行配送，靈活點客戶允許卡車和甩掛車進行配送；

（4）每條配送路線上各客戶點的需求量之和不可以超過所派汽車最大允許容量。

基于以上假設，建立SB-MVRP優化模型，相關數學符號定義如下：

N=O∪S∪L∪R表示物流網絡中所有節點集合。O表示配送中心；S表示甩掛點（甩掛車進行甩掛操作的中轉點）集合，s表示甩掛點標號；L表示靈活點（同時允許卡車和甩掛車進行配送任務的客戶點）集合，l表示靈活點標號；R表示限制點（只允許卡車進行配送任務的客戶點）集合，r表示限制點標號；i、j表示配送網絡中所有節點編號。t表示卡車標號，nt表示卡車啟動數量；k表示甩掛車標號，nk表示甩掛車啟動數量；ct、ck分別表示卡車和甩掛車的啟動費用；bt、bk分別表示卡車和甩掛車的單位里程所耗費用；f表示司機費用。aijt、aijk分別表示卡車和甩掛車從i→j行駛里程；h表示司機一天最大允許工作時間。

決策變量定義如下：

有上述定義可建立數學模型如下：

表示車輛行駛過程中所耗的費用之和；(nt+nk)f表示所需司機的費用之和；(ntct+nkck)表示車輛的啟動成本之和。具體數學表達如下：

式（2）表示所有車輛從配送中心出發回到配送中心；式（3）表示允許甩掛運輸的路徑在配送過程中只允許一次甩掛操作；式（4）表示限制點客戶只允許卡車進行一次配送；式（5）表示靈活點客戶允許卡車或者甩掛車進行一次配送；式（6）表示只允許卡車進行配送的路徑的容量約束；式（7）表示既允許卡車也允許甩掛車進行配送的路徑容量約束；式（8）表示只允許甩掛車進行配送的路徑的容量約束。

2 算法設計及有效性分析

2.1 算法設計

（1）編碼解碼。采用小數編碼的方式，按照小數由小至大的順序解釋成整數編碼，相等小數按前后位置解釋成整數。每條整數編碼可以解釋成一條配送路徑。

（2）遺傳操作。采用輪盤賭進行個體選擇。采用單點交叉。隨機選擇交叉位，將兩個個體交叉位后基因互換形成新個體。采用單點變異。隨機選擇個體某基因位，隨機產生一小數替換該基因位基因，實現個體變異。

（3）種群管理策略。在算法中，采用單種群管理策略，滿足給定種群規模m進行選擇、交叉、變異操作，并采用基因保留策略，更新最優解。

2.2 算法有效性分析

本文選取Solomon中R101的所有點的坐標并得到節點間距離，再選取所有點的Demand，作為客戶點需求量。如圖1所示配送中心以及待配送客戶點，如何在滿足所有客戶需求量以及滿足各路段道路條件的同時，在規定時間內花費最少費用完成所有配送并回到配送中心。假設配送網絡中卡車的最大裝載能力為200，甩掛車最大裝載能力為400；車輛平均行駛速度為60 km/h；卡車固定啟動成本為1，單位行駛成本為1；甩掛車固定啟動成本為2，單位行駛成本為1.5；甩掛點啟動成本為5；司機日工作時長為12 h，日工資為10。

為驗證本文設計的遺傳算法的有效性，取種群規模100，令交叉概率分別為0.9，變異概率0.1。最大迭代次數Maxgen=200，通過MATLAB軟件編程計算，并在一臺CPU為IntelCore(I7)，內存為8.0 GB的計算機上進行運算。圖3為最優解隨遺傳算法迭代次數的變化圖。由圖3可知，算法可以在有限迭代次數下達到收斂狀態。當迭代次數達到1700代左右，達到最優解收斂狀態。

圖3 遺傳算法迭代圖

3 結語

本文提出了一種允許甩掛的車輛路徑問題，針對該問題，以配送最低成本為目標，在滿足客戶點的需求量的前提下，建立了配送路徑總成本模型，并針對該模型設計了遺傳算法進行求解。通過2 000次的迭代發現，算法可在有限迭代次數內達到收斂狀態。