蔡 濤

CAI Tao

（中國鐵道科學(xué)研究院 通信信號研究所，北京 100081）

(Communication and Signaling Research Institute， China Academy of Railway Sciences， Beijing 100081， China)

高速鐵路列車運(yùn)行調(diào)整優(yōu)化模型研究

蔡 濤

CAI Tao

（中國鐵道科學(xué)研究院 通信信號研究所，北京 100081）

(Communication and Signaling Research Institute， China Academy of Railway Sciences， Beijing 100081， China)

在闡述鐵路列車運(yùn)行調(diào)整研究現(xiàn)狀的基礎(chǔ)上，針對日常列車運(yùn)行調(diào)整問題，根據(jù)高速鐵路列車運(yùn)行資源占用的特點(diǎn)，為每列列車賦予 1 個價值，以整體價值最大化為優(yōu)化目標(biāo)，建立基于時空網(wǎng)絡(luò)資源占用的數(shù)學(xué)模型，并運(yùn)用改進(jìn)拉格朗日松弛算法對該模型進(jìn)行化簡求解，以京滬高速鐵路進(jìn)行實例分析，結(jié)果表明該算法能夠滿足實際應(yīng)用的需要。

運(yùn)行計劃；價值函數(shù)；拉格朗日松弛；最優(yōu)化

鐵路運(yùn)輸調(diào)度是指為使運(yùn)輸生產(chǎn)控制在正常狀態(tài)，根據(jù)具體運(yùn)輸工作條件調(diào)整車輛分布及列車運(yùn)行，以解決可能或發(fā)生的困難。調(diào)度實踐證明，調(diào)度指揮的主要問題是在列車不按圖運(yùn)行時，根據(jù)列車和設(shè)備的狀態(tài)快速進(jìn)行最優(yōu)決策[1]；在區(qū)段通過能力使用緊張和高速行車的條件下，通常還需要對臨近區(qū)段進(jìn)行考慮，增加列車調(diào)度員進(jìn)行最優(yōu)決策的困難。因此，如何有效利用現(xiàn)有的線路資源，快速找到全局最優(yōu)或較優(yōu)高速鐵路行車調(diào)整方案，是鐵路運(yùn)輸組織管理和優(yōu)化研究領(lǐng)域亟需解決的問題[1]。在國內(nèi)研究中，許紅等[2]將列車分為 A類本線列車、B 類跨線列車和 C 類本線城際列車分別進(jìn)行建模，并采用遺傳算法進(jìn)行求解。謝美全等[3]結(jié)合我國客運(yùn)專線的實際情況，針對運(yùn)營情況復(fù)雜的線路提出基于定序的周期性列車運(yùn)行圖模型。汪波等[4]等將安排列車運(yùn)行線的問題看作周期事件安排問題，借助周期約束圖及周期勢差模型，建立周期運(yùn)行圖網(wǎng)絡(luò)模型。在國外研究中，XIE M 等[5]主要討論高速鐵路運(yùn)行圖調(diào)整問題，提出在發(fā)到時間確定情況下的整數(shù)線性規(guī)劃模型，以優(yōu)化循環(huán)動車組。Vansteenwegen P 等[6]考慮實時調(diào)度環(huán)境下的隨機(jī)擾動，基于列車不確定的運(yùn)行時間及制訂中期時刻表過程中的調(diào)度原則問題，提出隨機(jī)優(yōu)化模型。由于拉格朗日松弛算法 (Lagrangian Relaxation) 已經(jīng)在許多實際工程問題的研究中得到應(yīng)用，雖然其對模型的構(gòu)建和算法設(shè)計要求嚴(yán)格，但擁有優(yōu)秀的魯棒性和高效性特點(diǎn)，可以求解大規(guī)模的線性規(guī)劃問題，并且能給出明確的對偶間隙用于評價當(dāng)前解的質(zhì)量，因而仍然考慮將拉格朗日松弛算法用于求解日常列車運(yùn)行調(diào)整問題，并且以京滬高速鐵路 (以下簡稱“京滬高鐵”) 實際數(shù)據(jù)為背景進(jìn)行案例研究，對其適用性、可靠性進(jìn)行驗證。

1　列車運(yùn)行計劃編制模型的構(gòu)建

1.1問題描述

列車運(yùn)行計劃編制問題可以通過時空網(wǎng)絡(luò)進(jìn)行說明，如圖 1 所示?？v軸為時間，考慮將連續(xù)的時間離散化，形成 1 個列車時刻表。在我國鐵路系統(tǒng)中，時刻表通常以 1 min 為最小單位，橫軸表示資源 (車站和區(qū)間)。當(dāng)安排 1 列列車從始發(fā)站發(fā)出，根據(jù)基本列車運(yùn)行圖可以得到列車的最佳發(fā)車時間范圍，稱這個時間段是該列車在該車站的允許發(fā)車時間范圍。允許發(fā)車時間范圍越長，列車出發(fā)時間的選擇越多。

圖1　運(yùn)行計劃編制問題說明

在圖 1 中，假設(shè)列車 j 在每個車站的允許發(fā)車時間范圍均為 α min，如果時刻表以 1 min 為最小時間單位，那么列車 j 在每個車站的可選發(fā)車時間有 α 個，列車 j 到達(dá)終到站需要通過 β 個車站，可以編制出列車 j 的所有可行行車方案。列車 j 從始發(fā)站開始允許發(fā)車時間范圍為 α min，以此類推，最終列車 j 的可行方案有 αβ個。隨著列車數(shù)量和車站數(shù)量的增加，變量和約束的數(shù)量呈指數(shù)增長，那么優(yōu)化路網(wǎng)中列車運(yùn)行計劃將會在一個指數(shù)級增長的搜索空間內(nèi)尋找最優(yōu)解。

RT 是指列車在相鄰 2 個站間的純運(yùn)行時間，對于 1 列列車，RT 是 1 個定值，TT 是旅行時間，包括列車啟停時間和停站時間，一旦列車停站，則產(chǎn)生啟停車附加時分，為建模方便，將啟停車附加時間和停站時間合并，如圖 1 中的 ST。因此，列車經(jīng)過途中車站有 2 種選擇：①列車在途經(jīng)車站不停車(RT)；②由于運(yùn)行計劃或其他約束的影響，列車需要在中途車站停車作業(yè) (TT)。

在時空網(wǎng)絡(luò)中，如果同時考慮 2 列或 2 列以上的列車，列車之間會出現(xiàn)沖突，一旦發(fā)生沖突，就需要調(diào)整列車的發(fā)車時間和占用股道時間。考慮將區(qū)間、車站股道作為列車競爭的資源，并且對每個資源在每個時間點(diǎn)賦予 1 個價格，那么不同的運(yùn)行計劃就會花費(fèi)不同的資源和費(fèi)用，當(dāng)多個列車之間出現(xiàn)沖突時，可以通過改變在沖突時間點(diǎn)的資源價格來對多個列車的占用進(jìn)行排序。在迭代過程中，通過更新資源價格矩陣，找到列車由始發(fā)站到終到站利潤最大的路徑。每列車的利潤為列車收益減去列車在運(yùn)行途中占用資源的成本，從而構(gòu)建列車運(yùn)行計劃編制模型。

1.2模型構(gòu)建

式中：P 為優(yōu)化目標(biāo)函數(shù)，即所有列車在各個車站的發(fā)車時間價值最大，通過運(yùn)行圖鋪畫實現(xiàn)所有移動設(shè)備、固定設(shè)備及人工投入能夠取得最大化利益；j 為列車，j ∈ T，T 包含所有可能被鋪畫上運(yùn)行圖列車的集合，列車分為 2 個等級，分別用集合G，D 表示；i 為車站，i ∈ S，S 為線路沿線的所有車站的集合；設(shè) dij為列車 j ( j ∈ T ) 在 i ( fi≤i≤lj) 站的發(fā)車時刻，d ∈ D，0 ≤d≤1 440，為對應(yīng)于 dij的 0-1 決策變量，當(dāng)且僅當(dāng)時間點(diǎn) dij(0 ≤dij＜1 440， d ∈ Di， j ∈ T，fi≤i ＜lj) 被選作最優(yōu)解時，值為1；bij為列車 j 在車站 i 發(fā)車的價值；設(shè) aij為列車j ( j ∈ T ) 在 i ( fi＜i≤lj) 站的到達(dá)時刻，a ∈ A，0 ≤a≤ 1 440，為對應(yīng)于 aij的 0-1 決策變量，當(dāng)且僅當(dāng)時 間點(diǎn) aij(0 ≤aij≤1 440，a ∈ Ai，j ∈ T，fi≤i≤lj) 被選作最優(yōu)解時，值為 1；Li1為車站 i 的最小發(fā)車間隔時間；Li2為車站 i 的最小接車間隔時間；設(shè) wij為列車 j ( j ∈ T ) 在 i ( fi≤i≤lj) 站的等待時刻，w ∈ W， 0 ≤w≤1 400，zwij為對應(yīng)于 wij的 0-1 決策變量，當(dāng)且僅當(dāng)時間點(diǎn) wij(0 ≤wij＜1 440，w ∈ Wi，j ∈ T， fi≤i ＜lj) 被選作最優(yōu)解時，的值為 1；Mi為車站 i 的股道限制； j1為在 i 站于時間點(diǎn) d 之前發(fā)車的某趟列車； j2為在 i 站于時間點(diǎn) d 之后發(fā)車的某趟列車。

⑴ 式表示同一車站相同方向的發(fā)車時間點(diǎn)最多只能被占用 1 次；⑵ 式表示同車站同方向的接車時間點(diǎn)最多只能被占用 1 次；⑶ 式表示每趟列車的發(fā)車時刻數(shù)與到達(dá)時刻數(shù)相等，即保證運(yùn)行線的連續(xù)性；⑷ 式表示最小發(fā)車間隔約束；⑸ 式表示最小接車間隔約束；⑹ 式表示車站股道占用限制，同一車站同一時間不可停留過多列車；⑺ 式表示區(qū)間資源占用約束，即列車在區(qū)間內(nèi)不得越行。

dij，aij，wij及 0-1 變量之間的關(guān)系如下。

式中：j ∈ T ，fi＜i≤lj，Ri,i+1為列車 j 在 i 站與 i +1 站之間站間區(qū)間的運(yùn)行時間標(biāo)尺；如果 dij對應(yīng)的變量xd= 1，則對應(yīng)于滿足 ⑻ 式中 a 的變量

iji+1,j，表示列車 j 于 ai+1,j時刻到達(dá) i + 1 站。

式中：j ∈ T ，fi＜i≤lj，Pi,j為列車 j 在 i 站的停車時間標(biāo)準(zhǔn)，即如果 dij對應(yīng)的變量= 1，則對應(yīng)于滿足 ⑼ 式的 wi,j變量 zwij= 1，表示列車 j 于 wi,j時刻占用 i 站股道。

每一趟列車在所有途經(jīng)車站 (終到站除外) 都有1 個最佳發(fā)車時間 (圖定發(fā)車時刻)，該發(fā)車時刻帶來的效益最大，其價值也最大，表示時間點(diǎn) dij發(fā)車的價值，越偏離最佳發(fā)車時間價值衰減越大。各時間點(diǎn)的價值既可以通過人為合理定義，也可以按照某一函數(shù)曲線確定。通過線性價格函數(shù)來確定不同發(fā)車時間的價值，如圖 2 所示，為在圖定時刻發(fā)車能獲得最大效益，α1為早點(diǎn)范圍，α2為晚點(diǎn)范圍。

該模型的構(gòu)建基礎(chǔ)為在已有線路條件下，股道運(yùn)用方案為已知。因此，同一時間站內(nèi)能夠?？康牧熊嚁?shù)有限。中間站需要為列車運(yùn)行提供停車避讓的股道，如果某車站 i 上行有 h 條專用股道，下行有 g 條專用股道，同時有 r (r≥0) 條上下行共用的股道，則上行股道限制為 Mis= h + r，下行為 Mix= g + r；如果上行股道被占用數(shù) Cs= h + p (0 ≤p≤r)，下行股道被占用數(shù) Cx≤g，則上行限制仍然為 Mis= h + r，下行限制變?yōu)?Mix= h + r - p，反之亦然；如果上行股道被占用數(shù)為 Cs= h + p ，下行股道被占用數(shù)為 Cx= g + q，0 ≤p + q≤r，則上行限制變?yōu)?Mis= h + r - q，下行限制變?yōu)?Mix= g + r - p。

圖2　時間價值函數(shù)線

2　基于拉格朗日算法的模型求解過程

該模型的約束條件多而復(fù)雜，求解比較困難。模型包含 3 種變量，總變量數(shù)計算公式為Nv= 3 |T |×|S |，約束條件個數(shù)計算公式為 Nc= 2 |S | + |T | + 3×1 440×|S | + |S |×|T |2×1 440。對京滬高鐵的實際案例而言，如果對于 23 個車站，100 對列車進(jìn)行調(diào)整優(yōu)化，變量將達(dá)到 1.4 萬個，約束達(dá)到3.3億個，直接精確求解該問題有一定難度。

2.1拉格朗日松弛算法

拉格朗日松弛算法是一種分解協(xié)調(diào)算法，具有可以快速收斂到可行解，震蕩收斂到最優(yōu)解的特點(diǎn)[7]。拉格朗日乘子可以看作是每個車站在某時刻發(fā)車的時間占用價格?；诶窭嗜账沙诶碚?，如果將約束松弛，可以將原問題變成不考慮列車之間相互影響的若干個子問題。松弛約束條件 ⑷ 式至⑹ 式為拉格朗日松弛問題，給定 1 組非負(fù)的拉格朗日乘子，則高速鐵路運(yùn)行計劃編制問題的拉格朗日松弛問題記為 PL，則

為簡化問題求解，可以設(shè) PLD為 PL的拉格朗日對偶問題，計算公式為

進(jìn)一步簡化得到

式中：每一個子問題 qj表示 1 次列車的最優(yōu)調(diào)整方案，此時未考慮列車之間的相互影響，具體物理含義是該列車的價值減去占用各資源的費(fèi)用，各資源的占用費(fèi)用即為各拉格朗日乘子的取值；Q 表示僅與拉格朗日乘子相關(guān)而與決策變量無關(guān)的數(shù)值，在每一步迭代過程中，拉格朗日乘子通過算法先確定下來，此時 Q 值是 1 個定值，如果每個子問題均能取得最優(yōu)值，即得到最優(yōu)解。通過多次迭代改變拉格朗日乘子的取值，理論上當(dāng)拉格朗日乘子固定下來，即資源占用的費(fèi)用平穩(wěn)時系統(tǒng)達(dá)到最優(yōu)狀態(tài)。

2.2模型求解

在列車的站間區(qū)間運(yùn)行標(biāo)尺確定的情況下，按照約束條件 ⑽ 式至⒀ 式，將所有列車在可調(diào)整范圍內(nèi)的所有可行解列出，并計算其總價值 PLD，從中找出目標(biāo)值最優(yōu)方案。

對于模型 PL= max L，在每次迭代中，拉格朗日乘子都被更新。依據(jù)實際問題的特性，還可以選取特定節(jié)點(diǎn)來簡化問題。①節(jié)點(diǎn)選擇原則。根據(jù)我國高速鐵路的特點(diǎn)，選擇一些樞紐站、其他線路(支線)接入站作為節(jié)點(diǎn)，只有被選為節(jié)點(diǎn)的車站才能作為列車的始發(fā)站或終到站。②分支、剪枝。為減少工作量，可以利用目標(biāo)函數(shù)值進(jìn)行剪枝。③搜索最優(yōu)解。每兩個節(jié)點(diǎn)之間的線路都得到 1 個最優(yōu)解，通過搜索始發(fā)站到終到站的最優(yōu)路徑，形成 1個完整的列車運(yùn)行調(diào)整方案，最終得到 1 個子問題的解。

2.3算法步驟

運(yùn)用拉格朗日松弛算法，松弛掉列車之間的影響約束，從而將求多次列車的整體最優(yōu)調(diào)整方案的復(fù)雜問題轉(zhuǎn)變?yōu)榍竺恳淮瘟熊嚨淖顑?yōu)調(diào)整方案。算法的具體步驟如下。

步驟 1：初始化。將時間間隔設(shè)為 1 min，即 1天有 1 440 個時刻可供選擇。迭代次數(shù) n = 0。建立1 440×S 階 0 矩陣 λ1440×S，其中元素 λm×S為m (0≤m ＜1 440) 時刻從 i (1≤i ＜s) 車站發(fā)車所對應(yīng)的拉格朗日乘子。建立 t (列車數(shù)) 個 1 440×(lj－ fj+ 1) 階 0 矩陣，分別表示為列車 j ( j ∈ T)在 i (i ∈ S) 車站所安排的發(fā)車時刻、到達(dá)時刻和停車時刻。設(shè)定價值參數(shù) B、軌道限制參數(shù) Mi、步長調(diào)節(jié)因子 γ0。

步驟 2：安排高等級列車在各站的發(fā)車時間。高等級列車無需避讓，可以按照各自最佳發(fā)車時間運(yùn)行。用矩陣記錄列車的發(fā)車時刻，并且通過區(qū)間運(yùn)行標(biāo)尺及中間站停站時間推算到站時刻矩陣和停站時間矩陣，重復(fù)該步驟直至高等級列車完成安排。

步驟 3：安排低等級列車。低等級列車往往需要在中間站停車避讓，通常不能按照最佳發(fā)車時間發(fā)車，用分支定界方法在最佳發(fā)車時間鄰域搜尋利益最大點(diǎn) (較之最佳發(fā)車時間其價值次之、負(fù)影響小) 作為實際發(fā)車時間，并用矩陣記錄，以此推算矩陣和，重復(fù)該步驟直至低等級列車完成安排。

步驟 4：判斷是否滿足迭代停止標(biāo)準(zhǔn)。計算拉格朗日問題目標(biāo)值，再計算，如果 Δ≤ε (ε 為可接受的誤差值) 則進(jìn)行步驟 7，否則進(jìn)行步驟 6。

步驟 5：判斷是否達(dá)到最大迭代次數(shù)，如果n ＞ N，則進(jìn)行步驟 7，否則進(jìn)行步驟 6。

步驟 6：用 Bundle 算法更新拉格朗日乘子，n = n + 1，轉(zhuǎn)步驟 3。

步驟 7：運(yùn)用可行化方法將初始序列可行化，算法結(jié)束。

算法結(jié)束后，所有列車的運(yùn)行時間表 (發(fā)車時間 X，到站時間 Y 和停站時間 Z) 確定，可以將其輸出到列車時刻表上，或者按照運(yùn)行時刻鋪畫在列車運(yùn)行圖上。

3　算例分析

3.1數(shù)據(jù)整理

以京滬高鐵主要技術(shù)參數(shù)為例[8]，首先將京滬高鐵沿線的車站進(jìn)行編號，上海虹橋站為 01 號，按照上行方向依次編號直到 23 號北京南站。基本數(shù)據(jù)包括列車運(yùn)行標(biāo)尺，即列車區(qū)間運(yùn)行時分、啟停車附加時分和圖定停站時間；車站基本信息，即車站的上下行股道數(shù)，以及車站接車、發(fā)車最小間隔時間；價值函數(shù)參數(shù)；基本圖數(shù)據(jù)等。不同等級的列車其可調(diào)整范圍不同，等級越低可調(diào)整范圍越大。目標(biāo)函數(shù)的主要參數(shù)如表 1 所示。

表1　價值函數(shù)參數(shù)及可調(diào)整范圍

3.2案例設(shè)計

基本列車運(yùn)行圖根據(jù)京滬高鐵現(xiàn)行列車時刻表改編而來，保留原有的車次名稱、各中間站的停站時間及列車始發(fā)站和始發(fā)時間，其他各中間站的發(fā)車時間均根據(jù)列車運(yùn)行標(biāo)尺進(jìn)行推算。

根據(jù)京滬高鐵現(xiàn)行列車時刻表，在京滬全線范圍內(nèi)，包括本線列車和跨線列車作為整體調(diào)整優(yōu)化，場景 1 為 9 : 00—9 : 10 的 10 min 內(nèi)，運(yùn)行圖中包含的列車數(shù)是 9 列，場景 2 為 9 : 00—9 : 30 時間段運(yùn)行圖中包含的列車數(shù)是 26 列，場景 3 為 9 : 00—10 : 00 時間段內(nèi)運(yùn)行圖中包含的列車數(shù)是 34 列，場景 4 為 9 : 00—11 : 00 的時間段內(nèi)運(yùn)行圖中包含的列車數(shù)是 54 列。

為增加運(yùn)行調(diào)整的難度，場景設(shè)計為大面積運(yùn)行紊亂，通過計算機(jī)程序隨機(jī)生成擾動，每一次列車的始發(fā)時間均進(jìn)行調(diào)整，隨機(jī)生成 10% 的中間站股道故障，使可用股道數(shù)減少 1 條，該車站相鄰區(qū)間運(yùn)行時分增加 4 min。

3.3計算結(jié)果與分析

基于以上各項參數(shù)及數(shù)據(jù)的設(shè)定，最大迭代 80 步統(tǒng)計計算結(jié)果。當(dāng)列車數(shù)量為 9 列時，曲線“最優(yōu)值”為每一步迭代的最優(yōu)值；曲線“下界”為截至當(dāng)前迭代步為止，所出現(xiàn)的最好值。最優(yōu)上界為 5 302，最優(yōu)下界為 5 087，上下界之間的差值為 215，對偶間隙百分比是 4.1%，在實際工程應(yīng)用上可以認(rèn)為已經(jīng)找到最優(yōu)列車運(yùn)行調(diào)整方案。當(dāng)開行 26 列車時，下界值為 16 573；當(dāng)開行列車數(shù)為 34 列時，下界值為 28 924；當(dāng)開行列車數(shù)為 54列時，下界值為 42 538，下界值變化趨勢如圖 3 所示。在圖 3 中，在開始 40 步之內(nèi)曲線緩慢上升，這是由于列車之間的沖突較多，在某些時間點(diǎn)存在競爭，拉格朗日乘子值不斷變大，需要通過乘子的不斷調(diào)整，減少列車之間的沖突點(diǎn)，需要的迭代步數(shù)較多。隨著乘子的不斷調(diào)整，原問題目標(biāo)值不斷變大，并且不斷趨于穩(wěn)定，表示已經(jīng)消除列車之間的沖突點(diǎn)。

圖3　下界值變化趨勢圖

不同場景調(diào)整結(jié)果比較如表 2 所示，上下界之間差值的相對百分比不超過 10%，在工程應(yīng)用中認(rèn)為得到比較精確到解決方案。此外，其計算時間也比較短，最復(fù)雜的場景也能在 1 min 時間內(nèi)求得較優(yōu)解。綜上所述，使用拉格朗日算法可以在較短的時間內(nèi)對列車運(yùn)行調(diào)整方案進(jìn)行優(yōu)化，方便調(diào)度員實時調(diào)整列車運(yùn)行圖。

表2　調(diào)整結(jié)果

4　結(jié)束語

通過采用基于時空網(wǎng)絡(luò)方法對高速鐵路列車運(yùn)行調(diào)整問題進(jìn)行建模，將復(fù)雜的調(diào)度調(diào)整問題抽象化，運(yùn)用基于拉格朗日松弛算法的快速啟發(fā)式求解算法，通過簡化優(yōu)化條件，并且引入 Bundle 算法獲得更精確的拉格朗日乘子，大大提高算法精度。以京滬高速鐵路的實際數(shù)據(jù)為背景進(jìn)行案例研究，計算結(jié)果表明，該模型和算法能夠在較短的計算時間(1 min) 內(nèi)，為數(shù)十次列車的運(yùn)行調(diào)整提供接近全局最優(yōu)解的方案 (對偶間隙不超過10%)，為將來大規(guī)模的調(diào)度調(diào)整問題提供新的解決思路和計算方法。但是，為提高算法速度，在構(gòu)建模型時對實際問題進(jìn)行簡化和抽象，以車站和區(qū)間作為資源，而不是以進(jìn)路作為資源建模，雖然對于一般高速鐵路車站而言，該模型已經(jīng)完全能夠適應(yīng)列車運(yùn)行調(diào)整的需要，可以疏解資源占用沖突情況，但對樞紐站具有一定局限性，可以在將來的研究過程中細(xì)化模型約束條件，使其更加符合實際情況。

[1] 王宏剛，張 琦，王建英，等. 基于遺傳算法的高速鐵路行車調(diào)整模型[J]. 中國鐵道科學(xué)，2006，27(3)：96-100. WANG Hong-gang，ZHANG Qi，WANG Jian-ying，et al. GA-based Model of Train Operation Adjustment for High-Speed Railway[J]. China Railway Science，2006，27(3)：96-100.

[2] 許 紅，馬建軍，龍建成. 客運(yùn)專線列車運(yùn)行圖編制模型及計算方法的研究[J]. 鐵道學(xué)報，2007，29(2)：1-7. XU Hong，MA Jian-jun，LONG Jian-cheng. Research on the Model and Algorithm of the Train Working Diagram of Dedicated Passenger Line[J]. Journal of the China Railway Society，2007，29 (2)：1-7.

[3] 謝美全，聶 磊. 周期性列車運(yùn)行圖編制模型研究[J]. 鐵道學(xué)報，2009，31(4)：7-13. XIE Mei-quan，NIE Lei. Model of Cyclic Train Timetable[J]. Journal of the China Railway Society，2009，31(4)：7-13.

[4] 汪 波，楊 浩，牛 豐，等. 周期運(yùn)行圖編制模型與算法研究[J]. 鐵道學(xué)報，2007，29(5)：1-6. WANG Bo，YANG Hao，NIU Feng，et al. Study on Model and Algorithm of Periodic Train Diagram Generation[J]. Journal of the China Railway Society，2007，29(5)：1-6.

[5] XIE M，LI X. Railway Timetable Rescheduling based on the Feedback of Train-set Circulation[J]. Procedia-Social and Behavioral Sciences，2012，43(43)：781-789.

[6] Vansteenwegen P，Oudheusden D V. Decreasing the Passenger Waiting Time for an Intercity Rail Network[J]. Transportation Research：Part B，2007，41(4)：478-492.

[7] 康 寧，武小悅. 基于拉格朗日松弛的航天測控調(diào)度上界求解算法[J]. 國防科技大學(xué)學(xué)報，2011，33(3)：38-43. KANG Ning，WU Xiao-yue. TT&C Scheduling Upper Bound Solution Algorithm based on Lagrangian Relaxation[J]. Journal of National University of Defense Technology，2011，33(3)：38-43.

[8] Wikipedia. Beijing-Shanghai High-Speed Railway[EB/OL]. (2015-10-08) [2016-02-19]. https://en.wikipedia.org/wiki/ Beijing%E2%80%93Shanghai_High-Speed_Railway.

責(zé)任編輯：吳文娟

成都鐵路局增加運(yùn)力滿足市民踏青游需求

隨著天氣轉(zhuǎn)暖，外出踏青游玩的旅客日益增多，成都鐵路局?jǐn)U增短途運(yùn)能，靈活調(diào)整動車組上線運(yùn)用模式，保證日均可以增加 1.8 萬張票額，滿足市場需求。

2016年2月29日—3月3日期間，成都鐵路局將以成渝達(dá)三角區(qū)和四川省內(nèi)高鐵路網(wǎng)為重點(diǎn)，進(jìn)一步擴(kuò)增短途運(yùn)能，靈活調(diào)整動車組上線和入庫檢修數(shù)量，最大限度滿足旅客出游需求。

成都鐵路局將增開成都東至江油 C6214 次、江油至峨眉山 C6317 次、峨眉山至成都東 C6270次、成都東至峨眉山 C6269 次、峨眉山至成都東 C6272 次、成都東至峨眉山 C6271 次等7趟綿成樂城際動車組；重聯(lián)加開重慶北至內(nèi)江北G8622 次、內(nèi)江北至成都東 G8624 次、成都東至永川東 G8621 次、永川東至成都東 G8626 次、成都東至內(nèi)江北 G8623 次等 6 趟成渝高鐵動車組，并將重慶北至成都東 G8508 次、G8513 次等 7 趟動車實行重聯(lián)運(yùn)行，保證日均可以增加 1.8 萬張票額。

（摘自《人民鐵道》報）

Study on Optimization Model of High-speed Railway Train Operation Adjustment

Based on expounding study status of train operation adjustment, targeting with problems existing in daily train operation adjustment, according to characteristics of resources occupation of high-speed railway train operation, each train is given a value, and taking maximum overall value as the optimization object, the mathematical model of resources occupation based on time-space network is established, the model is simplified and solved by using improved Lagrangian relaxation algorithm, and then, taking Beijing-Shanghai high-speed railway as an example, the result shows the algorithm could satisfy the demand of actual application.

Operation Plan; Cost Function; Lagrangian Relaxation; Optimization

1003-1421(2016)03-0034-07+1；U284.59

A

U292.4

10.16668/j.cnki.issn.1003-1421.2016.03.07

2016-02-19

中國鐵道科學(xué)研究院基金項目(2015YJ054)