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

湯振源

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

0 引言

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

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

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

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

1 模型構(gòu)建

1.1 基本假設

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

1.2 基本符號

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

表1 基本符號說明Tab.1 Description of basic symbols

1.3 上層停站方案模型

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

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

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

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

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

上層開行方案模型應滿足如下2 個基本約束條件。

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

式中：β表示停站率。

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

1.4 下層客流博弈均衡模型

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

式中：M為懲罰因子。

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

式中：為權(quán)重值，表示w消費層次客流對票價、時間的敏感度，滿足

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

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

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

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

（1）局中人：同一OD 相同消費層次客流個體per。

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

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

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

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

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

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

下層客流博弈均衡分配模型應滿足如下3 個基本約束條件。

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

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

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

2 算法設計

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

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

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

圖1 開行區(qū)段編號示意圖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：消除約束。運用外罰函數(shù)法消除約束

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

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

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

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

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

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

圖4 單點交叉操作示意圖Fig.4 Single-point crossover operation

圖5 簡單變異操作示意圖Fig.5 Simple mutation operation

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

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

3 案例分析

3.1 案例背景

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

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

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

表2 蘭新高速鐵路站點編號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é)果分析

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

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

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

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

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

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

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

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

綜上，對上層每一代產(chǎn)生的解集，由算法流程及程序運行結(jié)果知，下層客流分配均能很好地收斂，故選取上層非支配序為1 的層級解集為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均未開行一站直達列車，這是因為模擬OD客流數(shù)據(jù)波動性較小造成的，使得各開行區(qū)段起訖點客流不能滿足開行直達列車的要求。

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

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

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

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

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

4 結(jié)束語

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