基于理想點法的高速鐵路列車停站方案優(yōu)化

查偉雄，任逸飛，李 劍，嚴(yán)利鑫

（華東交通大學(xué)交通運輸工程學(xué)院，南昌 330013）

列車停站方案是列車開行方案的重要環(huán)節(jié)，明確列車為旅客提供的服務(wù)區(qū)間，在列車徑路、類別、編組輛數(shù)、開行頻率確定后，根據(jù)客流需求和列車協(xié)調(diào)配合情況，確定各類列車的停站序列.高鐵列車停站越多越方便旅客出行和換乘，也滿足旅客的多元化需求，同時可以吸引更多客流，然而停站次數(shù)增多也會導(dǎo)致企業(yè)運營成本增加，乘客旅行時間增長，也不利于車底周轉(zhuǎn).因此，合理的停站方案選擇對增加鐵路企業(yè)的效益，提升鐵路在多種運輸方式中的競爭力有著重大的意義.

從現(xiàn)有的研究來看，國內(nèi)外學(xué)者大多將運輸成本最小化作為列車停站方案的目標(biāo)函數(shù)進行考慮.Chang等［1］將鐵路企業(yè)和旅客出行的成本最小作為目標(biāo)對臺灣列車停站方案進行優(yōu)化.Qi等［2］以列車空費距離和所有列車總停站數(shù)最小為目標(biāo)建立了一個多目標(biāo)線性規(guī)劃模型優(yōu)化列車停站方案.李得偉等［3］研究了如何使總停站次數(shù)最少.也有部分學(xué)者考慮到旅客的需求，建立了以旅客出行時間最小為目標(biāo)的模型來優(yōu)化列車停站方案.Niu等［4］以旅客總等待時間最小為目標(biāo)研究了時變條件下一條高鐵走廊的列車時刻表優(yōu)化問題.許若曦等［5］建立了混合整數(shù)規(guī)劃模型，側(cè)重于旅客換乘等待時間損失.牛豐等［6-7］構(gòu)建不確定客流條件下的高速列車停站方案機會約束規(guī)劃模型進行研究.田慧欣等［8-9］考慮到城際鐵路客流的時變特性，從客流出行時間信息入手，引入時空網(wǎng)絡(luò)方法，建立了更加完善的評價體系.還有部分學(xué)者建立了雙層規(guī)劃模型，將企業(yè)和旅客同時進行考慮.鄧連波等［10］建立了一個雙層規(guī)劃模型優(yōu)化旅客列車停站問題.黃志鵬等［11-12］構(gòu)建了能夠描述旅客出行決策和高鐵列車開行方案優(yōu)化的動態(tài)博弈過程的雙層規(guī)劃模型.目前大多數(shù)學(xué)者在進行客流分配的過程中一般采用全有全無法、用戶均衡模型或隨機用戶均衡模型，或?qū)⒖土髁慨?dāng)作約束條件考慮.同時，高速鐵路列車停站方案優(yōu)化為體現(xiàn)停站對經(jīng)濟效益、能力利用、運輸組織的難易程度等的影響，采用多目標(biāo)優(yōu)化方法更符合實際.但由于量綱、數(shù)量級等原因，難點在于目標(biāo)的集合.

鐵路運輸具有按流開車、大客流優(yōu)先的特點，本文結(jié)合鐵路運輸?shù)奶攸c，根據(jù)乘客對列車的選擇方式，即乘客會選擇在途時間最短的列車，提出了一種適用于鐵路的客流分配方式，并命名為大客流優(yōu)先分配法.將客流分配到每一列列車上，為停站方案制定、開行方案制定、客票分配等環(huán)節(jié)奠定基礎(chǔ).同時建立了以列車總停站次數(shù)、列車空費能力、旅客時間損失最小為目標(biāo)，滿足客流、列車運輸能力、每輛列車停站次數(shù)、始發(fā)終到站及重點車站停站約束的多目標(biāo)高速鐵路列車停站方案優(yōu)化模型，并設(shè)計了以理想點法為適應(yīng)度函數(shù)的改進遺傳算法進行求解，通過實例驗證了模型及算法的可行性.

1 高速鐵路列車停站方案數(shù)學(xué)描述

高速鐵路列車停站方案是高速鐵路列車在列車徑路、類別、編組輛數(shù)、開行頻率確定后，在各站點是否停站的停站序列［13］.本文主要以直線型多始發(fā)終到站列車停站方案為研究對象.設(shè)S={Si|i=1，2，…，n}為某高速鐵路線路上的車站集，n表示線路上的車站總數(shù).T={Tk|k=1，2，…，m}為線路中的列車集，m表示線路上的列車總數(shù).高速鐵路線路示意圖如圖1 所示.

圖1 高速鐵路線路示意圖Fig.1 Schematic diagram of high-speed railway line

對于不同的列車Tk，它們的編組輛數(shù)不盡相同，用Gk表示高速鐵路列車編組輛數(shù).高速鐵路列車編組輛數(shù)大多為8 節(jié)或16 節(jié).不同的編組輛數(shù)也對應(yīng)著不同的列車運輸能力，往往用額定載客量來描述列車運輸能力，用ck表示列車Tk的額定載客量.

引入0-1 變量xk，i來描述列車Tk在車站Si停與不停兩種情況，若列車Tk在車站Si停，則xk，i=1，若列車Tk在車站Si不停，則xk，i=0.

通常，一條線路上的列車停站方案包括一個以上的列車開行區(qū)段，對于不同開行區(qū)段的列車，它們的始發(fā)站和終到站不同，用sk表示列車Tk的始發(fā)站，用ek表示列車Tk的終到站.即當(dāng)Si=sk或Si=ek時，xk，i=1.用Rk表示列車Tk的開行區(qū)段，而不在開行區(qū)段中的車站，對于列車Tk來說，不存在停站作業(yè)，即當(dāng)Si?Rk時，xk，i=0.

2 高速鐵路列車停站方案優(yōu)化模型

2.1 模型假設(shè)

直線型高速鐵路停站方案的影響因素較多［14］，在建立模型之前，須做如下假設(shè)：

1）相同性假設(shè).假定雙向線路的客流量和收益相同，若要使整條線路的收益最大，只需要對單向線路進行研究.

2）確定性假設(shè).列車的起訖點、開行對數(shù)、開行時間、動車組編組、動車組周轉(zhuǎn)運用情況及客流均為已知條件，不考慮由于所制定的停站方案的不同所帶來的客流量的變化.

2.2 目標(biāo)函數(shù)設(shè)計

1）停站總次數(shù)最少.

增加列車停站次數(shù)將延長列車占用車底的時間.因此，在滿足旅客需求的前提下，盡量減少列車停站次數(shù)，可以降低運輸成本，提高鐵路企業(yè)經(jīng)濟效益.因此，以停站總次數(shù)最小為第一個優(yōu)化目標(biāo)建立目標(biāo)函數(shù)為

2）列車空費能力最小.

鐵路集團在制定列車停站方案時會保證列車的上座率達到一定標(biāo)準(zhǔn)，列車空費能力在某種程度上可以表示列車座位浪費情況，用站間空座位數(shù)與站間距離的乘積表示為

式中：Dk為列車Tk運行距離，km；qk，i，j為列車Tk上從車站Si到車站Sj的旅客數(shù)量；di，j為車站Si和車站Sj之間的距離.

3）旅客時間損失最小.

旅客在途時間由旅客候車時間、列車運行時間和列車停站消耗時間構(gòu)成.本文主要考慮列車停站消耗時間對旅客時間損失的影響，因此旅客時間損失為不下車的旅客由于列車停站而增加的旅行時間，計算公式為

式中：車站Sp為車站Si和車站Sj中間的車站；t1為列車的停站時間，min；t2為列車的啟停附加時間，min.

2.3 約束條件設(shè)計

列車停站方案必須盡可能滿足鐵路運輸需求并符合相關(guān)技術(shù)規(guī)范.因此，在編制過程中需要考慮一系列系統(tǒng)約束條件，如客流需求約束、列車運輸能力約束、每輛列車停站次數(shù)約束、始發(fā)終到站及重點車站停站約束等.

1）客流量約束.

停站方案的編制需遵從按流開車的原則［15］，即根據(jù)客流量的多少，確定列車是否進行停站服務(wù).因此，各區(qū)段上列車的載客數(shù)量都應(yīng)該滿足區(qū)段客流的需求，以盡可能地保證客流能夠全部帶走.約束條件為

式中：qi，j為從車站Si到車站Sj的客流 量.

2）列車運輸能力約束.

為保證高速鐵路列車的服務(wù)質(zhì)量和服務(wù)安全，需要保證在任何時候，高速鐵路列車上的旅客數(shù)量均不大于列車的定員數(shù)，即每個區(qū)間列車上的人數(shù)均不大于列車的定員.

設(shè)n個車站將高速鐵路線路分為n-1 個區(qū)間r，約束條件為

式中：ξr，i，j為0-1 變量，表示區(qū)間r是否在車站Si和車站Sj之間.

3）每輛列車停站次數(shù)約束.

列車停站次數(shù)過多會降低列車的旅行速度，同時影響了通過能力.為滿足旅客對便利性、快捷性、高服務(wù)質(zhì)量以及鐵路部門經(jīng)濟效益、運輸效率等不同方面的要求，需要對單次列車最大停站次數(shù)進行限制.同時為滿足必須的停站作業(yè)需求，需要對單次列車最小停站次數(shù)進行限制.約束條件為

式中：W1為列車Tk的最小規(guī)定停站次數(shù)；W2為列車Tk的最大規(guī)定停站次數(shù).

4）始發(fā)終到站及重點車站停站約束.

通常一條線路上的列車停站方案包括一個以上的列車開行區(qū)段，對于不同開行區(qū)段的列車，它們的始發(fā)站和終到站不同，列車在其始發(fā)終到站必須停車，同時為滿足必要的停站作業(yè)，在某些列車在相應(yīng)的重點車站也必須停車.對于列車Tk，不在其開行區(qū)段中的車站，不存在停站作業(yè)，約束條件為

式中：vk為列車Tk的重點車站.

5）取值范圍約束.

變量xk，i描述列車Tk在車站Si停與不停兩種情況，是0-1 決策變量，取值范圍為

變量qk，i，j取值范圍為

變量ck為列車Tk的額定載客量，為方便計算，高速鐵路8 節(jié)編組列車的額定載客量通常取600，16 節(jié)編組列車的額定載客量通常取1 200，取值范圍為

2.4 優(yōu)化模型分析

通過對目標(biāo)函數(shù)和約束條件的設(shè)計，得到高速鐵路停站方案優(yōu)化模型，該模型為多目標(biāo)0-1 非線性優(yōu)化模型，屬于NP-hard 問題，使用精確算法很難在較短時間內(nèi)獲得最優(yōu)解，因此選擇了人工智能算法來對其進行求解.

3 算法設(shè)計

針對模型，首先需要進行客流分配來確定每列列車上乘客的上下站點，才能對目標(biāo)進行求解.結(jié)合0-1 決策變量以及列車停站方案的特點，該模型適合用遺傳算法求解.本文利用理想點法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，并設(shè)計了結(jié)合大客流優(yōu)先分配法的遺傳算法對模型進行求解.

3.1 大客流優(yōu)先分配法

鐵路上的客流分配方式與道路上的客流分配方式不同，若把選擇不同的列車看作選擇路徑，路段的阻抗不是隨著客流增加而慢慢變化的，而是當(dāng)乘客數(shù)到達額定載客量時，后續(xù)的乘客就不能選擇乘坐這趟列車.因此不能采取常規(guī)的如用戶均衡等配流方法.

本文結(jié)合鐵路運輸按流開車、大客流優(yōu)先的特點，根據(jù)乘客對列車的選擇方式，即乘客會選擇在途時間最短的列車，提出了一種適用于鐵路的客流分配方式，并命名為大客流優(yōu)先分配法.具體算法思路為：根據(jù)按流開車的原則、開行方案的編制原則以及客票分配的原則，可以將客流數(shù)量最多的OD 點對的乘客優(yōu)先分配滿足乘客上下車、中途停站最少以及運行總里程最短的列車.根據(jù)客流數(shù)量大小依次分配，最后將所有客流分配完畢.

客流分配方式的具體算法分為4 個步驟.

步驟1：在客流OD 矩陣中選取數(shù)值最大的數(shù)a，a對應(yīng)了從車站Si到車站Sj的旅客數(shù)量.

步驟2：在事先生成的0-1 停站矩陣中選取滿足xk，i=1和xk，j=1且尚未滿員的列車，累加列車從i站到j(luò)站的停站0-1 變量，選取其中累加值最小的一列列車或幾列列車，也就是從車站Si到車站Sj中間停站次數(shù)最少的列車.

步驟3：計算這幾列列車的行駛里程長度，選取其中行駛里程數(shù)最短的一列或幾列列車，若是一列列車，將該列車額定載客量減去車站Si到車站Sj之間各區(qū)間的已有載客量，取最小值；若是幾列列車，將分別計算這幾列列車額定載客量減去該列車從車站Si到車站Sj之間各區(qū)間的已有載客量，取最小值.

步驟4：若待分配的客流數(shù)量小于此最小值，則將待分配的客流數(shù)量全部附加到該列車上或幾列列車上，將客流OD 矩陣中的對應(yīng)客流清零，并轉(zhuǎn)回步驟1 進行下一次分配.若待分配的客流數(shù)量大于等于此最小值，則將該最小值的客流附加到列車上.將客流OD 矩陣中的客流減去已經(jīng)分配下去的客流，并轉(zhuǎn)回步驟1 進行下一次分配，若最后=0，則說明該停站方案滿足客流需求.若最后qi，j-＞0，則說明該停站方案不合理.

3.2 理想點法

由于設(shè)計的優(yōu)化模型存在多個目標(biāo)，且目標(biāo)的單位和數(shù)量級具有較大差異，一般的權(quán)重賦值方法并不適用于將此多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題，理想點法具有可以無視不同目標(biāo)之間單位和數(shù)量級差異的優(yōu)點，因此本文引入理想點法作為適應(yīng)度函數(shù)，具體計算方法為：在相同的約束條件下，對多目標(biāo)問題中的各個目標(biāo)單獨進行求解，得到各個目標(biāo)的最優(yōu)解

引入懲罰因子αl，對于每一種停站方案都有一個實際值F={f1，f2，…，fl}，將實際值和期望值之間的偏差做比較來選擇問題的解，其數(shù)學(xué)表達式為

取適應(yīng)度函數(shù)的最小值，轉(zhuǎn)化后的單目標(biāo)問題的解即為原多目標(biāo)問題的解

在本文中，由于多目標(biāo)優(yōu)化的目標(biāo)數(shù)為3 個，因此l=1，2，3，對各目標(biāo)代入下文遺傳算法進行單目標(biāo)求解，計算出期望值，各目標(biāo)期望值分別為f1=438，f2=35 557 627，f3=706 390.

3.3 遺傳算法設(shè)計

遺傳算法的基礎(chǔ)思想就是先編碼，然后再隨機地生成初始的種群.以優(yōu)勝劣汰為基礎(chǔ)原則，根據(jù)目標(biāo)函數(shù)值所設(shè)定的適應(yīng)度函數(shù)，在群體中通過選取適應(yīng)度最好的個體直接從其中進入下一代，鄰域群體則是通過交叉變異而產(chǎn)生的，而且在其中存活下來的后代則是經(jīng)過自然選擇后目前在該種群中最好的染色體.具體算法分為9 個步驟.

步驟1：初始化，包括初始停站方案相關(guān)數(shù)據(jù)，車站數(shù)據(jù)、列車數(shù)據(jù)、客流數(shù)據(jù)等以及遺傳算法的交叉概率、變異概率、種群規(guī)模、最大迭代次數(shù).

步驟2：種群初始化.初始化種群P，種群大小為N.每一個個體代表一個列車停站方案.由于使用0和1 表示列車在車站是否停站，所以采用二進制編碼.以高速鐵路線上所有列車經(jīng)過的站點為一個染色體，一個站點作為一個基因位，所有站點的集合就是染色體的長度.基因取值為0 表示列車在該站不停站，取值為1 表示列車在該站停站.

步驟3：客流分配.運用大客流優(yōu)先分配法，將所有乘客分配到每一列列車上，若個體不滿足客流需求，則在適應(yīng)度計算時加一個較大懲罰因子，若滿足客流需求，則進入下一算法步驟.

步驟4：適應(yīng)度函數(shù)設(shè)定.運用理想點法將多目標(biāo)問題轉(zhuǎn)化為單目標(biāo)問題.求解每個目標(biāo)的最優(yōu)解作為期望值，通過比較實際值和期望值之間的偏差對個體從小到大進行排序.

步驟5：判斷是否達到最大迭代次數(shù)，若沒有，則繼續(xù)下面的算法步驟.若達到最大迭代次數(shù)，則輸出個體適應(yīng)度值最低的最佳個體作為結(jié)果.

步驟6：以適應(yīng)度函數(shù)的大小為依據(jù)，對群體進行排序，采取錦標(biāo)賽選擇，產(chǎn)生新一代種群.

步驟7：對種群中的染色體進行交叉操作，根據(jù)交叉概率隨機選擇2 條染色體，采用兩點交叉將2 條染色體對應(yīng)序列的基因進行交換.

步驟8：對種群中的染色體進行變異操作，根據(jù)變異概率隨機選擇染色體，采用單點變異隨機生成新個體.

步驟9：經(jīng)過選擇、交叉、變異后生成的新種群，轉(zhuǎn)向步驟3 進行計算.

4 算例分析

以京滬高鐵2018 年某日列車停站方案相關(guān)資料為例進行分析，京滬高速鐵路由北京南站至上海虹橋站，全長1 318 km，共設(shè)24 個車站，為方便計算，將天津西站和天津南站都統(tǒng)計為天津站，統(tǒng)計為23 個站.23 個車站將線路劃分為22 個區(qū)間，將車站沿下行方向依次標(biāo)號如圖2 所示.

圖2 京滬高鐵線路示意圖Fig.2 Schematic diagram of Beijing-Shanghai high-speed railway line

初始停站方案中列車總數(shù)m=62 列.各列車始發(fā)終到站均確定.停站時間t1=2 min，啟停附加時間為t2=3 min.編組輛數(shù)均為16 輛，列車定員ck=1 200 人.最小停站次數(shù)W1=2，最大停站次數(shù)W2=16.客流數(shù)據(jù)見表1.

表1 2018 年某日京滬高鐵下行列車客流表Tab.1 Passenger flow chart of Beijing-Shanghai high-speed railway on a certain date in 2018

4.1 計算過程

為驗證算法的有效性，采用電腦CPU 為2.6 GHz六核Intel Core i7，內(nèi)存為16 GB，MATLAB 2019 b 進行求解，參數(shù)設(shè)置：最大迭代次數(shù)500 次，初始種群規(guī)模為100，交叉概率為0.8，變異概率為0.2，先對各目標(biāo)進行單目標(biāo)求解，計算出期望值，各目標(biāo)期望值分別為f1=438，f2=35 557 627，f3=706 390.再利用理想點法求解得到優(yōu)化后的京滬高鐵列車停站方案.迭代次數(shù)圖如圖3所示.

由圖3 可見，算法在第346 代后趨于穩(wěn)定，轉(zhuǎn)化后的單目標(biāo)問題最小值為0.111.優(yōu)化后的列車停站方案如圖4 所示.

圖3 迭代次數(shù)圖Fig.3 Schematic diagram showing numbers of iterations

圖4 優(yōu)化后的列車停站方案圖Fig.4 Schematic diagram of optimized schedule for train stops

4.2 結(jié)果分析

將得到的優(yōu)化后的列車停站方案與現(xiàn)有列車停站方案在幾個方面做比較，結(jié)果如表2 所示.

由表2 可知，該列車停站方案的總停站次數(shù)為465 次，優(yōu)化前的原始停站方案的總停站次數(shù)為505 次，減少了40 次，優(yōu)化了7.92%.該列車停站方案的列車空費能力為36 257 241，優(yōu)化前的原始停站方案的列車空費能力為45 236 534，減少了8 979 293，優(yōu)化了19.84%.該列車停站方案的旅客損失時間為727 065 min，優(yōu)化前的原始停站方案的旅客損失時間為1 243 400 min，減少了516 335 min，優(yōu)化了41.52%.

表2 列車停站方案對比表Tab.2 Comparison of train stop schedule

研究結(jié)果顯示，相比較于原列車停站方案，新的列車停站方案在各方面都有所改進.針對總停站次數(shù)和列車空費能力的優(yōu)化效果并沒有旅客損失時間那么顯著，是因為提出的一種新的客流分配方法，可以極大程度地減少旅客因停站而損耗的時間，而為了滿足客流的出行需求，有些停站是必須的，所以針對列車總停站次數(shù)的優(yōu)化效果沒有那么明顯，但是也減少了不必要的停站.因此，研究成果可為列車停站方案的制定提供合理參考.

5 結(jié)論

1）建立了以總停站次數(shù)、列車空費能力、旅客損失時間最小為目標(biāo)函數(shù)的多目標(biāo)列車停站方案優(yōu)化模型.并提出大客流優(yōu)先分配法，設(shè)計了遺傳算法對模型進行求解.

2）以京滬高鐵為實例，對原列車停站方案進行優(yōu)化.結(jié)果表明，優(yōu)化后的列車停站方案能夠減少7.92%的停站次數(shù)，減少19.84%的列車空費能力，降低41.52%的旅客損失時間，研究成果可為停站方案的制定提供合理參考.

3）以直線性列車停站方案作為研究對象，很多條件已經(jīng)確定，復(fù)雜度較低.下一步研究方向是繼續(xù)完善客流分配方式，以及結(jié)合客流分配的高速鐵路開行方案優(yōu)化.