鐵路樞紐空車調配多目標優化模型及算法

李菲菲，肖旭航，金啟明

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

0 引言

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

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

1 空車調配問題分析

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

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

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

2 空車調配多目標優化模型的構建

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

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

2.3 建立模型

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

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

3 模型的求解算法

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

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

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

3.2.1 算法設計

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

2）初始解（和聲）的構造方法。為便于編程，本文設各空車供應站可選擇的空車運輸路徑數目均為c，當某供應站可選擇的運輸路徑小于c時可建立虛擬路徑將路徑數目補充至c，并令虛擬路徑的空車運輸能力為0。首先根據各車站各車種的供需關系以及路徑信息細分，生成一個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之間較大的數，本文取0.8。

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

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

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

5）微調規則。

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

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

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

6）解的評價。本文選取總的目標函數值Z作為解的評價，即Z越小，解的評價越優。

3.2.2 算法步驟描述

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

Step2生 成 一 個 隨 機 數rand1∈［0，1］，若rand1＜HMCR，轉Step3；否則轉Step4。

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

Step4用初始和聲的構造方法生成新的和聲記為Xnew。

Step5若Xnew優于HM中最差的和聲，則將Xnew替換掉HM中最差的和聲。

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

4 算例分析

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

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

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

表3 各空車供應站的空車出發時間

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

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

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

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

表7 算例仿真結果

5 結束語

空車調配是鐵路貨物運輸生產中的重要環節，將鐵路效益、貨主滿意度、路網運輸能力綜合考慮優化符合鐵路的發展方向。對于建立的多目標優化模型，改進的和聲搜索算法對模型的求解效果良好，可根據實際需求來調整權重系數及算法參數，以應對復雜多樣的實際情況。下一步將針對動態空車調配的綜合優化問題進行研究。