基于服務(wù)網(wǎng)絡(luò)動態(tài)配流的直達(dá)列車開行方案優(yōu)化編制方法

唐金金，楊露萍,周磊山

(1.北京交通大學(xué) 交通運(yùn)輸學(xué)院，北京　100044；2.中國鐵道科學(xué)研究院 運(yùn)輸及經(jīng)濟(jì)研究所，北京　100081)

鐵路車流組織是指確定車流在鐵路網(wǎng)絡(luò)上的運(yùn)行徑路、直達(dá)列車開行方案以及車流改編方案等[1]。由于鐵路路網(wǎng)規(guī)模龐大、車站數(shù)量多、OD車流方向眾多、車流和列車流繁多，使得運(yùn)行徑路、直達(dá)列車開行方案以及車流改編方案均非常龐大，國內(nèi)外眾多專家學(xué)者論證了該問題是NP-Hard問題。因此，實(shí)際鐵路車流組織過程中，將鐵路車流組織優(yōu)化問題分解為2步，第1步是車流徑路優(yōu)化，第2步是貨物列車編組計(jì)劃優(yōu)化，其中直達(dá)列車開行方案優(yōu)化是其核心。文獻(xiàn)[2]研究了鐵路路網(wǎng)上車流徑路優(yōu)化的0-1規(guī)劃模型及其合理徑路生成算法。文獻(xiàn)[2—11]嘗試用精確算法求解列車編組計(jì)劃優(yōu)化編制問題，但是難以求解大規(guī)模網(wǎng)絡(luò)問題。文獻(xiàn)[12—13]采用模擬退火等啟發(fā)式算法求解了大規(guī)模編組計(jì)劃優(yōu)化編制問題。然而既有列車編組計(jì)劃優(yōu)化編制模型和求解算法中依然存在2個難點(diǎn)難以克服。一是既有文獻(xiàn)假設(shè)車流集結(jié)參數(shù)為固定值，而實(shí)際集結(jié)參數(shù)應(yīng)為變量；二是在求解大規(guī)模路網(wǎng)的編組計(jì)劃優(yōu)化編制問題時，算法求解時間依然過長，難以滿足鐵路運(yùn)輸部門實(shí)際應(yīng)用要求。

為此，本文將編組計(jì)劃中的直達(dá)列車開行方案優(yōu)化編制問題轉(zhuǎn)化為網(wǎng)絡(luò)設(shè)計(jì)中的服務(wù)網(wǎng)絡(luò)動態(tài)配流問題。具體方法是根據(jù)所有可能的直達(dá)開行方案構(gòu)建服務(wù)網(wǎng)絡(luò)；參考道路交通中車流與能力關(guān)系的BPR函數(shù)，進(jìn)一步構(gòu)建路段旅行費(fèi)用與車流量的關(guān)系函數(shù)，從而將車流集結(jié)參數(shù)函數(shù)化；基于服務(wù)網(wǎng)絡(luò)動態(tài)配流算法，實(shí)現(xiàn)服務(wù)網(wǎng)絡(luò)流的平衡；此時服務(wù)網(wǎng)絡(luò)中存在車流量的方案弧則表示對應(yīng)編組站間需要開行直達(dá)列車，所有需要開行的直達(dá)列車即組成優(yōu)化的直達(dá)列車開行方案。以某地區(qū)鐵路網(wǎng)絡(luò)為例，驗(yàn)證本方法的可行性和有效性。

1　根據(jù)所有可能的直達(dá)列車開行方案構(gòu)建服務(wù)網(wǎng)絡(luò)的方法

根據(jù)所有可能的直達(dá)列車開行方案構(gòu)建服務(wù)網(wǎng)絡(luò)的核心思想：①將編組站視為服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)，編組站間可開行的直達(dá)去向視為節(jié)點(diǎn)間有向弧，并將該有向弧作為方案弧，將該直達(dá)去向車流的集結(jié)時間和旅行時間之和作為方案弧的旅行費(fèi)用；②將服務(wù)網(wǎng)絡(luò)節(jié)點(diǎn)進(jìn)一步分解成入流節(jié)點(diǎn)和出流節(jié)點(diǎn)，其中終到車流到達(dá)入流節(jié)點(diǎn)則停止，始發(fā)車流在出流節(jié)點(diǎn)集結(jié)，通過車流于入流節(jié)點(diǎn)進(jìn)入并在出流節(jié)點(diǎn)集結(jié)，從而有效地將車站的終到、始發(fā)和通過這3種車流分離；③同一節(jié)點(diǎn)的入流節(jié)點(diǎn)至出流節(jié)點(diǎn)間構(gòu)造1條有向弧，將該有向弧作為解體弧，供通過車流解體使用，并將車流的解體時間作為解體弧的旅行費(fèi)用。

為了較好地描述該問題，選取如圖1所示的包含4個編組站的鐵路線路進(jìn)行描述。其對應(yīng)的包含全部可能直達(dá)去向的開行方案如圖2所示。將這4個編組站作為服務(wù)網(wǎng)絡(luò)的節(jié)點(diǎn)，將對應(yīng)的直達(dá)去向作為節(jié)點(diǎn)間的方案弧，則可構(gòu)造出如圖3所示的服務(wù)網(wǎng)絡(luò)。

圖1包含4個編組站的鐵路線路

圖2　包含全部可能直達(dá)去向的直達(dá)列車開行方案

圖3　包含所有直達(dá)去向的服務(wù)網(wǎng)絡(luò)

將圖3中的各節(jié)點(diǎn)進(jìn)一步分為入流節(jié)點(diǎn)和出流節(jié)點(diǎn)，并在入流節(jié)點(diǎn)至出流節(jié)點(diǎn)間構(gòu)造有向弧，將此有向弧作為解體弧，則構(gòu)建的最終服務(wù)網(wǎng)絡(luò)如圖4所示。圖4中，入流節(jié)點(diǎn)的編號仍采用原節(jié)點(diǎn)的編號，出流節(jié)點(diǎn)的編號采用在原節(jié)點(diǎn)編號的后面加“01”的形式，如鐵路網(wǎng)中的編組站1，則其節(jié)點(diǎn)編號和入流節(jié)點(diǎn)編號均為1，而出流節(jié)點(diǎn)編號為101，從而便于表述節(jié)點(diǎn)間的關(guān)系。

圖4　包含方案弧和解體弧的最終服務(wù)網(wǎng)絡(luò)

但是，實(shí)際直達(dá)列車開行方案中不可能包含所有可能的直達(dá)去向，而是依據(jù)設(shè)定的目標(biāo)函數(shù)，在所有的直達(dá)去向中選擇某些直達(dá)去向，組成優(yōu)化的直達(dá)列車開行方案。

2　服務(wù)網(wǎng)絡(luò)動態(tài)配流的優(yōu)化模型

定義φ(i，k)為0-1變量，表示弧k是否為編組站i對應(yīng)的解體弧，若是則φ(i，k)=1， 否則φ(i，k)=0。θ(l，k)為0-1變量，表示弧k是否經(jīng)由區(qū)段l，若是則θ(l，k)=1， 否則θ(l，k)=0。

定義xq，k為0-1決策變量，表示貨車q是否用弧k運(yùn)輸，若是則xq，k=1， 否則xq，k=0。yi，j為0-1決策變量，表示i至j間是否開行直達(dá)列車，若是則yi，j=1，否則yi，j=0。

(1)

以全網(wǎng)絡(luò)車流總旅行費(fèi)用最小為目標(biāo)函數(shù)，構(gòu)建的服務(wù)網(wǎng)絡(luò)動態(tài)配流優(yōu)化模型為

(2)

s.t.

(3)

wi≤Wiφ(i，k)=1， ?i，?k

(4)

(5)

約束條件中：式(3)為區(qū)段通過能力約束，即經(jīng)由區(qū)段l的所有車流量之和應(yīng)不大于該區(qū)段的通過能力；式(4)為編組站改編能力約束，即需要在編組站i改編的所有車流量之和應(yīng)不大于該編組站的解體能力；式(5)為編組站的編發(fā)去向數(shù)總數(shù)約束，即經(jīng)由編組站i需要改編的車流方向總數(shù)應(yīng)不大于該編組站規(guī)定的最大去向數(shù)。

另外，通常在直達(dá)列車開行方案優(yōu)化編制模型當(dāng)中，還應(yīng)有車流組織方案唯一性約束，即保證每支車流都有列車將其送達(dá)前方編組站改編約束。但在本文中，由于將直達(dá)列車開行方案優(yōu)化編制問題轉(zhuǎn)化成了服務(wù)網(wǎng)絡(luò)動態(tài)配流問題，這2類約束在車流分配過程中可以自動完成，無需再考慮，因此，本文方法更加簡潔。

3　動態(tài)配流優(yōu)化模型的求解算法

Wardrop于1952年提出了交通網(wǎng)絡(luò)配流的2個基本原則[14]，即用戶最優(yōu)和系統(tǒng)最優(yōu)。用戶最優(yōu)是指根據(jù)個體旅行費(fèi)用最小選擇最短徑路，再根據(jù)最短徑路進(jìn)行配流；系統(tǒng)最優(yōu)是指根據(jù)全體用戶旅行費(fèi)用之和最小進(jìn)行配流。其他專家在后續(xù)的研究中論證了用戶最優(yōu)和系統(tǒng)最優(yōu)這2個原則的合理性[15]。

本文所構(gòu)建的服務(wù)網(wǎng)絡(luò)與交通網(wǎng)絡(luò)類似，求解動態(tài)配流優(yōu)化模型的核心算法是通過仿真的方法，基于用戶最優(yōu)的原則進(jìn)行服務(wù)網(wǎng)絡(luò)配流，最終實(shí)現(xiàn)網(wǎng)絡(luò)流量的平衡。該方法是：基于單個貨車旅行費(fèi)用最小選擇最短徑路，當(dāng)所有貨車實(shí)現(xiàn)最短徑路后就完成了1次配流；由于徑路上的車流量直接影響該徑路的旅行費(fèi)用，因此完成1次配流后，需要重新計(jì)算路段旅行費(fèi)用并對所有貨車進(jìn)行最短徑路計(jì)算，如果本次計(jì)算的貨車最短徑路與上一次配流過程對應(yīng)的最短徑路不一致，那么網(wǎng)絡(luò)流量沒有達(dá)到平衡，則以當(dāng)前網(wǎng)絡(luò)旅行費(fèi)用為基礎(chǔ)再次進(jìn)行配流；通過多次迭代仿真計(jì)算，使得所有貨車在路網(wǎng)上的旅行總費(fèi)用最少，服務(wù)網(wǎng)絡(luò)中車流量達(dá)到平衡，從而完成服務(wù)網(wǎng)絡(luò)配流。設(shè)計(jì)的求解算法框圖如圖5所示。

算法過程分為2步：第1步，基于服務(wù)網(wǎng)絡(luò)，計(jì)算任意OD車流間的最短徑路，依據(jù)最短徑路將車流分配到服務(wù)網(wǎng)絡(luò)上；第2步，判斷服務(wù)網(wǎng)絡(luò)上車流是否達(dá)到平衡，如果沒有達(dá)到，則繼續(xù)第1步，否則，計(jì)算完成，得到最優(yōu)方案。

定義算法中的參數(shù)：ε為平衡性判定參數(shù)，ε=0表示網(wǎng)絡(luò)流量沒有達(dá)到平衡，ε=1表示網(wǎng)絡(luò)流量達(dá)到平衡；δ為當(dāng)有向弧容量超出其能力時其旅行費(fèi)用的提升倍數(shù)，通常設(shè)其值為δ>3。

圖5　算法框圖

由此設(shè)計(jì)的模型求解算法步驟如下。

輸入: 鐵路網(wǎng)G，全部OD車流量。

輸出: 直達(dá)列車開行優(yōu)化方案。

步驟1：初始化。

步驟1.1： 依據(jù)鐵路網(wǎng)和所有OD車流，生成包含所有可能直達(dá)去向的初始直達(dá)列車開行方案。

步驟1.2： 依據(jù)鐵路網(wǎng)和初始直達(dá)列車開行方案構(gòu)造服務(wù)網(wǎng)絡(luò)；設(shè)定δ值，令ε=0。

步驟1.3： 以編組站間旅行時間為旅行費(fèi)用，求解任意OD車流間最短徑路，實(shí)現(xiàn)初始配流。

步驟1.4： 如果有向弧的流量為0，則設(shè)定該有向弧的流量為0.000 1，從而避免計(jì)算中產(chǎn)生無窮大數(shù)。

步驟2： 動態(tài)配流優(yōu)化過程。

While (ε=1)

步驟2.1： 依據(jù)式(1)計(jì)算所有有向弧的旅行費(fèi)用ck。

步驟2.2： 依據(jù)式(3)判定所有區(qū)段的流量是否超出其通過能力。如果不超出，則步驟2.3；否則提高對應(yīng)方案弧的旅行費(fèi)用δ倍，轉(zhuǎn)步驟2.3。

步驟2.3： 依據(jù)式(5)判定任意編組站i需要改編的車流方向總數(shù)是否超過其規(guī)定的最大編組去向數(shù)Mi。如果不超出，則轉(zhuǎn)步驟2.4；否則提高對應(yīng)解體弧的旅行費(fèi)用δ倍，轉(zhuǎn)步驟2.4。

步驟2.4： 依據(jù)式(4)判定所有編組站的改編車流量是否超出其改編能力。如果不超出，則轉(zhuǎn)步驟2.5；否則提高對應(yīng)解體弧的旅行費(fèi)用δ倍，轉(zhuǎn)步驟2.5。

步驟2.5： 計(jì)算所有貨車在服務(wù)網(wǎng)絡(luò)上的最短徑路，根據(jù)本次最短徑路進(jìn)行配流。

步驟2.6： 判定所有貨車在服務(wù)網(wǎng)絡(luò)上的最短徑路與上一次配流的最短徑路是否全部一致，如果存在不一致，那么服務(wù)網(wǎng)絡(luò)就沒有達(dá)到平衡，則令ε=0；否則，表明網(wǎng)絡(luò)流量平衡，令ε=1。

End while

步驟3： 得到服務(wù)網(wǎng)絡(luò)平衡配流的結(jié)果后，抽取有流量的方案弧，生成優(yōu)化的直達(dá)列車開行方案。

步驟4： 結(jié)束計(jì)算，保存數(shù)據(jù)，輸出優(yōu)化的直達(dá)列車開行方案。

4　實(shí)例應(yīng)用

為了驗(yàn)證本文所提出的直達(dá)列車開行方案優(yōu)化編制方法的可行性與先進(jìn)性，選取文獻(xiàn)[12]中的案例進(jìn)行對比分析，該案例中的鐵路網(wǎng)有19個編組站，如圖6所示。假設(shè)編組站平均解體時間為3 h，OD車流量表與其他參數(shù)詳見文獻(xiàn)[12]。

圖6　某區(qū)域鐵路網(wǎng)

按照本文方法，依據(jù)鐵路網(wǎng)結(jié)構(gòu)和OD車流量，構(gòu)建的包含方案弧和解體弧的服務(wù)網(wǎng)絡(luò)如圖7所示。

圖7　包含方案弧和解體弧的服務(wù)網(wǎng)絡(luò)

將本文提出的方法用C# 2010編程實(shí)現(xiàn)。在CPU為Inter Core i7 2.8 GHZ，內(nèi)存為4.0 GB，操縱系統(tǒng)為Windows Sever 2008條件下，對上述案例進(jìn)行服務(wù)網(wǎng)絡(luò)動態(tài)配流，經(jīng)過30次迭代達(dá)到網(wǎng)絡(luò)流量的平衡，完成全部配流過程耗時58 s。得到的直達(dá)列車開行優(yōu)化方案為：總旅行費(fèi)用39 062車小時，共有66個直達(dá)去向，見表1和圖8。由于直達(dá)去向較多，為了直觀，圖8中僅顯示了編組站2開行的直達(dá)列車開行方案，包括2-1,2-3,

表1　優(yōu)化解結(jié)果

圖8　服務(wù)網(wǎng)絡(luò)動態(tài)配流計(jì)算結(jié)果

2-4,2-5,2-8，寬的線條表示該方案弧存在車流。

文獻(xiàn)[12]計(jì)算得到的直達(dá)列車開行優(yōu)化方案為：總旅行費(fèi)用45 421車小時，共有69個直達(dá)去向。對比本文的與文獻(xiàn)[12]的計(jì)算結(jié)果可知：本文方案的總旅行費(fèi)用節(jié)省11%，少開行3個直達(dá)去向，可見本文的優(yōu)化效果優(yōu)于文獻(xiàn)[12]。

截止到2014年12月，全路有40個編組站[16]?？梢姳疚倪x取有19個編組站的網(wǎng)絡(luò)是有一定代表性的。

5　結(jié)　語

本文提出了利用服務(wù)網(wǎng)絡(luò)動態(tài)配流方法解決直達(dá)列車開行方案優(yōu)化編制問題。重點(diǎn)研究如何將直達(dá)列車開行方案優(yōu)化編制問題轉(zhuǎn)化為服務(wù)網(wǎng)絡(luò)動態(tài)配流優(yōu)化問題的方法，并構(gòu)建了全新的服務(wù)網(wǎng)絡(luò)動態(tài)配流模型，將直達(dá)車流集結(jié)車小時消耗與車流在各編組站內(nèi)改編車小時消耗統(tǒng)一轉(zhuǎn)化為車流在有向弧上的旅行費(fèi)用。運(yùn)用動態(tài)配流算法實(shí)現(xiàn)網(wǎng)絡(luò)流平衡，從而得出優(yōu)化的直達(dá)列車開行方案。以我國某區(qū)域鐵路網(wǎng)為例，對比分析了基于服務(wù)網(wǎng)絡(luò)動態(tài)配流的直達(dá)列車開行方案優(yōu)化編制方法與既有方法的優(yōu)劣，計(jì)算結(jié)果表明，采用本文方法能夠快速、準(zhǔn)確地得到優(yōu)化的直達(dá)列車開行方案。

[1]楊浩, 何世偉. 鐵路運(yùn)輸組織學(xué)[M].3版. 北京:中國鐵道出版社, 2011: 203-244.

(YANG Hao, HE Shiwei. Transportation Organization of Railway [M].3rd ed.Beijing: China Railway Publishing House， 2011: 203-244. in Chinese)

[2]林柏梁, 朱松年,陳竹生, 等. 路網(wǎng)上車流徑路優(yōu)化的0-1規(guī)劃模型及其合理徑路集生成算法[J]. 鐵道學(xué)報(bào),1997,19(1): 7-12.

(LIN Boliang, ZHU Songnian, CHEN Zhusheng, et al. The 0-1 Integer Programming Model for Optimal Car Routing Problem and Algorithm for the Available Set in Rail Network [J]. Journal of the China Railway Society, 1997,19(1): 7-12. in Chinese.)

[3]HARRY N Newton，CYNTHIA Barnhart，PAMELA H Vance. Constructing Railroad Blocking Plans to Minimize Handling Costs [J]. Transportation Science, 1998, 32(4): 330-345.

[4]CYNTHIA Barnhart，HONG Jin，PAMELA H Vance. Railroad Blocking: a Network Design Application [J].Operations Research, 2000, 48(4): 603-614.

[5]RAVINDRA K Ahuja，KRISHNA C Jha，JIAN Liu. Solving Real-Life Railroad Blocking Problems [J]. Interfaces, 2007, 37(5): 404-419.

[6]彭其淵, 閆海峰, 周勇. 集裝箱班列編組計(jì)劃相關(guān)因素分析[J]. 中國鐵道科學(xué), 2003,24(5):120-123.

(PENG Qiyuan, YAN Haifeng, ZHOU Yong. Analysis of Factors Relevant to Formation Plan of Container Blocks [J]. China Railway Science, 2003, 24(5):120-123. in Chinese)

[7]閆海峰, 彭其淵, 譚云江. 結(jié)點(diǎn)站間集裝箱班列開行方案的優(yōu)化模型及算法[J]. 中國鐵道科學(xué), 2008, 29(1): 97-101.

(YAN Haifeng, PENG Qiyuan, TAN Yunjiang. Optimization Model and Algorithm of Block Container Trains Formation Plan between Railway Network Container Freight Stations [J]. China Railway Science, 2008, 29(1): 97-101. in Chinese)

[8]陳崇雙, 王慈光, 薛鋒, 等. 貨物列車編組計(jì)劃國內(nèi)外研究綜述[J]. 鐵道學(xué)報(bào), 2012, 34(2): 8-20.

(CHEN Chongshuang, WANG Ciguang, XUE Feng, et al. Survey of Optimization of Train Formation Plan at Home and Abroad [J]. Journal of the China Railway Society, 2012, 34(2): 8-20. in Chinese)

[9]史峰, 李致中, 孫焰, 等. 列車編組計(jì)劃網(wǎng)絡(luò)優(yōu)化方法[J]. 鐵道學(xué)報(bào), 1994, 16(2): 74-79.

(SHI Feng, LI Zhizhong, SUN Yan, et al. A Network Optimizing Method for the Train Formation Plan [J]. Journal of the China Railway Society, 1994, 16(2): 74-79. in Chinese)

[10]王志美, 林柏梁, 陳雷, 等. 多點(diǎn)列車編組計(jì)劃優(yōu)化模型研究[J]. 中國鐵道科學(xué), 2012, 33(6):108-114.

(WANG Zhimei, LIN Boliang, CHEN Lei, et al. Research on the Optimization Model for Multi-Point Train Formation Plan [J]. China Railway Science, 2012, 33(6): 108-114. in Chinese)

[11]陳崇雙, 王慈光. 分組列車優(yōu)化組織理論與方法研究[J]. 中國鐵道科學(xué), 2015, 36(2):142-144.

(CHEN Chongshuang, WANG Ciguang. Research on Optimized Organization Theory and Method for Multi-Block Train [J]. China Railway Science, 2015, 36(2): 142-144. in Chinese)

[12]LIN Boliang, WANG Zhimei, JI Lijun, et al. Optimizing the Freight Train Connection Service Network of a Large-Scale Rail System [J]. Transportation Research Part B Methodological, 2012, 46(5):649-667.

[13]林柏梁, 田亞明, 王志美. 基于最遠(yuǎn)站法則的列車編組計(jì)劃優(yōu)化雙層規(guī)劃模型[J]. 中國鐵道科學(xué), 2011, 32(5):108-113.

(LIN Boliang, TIAN Yaming, WANG Zhimei. The Bi-Level Programming Model for Optimizing Train Formation Plan and Technical Station Load Distribution Based on the Remote Re-Classification Rule [J]. China Railway Science, 2011, 32(5):108-113. in Chinese)

[14]WARDROP J G. Some Theoretical Aspects of Road Traffic Research [J]. Proceeding of the Institution of Civil Engineering， 1952,1(2): 325-378.

[15]BECKMANN Martin J, MCGUIRE C B, WINSTEN Christopher B, et al. Studies in the Economics of Transportation [J]. Economic Journal, 1955, 26(12):820-821.

[16]彭開宇. 中國鐵道年鑒[M]. 北京:中國鐵道出版社, 2014：127-129.

(PENG Kaiyu. China Railway Yearbook[M]. Beijing: China Railway Publishing House, 2014：127-129. in Chinese)