鐵路樞紐空車調(diào)配多目標優(yōu)化模型及算法

李菲菲，肖旭航，金啟明

（蘭州交通大學 交通運輸學院，甘肅 蘭州730070）

0 引言

在鐵路貨物運輸中的空車調(diào)配，是指由卸大于裝的車站向裝大于卸的車站進行車輛排空，以保證裝車站能夠有足夠的空車進行裝車［1］。

針對空車調(diào)配問題，王鐵君［2］等針對求解大規(guī)?？哲囌{(diào)配問題提出混沌自適應變異的粒子群算法。程學慶［3］建立了空車調(diào)配的多目標優(yōu)化模型并利用Lingo求解。張紅斌［4］等建立了能力約束下的動態(tài)優(yōu)化模型，并使用融合K短路的模擬退火算法求解。閆建文［5］等建立了以空車到達時間可靠性最大和空車走行成本最小為優(yōu)化目標的模型。李立［6］等建立了評價空車調(diào)配效率的數(shù)學模型。于橫［7］等在考慮節(jié)點車流平衡、貨車保有量等約束條件下，建立了以鐵路最大收益為優(yōu)化目標的數(shù)學模型。蔣靈明［8］等用電磁鐵吸附效應理論構(gòu)造了空車調(diào)配算法。從上述文獻可以看出，已有的研究集中在模型與算法優(yōu)化方面，但存在著優(yōu)化角度單一或建模時沒有考慮到車種代用、路徑運輸能力等情況，且多為路網(wǎng)層面的空車調(diào)配研究。為此，本文在綜合考慮空車調(diào)配成本、貨主滿意度、路徑運輸能力限制、車種代用等因素下，建立樞紐內(nèi)空車調(diào)配問題的多目標優(yōu)化模型，并提出相應的求解算法。

1 空車調(diào)配問題分析

1.1 影響空車調(diào)配成本的因素分析在空車調(diào)配過程中，影響調(diào)配成本的因素主要有：空車的運輸成本；車種代用時產(chǎn)生的成本，如加固費用、加篷布費用等；由于空車提前到達裝車需求站所產(chǎn)生的積壓庫存成本，以及空車過晚到達需求站所產(chǎn)生的延誤損失費用。

1.2 貨主（客戶）滿意度本文以空車到達時間可靠性作為衡量客戶滿意度的標準［9］，即在貨主滿意的時段內(nèi)到達的空車越多，系統(tǒng)的到達時間可靠性越大，貨主滿意度越高。

1.3 路網(wǎng)運輸能力限制在空車調(diào)配過程中，鐵路為了降低空車運輸成本，通常會選擇最短的路徑來運輸空車，但這樣往往會造成路網(wǎng)中某些路段的流量超出其運輸能力，使路網(wǎng)流量分布不均衡，故在空車調(diào)配過程中需要考慮路徑調(diào)整。

2 空車調(diào)配多目標優(yōu)化模型的構(gòu)建

2.1 條件假設一是不考慮機車運用情況；二是空車需求站不考慮以重代空情況；三是各車種之間的代用費用為已知。

2.2 符號定義S為空車供應站集合，i∈S，i=1，2，...，n；D為空車需求站集合，j∈D，j=1，2，...，m；Si站能提供的空車總數(shù)為表示Si站所能提供的車種q輛數(shù)；Dj站需求的空車總數(shù)為表示Dj站所需求的車種r輛數(shù)表示車站Si至車站Dj所有可行路徑集合，其中表示Si至Dj的第k條路徑，λ（i，j）表示Si至Dj的可行路徑數(shù)為Si至Dj第k條路徑的最大空車運輸能力；ν為供應和需求所涉及的空車種類數(shù)為Si至Dj在第k條路徑上的空車運輸數(shù)為Si至Dj在第k條路徑上q種空車代用r種空車的運輸輛數(shù)為Si至Dj在第k條路徑上每輛空車的運輸成為車種q代用車種r的單位成本；Pj為Dj站的空車到達時間可靠性；ej為Dj站貨主滿意的最早裝車時間；lj為Dj站貨主滿意的最晚裝車時間；αj、βj分別為需求站Dj在單位時間內(nèi)每輛空車的積壓庫存成本、延誤損失費用為Si至Dj在路徑k上運輸?shù)某霭l(fā)時刻為Si至Dj在路徑k上的運輸時間為Si至Dj在路徑k上運輸?shù)牡竭_時刻；Punj為在貨主滿意的裝車時段內(nèi)到達Dj站的空車數(shù)。

2.3 建立模型

式（1）~式（4）為目標函數(shù)。式（1）為總運輸成本最??；式（2）為空車總的積壓庫存費用及延誤損失費用最小；式（3）為總車種代用費用最??；式（4）為空車調(diào)配系統(tǒng)的到達時間可靠性最大。

式（5）表示Si站發(fā)往各需求站的空車總數(shù)等于其空車供應量；式（6）表示Dj站從各供應站接收到的空車總數(shù)等于其空車需求量；式（7）為路徑運輸能力約束，表示各路徑的空車運輸量不得超過該路徑的最大運輸能力；式（8）為空車運達時刻的計算公式；式（9）為Dj站的到達時間可靠性計算公式；式（10）為各車種間的代用費用。

3 模型的求解算法

3.1 單目標處理首先分別求目標函數(shù)Z1、Z2、Z3、Z4的上界，然后將各目標函數(shù)通過式（11）轉(zhuǎn)化為一個總的目標函數(shù)Z，這樣即可將Z1、Z2、Z3、Z4轉(zhuǎn)化為具有相同量綱的單目標函數(shù)。式中：ηi為權(quán)重系數(shù)，

ηi≥0且η1+η2+η3+η4=1；

3.2 改進的和聲搜索算法和聲搜索算法是Geem Z W等人在2001提出的智能優(yōu)化算法［10］，具有適用范圍廣、原理簡單、調(diào)整參數(shù)少等優(yōu)點，本文選取改進的和聲搜索算法對模型進行求解。

3.2.1 算法設計

1）和聲記憶庫的規(guī)模HMS。HMS為記憶庫中和聲的個數(shù)，HMS越大，算法的全局搜索能力越強，但運算時間也會變長，本文取HMS=30。

2）初始解（和聲）的構(gòu)造方法。為便于編程，本文設各空車供應站可選擇的空車運輸路徑數(shù)目均為c，當某供應站可選擇的運輸路徑小于c時可建立虛擬路徑將路徑數(shù)目補充至c，并令虛擬路徑的空車運輸能力為0。首先根據(jù)各車站各車種的供需關(guān)系以及路徑信息細分，生成一個cνn×νm的矩陣，該矩陣中每個元素用yij表示，然后按照以下步驟生成初始解：

Step1隨機生成i、j，

其中i∈［1，cvn］，j∈［1，vm］。

Step2若當前元素所對應的車種沖突，則令yij=0，返回Step1；否則進行Step3。

Step7若矩陣中所有元素均被賦值，則停止步驟；否則返回Step1。

3）記憶庫取值概率HMCR。HMCR通常取0~1之間較大的數(shù)，本文取0.8。

4）微調(diào)概率PAR。傳統(tǒng)的和聲搜索算法PAR為一個固定值，具有一定的局限性，本文對PAR的取值設計進行了動態(tài)調(diào)整改進，如式（12）所示。

式中：PARmin為PAR的初始值，本文取0.4；PARmax為PAR的上限值，本文取0.9；Tmax為最大迭代次數(shù)，本文取50；t為當前的迭代次數(shù)。

從式（12）可以看出PAR在算法迭代過程中會隨著迭代次數(shù)增加而逐漸增大，這樣做的好處在于：較小的PAR在算法迭代初期會提高算法的局部尋優(yōu)質(zhì)量，較大的PAR在算法中后期有助于跳出局部最優(yōu)情況。

5）微調(diào)規(guī)則。

①隨機生成i、j，其中i∈［1，cνn］，j∈［1，νm］。

②若yij=0：在第i行中隨機挑選一個非0元素yih，在第j列中隨機挑選一個非0元素ygj，令ygh+θ、yij=yij+θ;若無法找到滿足上述條件的yih和ygj，則重新生成i，j進行微調(diào)。

③若yij≠0，在第i行中隨機挑選一個除yij之外的非零元素記為yij，然后在第h列中隨機挑選一個非零元素記為ygh；若第i行中無非零元素則在第j列中隨機挑選一個非零元素記為ygj，然后在第g行中隨機挑選一個非零元素記為ygh。令θ=min{yif，yij-θ；若無法找到滿足上述要求的ygh，則重新生成i，j進行微調(diào)。

6）解的評價。本文選取總的目標函數(shù)值Z作為解的評價，即Z越小，解的評價越優(yōu)。

3.2.2 算法步驟描述

Step1初始化算法參數(shù)，令迭代次數(shù)t=1，隨機生成HMS個初始和聲構(gòu)成記憶庫HM。

Step2生 成 一 個 隨 機 數(shù)rand1∈［0，1］，若rand1＜HMCR，轉(zhuǎn)Step3；否則轉(zhuǎn)Step4。

Step3在HM中隨機選出一和聲記為Xnew，生成一個隨機數(shù)rand2∈［0，1］，若rand2＜PAR，則對Xnew進行微調(diào)，轉(zhuǎn)Step5；否則不需進行此微調(diào)。

Step4用初始和聲的構(gòu)造方法生成新的和聲記為Xnew。

Step5若Xnew優(yōu)于HM中最差的和聲，則將Xnew替換掉HM中最差的和聲。

Step6令t=t+1，若t＞Tmax則終止迭代，輸出HM中最好的和聲；否則返回Step2。

4 算例分析

某鐵路樞紐內(nèi)有3個空車供應站，分別用S1，S2，S3表示；4個空車需求站，分別用D1，D2，D3，D4表示；共有3種類型的空車。表1為各車站的空車供需情況；表2為各車站之間的運輸成本、運輸時間及路徑信息；表3為各供應站空車的出發(fā)時間；表4為各空車需求站對空車到達時間的要求；表5為各需求站的積壓庫存成本及延誤損失費用；表6為各車種之間的代用成本。試制定合理的空車調(diào)配方案。

表1 各車站的空車供需情況 輛

表2 各車站之間的運輸成本、運輸時間及路徑信息 單位：h

表3 各空車供應站的空車出發(fā)時間

表4 空車需求站對空車到達時間要求

表5 各空車需求站的積壓庫存成本及延誤損失費用元/（車·h）

表6 車種代用費用 單位：元/車

算例在3.4GHZ的PC端，利用C++編程實現(xiàn)。取η1=η2=η3=η4=0.25，HMS取30，HMCR取0.8，PARmin取0.4，PARmax取0.8，最 大 迭 代 次 數(shù)Tmax取100。由于空車供應總量與空車需求總量不相等，故需要引入一個虛擬需求站D5將原問題轉(zhuǎn)換為產(chǎn)銷平衡問題，設D5到所有供應站的運輸成本為0，空車需求數(shù)為8輛。程序運行10次的平均運行時間為0.6s，求得的最優(yōu)調(diào)配方案如表7所示，最佳方案的運輸成本為2760元，積壓庫存費用為12元，車種代用成本為739元，整個調(diào)配系統(tǒng)的空車到達時間可靠性為98.5%，調(diào)配方案滿足路徑能力約束。

表7 算例仿真結(jié)果

5 結(jié)束語

空車調(diào)配是鐵路貨物運輸生產(chǎn)中的重要環(huán)節(jié)，將鐵路效益、貨主滿意度、路網(wǎng)運輸能力綜合考慮優(yōu)化符合鐵路的發(fā)展方向。對于建立的多目標優(yōu)化模型，改進的和聲搜索算法對模型的求解效果良好，可根據(jù)實際需求來調(diào)整權(quán)重系數(shù)及算法參數(shù)，以應對復雜多樣的實際情況。下一步將針對動態(tài)空車調(diào)配的綜合優(yōu)化問題進行研究。