基于Yalmip工具箱與遺傳算法的鐵路運(yùn)輸分配問題優(yōu)化方法

重慶郵電大學(xué) 張興銳 吳仕帥 孫佳欣

1 引言

隨著經(jīng)濟(jì)的快速發(fā)展，特別是工業(yè)經(jīng)濟(jì)的明顯提高，貨物運(yùn)送的效率也越來越重要。如何合理地進(jìn)行貨運(yùn)列車的調(diào)度分配影響著貨物運(yùn)輸?shù)男逝c收益等諸多因素。因此對(duì)貨物運(yùn)輸分配優(yōu)化問題進(jìn)行研究對(duì)進(jìn)一步提高鐵路服務(wù)水平有著重要意義。

2 相關(guān)簡(jiǎn)介

2.1 遺傳算法簡(jiǎn)介

遺傳算法是模擬自然界的生物進(jìn)化過程的一種計(jì)算模型，它采用簡(jiǎn)單的編碼技術(shù)來表示各種復(fù)雜的結(jié)構(gòu)，并通過對(duì)一組編碼表示進(jìn)行簡(jiǎn)單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導(dǎo)學(xué)習(xí)和確定搜索的方向。算法通常包含以下步驟：

Step1：編碼，遺傳算法的編碼通常包含浮點(diǎn)編碼和二進(jìn)制編碼，在本文中采用二進(jìn)制編碼。設(shè)某一參數(shù)的取值范圍為(L,U)，使用長(zhǎng)度為k的二進(jìn)制編碼表示該參數(shù)，則它共有種不同的編碼，每?jī)蓚€(gè)相鄰的編碼間隔；

Step2：解碼，將不直觀的二進(jìn)制數(shù)據(jù)串還原到十進(jìn)制；

Step3：交配，使用單點(diǎn)或者多點(diǎn)進(jìn)行交叉的算子。通過隨機(jī)數(shù)產(chǎn)生一個(gè)或多個(gè)交配位置，然后兩個(gè)個(gè)體在交配位置互換部分基因碼；

Step4：突變，使用基本位進(jìn)行基因突變；

Step5：個(gè)體適應(yīng)度評(píng)估，遺傳算法依照與個(gè)體適應(yīng)度成正比的幾率決定當(dāng)前種群中各個(gè)個(gè)體遺傳到下一代群體中的機(jī)會(huì)；

Step6：復(fù)制，復(fù)制運(yùn)算時(shí)根據(jù)個(gè)體適應(yīng)度大小決定遺傳到下一代的個(gè)體。

2.2 Yalmip工具箱簡(jiǎn)介

Yalmip[1]是由Lofberg開發(fā)的一種免費(fèi)開源的Matlab工具箱，其基于符號(hào)運(yùn)算工具箱編寫，可用來求解線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、混合規(guī)劃等標(biāo)準(zhǔn)規(guī)劃問題。Yalmip最大的特點(diǎn)在于可調(diào)用多個(gè)外部?jī)?yōu)化求解器（如Gurobi、CPLEX等），并形成一種統(tǒng)一的建模語言。該工具建模步驟可分為以下4步：

Step1：創(chuàng)建決策變量；

Step2：添加約束條件；

Step3：求解器參數(shù)配置；

Step4：求解問題及結(jié)果的相關(guān)顯示。

2.3 優(yōu)化方式

遺傳算法具有快速隨機(jī)的搜索能力及可擴(kuò)展性強(qiáng)等優(yōu)點(diǎn)，可與Yalmip工具箱結(jié)合進(jìn)行問題優(yōu)化。本文以Yalmip求解結(jié)果作為適應(yīng)度評(píng)估值，再利用遺傳算法進(jìn)行隨機(jī)搜索，算法步驟如圖1所示：

圖1 優(yōu)化算法步驟

3 實(shí)例求解

3.1 問題描述

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

圖2 鐵路網(wǎng)線拓?fù)鋱D

表1 各地集裝箱運(yùn)輸需求量

3.2 模型的建立與求解

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

3.2.1 符號(hào)說明

?

3.2.2 模型建立

首先求解當(dāng)條運(yùn)輸路徑已確定時(shí)，如何分配各條路徑的集裝箱使利益達(dá)到最大化問題。

易提取出以下約束條件：

（1）K條運(yùn)輸路線確定后，第個(gè)站點(diǎn)所得到的集裝箱總量不超過：

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

因此可列出求解模型：

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

Step1：采用DFS算法將24條路徑進(jìn)行生成并編號(hào)，得到；

Step2：編碼，此處精度為1，所以可得到編碼長(zhǎng)度；

Step3：隨機(jī)生成條初始路徑；

Step4：采用Yalmip工具箱計(jì)算這條路徑的適應(yīng)度，并根據(jù)適應(yīng)度進(jìn)行種群復(fù)制；

Step5：通過交叉和變異操作進(jìn)行種群更新；

Step6：達(dá)到種群停止進(jìn)化條件，程序結(jié)束;否則，重復(fù)4-5步。

3.2.3 模型求解

（1）確定K值

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

（2）遺傳算法參數(shù)初始化

表2 遺傳算法參數(shù)

（3）求解結(jié)果

表3 不同K值收益表

從表3所示可分析得到，K=7時(shí)，即列次趟次為7次時(shí)可收獲最大利益，最大利益為859100元。另外，可以發(fā)現(xiàn)求解結(jié)果和分析時(shí)的結(jié)果相同，當(dāng)K值過大時(shí)，會(huì)因?yàn)橛羞^多空閑車廂造成資源浪費(fèi)從而導(dǎo)致收益未能達(dá)到最大化；相反，當(dāng)K值過小時(shí)，會(huì)因?yàn)檩^多站點(diǎn)需求未能滿足，從而收益也未能達(dá)到最大化。

當(dāng)K=7時(shí)，列車路線與集裝箱分配表如4所示：

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

4 結(jié)語

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