基于客流博弈均衡的旅客列車雙層開行方案優(yōu)化

湯振源

(中鐵二院昆明勘察設(shè)計(jì)研究院有限責(zé)任公司 工程設(shè)計(jì)一處，云南 昆明 650200)

0 引言

旅客列車開行方案以客運(yùn)量為基礎(chǔ)，是運(yùn)輸組織的重要內(nèi)容之一。旅客列車開行方案優(yōu)化問題一直是該領(lǐng)域?qū)W者重點(diǎn)研究的課題。

列車開行方案方面，周文梁等[1]、付慧伶等[2]、秦進(jìn)等[3]構(gòu)建了考慮旅客出行需求的列車開行方案優(yōu)化模型，并采用智能算法對(duì)其進(jìn)行求解；史峰等[4]構(gòu)建旅客列車開行方案雙層規(guī)劃模型，并設(shè)計(jì)GP 算法求解下層多類用戶均衡模型、模擬退火算法求解上層旅客列車停站方案模型的混合算法，該研究運(yùn)用成熟的交通流均衡理論解決了下層鐵路旅客均衡問題；黃林堯等[5]、王正彬等[6]通過考慮旅客出行時(shí)間等因素，構(gòu)建了旅客列車開行方案優(yōu)化模型，并設(shè)計(jì)遺傳算法作為模型求解算法；Qi等[7]提出雙目標(biāo)混合整數(shù)線性規(guī)劃模型，并運(yùn)用GAMS對(duì)該模型進(jìn)行求解；Dong 等[8]基于旅客時(shí)間依賴性，構(gòu)建了列車停站方案與列車時(shí)刻表集成的組合優(yōu)化模型，并設(shè)計(jì)混合整數(shù)非線性規(guī)劃算法得到該模型優(yōu)化解；Cacchiani 等[9]通過考慮旅客數(shù)量的不確定性，構(gòu)建了混合整數(shù)線性規(guī)劃模型來獲得列車魯棒性停站方案。

客流均衡分配方面，王瑩等[10]通過確定不同弧段出行費(fèi)用及能力約束，構(gòu)建了整數(shù)網(wǎng)絡(luò)化客流分配模型；Meng 等[11]通過分析各類鐵路旅客的動(dòng)態(tài)選擇行為，構(gòu)建了需求-服務(wù)-資源組合優(yōu)化模型，并設(shè)計(jì)了拉格朗日松弛算法；Niu 等[12]考慮鐵路旅客時(shí)變性，構(gòu)建二次整數(shù)規(guī)劃模型，并設(shè)計(jì)精確非線性混合整數(shù)算法；孫晟凱等[13]通過分析地鐵高峰時(shí)段客流時(shí)空分布特征，提出了列車與客流動(dòng)態(tài)交互評(píng)價(jià)模型；Jiang 等[14]通過分析擁擠條件下地鐵旅客進(jìn)站流控制與列車實(shí)時(shí)調(diào)度關(guān)系，構(gòu)建了以旅客滯留懲罰值最小為目標(biāo)的組合優(yōu)化模型，并設(shè)計(jì)基于Q-Learning的算法求解該模型。

綜上，既有研究主要借鑒傳統(tǒng)交通客流分配理論研究鐵路旅客出行問題，對(duì)鐵路旅客多樣性選擇及潛在出行博弈分析較少，從鐵路與旅客2 方考慮，通過引入非合作博弈，提出一種旅客出行選擇均衡方法，并以此為下層模型構(gòu)建純整數(shù)非線性多目標(biāo)雙層規(guī)劃模型，以獲得鐵路與旅客均滿意的高速鐵路開行方案。

1 模型構(gòu)建

1.1 基本假設(shè)

該模型做如下假設(shè)：①依據(jù)單線高速鐵路制定開行方案，即僅考慮本線列車及本線客流；②上下行客流均衡；③不考慮遞遠(yuǎn)遞減對(duì)鐵路票價(jià)的影響；④對(duì)旅客換乘時(shí)間不加考慮。

1.2 基本符號(hào)

記ts為列車在站平均停留時(shí)間，鐵路旅客根據(jù)消費(fèi)水平分為g個(gè)層次，則不同OD 間客流f(i，j)按照消費(fèi)層次可以劃分為f w(i，j)，其中w=1，2，…，g。將w消費(fèi)層次客流中乘坐列車T的客流表示為(i，j)，則(i，j)中的客流個(gè)體可記為(i，j)。基本符號(hào)說明如表1所示。

表1 基本符號(hào)說明Tab.1 Description of basic symbols

1.3 上層停站方案模型

記上層0-1 決策變量為x(T，si)，其值為1 表示列車T在si停車。列車公里費(fèi)用函數(shù)CT為

列車固定使用費(fèi)用函數(shù)Cfix為

客票收入函數(shù)Cticket為

則鐵路凈收益目標(biāo)函數(shù)f1為

列車空座位走行距離目標(biāo)函數(shù)f2為

上層開行方案模型應(yīng)滿足如下2 個(gè)基本約束條件。

（1）列車停站約束，如公式⑹所示。

式中：β表示停站率。

（2）通過能力約束，如公式⑺所示。

1.4 下層客流博弈均衡模型

記w消費(fèi)層次客流的時(shí)間價(jià)值為σw，則OD 為i，j的w消費(fèi)層次客流個(gè)體per選擇乘坐列車T的票價(jià)費(fèi)用函數(shù)(i，j)與時(shí)間價(jià)值函數(shù)(i，j)分別如公式⑻、公式⑼所示。

式中：M為懲罰因子。

總加權(quán)費(fèi)用函數(shù)(i，j)如公式⑽所示。

式中：為權(quán)重值，表示w消費(fèi)層次客流對(duì)票價(jià)、時(shí)間的敏感度，滿足

w消費(fèi)層次客流個(gè)體per乘坐列車T的效用函數(shù)(i，j)如公式⑾所示。

w消費(fèi)層次客流的人均效用函數(shù)(i，j)如公式⑿所示。

則客流個(gè)體per的滿意度評(píng)價(jià)函數(shù)(i，j)如公式⒀所示。

下層非合作博弈[15-17]客流均衡模型中博弈要素說明如下。

（1）局中人：同一OD 相同消費(fèi)層次客流個(gè)體per。

（2）純策略：規(guī)定局中人per的策略為所選擇乘坐的列車T，以∈N表示。

（3）純策略集：以θijwper={|?l∈L，T∈ω(l)，x(T，si)= 1，x(T，sj)= 1}表示局中人per的可選策略集合。

（6）純策略局勢(shì)：以∈×θijwper表示OD 為i，j的w消費(fèi)層次中所有客流個(gè)體per的可選策略所構(gòu)成的f w(i，j)維向量。

由于純策略為混合策略的特例，故混合策略意義下的期望贏得函數(shù)如公式⒁所示。

由公式⑻至公式⒁知下層客流博弈均衡滿意度評(píng)價(jià)目標(biāo)函數(shù)如公式⒂所示。

由納什均衡定義可知，公式⒂對(duì)應(yīng)的最優(yōu)解應(yīng)為0。

下層客流博弈均衡分配模型應(yīng)滿足如下3 個(gè)基本約束條件。

（1）客流博弈均衡條件如公式⒃所示。

（2）列車上座率約束如公式⒄所示，該約束為聯(lián)系上下層聯(lián)系反應(yīng)函數(shù)。

（3）以同一OD間相同消費(fèi)層次客流中選擇乘坐列車T的客流個(gè)體為決策變量，如公式⒅所示。

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

運(yùn)用數(shù)學(xué)理論求解雙層規(guī)劃[18]精確最優(yōu)解有很大困難，所構(gòu)建的純整數(shù)雙層非線性規(guī)劃模型屬于典型的NP-Hard問題，運(yùn)用最優(yōu)化理論很難在多項(xiàng)式時(shí)間內(nèi)找到問題的解。因此，具有隨機(jī)、并行和分布式特點(diǎn)且對(duì)問題無連續(xù)性要求的群智能算法在求解雙層規(guī)劃問題時(shí)凸顯其優(yōu)勢(shì)，針對(duì)構(gòu)建的模型特征，采用NSGA-Ⅱ算法求解上層停站方案模型，QPSO算法求解下層客流博弈均衡模型[19]。

規(guī)定任意開行區(qū)段內(nèi)的列車種類數(shù)按停站方式確定為一站直達(dá)(以整數(shù)“1”表示)、大站停(以整數(shù)“2”表示)、擇站停(以整數(shù)“3”表示)和站站停(以整數(shù)“4”表示)4種。

步驟1：確定開行區(qū)段。開行區(qū)段編號(hào)示意圖如圖1所示。

圖1 開行區(qū)段編號(hào)示意圖Fig.1 Operation section coding

步驟2：調(diào)整原始OD客流表?？鐓^(qū)段OD客流調(diào)整如圖2所示。

圖2 跨區(qū)段OD客流調(diào)整Fig.2 OD passenger flow adjustment in cross-regional section

步驟3：確定上層染色體編碼形式。染色體編碼方式如圖3所示。

圖3 染色體編碼方式Fig.3 Chromosome coding mode

步驟4：消除約束。運(yùn)用外罰函數(shù)法消除約束

公式⑹、公式⑺、公式⒄，則公式⑷、公式⑸、公式⑽如公式⒆至公式所示。

式中：υ≥0 為懲罰因子；G1，G2，G3和G4分別為公式⑹、公式⑺、公式⒄所對(duì)應(yīng)的罰函數(shù)項(xiàng)。

步驟5：初始化上層種群X。

步驟6：求解下層納什均衡解。針對(duì)每個(gè)上層解x，初始化下層種群Y，種群Y按照公式、公式所進(jìn)化方程迭代更新。

式中：t表示下層迭代次數(shù)；pijwper(t+ 1)表示局部吸引子；隨機(jī)變量uijwper(t)~U(0，1)；?為收縮-擴(kuò)張系數(shù)；lijwper(t+ 1) 為特征長(zhǎng)度；mijw(t) 為平均最好位置。

步驟7：上層算法迭代。單點(diǎn)交叉操作示意圖如圖4所示，簡(jiǎn)單變異操作示意圖如圖5所示。

圖4 單點(diǎn)交叉操作示意圖Fig.4 Single-point crossover operation

圖5 簡(jiǎn)單變異操作示意圖Fig.5 Simple mutation operation

將步驟6 中求得的下層納什均衡解yNash回代至公式⒆、公式⒇，對(duì)上層種群X執(zhí)行非支配排序、擁擠度算子，然后執(zhí)行圖4、圖5所示的進(jìn)化算子。

步驟8：判斷迭代次數(shù)是否滿足，若滿足，算法終止，方案輸出。

3 案例分析

3.1 案例背景

以蘭新高速鐵路(蘭州西—烏魯木齊)為例，蘭新高速鐵路站點(diǎn)示意圖如圖6 所示。蘭新高速鐵路列車開行區(qū)段及其編號(hào)示意圖如圖7 所示。蘭新高速鐵路站點(diǎn)編號(hào)如表2 所示，開行區(qū)段站點(diǎn)如表3所示。

圖6 蘭新高速鐵路站點(diǎn)示意圖Fig.6 Lanzhou-Xinjiang High Speed Railway Station

圖7 蘭新高速鐵路列車開行區(qū)段及其編號(hào)示意圖Fig.7 Train operation sections and their numbers in Lanzhou-Xinjiang High Speed Railway

表2 蘭新高速鐵路站點(diǎn)編號(hào)Tab.2 Station number of Lanzhou-Xinjiang High Speed Railway

表3 蘭新高速鐵路區(qū)段劃分Tab.3 Division of Lanzhou-Xinjiang High Speed Railway sections

3.2 案例求解及結(jié)果分析

記列車座位等級(jí)μ={1，2，3}；列車種類u={1，2，3，4}；編組輛數(shù)b= 8，為固定編組；票價(jià)率r={{0.9，0.8，0.7，0.6}，{0.6，0.5，0.4，0.3}，{0.4，0.3，0.1，0.1}}；列車公里費(fèi)用c= 500元；列車固定費(fèi)用cfix= 1 000元；列車旅行速度v= 250 km/h；車輛定員A= 800 人；列車在站平均停留時(shí)間ts=4 min；列車最低載客率= 0.6；列車最高載客率= 1.1；客流波動(dòng)系數(shù)?=1.3；列車停站率β=0.6；w=1的消費(fèi)層次客流時(shí)間價(jià)值= 200元/h；w=2的消費(fèi)層次客流時(shí)間價(jià)值= 100 元/h；w=3 的消費(fèi)層次客流時(shí)間價(jià)值= 50 元/h；懲罰因子M=υ=5 000 000 000；權(quán)重系數(shù)= 0.1，= 0.9，= 0.5，= 0.5，= 0.9，= 0.1；收縮-擴(kuò)張系數(shù)?=0.5。

算法迭代次數(shù)Gen=500，上層種群數(shù)量chroms=200，交叉概率pc=0.95，變異概率pm=0.01，下層種群數(shù)量partics根據(jù)區(qū)段相同消費(fèi)層次客流人數(shù)動(dòng)態(tài)確定。

未按擁擠度值選取的前5 層Pareto 前沿值如圖8 所示。分析圖8 可知：函數(shù)f1的收斂速度較函數(shù)f2的收斂速度慢，說明上層開行方案對(duì)列車空座位走行公里的影響較收益目標(biāo)函數(shù)小，反映了運(yùn)用下層非合作博弈理論進(jìn)行客流均衡分配可有效降低列車開行費(fèi)用。

圖8 未按擁擠度值選取的前5層Pareto前沿值Fig. 8 Pareto frontier values selected without considering congestion values

迭代次數(shù)達(dá)500 次時(shí)的未按擁擠度值選取的前5層Pareto值如圖9。由圖9可知，當(dāng)f1值減小時(shí)(圖中為橫坐標(biāo)值增大時(shí))，各層f2值(圖中縱坐標(biāo)值)的波動(dòng)差異較小，列車空座位靡費(fèi)值較為穩(wěn)定。由于橫坐標(biāo)值增大意味著解是違背停站率約束的，故兩目標(biāo)函數(shù)具有沖突性，f2值的優(yōu)化在一定程度上會(huì)降低f1值的精度，說明運(yùn)用NSGA-Ⅱ算法解決該模型的合理性。

圖9 未按擁擠度值選取的前5層Pareto值Fig.9 Pareto values of first five layers selected without considering congestion values

按擁擠度值選取的前5 層Pareto 值如圖10 所示。由圖10 可知，NSGA-Ⅱ算法中按照擁擠度值從大到小選擇解個(gè)體可使Pareto前沿解的分布更加均勻；均為負(fù)相關(guān)函數(shù)，非支配序?yàn)?，3，4，5所對(duì)應(yīng)的散點(diǎn)圖(即圖10中的第2，3，4，5層級(jí)散點(diǎn)圖)負(fù)相關(guān)程度均比非支配序?yàn)? (即圖10 中的第1層級(jí)散點(diǎn)圖)的Pareto前沿解相關(guān)度要大。結(jié)合圖9 分析結(jié)果，當(dāng)鐵路收益值增加時(shí)，列車空座位走行公里數(shù)也增加，因此，選取鐵路收益值最大化，且列車空座位靡費(fèi)較少、列車空座位走行公里值最小化的非支配序?yàn)? 的Pareto 前沿解是科學(xué)合理的。

圖10 按擁擠度值選取的前5層Pareto值Fig.10 Pareto values of first five layers selected according to congestion values

綜上，對(duì)上層每一代產(chǎn)生的解集，由算法流程及程序運(yùn)行結(jié)果知，下層客流分配均能很好地收斂，故選取上層非支配序?yàn)? 的層級(jí)解集為Pareto前沿解，得到以下5種開行方案。開行方案1如表4所示，開行方案2如表5所示，開行方案3如表6所示，開行方案4如表7所示，開行方案5如表8所示。

表4 開行方案1Tab.4 First train operation plan

表5 開行方案2Tab.5 Second train operation plan

表6 開行方案3Tab.6 Third train operation plan

表7 開行方案4Tab.7 Fourth train operation plan

表8 開行方案5Tab.8 Fifth train operation plan

分析表4至表8可知，開行方案1—5中：

（1）開行區(qū)段1—6均未開行一站直達(dá)列車，這是因?yàn)槟MOD客流數(shù)據(jù)波動(dòng)性較小造成的，使得各開行區(qū)段起訖點(diǎn)客流不能滿足開行直達(dá)列車的要求。

（2）開行區(qū)段6 未開行任何一類列車，這是因?yàn)榧词箷?huì)出現(xiàn)換乘現(xiàn)象，從哈密站上車、到達(dá)吐哈站及其以遠(yuǎn)的旅客選擇開行區(qū)段4 和5 乘坐列車完成出行的效益較開行區(qū)段6 高，另一方面，這反映了雙層規(guī)劃的上下層關(guān)系：上層決策者對(duì)下層決策者具有支配作用，但這種作用不是絕對(duì)的，下層在上層指定的容許范圍內(nèi)可自主決策，并反作用于上層。

（3）只有開行區(qū)段5 開行一對(duì)大站停列車，這是由于6 個(gè)開行區(qū)段中只有開行區(qū)段5 同時(shí)包含蘭州西站、西寧站、烏魯木齊站。

（4）開行區(qū)段5 擇站停列車的開行，能夠降低開行區(qū)段4 站站停列車的開行對(duì)數(shù)，可有效減少長(zhǎng)遠(yuǎn)距離旅客的出行時(shí)間，因此，可將開行方案2 與開行方案5作為備選較優(yōu)開行方案。

由算法迭代結(jié)果知，開行方案5 與開行方案2相比，所對(duì)應(yīng)的鐵路凈收益目標(biāo)函數(shù)值最大，并且站站停列車開行頻率最小，故確定開行方案5 為最終滿意開行方案。滿意開行方案如圖11所示。

圖11 滿意開行方案Fig.11 Feasible and satisfactory train operation plan

4 結(jié)束語

綜合考慮鐵路運(yùn)營(yíng)部門與鐵路旅客兩方利益，首先運(yùn)用雙層規(guī)劃模型刻畫兩方利益博弈關(guān)系，通過求解納什均衡點(diǎn)來尋求使兩方利益最大化的鐵路部門開行方案與旅客出行選擇行為；其次將現(xiàn)實(shí)中旅客合理假設(shè)化為不同消費(fèi)層次的完全理性人，并通過OD 博弈環(huán)境劃分，使相同博弈環(huán)境中各消費(fèi)層次旅客均具備“理性知識(shí)”，從而做出使自身利益最大化的出行策略選擇。這種基于非合作博弈的客流均衡分配方法，在蘭新高速鐵路實(shí)例中得以驗(yàn)證，由該模型及算法得出的開行方案考慮到了每位旅客，不會(huì)造成部分鐵路旅客流失。