基于Yalmip工具箱與遺傳算法的鐵路運輸分配問題優化方法

重慶郵電大學 張興銳 吳仕帥 孫佳欣

1 引言

隨著經濟的快速發展，特別是工業經濟的明顯提高，貨物運送的效率也越來越重要。如何合理地進行貨運列車的調度分配影響著貨物運輸的效率與收益等諸多因素。因此對貨物運輸分配優化問題進行研究對進一步提高鐵路服務水平有著重要意義。

2 相關簡介

2.1 遺傳算法簡介

遺傳算法是模擬自然界的生物進化過程的一種計算模型，它采用簡單的編碼技術來表示各種復雜的結構，并通過對一組編碼表示進行簡單的遺傳操作和優勝劣汰的自然選擇來指導學習和確定搜索的方向。算法通常包含以下步驟：

Step1：編碼，遺傳算法的編碼通常包含浮點編碼和二進制編碼，在本文中采用二進制編碼。設某一參數的取值范圍為(L,U)，使用長度為k的二進制編碼表示該參數，則它共有種不同的編碼，每兩個相鄰的編碼間隔；

Step2：解碼，將不直觀的二進制數據串還原到十進制；

Step3：交配，使用單點或者多點進行交叉的算子。通過隨機數產生一個或多個交配位置，然后兩個個體在交配位置互換部分基因碼；

Step4：突變，使用基本位進行基因突變；

Step5：個體適應度評估，遺傳算法依照與個體適應度成正比的幾率決定當前種群中各個個體遺傳到下一代群體中的機會；

Step6：復制，復制運算時根據個體適應度大小決定遺傳到下一代的個體。

2.2 Yalmip工具箱簡介

Yalmip[1]是由Lofberg開發的一種免費開源的Matlab工具箱，其基于符號運算工具箱編寫，可用來求解線性規劃、非線性規劃、整數規劃、混合規劃等標準規劃問題。Yalmip最大的特點在于可調用多個外部優化求解器（如Gurobi、CPLEX等），并形成一種統一的建模語言。該工具建模步驟可分為以下4步：

Step1：創建決策變量；

Step2：添加約束條件；

Step3：求解器參數配置；

Step4：求解問題及結果的相關顯示。

2.3 優化方式

遺傳算法具有快速隨機的搜索能力及可擴展性強等優點，可與Yalmip工具箱結合進行問題優化。本文以Yalmip求解結果作為適應度評估值，再利用遺傳算法進行隨機搜索，算法步驟如圖1所示：

圖1 優化算法步驟

3 實例求解

3.1 問題描述

設有如下圖2鐵路網線，從車站A到其它站點的潛在集裝箱運輸需求量見下表1（鐵路部門不必將集裝箱全部運輸完畢），每天鐵路部門將以A站為起點F站為終點，沿不同的路線開行若干趟貨運列車，每列火車最大編組量為40節車廂，一節車廂最多容納3個集裝箱。已知每列火車列車開行的固定成本為15000元，每個集裝箱的運費為2元/公里，請為鐵路部門設計一個編組運輸方案，使鐵路部門獲利最大化[3]。

圖2 鐵路網線拓撲圖

表1 各地集裝箱運輸需求量

3.2 模型的建立與求解

題目要求設計一個編組運輸方案，即確定列車趟次與每趟車路線安排和貨物分配使得鐵路部門利益最大化。

3.2.1 符號說明

?

3.2.2 模型建立

首先求解當條運輸路徑已確定時，如何分配各條路徑的集裝箱使利益達到最大化問題。

易提取出以下約束條件：

（1）K條運輸路線確定后，第個站點所得到的集裝箱總量不超過：

（2）第k條路線列車集裝箱總量不超過40×3=120個：

因此可列出求解模型：

現在采用遺傳算法來確定這條路徑，算法步驟如下：

Step1：采用DFS算法將24條路徑進行生成并編號，得到；

Step2：編碼，此處精度為1，所以可得到編碼長度；

Step3：隨機生成條初始路徑；

Step4：采用Yalmip工具箱計算這條路徑的適應度，并根據適應度進行種群復制；

Step5：通過交叉和變異操作進行種群更新；

Step6：達到種群停止進化條件，程序結束;否則，重復4-5步。

3.2.3 模型求解

（1）確定K值

首先需要確定K值，如果K值過大，列車必然有較多空車廂無法達到利益最大化；K值過小，各地仍有較多集裝箱未能運輸，依然無法達到利益最大化。所以這里我們先采用估算方式初步確定K值，在進行左右滑動試算，最終確定K值達到利益最大化。由于各站點總集裝箱需求量為751個，單趟次列車最大容量為120個集裝箱，所以，其中ceil表示向上取整。

（2）遺傳算法參數初始化

表2 遺傳算法參數

（3）求解結果

表3 不同K值收益表

從表3所示可分析得到，K=7時，即列次趟次為7次時可收獲最大利益，最大利益為859100元。另外，可以發現求解結果和分析時的結果相同，當K值過大時，會因為有過多空閑車廂造成資源浪費從而導致收益未能達到最大化；相反，當K值過小時，會因為較多站點需求未能滿足，從而收益也未能達到最大化。

當K=7時，列車路線與集裝箱分配表如4所示：

表4 列車路線與集裝箱分配表

4 結語

鐵路運輸作為一種重要的運輸方式，鐵路的運輸分配優化對鐵路運輸效率與服務質量有著重要意義。本文介紹了遺傳算法與Yalmip求解問題的一般步驟，說明了Yalmip對優化問題求解的靈活、直觀、易行等特點。最后，通過一個運輸實例，證實了基于Yalmip工具箱與遺傳算法的優化方法的可行性與有效性。