湯振源
(中鐵二院昆明勘察設計研究院有限責任公司 工程設計一處,云南 昆明 650200)
旅客列車開行方案以客運量為基礎,是運輸組織的重要內容之一。旅客列車開行方案優化問題一直是該領域學者重點研究的課題。
列車開行方案方面,周文梁等[1]、付慧伶等[2]、秦進等[3]構建了考慮旅客出行需求的列車開行方案優化模型,并采用智能算法對其進行求解;史峰等[4]構建旅客列車開行方案雙層規劃模型,并設計GP 算法求解下層多類用戶均衡模型、模擬退火算法求解上層旅客列車停站方案模型的混合算法,該研究運用成熟的交通流均衡理論解決了下層鐵路旅客均衡問題;黃林堯等[5]、王正彬等[6]通過考慮旅客出行時間等因素,構建了旅客列車開行方案優化模型,并設計遺傳算法作為模型求解算法;Qi等[7]提出雙目標混合整數線性規劃模型,并運用GAMS對該模型進行求解;Dong 等[8]基于旅客時間依賴性,構建了列車停站方案與列車時刻表集成的組合優化模型,并設計混合整數非線性規劃算法得到該模型優化解;Cacchiani 等[9]通過考慮旅客數量的不確定性,構建了混合整數線性規劃模型來獲得列車魯棒性停站方案。
客流均衡分配方面,王瑩等[10]通過確定不同弧段出行費用及能力約束,構建了整數網絡化客流分配模型;Meng 等[11]通過分析各類鐵路旅客的動態選擇行為,構建了需求-服務-資源組合優化模型,并設計了拉格朗日松弛算法;Niu 等[12]考慮鐵路旅客時變性,構建二次整數規劃模型,并設計精確非線性混合整數算法;孫晟凱等[13]通過分析地鐵高峰時段客流時空分布特征,提出了列車與客流動態交互評價模型;Jiang 等[14]通過分析擁擠條件下地鐵旅客進站流控制與列車實時調度關系,構建了以旅客滯留懲罰值最小為目標的組合優化模型,并設計基于Q-Learning的算法求解該模型。
綜上,既有研究主要借鑒傳統交通客流分配理論研究鐵路旅客出行問題,對鐵路旅客多樣性選擇及潛在出行博弈分析較少,從鐵路與旅客2 方考慮,通過引入非合作博弈,提出一種旅客出行選擇均衡方法,并以此為下層模型構建純整數非線性多目標雙層規劃模型,以獲得鐵路與旅客均滿意的高速鐵路開行方案。
該模型做如下假設:①依據單線高速鐵路制定開行方案,即僅考慮本線列車及本線客流;②上下行客流均衡;③不考慮遞遠遞減對鐵路票價的影響;④對旅客換乘時間不加考慮。
記ts為列車在站平均停留時間,鐵路旅客根據消費水平分為g個層次,則不同OD 間客流f(i,j)按照消費層次可以劃分為f w(i,j),其中w=1,2,…,g。將w消費層次客流中乘坐列車T的客流表示為(i,j),則(i,j)中的客流個體可記為(i,j)?;痉栒f明如表1所示。
表1 基本符號說明Tab.1 Description of basic symbols
記上層0-1 決策變量為x(T,si),其值為1 表示列車T在si停車。列車公里費用函數CT為
列車固定使用費用函數Cfix為
客票收入函數Cticket為
則鐵路凈收益目標函數f1為
列車空座位走行距離目標函數f2為
上層開行方案模型應滿足如下2 個基本約束條件。
(1)列車停站約束,如公式⑹所示。
式中:β表示停站率。
(2)通過能力約束,如公式⑺所示。
記w消費層次客流的時間價值為σw,則OD 為i,j的w消費層次客流個體per選擇乘坐列車T的票價費用函數(i,j)與時間價值函數(i,j)分別如公式⑻、公式⑼所示。
式中:M為懲罰因子。
總加權費用函數(i,j)如公式⑽所示。
式中:為權重值,表示w消費層次客流對票價、時間的敏感度,滿足
w消費層次客流個體per乘坐列車T的效用函數(i,j)如公式⑾所示。
w消費層次客流的人均效用函數(i,j)如公式⑿所示。
則客流個體per的滿意度評價函數(i,j)如公式⒀所示。
下層非合作博弈[15-17]客流均衡模型中博弈要素說明如下。
(1)局中人:同一OD 相同消費層次客流個體per。
(2)純策略:規定局中人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的可選策略所構成的f w(i,j)維向量。
由于純策略為混合策略的特例,故混合策略意義下的期望贏得函數如公式⒁所示。
由公式⑻至公式⒁知下層客流博弈均衡滿意度評價目標函數如公式⒂所示。
由納什均衡定義可知,公式⒂對應的最優解應為0。
下層客流博弈均衡分配模型應滿足如下3 個基本約束條件。
(1)客流博弈均衡條件如公式⒃所示。
(2)列車上座率約束如公式⒄所示,該約束為聯系上下層聯系反應函數。
(3)以同一OD間相同消費層次客流中選擇乘坐列車T的客流個體為決策變量,如公式⒅所示。
運用數學理論求解雙層規劃[18]精確最優解有很大困難,所構建的純整數雙層非線性規劃模型屬于典型的NP-Hard問題,運用最優化理論很難在多項式時間內找到問題的解。因此,具有隨機、并行和分布式特點且對問題無連續性要求的群智能算法在求解雙層規劃問題時凸顯其優勢,針對構建的模型特征,采用NSGA-Ⅱ算法求解上層停站方案模型,QPSO算法求解下層客流博弈均衡模型[19]。
規定任意開行區段內的列車種類數按停站方式確定為一站直達(以整數“1”表示)、大站停(以整數“2”表示)、擇站停(以整數“3”表示)和站站停(以整數“4”表示)4種。
步驟1:確定開行區段。開行區段編號示意圖如圖1所示。
圖1 開行區段編號示意圖Fig.1 Operation section coding
步驟2:調整原始OD客流表??鐓^段OD客流調整如圖2所示。
圖2 跨區段OD客流調整Fig.2 OD passenger flow adjustment in cross-regional section
步驟3:確定上層染色體編碼形式。染色體編碼方式如圖3所示。
圖3 染色體編碼方式Fig.3 Chromosome coding mode
步驟4:消除約束。運用外罰函數法消除約束
公式⑹、公式⑺、公式⒄,則公式⑷、公式⑸、公式⑽如公式⒆至公式所示。
式中:υ≥0 為懲罰因子;G1,G2,G3和G4分別為公式⑹、公式⑺、公式⒄所對應的罰函數項。
步驟5:初始化上層種群X。
步驟6:求解下層納什均衡解。針對每個上層解x,初始化下層種群Y,種群Y按照公式、公式所進化方程迭代更新。
式中:t表示下層迭代次數;pijwper(t+ 1)表示局部吸引子;隨機變量uijwper(t)~U(0,1);?為收縮-擴張系數;lijwper(t+ 1) 為特征長度;mijw(t) 為平均最好位置。
步驟7:上層算法迭代。單點交叉操作示意圖如圖4所示,簡單變異操作示意圖如圖5所示。
圖4 單點交叉操作示意圖Fig.4 Single-point crossover operation
圖5 簡單變異操作示意圖Fig.5 Simple mutation operation
將步驟6 中求得的下層納什均衡解yNash回代至公式⒆、公式⒇,對上層種群X執行非支配排序、擁擠度算子,然后執行圖4、圖5所示的進化算子。
步驟8:判斷迭代次數是否滿足,若滿足,算法終止,方案輸出。
以蘭新高速鐵路(蘭州西—烏魯木齊)為例,蘭新高速鐵路站點示意圖如圖6 所示。蘭新高速鐵路列車開行區段及其編號示意圖如圖7 所示。蘭新高速鐵路站點編號如表2 所示,開行區段站點如表3所示。
圖6 蘭新高速鐵路站點示意圖Fig.6 Lanzhou-Xinjiang High Speed Railway Station
圖7 蘭新高速鐵路列車開行區段及其編號示意圖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 蘭新高速鐵路區段劃分Tab.3 Division of Lanzhou-Xinjiang High Speed Railway sections
記列車座位等級μ={1,2,3};列車種類u={1,2,3,4};編組輛數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;客流波動系數?=1.3;列車停站率β=0.6;w=1的消費層次客流時間價值= 200元/h;w=2的消費層次客流時間價值= 100 元/h;w=3 的消費層次客流時間價值= 50 元/h;懲罰因子M=υ=5 000 000 000;權重系數= 0.1,= 0.9,= 0.5,= 0.5,= 0.9,= 0.1;收縮-擴張系數?=0.5。
算法迭代次數Gen=500,上層種群數量chroms=200,交叉概率pc=0.95,變異概率pm=0.01,下層種群數量partics根據區段相同消費層次客流人數動態確定。
未按擁擠度值選取的前5 層Pareto 前沿值如圖8 所示。分析圖8 可知:函數f1的收斂速度較函數f2的收斂速度慢,說明上層開行方案對列車空座位走行公里的影響較收益目標函數小,反映了運用下層非合作博弈理論進行客流均衡分配可有效降低列車開行費用。
圖8 未按擁擠度值選取的前5層Pareto前沿值Fig. 8 Pareto frontier values selected without considering congestion values
迭代次數達500 次時的未按擁擠度值選取的前5層Pareto值如圖9。由圖9可知,當f1值減小時(圖中為橫坐標值增大時),各層f2值(圖中縱坐標值)的波動差異較小,列車空座位靡費值較為穩定。由于橫坐標值增大意味著解是違背停站率約束的,故兩目標函數具有沖突性,f2值的優化在一定程度上會降低f1值的精度,說明運用NSGA-Ⅱ算法解決該模型的合理性。
圖9 未按擁擠度值選取的前5層Pareto值Fig.9 Pareto values of first five layers selected without considering congestion values
按擁擠度值選取的前5 層Pareto 值如圖10 所示。由圖10 可知,NSGA-Ⅱ算法中按照擁擠度值從大到小選擇解個體可使Pareto前沿解的分布更加均勻;均為負相關函數,非支配序為2,3,4,5所對應的散點圖(即圖10中的第2,3,4,5層級散點圖)負相關程度均比非支配序為1 (即圖10 中的第1層級散點圖)的Pareto前沿解相關度要大。結合圖9 分析結果,當鐵路收益值增加時,列車空座位走行公里數也增加,因此,選取鐵路收益值最大化,且列車空座位靡費較少、列車空座位走行公里值最小化的非支配序為1 的Pareto 前沿解是科學合理的。
圖10 按擁擠度值選取的前5層Pareto值Fig.10 Pareto values of first five layers selected according to congestion values
綜上,對上層每一代產生的解集,由算法流程及程序運行結果知,下層客流分配均能很好地收斂,故選取上層非支配序為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)開行區段1—6均未開行一站直達列車,這是因為模擬OD客流數據波動性較小造成的,使得各開行區段起訖點客流不能滿足開行直達列車的要求。
(2)開行區段6 未開行任何一類列車,這是因為即使會出現換乘現象,從哈密站上車、到達吐哈站及其以遠的旅客選擇開行區段4 和5 乘坐列車完成出行的效益較開行區段6 高,另一方面,這反映了雙層規劃的上下層關系:上層決策者對下層決策者具有支配作用,但這種作用不是絕對的,下層在上層指定的容許范圍內可自主決策,并反作用于上層。
(3)只有開行區段5 開行一對大站停列車,這是由于6 個開行區段中只有開行區段5 同時包含蘭州西站、西寧站、烏魯木齊站。
(4)開行區段5 擇站停列車的開行,能夠降低開行區段4 站站停列車的開行對數,可有效減少長遠距離旅客的出行時間,因此,可將開行方案2 與開行方案5作為備選較優開行方案。
由算法迭代結果知,開行方案5 與開行方案2相比,所對應的鐵路凈收益目標函數值最大,并且站站停列車開行頻率最小,故確定開行方案5 為最終滿意開行方案。滿意開行方案如圖11所示。
圖11 滿意開行方案Fig.11 Feasible and satisfactory train operation plan
綜合考慮鐵路運營部門與鐵路旅客兩方利益,首先運用雙層規劃模型刻畫兩方利益博弈關系,通過求解納什均衡點來尋求使兩方利益最大化的鐵路部門開行方案與旅客出行選擇行為;其次將現實中旅客合理假設化為不同消費層次的完全理性人,并通過OD 博弈環境劃分,使相同博弈環境中各消費層次旅客均具備“理性知識”,從而做出使自身利益最大化的出行策略選擇。這種基于非合作博弈的客流均衡分配方法,在蘭新高速鐵路實例中得以驗證,由該模型及算法得出的開行方案考慮到了每位旅客,不會造成部分鐵路旅客流失。