基于時段偏好的高速鐵路列車停站方案雙層規(guī)劃方法

蔡 蕓，王 濤，樊昊煜，司曉鑫，黃志鵬

（1.中國鐵路蘭州局集團有限公司 財務(wù)部，甘肅 蘭州 730000；2.中國鐵路蘭州局集團有限公司 華澳鐵路綜合工程公司，甘肅 蘭州 730000；3.蘭州交通大學 交通運輸學院，甘肅 蘭州 730070；4.中國鐵路蘭州局集團有限公司 蘭州車務(wù)段，甘肅 蘭州 730050)

0 引言

高速鐵路的發(fā)展使得旅客出行不再局限于到達目的地，對于出行時段也有了更多的關(guān)注，旅客會根據(jù)原有的經(jīng)驗習慣與出行目的來選擇最理想的出行時段。在高速鐵路一日運營時段內(nèi)，旅客出行需求表現(xiàn)出明顯不均衡的時段偏好。此外，鐵路部門在組織運營時也應(yīng)當制定不同時段的列車停站方案。

在以往研究中，牛豐等[1]根據(jù)旅客出行目的不同確定了旅客需求置信度，以停站總時間最小為目標建立了高速鐵路列車停站方案優(yōu)化模型；Shang等[2]在時空狀態(tài)三維網(wǎng)絡(luò)中說明不同車站接收到的列車座位容量和旅客候車人數(shù)的信息不同，因此基于容量限制下優(yōu)化列車停站方案，合理安排所有旅客乘車；Qi 等[3]結(jié)合客流分布特點對列車運營區(qū)段和停站方案進行了綜合優(yōu)化；Niu 等[4]考慮時變需求以及最大限度減少旅客等待時間，優(yōu)化停站方案；許若曦等[5]基于減少列車中小站停站次數(shù)，增加相鄰大站間站站停列車等策略來優(yōu)化列車停站方案；黃志鵬[6]證明了基于旅行時間的旅客滿意度與不同停站方案的列車開行次序密切相關(guān)；高明瑤等[7]建立多目標混合0-1 規(guī)劃模型，運用理想點法和遺傳算法求得列車停站方案優(yōu)化解；Yue 等[8]使用拉格朗日松弛法將數(shù)學模型轉(zhuǎn)換為簡單的線性規(guī)劃問題，然后基于列生成算法通過迭代過程更新受限主問題(RMP)和子問題來尋找最佳解決方案；張小炳等[9]結(jié)合優(yōu)化停站方案的模型特點，設(shè)計了具有自適應(yīng)性的遺傳退火算法，控制全局的尋優(yōu)方向，模擬退火的鄰域搜索策略提高算法的鄰域搜索能力，最終快速搜索高質(zhì)量的解；Dong 等[10]用擴展的自適應(yīng)大鄰域搜索元啟發(fā)式方法對通勤鐵路列車停站計劃和時間表整合優(yōu)化。

為此，基于旅客對出行時段的偏好建立一個雙層規(guī)劃模型來優(yōu)化各個時段某一高速鐵路不同停站方案列車的開行數(shù)量，并將客流分配在各個出行時段上，使旅客出行需求與列車停站方案相互影響。研究在既有文獻基礎(chǔ)上做了以下創(chuàng)新。首先，同時考慮旅客的出行時段偏好與列車停站方案，并將多OD 客流需求分配在各個出行時段上；其次是不同于以往周期化的停站方案優(yōu)化[11]，研究制定了按照出行時段分別優(yōu)化的停站方案。

1 基于時段偏好的高速鐵路列車停站方案雙層規(guī)劃模型構(gòu)建與算法

1.1 問題描述

（1）旅客出行時段選擇博弈。高速鐵路全天的發(fā)車時間通常在6 : 00—22 : 00，以1 h 為一個時段，將6 : 00—6 : 59 標記為時段1，按照時間順序依次編號2，3，…，16，共16 個時段。不同時段對旅客的吸引度不同，同時，不同時段的可達度也不同。旅客對各個出行時段的偏好性，一方面表現(xiàn)為不同時段對旅客的吸引度具有很大差異，這種差異是客觀存在的，受到多種客觀因素的影響，如通勤客流占全部客流比重較大的車站，對旅客吸引度最高的時段為早晚高峰時段；又如旅客總是期望在城市公交方便的白天時段出行等，都是影響旅客選擇出行時段的客觀因素。對所有車站以往的客流數(shù)據(jù)統(tǒng)計分析，按照平均時段客流比例得出每個車站的時段吸引度。另一方面，旅客對各個出行時段的偏好性，還表現(xiàn)為旅客對不同時段可達度的選擇。當某個出行時段的吸引度較大時，大量的旅客均期望在這個時段出行，這時這個時段的可達度會大大降低?；蛘呗每蜑榱舜_保能夠在這個時段出行，其必須提前很早購票，使得旅客的出行靈活性降低。因此，旅客會根據(jù)出行經(jīng)驗，在時段吸引度和可達度之間進行博弈。博弈的結(jié)果是部分旅客偏好于吸引度，降低了可達度；部分旅客偏好于可達度，選擇吸引度較低的時段出行。最終形成一個UE 平衡狀態(tài)，即旅客選擇出行的任意時段，其出行阻抗都是一樣的。

（2）列車停站方案選擇博弈。鐵路運營部門在制定列車停站方案時，要考慮2 個方面的因素，一是了解旅客對出行時段的偏好，二是降低運營成本。研究以出行時段為單元，依據(jù)旅客對時段的偏好性，分別制定各個出行時段的列車停站方案及同種停站方案的列車開行數(shù)量，最大限度地滿足差異化的時段出行需求。同時列車開行數(shù)量和停站次數(shù)越多，其成本也越大。因此，在滿足旅客出行需求時，也要考慮運營成本問題。將符合停站約束的所有停站方案作為備選方案，各個時段列車停站方案均是備選方案中的一種或多種。

（3）優(yōu)化思路。在輸入端確定始發(fā)站至終到站間單方向的OD 客流需求、列車停站方案備選集和各車站的不同時段的旅客吸引度；輸出端為各時段平衡配流結(jié)果、各時段列車停站方案。在雙層規(guī)劃模型中，下層的配流結(jié)果會影響上層的列車停站方案及列車開行數(shù)量；上層模型確定的停站方案會影響旅客的出行時段選擇，進而影響各時段的配流結(jié)果。優(yōu)化流程如圖1 所示。

圖1 優(yōu)化流程Fig.1 Optimized flow scheme

1.2 模型構(gòu)建

（1）符號約定。①集合和下標。S為車站集合；H為列車停站方案集合；T為出行時段集合；i，j用來標識車站，i，j∈S；h用來標識列車停站方案，h∈H；t用來標識出行時段，t∈T。②輸入?yún)?shù)。qij為車站i→j的客流需求量，人；為車站i在第t時段無流量加載時的時段阻抗；為在第t時段能夠分配給車站i的最大客票數(shù)，張；Rh為第h種停站方案列車的開行成本，元；Ft為第t時段，始發(fā)站的發(fā)車能力，列；為第h種停站方案的列車分配給車站i的票額比例；α為調(diào)節(jié)系數(shù)；Y為列車定員數(shù)，人。③決策和輔助變量。為車站i→j的客流被分配到第t個時段的客流量，人；為0-1 變量，代表第t時段第h種停站方案列車是否開行；為下層決策中在車站i上車的客流被分配在第t時段的客流量，人；為上層決策中第t時段第h種停站方案列車的開行數(shù)量，列。

（2）上層規(guī)劃。優(yōu)化目標為鐵路運營成本最小化，目標函數(shù)如公式(1)所示。

約束條件包括發(fā)車能力約束和各時段供需平衡約束，其中發(fā)車能力約束為

各時段供需平衡約束為

式中：Y·表示第h類停站方案列車的全部席位數(shù)量，個；Y··表示第h類列車提供給車站i的客票數(shù)，張。

（3）下層規(guī)劃。①阻抗函數(shù)及客流均衡條件。旅客對各個出行時段的偏好性受到時段吸引度和時段可達度的影響。時段吸引度是客觀存在，可達度與時段上加載的流量有關(guān)。據(jù)此構(gòu)造各車站不同出行時段的阻抗函數(shù)，如公式(5)所示。

其中的取值與時段吸引度負相關(guān)，時段吸引度越高，取值越小。

對于在車站i上車的旅客，當時段t有流量加載時，即＞ 0，出行阻抗為最小；當時段t無流量加載時，即= 0，出行阻抗大于均衡狀態(tài)時的阻抗。由于不同車站的客流狀況不同，因此用戶均衡(User Equilibrium，UE)條件也不同，如公式(6)所示，fimin表示車站i的旅客最小出行阻抗。

其中，公式(8)滿足了客流守恒，即客流需求被分配到了阻抗最小的各個時段；公式(9)表示車站i→j的客流被分配在第t時段流量為正值；公式(10)表示任意時段t的流量由多個OD 客流構(gòu)成。

1.3 算法設(shè)計

雙層規(guī)劃問題被公認為是極其困難求解的優(yōu)化問題之一，采用遺傳算法對上層規(guī)劃求解，同時運用Frank-Wolfe 算法求解下層規(guī)劃。

（1）染色體編碼。采用0-1 編碼和整數(shù)編碼2種編碼方法[12]求解模型。其中0-1 編碼確定各時段各種停站方案的列車是否開行，即“1”表示開，“0”表示不開；整數(shù)編碼確定各時段各種停站方案的列車的開行數(shù)量。2 種編碼的染色體均由16 個基因片段組成，分別表示各個時段t上不同停站方案和開行數(shù)量。染色體示意圖如圖2 所示。

圖2 染色體示意圖Fig.2 Chromosome schematics

（2）算法流程。采用基于嵌套Frank-Wolfe 算法的遺傳算法對模型進行求解。其中，上層決策變量用遺傳算子編碼，下層規(guī)劃用Frank-Wolfe 算法求解。算法的具體實現(xiàn)步驟如下。

步驟 1：初始化。按照上述染色體編碼規(guī)則和約束條件(8)，隨機生成規(guī)模為popsize的初始停站方案()的可行解種群；設(shè)置上層規(guī)劃最優(yōu)目標E*= 0；設(shè)置最優(yōu)停站方案集W*為零向量；迭代次數(shù)b= 0。

步驟 2：檢查和判斷。依次檢查各染色體在時段t上第h類停站方案是否在車站i和j均停車，如果滿足，將時段t納入i→j的客流出行時段，停止檢查；如果不滿足，繼續(xù)檢查，直到時段t上所有停站方案均檢查完畢。完成i→j客流可選擇出行時段的集合，轉(zhuǎn)下一步。

步驟 3：用戶平衡配流。對于當前開行方案W(i)，用Frank-Wolfe 算法求解下層規(guī)劃，得到符合Wardrop User Equilibrium 準則的，并記錄所有可行解對應(yīng)的平衡配流結(jié)果和阻抗值。

步驟4：整數(shù)編碼。對步驟1 產(chǎn)生的0-1 編碼染色體中“1”的基因位置隨機賦1 個整數(shù)值，并滿足公式(8)、公式(10)約束。

步驟 5：遺傳操作。對列車開行數(shù)量()的初始種群進行選擇、交叉和變異操作，搜尋當前種群中適應(yīng)度最高的可行解W(b)，并更新最優(yōu)停站方案集W*=W(b)；迭代次數(shù)b=b+ 1。

步驟6：終止檢驗。如果迭代次數(shù)b大于迭代上限Ge，輸出最優(yōu)解W*，否則，轉(zhuǎn)步驟5。

圖3 西蘭高速鐵路車站示意圖Fig.3 Stations on Xi’an-Lanzhou high speed railway

2 案例分析

2.1 參數(shù)設(shè)置

（1）線路和車站。以西蘭高速鐵路(西安北—蘭州西)為例。為了計算方便，將蘭州西站編號為1，按照上行方向依次編號，西蘭高速鐵路車站示意圖如圖3 所示。

（2）OD 客流需求。為了全面了解旅客出行從出發(fā)到終到的過程，旅客起訖點的OD 客流需求是研究列車開行方案的基礎(chǔ)，它反映了最直接的客流需求。西蘭高速鐵路OD 客流需求如表1 所示。

（3）列車停站方案備選集。西蘭高速鐵路共設(shè)車站10 座，其中蘭州西、西安北為始發(fā)、終到車站，必停車。另外在4 個區(qū)域中心所在的定西北站、天水南站、寶雞南站、咸陽秦都站必停車。在其他車站設(shè)置停車次數(shù)上限為2 次，則全部停站方案為列車停站方案如圖4 所示。

其中，每種停站方案的開行成本為R= {8.0，8.2，8.3，8.3，8.3，8.7，8.5，8.5，8.6，8.6，8.7}{。

（4）阻抗設(shè)置。各車站在不同時段無客流加載條件下的時段阻抗如表2 所示。其中，距離始發(fā)站較遠的車站，每日首列車到達該站時的時段會相應(yīng)延遲，如車站3 到9，用M表示該時段出行阻抗非常大，不可能有流量加載。

（5）其他參數(shù)設(shè)置。采用16 輛編組CRH2 動車組列車，列車定員Y= 1 220，調(diào)節(jié)系數(shù)α= 3。種群規(guī)模popsize= 200，交叉概率Pc= 0.95，變異概率Pm= 0.05，最大停滯迭代次數(shù)為10，最大迭代次數(shù)為50，平衡配流精度e= 0.000 1。

表1 西蘭高速鐵路OD 客流需求 人Tab.1 OD passenger flow demand of Xi’an-Lanzhou high-speed railway

圖4 列車停站方案Fig.4 Train stopping scheme

表2 各車站在不同時段無客流加載條件下的時段阻抗Tab.2 Impedance without passenger flow loading in each period

2.2 計算結(jié)果分析

（1）下層配流結(jié)果。通過軟件編程，對該算例進行求解。下層規(guī)劃計算數(shù)據(jù)各時段配流結(jié)果如表3 所示。各上車站的OD 客流被分配在各個時段上出行，各時段客流具有明顯的波動性。

（2）上層開行方案優(yōu)化結(jié)果。通過下層規(guī)劃的配流結(jié)果和上層規(guī)劃開行方案的迭代，最終經(jīng)過50 代的進化篩選，得到16 個時段11 種列車的分布情況，第1—8 時段各種停站方案列車開行數(shù)量如圖5 所示，第9—16 時段各種停站方案列車開行數(shù)量如圖6 所示。各類列車均有開行，能夠服務(wù)沿途所有車站的旅客乘降。但是各類列車的分布不均勻，這與不同OD 客流量大小有關(guān)。最終優(yōu)化的列車停站方案，第1—8 時段列車停站方案如圖7 所示，第9—16 時段列車停站方案如圖8 所示。

表3 各時段配流結(jié)果 人Tab.3 Distribution result of each period

圖5 第1—8 時段各種停站方案列車開行數(shù)量Fig.5 The number of trains in various train stopping scheme during periods 1—8

在傳統(tǒng)的列車開行方案設(shè)計中，區(qū)段內(nèi)開行列車數(shù)是由最大斷面客流需求計算得到的，這在一定程度上體現(xiàn)了賣方市場的特點，使得旅客出行選擇的方案相對較少，客流量分配的優(yōu)化目標是基于Wardrop 第二原理(系統(tǒng)最優(yōu))的。而由于本次研究模型的流量分配模型是按照交通網(wǎng)絡(luò)配流Wardrop 第一原理——用戶均衡(UE)進行的，其目標是要達到相同OD 的旅客選擇各個出行方案(不同時段的不同類型列車出行)的總阻抗(廣義費用)相等且最小。當阻抗函數(shù)中列車能力參數(shù)過小時，在不允許列車超員的情形下，是不存在“相同OD 客流最小且相等的流量分配方案”的。研究的基礎(chǔ)是為了提供以人為本的優(yōu)質(zhì)服務(wù)，以用戶為中心，并綜合考慮企業(yè)運輸成本而設(shè)計的列車開行方案。

圖6 第9—16 時段各種停站方案列車開行數(shù)量Fig.6 The number of trains in various train stopping scheme during periods 9—16

圖7 第1—8 時段列車停站方案Fig.7 The train stopping scheme during periods 1—8

3 結(jié)論

高速鐵路旅客出行時段偏好性與可達性的博弈過程是一個特別的切入點，通過研究得出以下結(jié)論。

（1）旅客出行時段的選擇最終會形成一個UE平衡狀態(tài)，即旅客選擇出行的任意時段，其出行阻抗都相同。

（2）根據(jù)客流分時段制定列車開行方案不僅能最大程度滿足旅客需求，同時也能合理利用鐵路資源，避免嚴重的擁擠和運能浪費現(xiàn)象。

（3）為提高求解效率設(shè)計了專門的基于嵌套Frank-Wolfe 配流方法的啟發(fā)式算法對模型求解，最終得出優(yōu)化的列車開行方案。

研究不足之處在于只考慮了1 條高速鐵路走廊列車停站方案的優(yōu)化問題，并未涉及列車編組內(nèi)容、座位席別以及帶有換乘站的高速鐵路網(wǎng)絡(luò)列車開行方案優(yōu)化研究，這也將是下一步的研究重點。