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

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

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

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

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

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

高速鐵路列車停站方案是高速鐵路列車在列車徑路、類別、編組輛數(shù)、開行頻率確定后，在各站點(diǎn)是否停站的停站序列［13］.本文主要以直線型多始發(fā)終到站列車停站方案為研究對(duì)象.設(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

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

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

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

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

2.1 模型假設(shè)

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

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

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

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

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

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

2）列車空費(fèi)能力最小.

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

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

3）旅客時(shí)間損失最小.

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

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

2.3 約束條件設(shè)計(jì)

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

1）客流量約束.

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

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

2）列車運(yùn)輸能力約束.

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

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

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

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

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

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

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

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

式中：vk為列車Tk的重點(diǎn)車站.

5）取值范圍約束.

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

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

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

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

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

3 算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

3.2 理想點(diǎn)法

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

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

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

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

3.3 遺傳算法設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

4 算例分析

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

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

初始停站方案中列車總數(shù)m=62 列.各列車始發(fā)終到站均確定.停站時(shí)間t1=2 min，啟停附加時(shí)間為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 計(jì)算過程

為驗(yàn)證算法的有效性，采用電腦CPU 為2.6 GHz六核Intel Core i7，內(nèi)存為16 GB，MATLAB 2019 b 進(jìn)行求解，參數(shù)設(shè)置：最大迭代次數(shù)500 次，初始種群規(guī)模為100，交叉概率為0.8，變異概率為0.2，先對(duì)各目標(biāo)進(jìn)行單目標(biāo)求解，計(jì)算出期望值，各目標(biāo)期望值分別為f1=438，f2=35 557 627，f3=706 390.再利用理想點(diǎn)法求解得到優(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)有列車停站方案在幾個(gè)方面做比較，結(jié)果如表2 所示.

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

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

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

5 結(jié)論

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

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

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