鐵路空車調配問題的區間線性規劃模型及算法

曲思源

（上海鐵路局運輸處，上海200071）

鐵路空車調配問題的區間線性規劃模型及算法

曲思源

（上海鐵路局運輸處，上海200071）

摘要：鐵路空車調配問題是合理解決空車需求與供應之間的不平衡問題。在借鑒空車調配問題模型已有成果的基礎上，圍繞空車供應與需求量的不確定性、空車調配的時效性、路段通過能力的限制性3個方面，對區間數運用于空車調配問題加以適應性分析，以空車總走行公里最少和到達時間滿足空車需求限定時間可信度加權和最大為目標，提出利用線性區間規劃理論解決空車調配問題的模型和算法，并結合算例驗證了區間規劃的靈活性和簡便性，使得空車調整模型符合運輸生產實際并具有普遍意義，該模型的采用對路網上空車調整問題將起到很好的借鑒作用。

關鍵詞：鐵路運輸；區間規劃；空車調配；模型

鐵路空車調配問題是合理解決空車需求與供應之間的不平衡問題。受路網規模龐大和涉及因素復雜等影響，長期以來空車調配一直是理論研究上的難點。許多學者針對這一問題展開研究，構建了一系列模型及算法，成效顯著。分析目前該領域的研究工作主要有如下特點：可將空車調配問題分為靜態和動態優化兩種類型，靜態調配研究通常以空車走行公里或運輸費用最小化為目標構建模型獲得路網供需節點間的空車最優分配方案。前提是不考慮隨機變化，假設一段時期內的空車供需情況是穩定的。靜態調配模型大多作為簡單的運輸問題處理，研究方法包括傳統運輸問題方法以及現代啟發式方法包括遺傳、蟻群、粒子群法等［1-4］。動態優化使得模型進一步符合空車調配的運輸組織實際，主要表現在運輸時間、空車供給量和需求量以及路段通過能力等方面具有隨機特征。文獻［5］提出了基于時間約束的空車調配模型和求解算法；文獻［6］考慮到路網運輸能力限制，采取了迭代算法進行分步優化；文獻［7］引入隨機規劃理論研究了鐵路空車調配的隨機性。同時，文獻［8］引入“時間窗”約束條件，文獻［9］利用模糊數學隸屬度函數提出貨主滿意度，使得空車調整向裝車站的配空時機方向擴展。然而，利用區間規劃理論研究空車調配問題較少。本研究在前人學者研究成果的基礎上，針對鐵路空車調配運輸過程中的不確定性和動態性等因素，構建基于區間規劃的空車調整模型，體現出區間規劃靈活以及簡便的求解特征，以便為空車調配問題提供新的思路和方法。

1　區間數運用空車調配問題的適應性分析

1.1空車供求的不確定性

空車調配確定性模型往往都是假設卸車站的空車數、裝車站需要的空車數是確定的，實際上每天卸車站產生的空車數由于作業車延誤、扣修車輛和到達貨車信息不準確等不確定性因素，裝車站由于路網意外情況導致的停限裝、貨主需求不同和資金等不確定性因素影響，需要對確定性模型進行改進［7］。也就是說，空車供應和需求量均存在著不確定因素。目前的不確定系統優化問題比較成熟的模型有隨機與模糊數學規劃方法。隨機規劃問題中，以一定的概率滿足運輸需求，并假定空車數據服從某些分布的隨機變量，要求系數的分布函數為已知；而模糊規劃問題要求知道系數的隸屬度函數。在實際問題中，分布函數與隸屬度函數并不總是容易得到。很多情況下，數學規劃問題的系數在某個區間內變化范圍是容易知道的。在空車調配過程中，空車供應數和需求數可描述為區間數，不確定系統用區間規劃的模型描述與求解會變得簡單實用，同時也符合實際需要。

1.2路段通過能力限制

一般而言，空車在調配過程中要按照最短徑路運送，而且在同一路段不準許空車對流，這樣空車從卸車站到裝車站的單位走行公里是確定值，以保證正常的運輸秩序。但是，空車在運送過程中，經常受徑路上的路段通過能力限制，路段通過能力限制（比如施工、設備故障等情況影響）主要體現在運送的空車流量方面無法達到該路段的空車容量。在考慮空車調配模型過程中，路段通過能力限制不能忽視。此時，需要采取車流迂回徑路的調整方式，其前提是不影響迂回徑路正常的運輸秩序。這種現象在調度指揮過程中經常遇到。調度員在做計劃的過程中，要事先考慮路段限制情況，再分配給該路段限制通過空車數量，路段限制能力是空車調配模型的主要約束條件之一。

1.3空車到達實效性

為了操作上的方便，目前各鐵路局使用的空車調配方法，一般都淡化了車流的時效性，而采用比較籠統的方法。隨著各種交通方式競爭的激烈和現代物流理論的發展，貨主對鐵路空車按時到達裝車站的時間要求越來越高。只有在規定時間內到達的空車才會使貨物得到及時裝運。因此，在運輸組織的實際過程中，不考慮時效性的空車調配會帶來不良后果：一是造成了貨源流失，站點的計劃貨源由于無車可裝而轉向其他運輸方式；二是造成了裝車站裝車資源的浪費，而其它裝車站裝車資源匱乏。這樣，建立空車送達時間表就顯得尤為重要，這也是提高鐵路運輸服務質量的表現。在空車運送過程中，受各種變化的運輸環境影響，調度員要做好列車運行計劃調整，通過階段計劃不斷地將空車到達裝車站時間精確，運送時間是一個區間數就顯得更為合理。因此，在空車調配過程中，空車從卸車站到達裝車站的時間可用區間數表示，具有一定的不確定性，符合實際需要，同時要規定裝車站送達限制時間。

綜上，在空車調配過程中，還需要考慮各種隨機和干擾因素，可將這些因素初步劃歸為區間數處理，而區間數的兩端取值根據這些因素的影響而變化，通過取值的不同表現出各種因素的變化。

2　區間線性規劃基本理論

2.1區間數定義

參考文獻［10］，給出定義1—定義3。

定義1

定義2

定義3

為A≤B的可信度。

2.2區間規劃模型及求解

20世紀60年代曾引起學者們關注的區間線性規劃指的是下述問題[10 ]

定理1

滿足AIx≥bI,x≥0時x的最小取值范圍為

最大取值范圍為

下面給出有關證明。

若x≥0滿足A-x≥b+，必有Ax≥A-x≥b+≥b成立，亦即x≥0只要滿足式（1），則必滿足Ax≥b,AAI,bbI，這就證明了

所以，式（1）表示的是滿足AIx≥bI,x≥0時x的最小取值范圍。又由于對任意的x≥0，成立任取AAI,bbI，x≥0，若Ax≥b，x≥0，則有

所以，式（2）表示的是滿足AIx≥bI,x≥0時的x的最大取值范圍。證畢。

3　模型構建與求解

3.1模型構建

當給定需求點Dj的從空車運送時間開始計時的裝車站空車需求限定期Tij，根據定義3，可得資源Si準時運到Dj的可信度為

這樣，建立目標如下

目標函數式（4）表示空車總走行公里最少；目標式（5）表示空車運送時間滿足裝車站裝車需求時間限制的可信度加權值最大。

限制條件中，式（6）—式（7）表示空車供需平衡；式（8）表示路段能力限制，L為路網上所有路段集合，l為路網上任意路段，有lL，相應路段的流量和容量分別為fl和fL；式（9）確保0～1變量yij=1僅當xij>0，表示任意小的正數，M表示任意大的正數；式（11）表示Si→Dj運送時間tij

I小于等于從空車運送時間開始計時的裝車站空車需求限定期。

3.2模型求解

考慮到可信度取值，其累加值比較小，當第一部分值較大時，在整個模型中所占的比重非常小，它對總目標函數的影響很少，有可能搜索不到最優解。為增強時間期限的變化，要通過轉換因子轉換以確保目標結果正確，轉化為的單目標規劃模型

令bij=1-ij(i=1,2,…,m;j=1,2,…,n)，存在

這樣，多目標可轉換為單目標

然后根據區間規劃求解方法進行求解，因運輸問題具有特性，如ij=1，可直接利用Lingo軟件進行求解，并把路段通過能力限制作為限制條件之一。

4　　算例

現模擬某鐵路局管內配空實例，存在3個卸空站、4個裝車需求站。考慮到隨機干擾等因素，其發送、需求量及走行公里如表1所示；運送時間及裝車需求時間如表2所示。設S1→D1路段能力限制為40輛，S3→D2限制為70輛，且1=0.6,2=0.4。

表1　卸車站、裝車站走行公里及發送量和需求量表Tab.1 Running kilometers，sending quantity and demand quantity at unloading stations and loading stations

表2　卸車站、裝車站運送時間和限定時間Tab. 2 The delivery time and time limit of unloading stations and loading stations　h

求解步驟如下：

2）利用LINGO軟件進行求解，按照式（14）可得最優方案運輸費用z=[35 943.0,40 431.6]，其區間解如表3所示。

表3　區間解Tab.3 The interval solution　　輛

算例表明，該模型能夠很好的解決空車調整實際并克服經驗決策，使得配空更科學、合理，在當前壓縮運輸成本、增運節支方面起到很好的效果，可用于編制高質量的空車調配計劃。

5　　結語

采用區間規劃方法驗證了鐵路空車調配的可行和有效性，使得不確定模型更接近實際問題，反映現場作業情況，為空車調配問題提供新的思路和方法。然而，一個復雜的決策問題通常在各種不確定因素混合環境之中，這種不確定性不再是單一的隨機性或模糊性，而是它們相互滲透、相互影響，模糊隨機性是一種具體體現。所以，不確定性優化研究將在鐵路運輸管理中越來越受到重視。空車調配模型需要進一步研究各種干擾因素的模糊隨機性等機會約束的影響。

[1]劉洪濤.技術計劃空車調整的數學模型[J].鐵路計算機應用, 2005,14(7):21-23.

[2]杜艷平,尹曉峰,劉春煌.采用蟻群算法求解鐵路空車調整問題[J].中國鐵道科學, 2006,27(4):119-122.

[3]閆海峰,譚云江,朱健梅.鐵路空車調整蟻群算法的研究[J].鐵道運輸與經濟, 2006,28(8):31-34.

[4]鄔開俊,魯懷偉,王鐵君.基于自適應變異粒子群算法的鐵路空車調配[J].蘭州理工大學學報, 2011,37(2):102-105.

[5]李宗平,夏劍鋒,基于時間約束的鐵路空車調配模型與算法[J].西南交通大學學報, 2005,40(3):361-365.

[6]林柏梁,喬國會.基于線路能力約束下的鐵路空車調配迭代算法[J].中國鐵道科學, 2008,29(1):93-96.

[7]雷中林,何世偉,宋瑞,等.鐵路空車調配問題的隨機機會約束模型及遺傳算法[J].鐵道學報, 2005,27(5):1-5.

[8]陳昱,張喜.帶時間窗空車調整問題的遺傳算法研究[J].鐵路計算機應用, 2007,16(2):4-7.

[9]程學慶,蒲云.基于貨主滿意度的模糊空車調配模型的研究[J].鐵道運輸與經濟, 2007, 29(11): 71-73.

[10]李煒.線性規劃及其擴展[M].北京:國防工業出版社, 2011:8.

（責任編輯姜紅貴）

Interval Linear Programming Model and Algorithm for Railway Empty Car Distribution

Qu Siyuan
(Transport Department, Shanghai Railway Bureau, Shanghai 200071, China)

Abstract:Railway empty car distribution is a solution to the demand and supply imbalance of empty cars. On the ba?sis of the empty car distribution model, centering on three aspects including the supply and demand uncertainty of empty cars, the deployment timeliness and the limit of interval capability, this paper conducts adaptive analysis of the empty car distribution. To achieve minimum kilometers of the total empty mileage and the maximum weighted credibility of the empty demand for limited time in terms of arrival time, the paper proposes linear interval planning theory to obtain the model and algorithm of empty car distribution. Combined with examples to verify the flexibility and simplicity of the interval planning, it concludes the proposed empty distribution model can meet the practical transportation and production demands, providing reference and significance for the distribution of railway empty car.

Key words:railway transport; interval linear programming; empty car distribution; model

作者簡介：曲思源（1972—），男，高級工程師，博士，研究方向為交通運輸規劃與管理。

收稿日期：2014-11-14

文章編號：1005-0523（2015）03-0006-06

中圖分類號：U292.45

文獻標志碼：A