秦永勝，孟學(xué)雷，沈發(fā)才，張豐婷，劉仁華

(蘭州交通大學(xué) 交通運(yùn)輸學(xué)院，甘肅 蘭州 730070)

高速鐵路列車停站方案的編制需要考慮各種因素，不僅要滿足客流的出行需求，還應(yīng)考慮實(shí)現(xiàn)鐵路運(yùn)輸能力的高效利用和運(yùn)輸成本的最小化。近年來，許多學(xué)者對(duì)這一問題進(jìn)行了研究，GO‐OSSENS 等[1]通過對(duì)幾種線路中斷模式下的線路規(guī)劃問題模型進(jìn)行正確性和等價(jià)性證明。為充分體現(xiàn)鐵路運(yùn)輸?shù)谋憬菪?，以旅行時(shí)間最小為目標(biāo)構(gòu)建了停站方案優(yōu)化模型；CLAESSENS 等[2]通過研究荷蘭鐵路成本最優(yōu)分配問題，提出了新的運(yùn)營成本替代方法，并以此構(gòu)建了開行方案優(yōu)化模型，通過將構(gòu)建的非線性模型轉(zhuǎn)化為具有二元決策變量的線性模型，提出了基于約束滿足和分支定界過程的算法，最后以荷蘭鐵路部分?jǐn)?shù)據(jù)進(jìn)行了實(shí)例驗(yàn)證；CHANG 等[3]將旅客的旅行時(shí)間和鐵路公司的運(yùn)營總成本綜合分析，構(gòu)建了開行方案優(yōu)化模型，采用模糊數(shù)學(xué)規(guī)劃方法進(jìn)行求解，最后以臺(tái)灣擬建高鐵的數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；張小炳等[4]通過分析停站方案的均衡性和可達(dá)性構(gòu)建了優(yōu)化模型，采用遺傳退火算法進(jìn)行求解，并用京滬高鐵的數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；牛豐等[5]基于不確定客流，構(gòu)建了停站方案機(jī)會(huì)約束規(guī)劃模型，利用不確定理論的相關(guān)知識(shí)將其轉(zhuǎn)化為確定性的等價(jià)類模型，并通過MATLAB 平臺(tái)調(diào)用GUROBI 優(yōu)化軟件對(duì)模型進(jìn)行求解和計(jì)算分析。最后用武廣段高速鐵路數(shù)據(jù)進(jìn)行實(shí)例分析；李得偉等[6]以中間站節(jié)點(diǎn)服務(wù)頻率為切入點(diǎn)，構(gòu)建了帶有叉乘約束的非線性規(guī)劃模型并將其轉(zhuǎn)換為普通的連續(xù)性規(guī)劃問題，進(jìn)行模擬迭代求解；楊曉等[7]以節(jié)點(diǎn)服務(wù)頻率為約束，構(gòu)建了列車停站方案優(yōu)化模型，并使用lingo軟件進(jìn)行模型求解，最后用國內(nèi)某高速鐵路數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；閆海峰等[8]通過考慮運(yùn)行圖的通過能力，以運(yùn)行線在運(yùn)行圖上占用的時(shí)間最少為目標(biāo)，構(gòu)建了停站方案優(yōu)化模型，使用lingo 軟件中內(nèi)置的全局優(yōu)化算法進(jìn)行求解，并基于京滬高鐵的部分?jǐn)?shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；簡星等[9]通過推導(dǎo)出發(fā)運(yùn)行線間隔時(shí)間公式，以運(yùn)行線總占用時(shí)間最小為目標(biāo)，構(gòu)建了停站方案優(yōu)化模型，采用模擬退火算法進(jìn)行求解，并以長沙南至衡陽東區(qū)段數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；許若曦等[10]以大站間快車比例為切入點(diǎn)，構(gòu)建了提升旅客出行效率的停站方案優(yōu)化模型，使用遺傳算法進(jìn)行求解，并基于京廣高鐵的數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；史峰等[11]以旅客需求為切入點(diǎn)，構(gòu)造了旅客彈性需求函數(shù)，以用戶平衡分配為基礎(chǔ)，構(gòu)建了開行方案雙層規(guī)劃模型，并采用模擬退火算法進(jìn)行求解；史峰等[12]通過綜合考慮旅客開行方案和換乘方案，構(gòu)建了雙層優(yōu)化模型，并采用模擬退火算法進(jìn)行求解；何宇強(qiáng)等[13]以旅客服務(wù)質(zhì)量為切入點(diǎn)，提出旅客方便度概念；將列車開行最大收益和旅客最大方便度作為目標(biāo)，構(gòu)建了多目標(biāo)雙層規(guī)劃模型，采用混沌算法進(jìn)行求解，并以石太客運(yùn)專線數(shù)據(jù)進(jìn)行實(shí)例驗(yàn)證；周文梁等[14]以鐵路運(yùn)營效益最大和旅客出行費(fèi)用最小為目標(biāo)，構(gòu)建了開行方案和運(yùn)行圖綜合優(yōu)化的雙層規(guī)劃模型，使用模擬退火算法進(jìn)行模型求解和算例驗(yàn)證；周文梁等[15]基于旅客時(shí)段出行需求與廣義出行費(fèi)用建立了彈性需求函數(shù)，以列車開行收益最大為目標(biāo)，構(gòu)建了基于候選列車集的開行方案優(yōu)化模型，并使用模擬退火算法進(jìn)行模型求解和算例驗(yàn)證。綜上，目前的文獻(xiàn)主要從旅客旅行時(shí)間[1,3,5,9,11?12]、出行費(fèi)用[14?15]、運(yùn)營成本[2,12]、旅客出行方便度[6?7,13]、運(yùn)行圖通過能力[8?9]等方面對(duì)列車停站方案問題展開了研究，構(gòu)建了線性規(guī)劃、非線性規(guī)劃、機(jī)會(huì)約束規(guī)劃、雙層規(guī)劃等優(yōu)化模型，但是對(duì)于在列車運(yùn)行調(diào)整計(jì)劃中考慮停站方案對(duì)于動(dòng)車組數(shù)量影響的研究較少。本文從實(shí)際出發(fā)，在開行區(qū)段、客流需求、列車種類、數(shù)量、等級(jí)已知的條件下，綜合考慮停站方案和時(shí)間因素對(duì)動(dòng)車組數(shù)量的影響，并以此構(gòu)建了研究模型和設(shè)計(jì)了求解算法。

1 問題描述

我國現(xiàn)行編制高速鐵路列車停站方案時(shí)采用的方法大多是根據(jù)確定的開行區(qū)段、運(yùn)行徑路、列車種類、編組輛數(shù)以及客流需求等確定初始的停站方案。從停站方案的編制過程中，不難發(fā)現(xiàn)現(xiàn)行的停站方案編制方法沒有充分考慮動(dòng)車組運(yùn)用的情況。因此，在滿足客流需求、通過能力等的條件下，停站方案仍有一定的調(diào)整空間使得動(dòng)車組的運(yùn)用更合理。

如圖1 所示，圖中共有4 條運(yùn)行線，其中運(yùn)行線G4和G3是接續(xù)的，即可以用一組動(dòng)車組順序的完成G4，G3 的運(yùn)輸任務(wù)；運(yùn)行線G2 和G1 是不接續(xù)的。那么要完成G2 和G1 的運(yùn)輸任務(wù)，就需要2組動(dòng)車組。如果想要減少動(dòng)車組的使用數(shù)量，就必須使得G1和G2接續(xù)。一種做法是通過不斷地調(diào)整運(yùn)行線的出發(fā)時(shí)間，使得接續(xù)盡可能的多。如圖1 中，通過將G2 運(yùn)行線左移(在滿足時(shí)間約束的條件下)，使得運(yùn)行線G2 和G1 接續(xù)，從而減少了一組動(dòng)車組；另一種做法是通過調(diào)整運(yùn)行線的停站方案，如圖2所示，通過取消G2運(yùn)行線的c停站和G1 運(yùn)行線的b 停站，使得運(yùn)行線G2 和G1 接續(xù)，從而減少了一組動(dòng)車組。

圖1 列車運(yùn)行圖Fig.1 Train operation diagram

圖2 列車運(yùn)行圖Fig.2 Train operation diagram

通過上述舉例可以說明：第一，在鋪畫運(yùn)行圖時(shí)，運(yùn)行線在運(yùn)行圖上的排列方式直接影響運(yùn)用動(dòng)車組的數(shù)量；第二，在運(yùn)行線排列方式一定時(shí)(運(yùn)行線始發(fā)時(shí)間不可調(diào)整時(shí))，對(duì)于不同的列車停站方案，其停站的次數(shù)直接影響著列車運(yùn)行時(shí)間，通過調(diào)整車站停站方式，使得小的時(shí)間范圍內(nèi)原本不接續(xù)的運(yùn)行線接續(xù)(如圖2 所示)，從而減少運(yùn)用動(dòng)車組的數(shù)量。

因此，通過合理地調(diào)整列車在中間站的停站方式和運(yùn)行圖中各個(gè)運(yùn)行線的排列方式可以實(shí)現(xiàn)旅行時(shí)間最小和運(yùn)用動(dòng)車組數(shù)量最少這一目標(biāo)。

2 建立模型

2.1 模型假設(shè)

1) 選定的客流區(qū)段內(nèi)存在2 種列車種類和等級(jí)；

2) 只考慮區(qū)間通過能力，不考慮車站通過能力和到發(fā)線通過能力的影響；

3) 對(duì)初始停站方案的起訖點(diǎn)和運(yùn)行徑路不做改變；

4) 將列車的起停附加時(shí)分計(jì)入列車的停站時(shí)間中，并將停站時(shí)間設(shè)為定值；

5) 本文旨在研究停站方案對(duì)動(dòng)車組接續(xù)的影響，默認(rèn)在2站間沒有可達(dá)列車時(shí)，旅客選擇換乘其他車輛。

2.2 參數(shù)列表

參數(shù)列表見表1。

表1 參數(shù)列表Table 1 Parameter list

2.3 目標(biāo)函數(shù)

本文所建模型的目標(biāo)有2個(gè)。一是最大程度上減少一日內(nèi)運(yùn)用動(dòng)車組的數(shù)量，緩解動(dòng)車組數(shù)量緊張問題。二是最小化旅客旅行時(shí)間，提高服務(wù)質(zhì)量。

1) 所需動(dòng)車組數(shù)量：以運(yùn)行線總數(shù)量與接續(xù)次數(shù)之差表示。

為使各目標(biāo)量綱統(tǒng)一，進(jìn)行歸一化：

2)旅客旅行時(shí)間

對(duì)于旅行時(shí)間長短的影響因素(不包括線路長度和列車運(yùn)行速度)主要有2 個(gè)：列車停站次數(shù)和列車越行時(shí)間，尤其是越行時(shí)間，其直接增加了旅客旅行時(shí)間，影響了旅客的乘車體驗(yàn)。所以將旅行時(shí)間最小這一目標(biāo)轉(zhuǎn)化為不同權(quán)重下的停站次數(shù)最小和列車越行時(shí)間最小，如式(3)～(5)所示。

歸一化處理：

2.4 約束條件

1) 與客戶需求有關(guān)的約束

旅客服務(wù)質(zhì)量和停站率。本文以各個(gè)車站的停站次數(shù)來衡量停站方案的旅客服務(wù)質(zhì)量。為不造成運(yùn)輸能力浪費(fèi)，選取平均上座率α作為初始停站次數(shù)的系數(shù)，如式(7)所示。

2) 與時(shí)間有關(guān)的約束

列車出發(fā)時(shí)間間隔。對(duì)于同一方向出發(fā)的列車，由于線路采取的閉塞方式不同，就需要采取不同的出發(fā)間隔時(shí)間，以確保列車運(yùn)行安全。本文以同方向每個(gè)站每列列車與其他列車出發(fā)時(shí)間之差的絕對(duì)值滿足出發(fā)時(shí)間間隔表示，如式(11)所示。

列車追蹤時(shí)間間隔。對(duì)于同向行駛的2 列列車，其必須保持足夠的安全距離。在本文中追蹤時(shí)間間隔主要是確保直達(dá)列車與前行擇站停列車的安全時(shí)距的。為使模型簡單，本文以同方向每個(gè)站直達(dá)列車與擇站停列車出發(fā)時(shí)間之差的絕對(duì)值滿足追蹤時(shí)間間隔表示，如式(12)所示。

滿足在站接續(xù)作業(yè)時(shí)間標(biāo)準(zhǔn)。如果在始發(fā)站或終到站2列列車運(yùn)行線之間存在接續(xù)關(guān)系，以出發(fā)列車出發(fā)時(shí)間與到達(dá)列車到達(dá)時(shí)間之差滿足動(dòng)車組接續(xù)時(shí)間表示，如式(13)所示。

列車到站時(shí)間間隔。如果短時(shí)間內(nèi)有大量列車到達(dá)車站，會(huì)對(duì)車站的接車能力造成很大的沖擊，而且也存在很大的安全隱患。因此，列車到達(dá)時(shí)應(yīng)保持一定的時(shí)間間隔。本文以同方向每個(gè)站每列列車與其他列車到達(dá)時(shí)間之差的絕對(duì)值滿足到達(dá)時(shí)間間隔表示，如式(14)所示。

3) 與動(dòng)車組類型有關(guān)的約束

在始發(fā)站或終到站，如果2條運(yùn)行線接續(xù)，那么這2條運(yùn)行線所需的動(dòng)車組類型必須相同。本文以出發(fā)運(yùn)行線所需動(dòng)車組類型與到達(dá)運(yùn)行線動(dòng)車組類型相同表示，如式(17)所示。

3 求解算法

本文所構(gòu)建的基于動(dòng)車組接續(xù)的高速鐵路列車停站方案設(shè)計(jì)研究模型，當(dāng)開行的列車數(shù)量和開行區(qū)段內(nèi)的車站數(shù)量增加時(shí)，模型的變量會(huì)大幅度增加，運(yùn)算規(guī)模會(huì)呈現(xiàn)幾何級(jí)數(shù)遞增。因此本文選取算法復(fù)雜程度較低，滿意程度較高的人工蜂群隨機(jī)搜索算法。

3.1 解的向量表現(xiàn)形式

解的信息包括停站方案(fj1)、出發(fā)時(shí)間(fj2)以及到達(dá)時(shí)間(fj3)，故解的表達(dá)形式為：

因?yàn)槊織l運(yùn)行線的停站序列是隨機(jī)產(chǎn)生的，所以每條運(yùn)行線的停站方案是不同的，即停站方案中的0-1變量構(gòu)成的停站序列是不同的。

通過決策變量，停站方案fj1以及各站停站時(shí)間(包括起停附加時(shí)分)可以獲得運(yùn)行線在各站的出發(fā)時(shí)間和到達(dá)時(shí)間：

3.2 初始解的生成算法

算法步驟如下。

Step 1：輸入原始數(shù)據(jù)(區(qū)間運(yùn)行時(shí)分、各站停站時(shí)分、運(yùn)行線數(shù)量(G0、D0)、各站停站頻率、各項(xiàng)間隔時(shí)間)；

Step 2：根據(jù)決策變量生成停站方案；

Step 3：判斷停站率等約束，滿足，轉(zhuǎn)Step 4；不滿足，轉(zhuǎn)Step 2；

Step 4：在可運(yùn)行時(shí)間窗內(nèi)(即式(15)的可運(yùn)行時(shí)間范圍)隨機(jī)生成直達(dá)列車始發(fā)時(shí)間，并計(jì)算在各站出發(fā)、到達(dá)時(shí)間；

Step 5：判斷時(shí)間間隔等約束，滿足，轉(zhuǎn)Step 6；不滿足，轉(zhuǎn)Step 4；

Step 6：擇站停列車按順序?qū)Φ趈(j初值為1)條運(yùn)行線隨機(jī)生成可運(yùn)行時(shí)間窗內(nèi)的始發(fā)時(shí)間；

Step 7：判斷是否j%2=1(編寫的算法是單數(shù)為上行，雙數(shù)為下行)，是，轉(zhuǎn)Step 8;否，轉(zhuǎn)Step 12；Step 8：計(jì)算第k(每次初值為2)個(gè)中間站到達(dá)、出發(fā)時(shí)間；

Step 9：判斷該站是否被直達(dá)列車越行。是，則計(jì)算越行時(shí)間，并加入停站時(shí)間之中；

Step 10：判斷時(shí)間間隔等約束，滿足，轉(zhuǎn)Step11；不滿足，轉(zhuǎn)Step6；

Step 11：是否k=C，是，轉(zhuǎn)Step 16；否，k=k+1，轉(zhuǎn)Step 8；

Step 12：計(jì)算第k(每次初值為C?1)個(gè)中間站到達(dá)、出發(fā)時(shí)間；

Step 13：判斷該站是否被直達(dá)列車越行。是，則計(jì)算越行時(shí)間，并加入停站時(shí)間之中；

Step 14：判斷時(shí)間間隔等約束，滿足，轉(zhuǎn)Step 15；不滿足，轉(zhuǎn)Step 6；

Step 15：是否k=1，是，轉(zhuǎn)Step 16；否，k=k?1，轉(zhuǎn)Step 12；

Step 16：是否j=N，是，轉(zhuǎn)Step 17；否，j=j+1，轉(zhuǎn)Step 6；

Step 17：計(jì)算目標(biāo)值；

Step 18：生成初始解方案。

3.3 算法鄰域構(gòu)造

對(duì)于判斷鄰域解的可行性，在鄰域停站方案構(gòu)造完成后，第一，判斷其是否滿足客流需求(即式(7)～(8)約束)，不滿足則重新構(gòu)造鄰域停站方案；第二，對(duì)滿足客流需求的鄰域停站方案，計(jì)算各站(除始發(fā)站外)出發(fā)到達(dá)時(shí)間，并判斷各時(shí)間間隔約束，不滿足則重新構(gòu)造鄰域停站方案，構(gòu)造次數(shù)達(dá)到鄰域內(nèi)部搜索次數(shù)limit1 后，還不能滿足時(shí)間間隔，則在可運(yùn)行時(shí)間窗內(nèi)重新生成始發(fā)時(shí)間，并判斷時(shí)間間隔約束，直至生成新的可行解。

圖3 鄰域構(gòu)造示意圖Fig.3 Schematic diagram of the domain construction

3.4 算法步驟

Step 1：輸入原始數(shù)據(jù)(車站數(shù)量和等級(jí)，列車種類、數(shù)量和等級(jí)，各站停站時(shí)間，各站最小停站率，列車最大停站率)；

Step 2：設(shè)定算法參數(shù)，包括種群規(guī)模NP，采蜜蜂數(shù)量FoodNumber，局部循環(huán)次數(shù)limit 和最大迭代次數(shù)MaxCycle等；

Step 3：初始化：使用初始解算法生成原始種群解(解的內(nèi)容包括停站方案、各站出發(fā)時(shí)間、各站到達(dá)時(shí)間)；

Step 4：根據(jù)目標(biāo)函數(shù)公式計(jì)算種群中各蜜蜂(各初始解方案)的適應(yīng)值，并得出最優(yōu)初始可行解(即獲得最優(yōu)解H 的停站方案、各站出發(fā)時(shí)間、各站到達(dá)時(shí)間、所需動(dòng)車組數(shù)量、總旅行時(shí)間)；

Step 5：采蜜蜂通過鄰域構(gòu)造方法對(duì)初始可行解進(jìn)行優(yōu)化，若新解FitnessSol

Step 6：根據(jù)limit 判斷是否有放棄的蜜源，若有，采蜜蜂轉(zhuǎn)換為偵察蜂并隨機(jī)產(chǎn)生一個(gè)新蜜源(即新的可行解)；

Step 7：計(jì)算選擇蜜源的概率prob；

Step 8：觀察蜂根據(jù)概率prob 選擇可行解，并在該可行解鄰域內(nèi)進(jìn)行優(yōu)化，若新解FitnessSol

Step 9：根據(jù)limit 判斷是否有放棄的蜜源，若有，觀察蜂轉(zhuǎn)換為偵察蜂并隨機(jī)產(chǎn)生一個(gè)新蜜源；

Step 10：將當(dāng)前最優(yōu)解保存在value，并進(jìn)行迭代次數(shù)檢驗(yàn)，iter=iter+1,若iter

Step 11：輸出最優(yōu)解。

4 實(shí)例分析

4.1 參數(shù)設(shè)定

算法參數(shù)見表2。

表2 算法參數(shù)Table 2 Algorithm parameter value

蜂群參數(shù)(種群規(guī)模、迭代次數(shù)、局部搜索次數(shù))取值對(duì)求解結(jié)果都有較大影響。本文通過多次測(cè)試，確定種群規(guī)模NP=50，迭代次數(shù)MaxCycle=100，局部搜索次數(shù)limit=5，鄰域內(nèi)部搜索次數(shù)limit1=50。

4.2 計(jì)算分析

根據(jù)本文構(gòu)建的模型和設(shè)計(jì)的求解算法，計(jì)算得到的初始解列車停站方案(按運(yùn)行圖中時(shí)間順序排列)如圖4 所示，初始解列車運(yùn)行圖如圖6 所示。優(yōu)化后最優(yōu)解列車停站方案(按運(yùn)行圖中時(shí)間順序排列)如圖5所示，優(yōu)化后列車運(yùn)行圖如圖7所示。初始解與最優(yōu)解結(jié)果對(duì)比如表3所示。

圖4 初始解列車停站方案Fig.4 Initial solution of train stopping plan

圖5 最優(yōu)解列車停站方案Fig.5 Optimal train stopping plan

圖6 初始解列車運(yùn)行圖Fig.6 Initial train operation diagram

圖7 最優(yōu)解列車運(yùn)行圖Fig.7 Optimal train operation diagram

表3 初始解與最優(yōu)解結(jié)果對(duì)比Table 3 Initial solution is compared with the optimal solution

與初始解相比：

1) 在滿足客流需求的條件下，列車停站總次數(shù)減少了10.9%；

2) 列車越行時(shí)間增加了61 min，越行時(shí)間的增多是因?yàn)樵谧非筮\(yùn)用動(dòng)車組數(shù)量最少這一目標(biāo)過程中，運(yùn)行圖中運(yùn)行線小范圍集中造成的；

3)初始解所需動(dòng)車組數(shù)量為直達(dá)列車4列、擇站停列車19 列，最優(yōu)解所需動(dòng)車組數(shù)量為直達(dá)列車2 列，擇站停列車14 列。所需直達(dá)列車等級(jí)的動(dòng)車組數(shù)量減少了50%，所需擇站停列車等級(jí)的動(dòng)車組數(shù)量減少了26.3%，總體上所需動(dòng)車組數(shù)量減少了30.4%。

5 結(jié)論

1) 本文構(gòu)建的研究模型能夠準(zhǔn)確描述停站方案與動(dòng)車組接續(xù)之間的制約關(guān)系，以及充分體現(xiàn)協(xié)同優(yōu)化的思想，且實(shí)例表明模型有效。

2) 對(duì)于求解模型的算法，本文針對(duì)初始解和鄰域的生成進(jìn)行了算法的設(shè)計(jì)，實(shí)例表明設(shè)計(jì)的算法高效、準(zhǔn)確。

3) 提供了一套行之有效的高速鐵路列車停站方案編制的理論方法，為鐵路運(yùn)營工作提供決策支持，能夠運(yùn)用在鐵路運(yùn)輸生產(chǎn)的決策工作中。

本文從全局的角度分析了列車停站方案、運(yùn)行圖以及動(dòng)車組接續(xù)之間的關(guān)系，使得各個(gè)計(jì)劃之間的聯(lián)系更加緊密，模型更具有可行性，設(shè)計(jì)了更貼合模型的人工蜂群算法，實(shí)例分析結(jié)果顯示優(yōu)化后的各項(xiàng)指標(biāo)都得到了明顯的改進(jìn)。但由于實(shí)際的停站方案考慮的條件更為復(fù)雜，如何在進(jìn)一步滿足旅客需求的條件下，實(shí)現(xiàn)停站方案的合理編制和動(dòng)車組的高效利用是今后需要深入研究的方向。