孫國鋒，景 云,2，馬亞雯

(1.北京交通大學(xué) 交通運輸學(xué)院, 北京 100044; 2.北京交通大學(xué) 智慧高鐵系統(tǒng)前沿科學(xué)中心, 北京 100044;3.中國市政西北設(shè)計研究院有限公司，甘肅 蘭州 730030)

現(xiàn)階段高速鐵路(以下簡稱“高鐵”)旅客的出行需求呈現(xiàn)多維化，個性化的特點[1]。傳統(tǒng)列車開行方案在給定客流總量基礎(chǔ)上，決策列車起訖點，開行數(shù)量及停站方案等內(nèi)容[2]，較少考慮對旅客出行時刻、旅行時間和票價等需求的響應(yīng)。因此，有必要根據(jù)多維個性化客流需求，研究匹配旅客多維出行需求的動態(tài)列車開行方案優(yōu)化問題。

列車開行方案的研究思路一般基于客流需求總量[3-5]和備選集思想[6-10]，編制滿足旅客空間位移需求的開行方案。文獻[3-5]均采用雙層規(guī)劃方法建立列車開行方案模型。為簡化列車開行方案優(yōu)化問題規(guī)模，一些研究預(yù)先給定部分變量，在此基礎(chǔ)上優(yōu)化其余變量，例如文獻[6]在給定列車停站方案的基礎(chǔ)上，優(yōu)化列車運行路徑和客流徑路，文獻[7]預(yù)先給定了列車的起訖站等；還有一些研究采用壓縮變量可行域的方法簡化問題，如文獻[8]在生成備選開行列車集合基礎(chǔ)上研究列車開行方案問題。在求解策略方面，文獻[3-5]均設(shè)計了啟發(fā)式求解方法，而在運用備選集思想簡化問題后，也可以使用多項式算法求解列車開行方案問題，如列生成算法[6]、拉格朗日松弛算法[8]等。上述研究較少考慮旅客時間需求，導(dǎo)致列車開行方案難以滿足多維旅客出行需求。

近年來，也有學(xué)者在研究列車開行方案問題中考慮了客流時變需求[11-14]。文獻[11]考慮旅客出行時變需求，在列車開行方案中引入時間要素，得到了匹配時變需求的列車開行方案；文獻[12]在傳統(tǒng)列車開行方案中增加了列車始發(fā)時間的估計值，運用雙層規(guī)劃方法研究了面向服務(wù)水平的高鐵列車開行方案優(yōu)化問題；文獻[13]在研究城際高鐵開行方案中引入了客流出行時間信息，基于時空網(wǎng)絡(luò)構(gòu)建了開行方案優(yōu)化模型，對客流時變特征明顯的城際鐵路列車開行方案進行了研究。雖然部分研究將旅客的時變需求引入列車開行方案問題中，但未考慮旅客出行需求與列車開行方案之間互相反饋的影響關(guān)系，未系統(tǒng)的考慮旅客多維度出行需求對列車開行方案問題的影響。

不同于傳統(tǒng)列車開行方案優(yōu)化問題，本文考慮了出行時刻、旅行時間、票價等旅客需求，引入動態(tài)列車開行方案概念，在傳統(tǒng)開行方案決策變量基礎(chǔ)上，優(yōu)化列車的始發(fā)時刻。

1 動態(tài)列車開行方案的內(nèi)涵

1.1 動態(tài)列車開行方案定義

列車開行方案在較長的時間周期中(1年或2年)是靜態(tài)不變的，僅在新編列車運行圖之前進行微調(diào)。然而，隨著高鐵旅客出行需求的個性化發(fā)展，應(yīng)當(dāng)考慮旅客的出行選擇行為，動態(tài)優(yōu)化列車開行方案。因此，動態(tài)列車開行方案是指，以滿足旅客出行需求為目標(biāo)，確定起訖站、停站方案、開行數(shù)量等靜態(tài)指標(biāo)及出發(fā)時刻、列車等級、票價等影響乘客出行選擇行為的動態(tài)指標(biāo)。

傳統(tǒng)的列車開行方案問題一般是以O(shè)D客流量為驅(qū)動，決策開行方案靜態(tài)指標(biāo)[15]，在客流分配過程中不考慮旅客出行選擇行為。動態(tài)列車開行方案在考慮旅客選擇行為的基礎(chǔ)上，動態(tài)分配客流，優(yōu)化列車始發(fā)時刻等動態(tài)指標(biāo)，與開行方案-運行圖協(xié)同優(yōu)化問題的區(qū)別在于動態(tài)列車開行方案優(yōu)化不考慮運行線沖突消解問題。

1.2 動態(tài)列車開行方案優(yōu)化問題描述

沿高鐵列車運行方向，車站集合為U={1,2,3,…,m}，m為車站數(shù)，車站u∈U由列車始發(fā)終到候選車站和非始發(fā)終到候選車站兩類組成，見圖1。

圖1 高鐵線路示意

本文提出考慮旅客多維出行需求的動態(tài)列車開行方案優(yōu)化，主要研究思路為：首先，基于高鐵線路的最小列車追蹤時間值，生成研究時段內(nèi)可行開行列車備選集合。然后，以備選開行列車集合為輸入，基于時空網(wǎng)絡(luò)構(gòu)建動態(tài)列車開行方案優(yōu)化問題模型；模型的輸入為路網(wǎng)信息、備選列車信息、旅客需求信息；目標(biāo)函數(shù)為系統(tǒng)效用最大化；決策變量為列車選擇開行弧段變量和客流分配變量；模型輸出為列車開行和客流分配方案，其中列車開行方案包括開行列車對數(shù)、每列車的發(fā)車時刻、列車停站。最后，設(shè)計基于模擬退火算法框架的求解算法，并以實際案例驗證模型和算法的有效性。

在建立模型時，重點圍繞旅客需求與動態(tài)開行方案之間的關(guān)系進行優(yōu)化，因此需要對高鐵運輸服務(wù)過程中的影響因素進行假設(shè)：

(1)列車的所有席位為二等座。

(2)所有列車均采用固定編組的方式，并且列車的定員一致。

(3)計算列車在區(qū)間運行時間時，只考慮區(qū)間純運行時分，不考慮起停車附加時分[16]。

(4)在優(yōu)化動態(tài)列車開行方案中，假設(shè)各車站候車能力和到發(fā)線能力充足。

1.3 符號說明

動態(tài)列車開行方案優(yōu)化模型的相關(guān)集合、索引、參數(shù)和變量見表1。

表1 集合、索引、參數(shù)和變量

2 旅客多維出行需求及時空網(wǎng)絡(luò)

2.1 多維旅客出行需求分析

影響旅客出行選擇行為的主要因素包括旅行時間、期望出發(fā)時刻和票價等?；诼每统鲂羞x擇的3個需求屬性，在效用函數(shù)中考慮3個影響因素，分別是旅行時間Tn,i，旅客期望出行時間偏差πn,i和票價Fn,i。則旅客群體n選擇列車i的效用函數(shù)μn,i為

μn,i=α1Tn,i+α2πn,i+Fn,i

(1)

(2)

MNL模型通常會高估或錯誤分配重新選擇概率，而廣義吸引模型(Generalized Attraction Model，GAM)可以有效解決該問題[17]，準(zhǔn)確描述旅客對列車的選擇行為。

在GAM中，wn,i為列車i∈I對旅客群體n的影子吸引力，則旅客群體n選擇任列車i∈I′的概率pn,i為

(3)

(4)

根據(jù)式(4)可更準(zhǔn)確描述高鐵旅客的決策過程。

2.2 時空網(wǎng)絡(luò)構(gòu)建

利用時空網(wǎng)絡(luò)描述動態(tài)列車開行方案優(yōu)化問題，時空網(wǎng)絡(luò)有向圖為G=(H，A)。(u,s)∈H表示時間坐標(biāo)為s、空間坐標(biāo)為u的節(jié)點，弧(u,v,s,t)∈A表示在s時刻從節(jié)點u出發(fā)至t時刻到達節(jié)點v的路徑。

時空網(wǎng)絡(luò)構(gòu)建過程見圖2，包含2類弧段，分別為運行弧和停站弧。其中運行弧是連接相鄰兩車站頂點之間的弧段；停站弧是連接同一車站節(jié)點不同時刻之間的弧段。列車對時空網(wǎng)絡(luò)弧段占用形成了完整的列車時空路徑，可描述列車在各站的到發(fā)時刻及停站方案。

圖2 時空網(wǎng)絡(luò)示意

3 模型建立

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

綜合考慮企業(yè)運營收益和旅客出行需求，以系統(tǒng)的整體效用最大為目標(biāo)，從最大化高鐵運輸收益、最小化旅客總旅行時間損失和期望出發(fā)時間偏差等3方面來構(gòu)造目標(biāo)函數(shù)。目標(biāo)函數(shù)為

(ω1Fn,i-ω2α1Tn,i-ω3α2πn,i)

(5)

(6)

(7)

3.2 約束條件

(1)列車流平衡約束

(8)

(2)列車始發(fā)終到車站約束

列車必須從始發(fā)、終到候選集合中選擇始發(fā)車站和終到車站

(9)

(3)客流分配約束

對同一時段內(nèi)相同起訖點的客流進行合并，形成旅客群體。每個旅客群體最多只能選擇一列高鐵列車出行。

(10)

(11)

(4)客流平衡約束

任意旅客群體只能在一個時空節(jié)點上車或者下車，則客流平衡約束為

?(u,s)∈V

(12)

(13)

(14)

(15)

(5)列車能力約束

列車所分配的旅客數(shù)量不得超過列車的額定載客能力，即

(16)

(6)開行列車數(shù)量約束[13]

模型的目標(biāo)函數(shù)主要考慮旅客多維出行需求，可能會造成開行列車數(shù)量越多，目標(biāo)函數(shù)越好的情況。因此，在保證旅客服務(wù)質(zhì)量的同時，為了減少高速鐵路企業(yè)的運營成本，應(yīng)對列車開行數(shù)量進行約束

Num(Ω)≤Nummax

(17)

(7)安全間隔約束

列車在始發(fā)站的出發(fā)時刻必須滿足安全出發(fā)間隔。約束為

(18)

(8)變量約束為

(19)

(20)

(21)

(22)

4 算法設(shè)計

本文構(gòu)建的非線性整數(shù)規(guī)劃模型為NP-hard問題，很難在多項式時間內(nèi)求解，元啟發(fā)式算法對求解該類問題具有很好的效果，作為元啟發(fā)式算法之一的模擬退火算法被多次運用求解列車開行方案問題[11,13-14,18]。因此，本文結(jié)合問題特點，基于模擬退火算法框架設(shè)計求解算法。

運用模擬退火算法求解動態(tài)列車開行方案問題的思路如下：生成由停站方案、列車在始發(fā)站發(fā)車時刻、客流分配三部分組成的初始解；通過設(shè)計刪除列車、拆分列車、超出上座率客流調(diào)整、未分配客流重新分配等方法生成鄰域解；在內(nèi)層循環(huán)中，分別設(shè)計隨機交換停站信息和合并開行列車策略，若產(chǎn)生新解優(yōu)于當(dāng)前解，則用新解替換當(dāng)前解，否則，按給定的概率隨機替換當(dāng)前解；在算法外層，保存算法歷史最優(yōu)解；當(dāng)滿足算法終止條件時算法結(jié)束，得到動態(tài)開行方案最優(yōu)解。

4.1 初始解的生成

(1)解的表達形式

動態(tài)列車開行方案初始解的構(gòu)成包括列車開行解和客流分配解兩部分，即問題的解Ω為

(23)

(24)

式中：Ti為列車i的開行解，由停站方案和列車發(fā)車時刻組成；Pi為分配給列車i的客流。STi為列車i的停站，表示列車在沿途各車站的停站弧占用情況，取值為0或1；DTi為列車i的發(fā)車時刻，表示列車i在始發(fā)站占用列車運行弧的情況。由于列車在各區(qū)間的運行時分和停站時長已知，可通過式(24)確定列車在各站的到發(fā)時刻。

(2)基于貪心算法的初始解生成方法

在生成初始解的過程中，客流分配解采用貪心算法生成，在客流分配解的基礎(chǔ)上，根據(jù)分配客流的始發(fā)終到車站需求，生成列車開行解?？土鞣峙浣馍傻姆椒ㄈ缦?。

遍歷長度為m的旅客群體列表，每次選擇一個未分配的旅客群體進行分配，遍歷旅客群體的期望出發(fā)時間序列，將該旅客群體分配給期望出發(fā)時間偏差最小的列車，執(zhí)行m次迭代后將返回的結(jié)果作為客流分配的初始結(jié)果。具體流程如下：

Step1初始化。初始化客流分配列表，生成n行m列取值為0的二維初始客流分配列表。

Step2基于貪心算法生成客流分配列表。

生活中，我們可以有意制造這樣的機會。比如：當(dāng)孩子請你幫他做一件事時，你可以告訴他：“媽媽還有事，五分鐘后能幫你，你可以等一會嗎？”當(dāng)孩子問你問題時，你不妨說：“這個問題很有意思，讓媽媽想一下，你也再思考下，五分鐘后我們來交換答案好嗎？”當(dāng)孩子渴望立即得到回應(yīng)，興奮地要跟你講一件事時，如果你正在忙，大可不必停下手中事轉(zhuǎn)向他，而是可以讓他稍作等待。

for 每個旅客群體n∈N

初始化旅客群體n的期望出發(fā)時間偏差列表。

for 每列車i∈I

計算期望出發(fā)時間偏差πn,i，將旅客群體n對每列車的期望出發(fā)時間偏差添加到期望出發(fā)時間偏差列表中。

Step3計算旅客群體n的期望出發(fā)時間偏差列表中的最小值。

Step4將最小值對應(yīng)索引處的客流分配結(jié)果由0改為1。

Step5通過貪心算法可生成期望出發(fā)時間偏差值相對較好的客流分配初始解，合并列車開行初始解和客流分配初始解便可生成動態(tài)列車開行方案問題的初始解。

4.2 鄰域解的生成

動態(tài)列車開行方案生成鄰域解，需要同時考慮列車開行解和客流分配解，生成策略主要包括：停開列車、拆分列車、超出上座率閾值的客流分配調(diào)整、未分配客流重新分配。

(1)停開列車和拆分列車[13]

檢查每列車在各區(qū)間的上座率，若某列車在各區(qū)間的上座率均小于規(guī)定停開列車閾值，則停開該列車。若某列車在某區(qū)間的上座率小于規(guī)定拆分列車閾值，對列車進行拆分，停開低于閾值區(qū)間的列車，更新拆分列車后新列車在始發(fā)站的發(fā)車時刻。

(2)調(diào)整超出上座率閾值的客流分配

檢查每列車在各弧段的上座率，如果列車在某弧段的上座率大于上座率閾值，首先計算超出上座率閾值的客流數(shù)量；然后隨機搜索上座率小于上座率閾值的列車，按照期望出發(fā)時間偏差由大到小將超出客流在客流分配列表中的值由1改為0，直至所有弧段上座率滿足列車能力約束。

(3)未分配客流重新分配

當(dāng)停開列車、拆分列車及調(diào)整超出上座率閾值的客流分配后，可能存在未分配的客流，重新分配該部分客流，直至所有客流均被分配。

首先遍歷未分配旅客n∈N，判斷旅客群體n的出行需求弧段；然后遍歷列車開行列表，如果列車i的開行弧段滿足旅客群體n的出行需求弧段，并且該弧段上座率小于上座率規(guī)定閾值，則將旅客群體n分配至列車i；最后檢查所有旅客是否全部分配，如果還有旅客未被分配，則采用貪心算法，增開列車，直至所有未被分配旅客均分配完畢。

4.3 適應(yīng)度函數(shù)及內(nèi)層合并列車操作

(1)適應(yīng)度函數(shù)

解Ω的適應(yīng)度函數(shù)為

fitness(Ω)=Z(Ω)-Λ·Num(Ω)

(25)

式中：fitness(Ω)為當(dāng)前解Ω對應(yīng)的適應(yīng)度函數(shù)；Z(Ω)為當(dāng)前解Ω的目標(biāo)函數(shù)值；Λ為開行列車懲罰系數(shù)；Num(Ω)為當(dāng)前解Ω的開行列車數(shù)量。

(2)合并列車操作

首先在列車開行解中隨機生成需要合并的列車i_num_col，然后在i_num_col±10范圍內(nèi)隨機生成需要合并的另一列車，判斷生成的兩列車是否均開行。如果不是，重新執(zhí)行該步驟，直至生成均開行列車的兩行解；如果是，則對生成的兩行解進行合并，將原本分配給兩列車的客流重新分配給合并后的列車。計算合并后新解在各區(qū)間的客座率，對超出客座率的客流重新分配，分配過程為：計算每列車在各區(qū)間的平均客座率，如果當(dāng)前平均客座率大于0且小于閾值L，則將當(dāng)前客流分配給該列車，遍歷所有列車后，若還存在未分配客流，增開列車，直至所有客流全部被分配。

4.4 基于模擬退火的算法步驟

模擬退火算法，需要設(shè)置初始溫度、溫度下降規(guī)則、同溫度下迭代次數(shù)、終止規(guī)則等參數(shù)。溫度下降規(guī)則選擇給定降溫系數(shù)下降方式；同一溫度下的迭代次數(shù)使用最大迭代次數(shù)進行控制；算法終止規(guī)則使用當(dāng)前溫度低于給定的終止溫度。算法步驟如下：

Step1初始化。初始化初始溫度為Γ0，終止溫度為Γe，退火步長，允許接受概率為初始化初始解為Ω0。

Step3當(dāng)前溫度Γ>Γe，執(zhí)行內(nèi)層算法：

Step5溫度下降，Γ=Γ×，返回Step3。

5 案例分析

5.1 基礎(chǔ)數(shù)據(jù)

北京北—呼和浩特東高鐵，運營里程為459 km，沿線共設(shè)車站16個。根據(jù)線路結(jié)構(gòu)特點及現(xiàn)有列車開行模式，由于沙河站和旗下營南站客流極少，故暫不考慮這兩個車站。考慮到北京北和清河站的動車段配屬在清河，兩個車站的旅客出行需求相似，可將北京北站和清河站合并為清河站，客流需求數(shù)據(jù)也相應(yīng)合并處理。共13個車站，車站編號依次為1～13，線路和車站信息見圖3，區(qū)間運行時分信息通過列車運行圖獲得。

圖3 清河(北京北)—呼和浩特東間區(qū)間和車站信息

按照2021年某日客流優(yōu)化動態(tài)列車開行方案，總客流為23 790人，由于篇幅有限，未詳細列舉各OD的客流信息。依據(jù)現(xiàn)行開行方案隨機生成某時間段旅客出發(fā)時刻需求。為了減少問題計算規(guī)模，對同一時段內(nèi)相同起訖點的客流進行合并，形成旅客群體共計793組。

算法中相關(guān)參數(shù)取值分別為：Γ0=100；Γe=0.1；=0.9；鄰域解生成過程中，允許刪除列車閾值為0.10；允許拆分列車閾值為0.18；適應(yīng)度函數(shù)中，Λ=1 000；合并列車操作中，L=0.75。

5.2 優(yōu)化結(jié)果分析

(1)動態(tài)開行方案結(jié)果分析

動態(tài)列車開行方案見圖4，圖中圓圈表示列車在該站停車，列車開行數(shù)量共計28列，列車起訖點和開行數(shù)量見表2。

圖4 清河(北京北)—呼和浩特東動態(tài)列車開行方案

表2 優(yōu)化前后列車起訖點和開行數(shù)量對比 列

優(yōu)化后開行列車總對數(shù)共計減少2列。優(yōu)化前全部開行清河(北京北)—呼和浩特東的長程列車，優(yōu)化后除開行長程列車外，還增開清河(北京北)—張家口/烏蘭察布的短程列車，滿足旅客出行需求。

優(yōu)化前后各個車站經(jīng)過的列車數(shù)、停站列車數(shù)對比情況如圖5所示。圖中橫坐標(biāo)為各車站序號，左側(cè)縱坐標(biāo)為停站列車數(shù)，右側(cè)縱坐標(biāo)為經(jīng)停比。優(yōu)化前后開行列車及停站方案綜合對比情況見表3。

圖5 各車站列車停站情況

表3 優(yōu)化前后列車開行及停站對比

表3中的停站總數(shù)包含列車在始發(fā)終到站的停站次數(shù)。優(yōu)化后開行列車數(shù)量減少了6.67%，列車停站總數(shù)減少了14.94%；優(yōu)化后得到的動態(tài)列車開行方案在滿足旅客多維需求的同時，減少了列車開行對數(shù)和停站次數(shù)，有效降低高速鐵路運營成本。

優(yōu)化后開行方案在各區(qū)間的客座率見圖6。所有列車的平均客座率為51.14%；列車在各區(qū)間的客座率比較均衡，客流分配結(jié)果滿足列車能力約束。

圖6 各區(qū)間列車客座率

(2)優(yōu)化目標(biāo)結(jié)果分析

目標(biāo)函數(shù)及各部分的數(shù)值隨迭代次數(shù)的變化規(guī)律，如圖7所示。隨著迭代次數(shù)的增加，目標(biāo)函數(shù)整體呈現(xiàn)增長趨勢，旅客群體總旅行時間損失和期望出發(fā)時間偏差呈現(xiàn)遞減趨勢。

圖7 目標(biāo)函數(shù)及各部分的數(shù)值隨迭代次數(shù)的變化規(guī)律

為了進一步驗證模型的正確性和適用性，對可變參數(shù)ω1、ω2和ω3取不同值的計算結(jié)果進行分析，得到動態(tài)列車開行方案統(tǒng)計指標(biāo)見表4。表中客票收益、總旅行時間損失、期望出發(fā)時間偏差均為基于旅客群體選擇概率的計算結(jié)果。當(dāng)ω1的取值增加時，考慮旅客群體選擇概率的系統(tǒng)客票收益呈遞增趨勢，ω2和ω3取不同值的計算結(jié)果也具有相似的特征。符合動態(tài)列車開行方案的優(yōu)化目標(biāo)。

表4 不同參數(shù)取值下動態(tài)列車開行方案統(tǒng)計指標(biāo)

(3)計算效率分析

算法在PyCharm 2021平臺使用Python語言實現(xiàn)，運行環(huán)境為1臺CPU Intel i7-5500U，4 GB內(nèi)存的計算機，當(dāng)ω1、ω2和ω3取不同參數(shù)值時，算法平均計算時間約為3.6 h。ω1=0.3,ω2=0.4,ω3=0.3時算法收斂迭代過程如圖8所示，算法迭代至35代時收斂。本文設(shè)計的求解算法整體收斂性良好，能有效求解動態(tài)列車開行方案優(yōu)化問題。

圖8 算法收斂迭代圖

6 結(jié)論

本文引入廣義吸引力模型描述旅客出行選擇行為，構(gòu)建開行方案時空網(wǎng)絡(luò)，將旅客對列車的選擇概率嵌入目標(biāo)函數(shù)，建立基于旅客多維出行需求的動態(tài)列車開行方案優(yōu)化模型，以鐵路運營企業(yè)和旅客系統(tǒng)最優(yōu)為目標(biāo)，考慮列車流平衡約束、始發(fā)終到站約束、客流分配約束、客流平衡約束、列車能力約束、列車開行數(shù)量約束、發(fā)車安全間隔約束，設(shè)計模擬退火算法進行求解。實例計算結(jié)果表明，本文所構(gòu)建的列車開行方案模型與算法能設(shè)計考慮旅客出行選擇行為的開行方案，優(yōu)化列車出發(fā)時刻等動態(tài)指標(biāo)，響應(yīng)旅客多維出行需求，為面向市場導(dǎo)向的高鐵開行方案制定提供決策支撐。

在未來的研究中，將進一步考慮路網(wǎng)條件下動態(tài)列車開行方案優(yōu)化問題，設(shè)計更加高效的算法求解動態(tài)開行方案優(yōu)化問題。