李菲菲，肖旭航，金啟明

（蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州730070）

0 引言

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

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

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

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

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

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

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

2.1 條件假設(shè)一是不考慮機(jī)車運(yùn)用情況；二是空車需求站不考慮以重代空情況；三是各車種之間的代用費(fèi)用為已知。

2.2 符號(hào)定義S為空車供應(yīng)站集合，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條路徑的最大空車運(yùn)輸能力；ν為供應(yīng)和需求所涉及的空車種類數(shù)為Si至Dj在第k條路徑上的空車運(yùn)輸數(shù)為Si至Dj在第k條路徑上q種空車代用r種空車的運(yùn)輸輛數(shù)為Si至Dj在第k條路徑上每輛空車的運(yùn)輸成為車種q代用車種r的單位成本；Pj為Dj站的空車到達(dá)時(shí)間可靠性；ej為Dj站貨主滿意的最早裝車時(shí)間；lj為Dj站貨主滿意的最晚裝車時(shí)間；αj、βj分別為需求站Dj在單位時(shí)間內(nèi)每輛空車的積壓庫(kù)存成本、延誤損失費(fèi)用為Si至Dj在路徑k上運(yùn)輸?shù)某霭l(fā)時(shí)刻為Si至Dj在路徑k上的運(yùn)輸時(shí)間為Si至Dj在路徑k上運(yùn)輸?shù)牡竭_(dá)時(shí)刻；Punj為在貨主滿意的裝車時(shí)段內(nèi)到達(dá)Dj站的空車數(shù)。

2.3 建立模型

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

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

3 模型的求解算法

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

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

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

3.2.1 算法設(shè)計(jì)

1）和聲記憶庫(kù)的規(guī)模HMS。HMS為記憶庫(kù)中和聲的個(gè)數(shù)，HMS越大，算法的全局搜索能力越強(qiáng)，但運(yùn)算時(shí)間也會(huì)變長(zhǎng)，本文取HMS=30。

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

Step1隨機(jī)生成i、j，

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

Step2若當(dāng)前元素所對(duì)應(yīng)的車種沖突，則令yij=0，返回Step1；否則進(jìn)行Step3。

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

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

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

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

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

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

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

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

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

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

3.2.2 算法步驟描述

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

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

Step3在HM中隨機(jī)選出一和聲記為Xnew，生成一個(gè)隨機(jī)數(shù)rand2∈［0，1］，若rand2＜PAR，則對(duì)Xnew進(jìn)行微調(diào)，轉(zhuǎn)Step5；否則不需進(jìn)行此微調(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個(gè)空車供應(yīng)站，分別用S1，S2，S3表示；4個(gè)空車需求站，分別用D1，D2，D3，D4表示；共有3種類型的空車。表1為各車站的空車供需情況；表2為各車站之間的運(yùn)輸成本、運(yùn)輸時(shí)間及路徑信息；表3為各供應(yīng)站空車的出發(fā)時(shí)間；表4為各空車需求站對(duì)空車到達(dá)時(shí)間的要求；表5為各需求站的積壓庫(kù)存成本及延誤損失費(fèi)用；表6為各車種之間的代用成本。試制定合理的空車調(diào)配方案。

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

表2 各車站之間的運(yùn)輸成本、運(yùn)輸時(shí)間及路徑信息 單位：h

表3 各空車供應(yīng)站的空車出發(fā)時(shí)間

表4 空車需求站對(duì)空車到達(dá)時(shí)間要求

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

表6 車種代用費(fèi)用 單位：元/車

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

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

5 結(jié)束語

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