車種代用情況下的空車調(diào)配優(yōu)化模型及其求解

楊喜娟

（蘭州交通大學(xué)電子與信息工程學(xué)院）

（甘肅省軌道交通裝備系統(tǒng)動(dòng)力學(xué)與可靠性重點(diǎn)實(shí)驗(yàn)室 （蘭州交通大學(xué)），甘肅 蘭州730070）

張治娟 （甘肅省軌道交通裝備系統(tǒng)動(dòng)力學(xué)與可靠性重點(diǎn)實(shí)驗(yàn)室 （蘭州交通大學(xué)），甘肅 蘭州730070）

空車調(diào)配是鐵路運(yùn)輸中的重要組成部分，是指導(dǎo)運(yùn)輸生產(chǎn)的重要手段。由于我國鐵路貨車大部分是全路通用的，沒有固定的配屬站，且空車走行公里為非生產(chǎn)走行，不產(chǎn)生運(yùn)輸產(chǎn)品，因而存在空車調(diào)配優(yōu)化的問題［1－4］。為此，筆者建立了車種代作情況下的空車調(diào)配優(yōu)化模型，并應(yīng)用蟻群算法對其進(jìn)行了求解。

1 車種代用情況下的空車調(diào)配優(yōu)化模型

設(shè)有n個(gè)空車供應(yīng)點(diǎn)Ai（i＝1，2，…，n），供應(yīng)點(diǎn)對u種空車的供應(yīng)構(gòu)成集合節(jié)點(diǎn)Ai對u種空車的總供應(yīng)量為；有r個(gè)空車需求點(diǎn)Sj（j＝1，2，…，r），需求點(diǎn)對u種空車的需求構(gòu)成集合，節(jié)點(diǎn)Sj對u種空車的總需求量從Ai到Sj的距離為cij。設(shè)空車調(diào)整數(shù)量決策變量表示由i節(jié)點(diǎn)向j節(jié)點(diǎn)供應(yīng)的裝運(yùn)v種貨物的u種空車數(shù)，≥0且為整數(shù)表示j車站待裝的v種貨物的數(shù)量；Quv表示u種空車裝v種貨物的載重量。針對以上變量，假設(shè)所討論的對象整體是一個(gè)封閉的系統(tǒng)，即該系統(tǒng)內(nèi)所有節(jié)點(diǎn)產(chǎn)生的空車的數(shù)量與需求的數(shù)量是平衡的。

對于空車供應(yīng)節(jié)點(diǎn)i，假設(shè)貨物的種類為r，發(fā)出的空車總數(shù)量應(yīng)與該節(jié)點(diǎn)的空車供應(yīng)量相等，即：

對于空車需求節(jié)點(diǎn)，到達(dá)的空車總數(shù)量應(yīng)與該節(jié)點(diǎn)的空車需求量相等，即：

假設(shè)空車產(chǎn)生u種空車數(shù)等于空車的需求的u種空車數(shù)，即平衡運(yùn)輸，即：

對于空車需求節(jié)點(diǎn)j來說，假設(shè)空車的種類數(shù)為s，對某種貨物v的供給能力限制為：

對于u種空車來說，總的走行公里數(shù)為：

則所有空車的走行公里數(shù)為：

則在平衡情況下，空車調(diào)配優(yōu)化的數(shù)學(xué)模型如下：：

約束條件為式（1）～（4），其中，u∈U，v∈V，U為空車種類的集合；V為貨物種類的集合。

2 應(yīng)用蟻群算法求解空車調(diào)配優(yōu)化模型

2.1 蟻群算法基本原理

意大利學(xué)者M(jìn).Dorigo于1991年提出蟻群算法［8］。該算法利用具有記憶功能的人工螞蟻，通過個(gè)體之間相互協(xié)作，相互進(jìn)行信息交流來尋找一條從源節(jié)點(diǎn)到目的節(jié)點(diǎn)的最短路徑。

2.2 用有向圖描述空車調(diào)配模型

2.3 空車調(diào)配優(yōu)化的算法描述

在求解過程中，若干螞蟻過程之間通過信息素值來交換信息，合作求解并不斷優(yōu)化，其中信息素值分布式存儲在連接圖中，與各弧相關(guān)聯(lián)。每只螞蟻是一個(gè)獨(dú)立的用于構(gòu)造解的過程，螞蟻的任務(wù)是在約束條件下將所有空車的調(diào)配作為一項(xiàng)任務(wù)，如果將某一車站供應(yīng)站的空車種i指派至某一空車需求地的某一物資j，則連接點(diǎn)i與j，同時(shí)，在此弧上留下信息素。由于對每個(gè)車站的每種物資都指派一項(xiàng)任務(wù)，所以，最終的可行解是連接任務(wù)與物資的若干條弧。由2個(gè)步驟形成完整的解：螞蟻選擇應(yīng)當(dāng)被指派的任務(wù)；將該任務(wù)指派至某一物資，使用弧 （i，j）的信息素以及啟發(fā)式信息來決定指派的次序，應(yīng)用局部優(yōu)化進(jìn)行信息素更新，在所有的m個(gè)螞蟻都構(gòu)造完解后，再應(yīng)用全局信息素更新。下面對求解過程進(jìn)行描述。

節(jié)點(diǎn)間的距離矩陣D＝｛cij｝，T＝｛τij（t）｜i∈K，j∈P｝是t時(shí)刻集合G中元素（節(jié)點(diǎn)）兩兩連接邊上殘留信息量的集合，τij表示t時(shí)刻路徑（i，j）上的信息素量。在初始時(shí)刻各條信息量相等，并設(shè)τij（0）＝const。螞蟻k（k＝1，2，…，m）在運(yùn)動(dòng)過程中，根據(jù)每條路徑上的信息量決定其轉(zhuǎn)移方向。設(shè)置二維禁忌表Tuabk（k＝1，2，…，m）和Pslk來記錄螞蟻k當(dāng)前所經(jīng)過的節(jié)點(diǎn)和配送數(shù)量，集合隨著Taubk進(jìn)化過程作動(dòng)態(tài)調(diào)整。初始化時(shí)將m只螞蟻隨機(jī)分配到集合K上，在搜索過程中，螞蟻根據(jù)各條路徑上的信息量及路徑的啟發(fā)信息來計(jì)算狀態(tài)轉(zhuǎn)移概率。用pkij表示在t時(shí)刻螞蟻k由節(jié)點(diǎn)i轉(zhuǎn)移到節(jié)點(diǎn)j的狀態(tài)轉(zhuǎn)移概率［6］，計(jì)算如下：

式中，Taubk中所有元素組成的集合為N，則allowedk＝｛H－N｝表示螞蟻下一步允許選擇的節(jié)點(diǎn)，即可選擇的節(jié)點(diǎn)集合；ηij為空車i轉(zhuǎn)移到物資j的啟發(fā)信息，取ηij＝1／cij；α為信息啟發(fā)式因子，表示在路徑（i，j）上殘留信息的重要程度；β為期望啟發(fā)式因子，表示啟發(fā)信息的相對重要性。

在每只螞蟻配送完一種空車后，調(diào)整Taubk和Pslk，并對信息量進(jìn)行調(diào)整，調(diào)整規(guī)則如下［6］：

在每只螞蟻把所有的空車都配送完以后，清空Taubk（k＝1，2，…，m）和，準(zhǔn)備下一次搜索，并進(jìn)行全局信息素更新規(guī)則，全局更新規(guī)則如下：

式中，Lk為最佳路徑的長度。

所有螞蟻重復(fù)上述工作直到滿足循環(huán)條件退出。

3 仿真試驗(yàn)

設(shè)空車產(chǎn)生地為s1、s2、s3，空車需求地為t1、t2、t3，空車種類有u1（集裝箱平車 XN17）、u2（敞車C64）、u3（棚車P64GK），貨物種類有v1（糧食）、v2（木材）。則有u3裝v1、u2裝v2、u1和u2可代裝v1、u1可代裝v2?？哲嚬┙o表、貨物供給表、貨車標(biāo)記載重和裝運(yùn)貨物品類重量表以及運(yùn)輸距離表如表1～4所示。

表1 空車供給表

表2 貨物供給表

表3 貨車標(biāo)記載重和裝運(yùn)貨物品類重量表

表4 運(yùn)輸距離表

采用蟻群算法求解上述問題，首先代入約束條件和目標(biāo)函數(shù)，再使用Matlab7.0對算例進(jìn)行求解，使用的參數(shù)為m＝15；ρ＝0.2；α＝2；β＝4；NC max＝200；Q＝10000。在仿真過程中連續(xù)計(jì)算20次，具體計(jì)算結(jié)果如表5所示。

表5 利用蟻群算法連續(xù)進(jìn)行20次計(jì)算的統(tǒng)計(jì)結(jié)果表

從表5可以看出，使用蟻群算法求解車種代用下的空車調(diào)配模型具有得到最優(yōu)解的比率高、平均解相對誤差低、最優(yōu)解的收斂速度較快等優(yōu)點(diǎn)，能很好地解決空車產(chǎn)生總數(shù)和空車需求總數(shù)相等的平衡運(yùn)輸問題。