考慮跨線列車的高速鐵路能力最大化合理利用研究

王宇強，魏玉光，商 攀，張進川

(北京交通大學 交通運輸學院，北京 100044)

在高速鐵路(以下簡稱高鐵)運營管理過程中，列車停站方案、列車種類、開行區段及開行頻率是在列車開行方案編制階段基于客流需求優化得到的。近年來客流需求不斷增長，所需開行列車數量增加，從而導致在鋪畫運行圖時考慮到列車沖突問題可能無法得到一個包含所有列車的鋪畫方案。因此，如何優化利用高速鐵路線路通過能力，以實現盡可能地開行更多列車，成為亟需解決的問題。影響高鐵能力利用的因素眾多，本文以列車停站方案和列車時刻表為對象展開研究。

目前，關于列車停站方案和時刻表的研究眾多，但由于問題的復雜性，大部分學者將二者分開研究。在優化停站方案方面，文獻[1]提出了一種0-1雙層規劃模型來解決列車的停站方案和旅客換乘選擇問題，上層模型通過調整列車停站方案來最大化運營效益，下層模型目標為最小化乘客換乘時間。文獻[2]通過在高峰時間段采用區域停站策略來最小化乘客出行時間和地鐵運營成本。文獻[3]建立了基于乘客總體出行時間最小的軌道交通列車跨站停車0-1整數規劃模型，并利用禁忌搜索算法求解，最終通過算例驗證了方法的可行性。文獻[4]構建了旅客列車服務優化配置多目標規劃模型，該模型通過協調列車停站方案和開行頻率使運營總費用和乘客出行總時間最小。文獻[5]基于多商品流問題構建了時間-空間-狀態網，提出了以公平為導向的隔站停車策略，建立了線性優化模型，并采用拉格朗日松弛法算法求解。在優化列車時刻表時，文獻[6]構建了累計流變量模型對高鐵運行圖進行優化，并設計了拉格朗日松弛算法求解，將復雜的列車組合優化問題轉化為單列車的最短路徑問題集合，從而降低求解難度。文獻[7-8]建立了列車時刻表多目標優化模型來降低列車的能源消耗以及乘客的出行總時間。文獻[9]構建了高鐵通過能力最大條件下的運行圖優化模型，根據列車運行過程中不得有沖突的特點將該問題抽象為時空網絡中帶約束的最大獨立集問題。通過D-W分解將模型進行轉化及線性松弛，最后采用列生成算法及分支定界算法求解。

但由于列車停站方案和時刻表的制定相互關聯，越來越多的學者將兩者同時優化生成。文獻[10]提出一種新的多目標混合整數規劃模型來同時優化列車停站方案和時刻表，目標函數為最小化列車的總停站時間和期望到達時刻與實際到達時刻之間的差值，最后使用Cplex求解。文獻[11]構建了高鐵時空網絡，建立了使列車總收益最大的整數線性規劃模型，然后使用基于列生成的啟發式算法求解，最后在京滬高鐵上驗證了模型和算法的可行性。文獻[12]構建的模型考慮了動態客流和線路設備能力，為每列車選擇停站方案且優化時刻表，研究了動態客流的變化對列車時刻表及列車服務模式的影響。文獻[13]分別以乘客時空可達性和列車運行可靠度為側重點對高鐵能力進行建模和求解，最后使用多智體仿真軟件NetLogo，基于京滬高鐵算例多模型進行了仿真實驗。

既有文獻大多以最小化列車總運行時間和最小化優化后時刻表與現有時刻表的差異為目標，較為缺乏以高鐵能力利用為導向的研究。因此，本文研究以提高高鐵能力利用為目標的列車停站方案和列車時刻表優化問題，其中高鐵能力指在研究時間段內，高鐵線路在一定的機車車輛類型，信號設備和行車組織方法條件下所能開行的最大列車數量。研究的主要內容為：

(1)將開行方案生成的需求列車集合分為高等級列車集合(停站次數較少但多為大站停車)與低等級列車集合(停站次數較多)，保留高等級列車的停站方案，刪除低等級列車的停站方案，通過優化生成所有需求列車的時刻表與低等級列車停站方案，將開行方案中確定的列車盡可能多地鋪畫到運行圖中，從而優化高鐵通過能力。兩個列車集合中的列車通過運營商的決策確定，當運營商希望盡量滿足乘客OD的直達性，提高高鐵服務質量時，高等級列車數量大于低等級列車數量，當運營商希望在一定時間內開行更多列車時，低等級列車數量大于高等級列車數量。

(2)將跨線列車列入優化對象，進行本線列車和跨線列車的協同優化，定義從本線到其它線的跨線列車為本線下線跨線列車，從其他線到本線的跨線列車為本線上線跨線列車。

(3)構建基于高鐵物理網的高鐵時空絡。基于高鐵時空網絡建立整數規劃模型，目標函數為最大化高鐵開行列車數和最小化列車總運行時間。為大規模案例設計了基于交替方向乘子法(ADMM)分解的算法，將原始問題中的困難約束作為懲罰項松弛到原目標函數中，提高了求解效率。

1 高鐵時空網絡的構建

高鐵能力利用優化問題的本質為將有限的時空資源合理分配給各個列車的組合優化問題。因此可以通過構建時空網來描述高鐵列車的運行過程。

圖1為高鐵物理網絡，包括5個車站以及4個運行區段，其中車站3為跨線站。為構建高鐵時空網，將車站分解為列車進站點和出站點，兩點之間的連線表示列車的停站或跨線過程。同時，為在時空網絡中完整地描述列車運行路徑，新建表示列車在時空網中生成的列車生成點和列車在時空網中消失的虛擬到達點，見圖2。

圖1 高鐵物理網

圖2 改進后的高鐵物理網

在高鐵物理網的基礎上引入時間維度且將時間離散為較小的單元(如1 min)，構建時空網絡(V,A)，其中V為時空網中的頂點集合，A為時空網中的弧集合。V包括列車生成點、列車進站點、列車出站點和虛擬到達點。頂點(i,t)為在i點的t時刻；(i,j,t,s)為從(i,t)到(j,s)的一條有向弧。為了更好地描述高鐵運行過程，設立7種類型的弧：

(1)區間運行弧(i,j,t,s)表示列車從k站列車出站點i的t時刻運行到k+1站列車進站點j的s時刻，見圖3(a)。本文設立兩種類型的運行弧，分別為高速列車運行弧集合Ag和中速列車運行弧集合Ad，(i,j,t,s)∈Ar,Ar=Ad+Ag，Ar為列車運行弧集合。

(2)始發列車進站弧(i,i′,t,s)表示始發列車進入k站到發線的作業過程，而在k站的上線跨線列車可以視為在本線k站的始發列車，通過連接k站的列車生成點i與k站的列車進站點i′生成，見圖3(b)中的第ⅰ類弧，(i,i′,t,s)∈As，As為始發列車進站弧集合。

圖3 時空網中各類弧的構建

(3)終到列車出站弧(i,i′,t,T)表示終到列車離開k站到發線的作業過程，在k站的下線跨線列車可以視為在本線k站的終到列車，通過連接k站的列車出站點i與k站的列車虛擬到達點i′生成，如圖3(b)中的第ⅱ類弧。其中，T為時空網絡的時間界限，(i,i′,t,T)∈Az，Az為終到列車出站弧集合。

(4)停站弧(i,i′,t,s)∈Aw與跨線弧(i,i′,t,s)∈Ac表示列車在k站的停站作業和跨線作業，Aw為停站弧集合，Ac為跨線弧集合。停站時間或跨線時間加起停附加時間為s-t。列車的最大、最小停站時間通過時空網中停站弧的時間權重來確定。兩類弧通過連接k站的列車進站點i與k站的列車出站點i′而生成，如圖3(b)中的第ⅲ類和第ⅳ類弧，其中3種不同時間權重的弧代表不同的停站時間，時間權重最大和最小的弧可以表示相應的列車最大、最小停站時間。

(5)通過弧(i,i′,t,t)表示不停站列車直接通過車站，為一條平行于縱軸的弧，該弧通過連接k站的列車進站點i與k站的列車出站點i′生成，見圖3(b)中的第ⅴ類弧，(i,i′,t,t)∈At，At為通過弧集合。

(6)虛擬運行弧(i,j,t,T)表示有些需求列車在能力飽和情況下需要到達終點必須選擇的弧，通過連接各列車始發站的列車生成點i與終到站的虛擬到達點j生成，(i,j,t,T)∈Adummy，Adummy為虛擬運行弧集合。

在建立的時空網絡中，運行弧，停站弧、跨線弧、始發列車進站弧和終到列車出站弧的費用為列車的實際作業時間，通過弧的費用為0，虛擬運行弧的費用為無限大，如9 999。

2 模型的構建

2.1 模型假設

在構建模型前，提出以下假設：

(1)只選擇線路的一個方向(稱為正向)進行研究，另一個方向(稱為對向)可同樣利用此方法優化。

(2)各列車在各區段內的運行時間固定且已知。

(3)列車的起停附加時間固定且已知。

(4)最小列車間隔時間固定且已知。

(5)不考慮車底的運用情況。

2.2 構建模型

本文提出的整數規劃模型中，輸入參數為：列車的開行方案，包括列車運行區段、列車種類、列車開行數量以及高等級列車的停站方案；列車的最小列車間隔時間；不同速度等級的列車在各區段的運行時間；不同停站弧和跨線弧的時間權重；各列車的最大最小出發時間。模型的輸出結果為：列車時刻表以及低等級列車停站方案。

由于列車的停站、跨線、運行等作業都可用時空網中不同類型的時空弧表示，因此高鐵運行時刻表與停站優化問題可以建模為具有邊際條件約束的網絡多商品流優化問題。模型目標函數為

(1)

式(1)表示最大化列車集合K(K=K高∪K低，K高、K低分別為高等級列車、低等級列車集合，集合K內列車根據現有開行方案確定)在研究時間段內選擇運行弧的數量，即最大化列車開行數。

為了方便算法的求解，我們將其轉換為

(2)

式中：ci,j,t,s為時空網中每條弧的費用。

轉化目的為最小化列車在研究時間段內的總費用。由于虛擬運行弧的ci,j,t,s為一個特別大的值，所以通過阻止列車選擇虛擬運行弧，也就是通過最小化整個研究時間段內的總費用來最大化列車開行數。

模型約束條件為：

(1)高鐵始發列車、終到列車停站約束

(3)

(4)

為了盡可能的如實反映列車運行的全過程和跨線列車的跨線過程，引入高鐵始發列車、終到列車停站約束，對于跨線列車而言，始發列車進站弧實際描述了跨線列車在本線生成的過程，終到列車出站弧實際描述了跨線列車從本線消失的過程。該約束表示始發列車以及本線上線列車必須在其始發站進行停站作業或跨線作業，而終到列車以及本線下線列車必須在其終到站進行停站作業或跨線作業。

(2)跨線列車跨線約束

(5)

式中：Kk為跨線列車集合。

由于跨線列車a∈Kk在進行跨線作業時會切割車站咽喉，造成更多的等待時間，在時空網中則反映為跨線列車a∈Kk在跨線站必須選擇跨線弧(i,j,t,s)∈Ac。

(3)高鐵列車速度約束

(6)

本文設立了兩種速度類型的高速鐵路列車，分別為中速列車集合Kd，高速列車集合Kg，且設立了兩種類型的列車運行弧，分別為中速列車運行弧Ad，高速列車運行弧Ag，該約束規定了高速列車可以選擇中速列車運行弧運行而中速列車禁止選擇高速列車運行弧運行。

(4)流平衡約束

(7)

(5)列車停站次數約束

?k∈Si,i′∈Vk

(8)

式中：vk為車站k為了滿足乘客OD的可達性而需要的列車最小停站次數，vk的值通過現有的開行方案確定；S為高鐵車站集合；Vk為高鐵車站k的頂點集合。在高等級列車停站方案確定的基礎上，該約束規定了各車站對于停站次數的需求。

(6)最小列車間隔時間約束

(9)

式中：φ(i,j,t,s)為列車沖突弧集，φ(i,j,t,s)∈Ar∪Az。

式(9)表示了列車在高速鐵路運行中的安全因素，前車與后車的出發與到達時間間隔必須大于等于相應的最小列車間隔時間，即在(i,j)間，如果有一條運行弧或終到列車出站弧(i,j,t,s)被列車a選中，那么φ(i,j,t,s)∈Ar∪Az內的所有弧將禁止被選用。

(7)列車出發時間約束

(10)

該約束規定了列車a在其起始站的出發時刻不能早于最小出發時刻，也不能晚于最大出發時刻，運營商根據客流需求規定了某些或全部列車的出發時間段，對于大規模網絡問題，該參數可參照以往時刻表來確定。

3 基于ADMM分解的算法求解

本文提出的整數規劃模型在處理小規模案例時可以直接用Cplex求解，當計算大規模案例時，模型中的困難約束(如式(8)、式(9))會引發大規模列車組合，Cplex無法在短時間內求得最優解。所以提出基于ADMM分解的算法對大規模案例進行求解，ADMM分解算法為增廣拉格朗日松弛與塊坐標下降法的結合。

拉格朗日松弛是將原模型中的困難約束松弛，并引入拉格朗日乘子，將其乘積作為懲罰項帶入原目標函數中，則原問題可分解為多個獨立的子問題。增廣拉格朗日松弛是在拉格朗日松弛的基礎上，為提高解的質量，再為目標函數引入一個非線性的二次懲罰項。通過塊坐標下降法將增廣拉格朗日松弛問題線性化，按照順序依次求解各子問題從而求得最終解。該方法可以解決拉格朗日松弛后帶來的對稱性問題，加快收斂速度提高算法效率[14]。

通過使用基于ADMM分解的算法，引入拉格朗日乘子λi,j,t,s和μi,j,t,s以及二次項懲罰乘子ρ和ρ′，將復雜約束式(8)、式(9)松弛且作為懲罰項添加到目標函數式(2)中，得到新的目標函數

約束條件為式(7)、式(10)，則原問題變為基于時間的最短路徑問題，各個列車的最短路徑相互獨立。

每列列車的最短路徑目標函數為

(12)

通過公式推導得到

(13)

式中：

(14)

推導過程見文獻[14]。基于ADMM分解的算法步驟為

Step1初始化迭代次數n=0，初始化拉格朗日乘子λi,j,t,s=0，μi,j,τ=0和二次項懲罰乘子ρ、ρ′，生成初始下界解{Xlower}和上界解{Xuper}，設置最優下界LLB=-∞，LUB=+∞。

Step4更新拉格朗日乘子：

?(i,j,t,s)∈Aw∪Ac

?(i,j,t,s)∈Ar∪Az

Step5如果n等于預先設好的最大迭代次數，終止算法，否則，n=n+1轉到Step2。

4 案例驗證

以京滬高鐵為例，通過優化生成所有列車的時刻表與低等級列車的停站方案，在考慮跨線列車的情況下優化其能力利用。提出的算法將在Python平臺上實現，算法運行環境為一臺內存16 GB，CPU：i7-770HQ 2.80 GHz的臺式計算機。

京滬高鐵共有23個站，各種類列車在各區段的純運行時間見表1，本文規定最小列車間隔時間為4 min，起停附加時間為2 min，研究的時間總長度為10 h，時間離散化后的單位時間為1 min。京滬高鐵為雙線鐵路，本文僅考慮北京南—上海虹橋方向的高鐵列車。表2為各列車的運行區段和開行數，由現有開行方案確定，本文不研究列車開行方案的生成，所以需求數為假設但大于研究時間段內的理論通過能力，其中跨線列車包括7列正向跨線列車，高等級列車集合為北京—上海的高速列車以及北京—南京的高速列車，其余列車為低等級列車。由于篇幅有限，本文針對高等級列車集合與低等級列車集合的劃分僅進行這一個實驗，其他情況可按相同方法進行優化。由于京滬高鐵跨線列車眾多，本文只選取在徐州東站進行上線、下線的跨線列車為研究對象。

分別使用基于ADMM分解的算法和基于拉格朗日松弛的算法優化整個京滬高鐵的能力利用，迭代次數200次，兩種算法求解時間分別為22 126 s與20 194 s。運行圖鋪畫結果見圖4，目標函數值的上界，基于ADMM分解算法的下界和基于拉格朗日松弛算法的下界隨迭代次數變化曲線見圖5，其中上界與基于ADMM分解算法的下界間隔為1.56%，上界與基于拉格朗日松弛算法的下界間隔為6.83%，且基于ADMM分解算法的收斂速度明顯優于基于拉格朗日松弛算法的收斂速度，基于ADMM分解算法第46次迭代時的目標函數值就達到了基于拉格朗日松弛算法的最優下界。

圖4中北京南—上海虹橋方向的本線和跨線列車由于最小列車間隔時間約束，列車出發時間約束和列車停站次數約束的限制，影響了研究時間段內的最大通過能力，最大開行數為55列，運行線。為了更直觀的體現跨線列車對本線列車能力的影響，進行的另一個實驗將北京南—上海虹橋方向的跨線列車改為本線列車，實驗結果為在相同研究時間段內可開行57列列車，比考慮跨線列車的情況多2列，證明跨線列車對本線列車的能力有很大的影響，在研究高速鐵路能力優化時考慮跨線列車的影響更符合實際情況且非常必要。

表1 列車在各區段的運行時間 min

表2 列車OD及對應的列車數量

圖4 北京南—上海虹橋方向列車運行圖

圖5 上下界隨迭代次數變化曲線

5 結論

本文基于高鐵物理網構建了高鐵時空網，列車的停站作業和跨線作業可以直接使用停站弧和跨線弧來表示，而跨線列車的上線和下線作業分別可以看作是本線列車的始發和終到作業，基于此，將跨線列車納入研究對象，提出了一種高鐵最大通過能力下優化生成列車時刻表和停站方案的整數規劃模型。

由于所研究的問題規模很大，設計了基于ADMM分解的算法對模型進行求解，結果表明本文提出的算法與基于拉格朗日松弛的算法相比，可以在較短時間內得到收斂且目標函數值上下界的差值更小。

本文對于列車的停站需求處理不夠完善，沒有充分考慮客流OD的直達性與時間分布差異性，在未來的研究中我們會將動態客流需求作為模型輸入從而生成列車停站方案和時刻表以及進行客流分配，確保乘客OD的直達性以及考慮客流在時間分布上的差異性。且會提出更有效率的算法來擴大研究案例的規模，同時優化兩條及兩個方向的高鐵線路通過能力。