蔡 蕓,王 濤,樊昊煜,司曉鑫,黃志鵬
(1.中國(guó)鐵路蘭州局集團(tuán)有限公司 財(cái)務(wù)部,甘肅 蘭州 730000;2.中國(guó)鐵路蘭州局集團(tuán)有限公司 華澳鐵路綜合工程公司,甘肅 蘭州 730000;3.蘭州交通大學(xué) 交通運(yùn)輸學(xué)院,甘肅 蘭州 730070;4.中國(guó)鐵路蘭州局集團(tuán)有限公司 蘭州車(chē)務(wù)段,甘肅 蘭州 730050)
高速鐵路的發(fā)展使得旅客出行不再局限于到達(dá)目的地,對(duì)于出行時(shí)段也有了更多的關(guān)注,旅客會(huì)根據(jù)原有的經(jīng)驗(yàn)習(xí)慣與出行目的來(lái)選擇最理想的出行時(shí)段。在高速鐵路一日運(yùn)營(yíng)時(shí)段內(nèi),旅客出行需求表現(xiàn)出明顯不均衡的時(shí)段偏好。此外,鐵路部門(mén)在組織運(yùn)營(yíng)時(shí)也應(yīng)當(dāng)制定不同時(shí)段的列車(chē)停站方案。
在以往研究中,牛豐等[1]根據(jù)旅客出行目的不同確定了旅客需求置信度,以停站總時(shí)間最小為目標(biāo)建立了高速鐵路列車(chē)停站方案優(yōu)化模型;Shang等[2]在時(shí)空狀態(tài)三維網(wǎng)絡(luò)中說(shuō)明不同車(chē)站接收到的列車(chē)座位容量和旅客候車(chē)人數(shù)的信息不同,因此基于容量限制下優(yōu)化列車(chē)停站方案,合理安排所有旅客乘車(chē);Qi 等[3]結(jié)合客流分布特點(diǎn)對(duì)列車(chē)運(yùn)營(yíng)區(qū)段和停站方案進(jìn)行了綜合優(yōu)化;Niu 等[4]考慮時(shí)變需求以及最大限度減少旅客等待時(shí)間,優(yōu)化停站方案;許若曦等[5]基于減少列車(chē)中小站停站次數(shù),增加相鄰大站間站站停列車(chē)等策略來(lái)優(yōu)化列車(chē)停站方案;黃志鵬[6]證明了基于旅行時(shí)間的旅客滿(mǎn)意度與不同停站方案的列車(chē)開(kāi)行次序密切相關(guān);高明瑤等[7]建立多目標(biāo)混合0-1 規(guī)劃模型,運(yùn)用理想點(diǎn)法和遺傳算法求得列車(chē)停站方案優(yōu)化解;Yue 等[8]使用拉格朗日松弛法將數(shù)學(xué)模型轉(zhuǎn)換為簡(jiǎn)單的線(xiàn)性規(guī)劃問(wèn)題,然后基于列生成算法通過(guò)迭代過(guò)程更新受限主問(wèn)題(RMP)和子問(wèn)題來(lái)尋找最佳解決方案;張小炳等[9]結(jié)合優(yōu)化停站方案的模型特點(diǎn),設(shè)計(jì)了具有自適應(yīng)性的遺傳退火算法,控制全局的尋優(yōu)方向,模擬退火的鄰域搜索策略提高算法的鄰域搜索能力,最終快速搜索高質(zhì)量的解;Dong 等[10]用擴(kuò)展的自適應(yīng)大鄰域搜索元啟發(fā)式方法對(duì)通勤鐵路列車(chē)停站計(jì)劃和時(shí)間表整合優(yōu)化。
為此,基于旅客對(duì)出行時(shí)段的偏好建立一個(gè)雙層規(guī)劃模型來(lái)優(yōu)化各個(gè)時(shí)段某一高速鐵路不同停站方案列車(chē)的開(kāi)行數(shù)量,并將客流分配在各個(gè)出行時(shí)段上,使旅客出行需求與列車(chē)停站方案相互影響。研究在既有文獻(xiàn)基礎(chǔ)上做了以下創(chuàng)新。首先,同時(shí)考慮旅客的出行時(shí)段偏好與列車(chē)停站方案,并將多OD 客流需求分配在各個(gè)出行時(shí)段上;其次是不同于以往周期化的停站方案優(yōu)化[11],研究制定了按照出行時(shí)段分別優(yōu)化的停站方案。
(1)旅客出行時(shí)段選擇博弈。高速鐵路全天的發(fā)車(chē)時(shí)間通常在6 : 00—22 : 00,以1 h 為一個(gè)時(shí)段,將6 : 00—6 : 59 標(biāo)記為時(shí)段1,按照時(shí)間順序依次編號(hào)2,3,…,16,共16 個(gè)時(shí)段。不同時(shí)段對(duì)旅客的吸引度不同,同時(shí),不同時(shí)段的可達(dá)度也不同。旅客對(duì)各個(gè)出行時(shí)段的偏好性,一方面表現(xiàn)為不同時(shí)段對(duì)旅客的吸引度具有很大差異,這種差異是客觀(guān)存在的,受到多種客觀(guān)因素的影響,如通勤客流占全部客流比重較大的車(chē)站,對(duì)旅客吸引度最高的時(shí)段為早晚高峰時(shí)段;又如旅客總是期望在城市公交方便的白天時(shí)段出行等,都是影響旅客選擇出行時(shí)段的客觀(guān)因素。對(duì)所有車(chē)站以往的客流數(shù)據(jù)統(tǒng)計(jì)分析,按照平均時(shí)段客流比例得出每個(gè)車(chē)站的時(shí)段吸引度。另一方面,旅客對(duì)各個(gè)出行時(shí)段的偏好性,還表現(xiàn)為旅客對(duì)不同時(shí)段可達(dá)度的選擇。當(dāng)某個(gè)出行時(shí)段的吸引度較大時(shí),大量的旅客均期望在這個(gè)時(shí)段出行,這時(shí)這個(gè)時(shí)段的可達(dá)度會(huì)大大降低。或者旅客為了確保能夠在這個(gè)時(shí)段出行,其必須提前很早購(gòu)票,使得旅客的出行靈活性降低。因此,旅客會(huì)根據(jù)出行經(jīng)驗(yàn),在時(shí)段吸引度和可達(dá)度之間進(jìn)行博弈。博弈的結(jié)果是部分旅客偏好于吸引度,降低了可達(dá)度;部分旅客偏好于可達(dá)度,選擇吸引度較低的時(shí)段出行。最終形成一個(gè)UE 平衡狀態(tài),即旅客選擇出行的任意時(shí)段,其出行阻抗都是一樣的。
(2)列車(chē)停站方案選擇博弈。鐵路運(yùn)營(yíng)部門(mén)在制定列車(chē)停站方案時(shí),要考慮2 個(gè)方面的因素,一是了解旅客對(duì)出行時(shí)段的偏好,二是降低運(yùn)營(yíng)成本。研究以出行時(shí)段為單元,依據(jù)旅客對(duì)時(shí)段的偏好性,分別制定各個(gè)出行時(shí)段的列車(chē)停站方案及同種停站方案的列車(chē)開(kāi)行數(shù)量,最大限度地滿(mǎn)足差異化的時(shí)段出行需求。同時(shí)列車(chē)開(kāi)行數(shù)量和停站次數(shù)越多,其成本也越大。因此,在滿(mǎn)足旅客出行需求時(shí),也要考慮運(yùn)營(yíng)成本問(wèn)題。將符合停站約束的所有停站方案作為備選方案,各個(gè)時(shí)段列車(chē)停站方案均是備選方案中的一種或多種。
(3)優(yōu)化思路。在輸入端確定始發(fā)站至終到站間單方向的OD 客流需求、列車(chē)停站方案?jìng)溥x集和各車(chē)站的不同時(shí)段的旅客吸引度;輸出端為各時(shí)段平衡配流結(jié)果、各時(shí)段列車(chē)停站方案。在雙層規(guī)劃模型中,下層的配流結(jié)果會(huì)影響上層的列車(chē)停站方案及列車(chē)開(kāi)行數(shù)量;上層模型確定的停站方案會(huì)影響旅客的出行時(shí)段選擇,進(jìn)而影響各時(shí)段的配流結(jié)果。優(yōu)化流程如圖1 所示。
圖1 優(yōu)化流程Fig.1 Optimized flow scheme
(1)符號(hào)約定。①集合和下標(biāo)。S為車(chē)站集合;H為列車(chē)停站方案集合;T為出行時(shí)段集合;i,j用來(lái)標(biāo)識(shí)車(chē)站,i,j∈S;h用來(lái)標(biāo)識(shí)列車(chē)停站方案,h∈H;t用來(lái)標(biāo)識(shí)出行時(shí)段,t∈T。②輸入?yún)?shù)。qij為車(chē)站i→j的客流需求量,人;為車(chē)站i在第t時(shí)段無(wú)流量加載時(shí)的時(shí)段阻抗;為在第t時(shí)段能夠分配給車(chē)站i的最大客票數(shù),張;Rh為第h種停站方案列車(chē)的開(kāi)行成本,元;Ft為第t時(shí)段,始發(fā)站的發(fā)車(chē)能力,列;為第h種停站方案的列車(chē)分配給車(chē)站i的票額比例;α為調(diào)節(jié)系數(shù);Y為列車(chē)定員數(shù),人。③決策和輔助變量。為車(chē)站i→j的客流被分配到第t個(gè)時(shí)段的客流量,人;為0-1 變量,代表第t時(shí)段第h種停站方案列車(chē)是否開(kāi)行;為下層決策中在車(chē)站i上車(chē)的客流被分配在第t時(shí)段的客流量,人;為上層決策中第t時(shí)段第h種停站方案列車(chē)的開(kāi)行數(shù)量,列。
(2)上層規(guī)劃。優(yōu)化目標(biāo)為鐵路運(yùn)營(yíng)成本最小化,目標(biāo)函數(shù)如公式(1)所示。
約束條件包括發(fā)車(chē)能力約束和各時(shí)段供需平衡約束,其中發(fā)車(chē)能力約束為
各時(shí)段供需平衡約束為
式中:Y·表示第h類(lèi)停站方案列車(chē)的全部席位數(shù)量,個(gè);Y··表示第h類(lèi)列車(chē)提供給車(chē)站i的客票數(shù),張。
(3)下層規(guī)劃。①阻抗函數(shù)及客流均衡條件。旅客對(duì)各個(gè)出行時(shí)段的偏好性受到時(shí)段吸引度和時(shí)段可達(dá)度的影響。時(shí)段吸引度是客觀(guān)存在,可達(dá)度與時(shí)段上加載的流量有關(guān)。據(jù)此構(gòu)造各車(chē)站不同出行時(shí)段的阻抗函數(shù),如公式(5)所示。
其中的取值與時(shí)段吸引度負(fù)相關(guān),時(shí)段吸引度越高,取值越小。
對(duì)于在車(chē)站i上車(chē)的旅客,當(dāng)時(shí)段t有流量加載時(shí),即> 0,出行阻抗為最小;當(dāng)時(shí)段t無(wú)流量加載時(shí),即= 0,出行阻抗大于均衡狀態(tài)時(shí)的阻抗。由于不同車(chē)站的客流狀況不同,因此用戶(hù)均衡(User Equilibrium,UE)條件也不同,如公式(6)所示,fimin表示車(chē)站i的旅客最小出行阻抗。
其中,公式(8)滿(mǎn)足了客流守恒,即客流需求被分配到了阻抗最小的各個(gè)時(shí)段;公式(9)表示車(chē)站i→j的客流被分配在第t時(shí)段流量為正值;公式(10)表示任意時(shí)段t的流量由多個(gè)OD 客流構(gòu)成。
雙層規(guī)劃問(wèn)題被公認(rèn)為是極其困難求解的優(yōu)化問(wèn)題之一,采用遺傳算法對(duì)上層規(guī)劃求解,同時(shí)運(yùn)用Frank-Wolfe 算法求解下層規(guī)劃。
(1)染色體編碼。采用0-1 編碼和整數(shù)編碼2種編碼方法[12]求解模型。其中0-1 編碼確定各時(shí)段各種停站方案的列車(chē)是否開(kāi)行,即“1”表示開(kāi),“0”表示不開(kāi);整數(shù)編碼確定各時(shí)段各種停站方案的列車(chē)的開(kāi)行數(shù)量。2 種編碼的染色體均由16 個(gè)基因片段組成,分別表示各個(gè)時(shí)段t上不同停站方案和開(kāi)行數(shù)量。染色體示意圖如圖2 所示。
圖2 染色體示意圖Fig.2 Chromosome schematics
(2)算法流程。采用基于嵌套Frank-Wolfe 算法的遺傳算法對(duì)模型進(jìn)行求解。其中,上層決策變量用遺傳算子編碼,下層規(guī)劃用Frank-Wolfe 算法求解。算法的具體實(shí)現(xiàn)步驟如下。
步驟 1:初始化。按照上述染色體編碼規(guī)則和約束條件(8),隨機(jī)生成規(guī)模為popsize的初始停站方案()的可行解種群;設(shè)置上層規(guī)劃最優(yōu)目標(biāo)E*= 0;設(shè)置最優(yōu)停站方案集W*為零向量;迭代次數(shù)b= 0。
步驟 2:檢查和判斷。依次檢查各染色體在時(shí)段t上第h類(lèi)停站方案是否在車(chē)站i和j均停車(chē),如果滿(mǎn)足,將時(shí)段t納入i→j的客流出行時(shí)段,停止檢查;如果不滿(mǎn)足,繼續(xù)檢查,直到時(shí)段t上所有停站方案均檢查完畢。完成i→j客流可選擇出行時(shí)段的集合,轉(zhuǎn)下一步。
步驟 3:用戶(hù)平衡配流。對(duì)于當(dāng)前開(kāi)行方案W(i),用Frank-Wolfe 算法求解下層規(guī)劃,得到符合Wardrop User Equilibrium 準(zhǔn)則的,并記錄所有可行解對(duì)應(yīng)的平衡配流結(jié)果和阻抗值。
步驟4:整數(shù)編碼。對(duì)步驟1 產(chǎn)生的0-1 編碼染色體中“1”的基因位置隨機(jī)賦1 個(gè)整數(shù)值,并滿(mǎn)足公式(8)、公式(10)約束。
步驟 5:遺傳操作。對(duì)列車(chē)開(kāi)行數(shù)量()的初始種群進(jìn)行選擇、交叉和變異操作,搜尋當(dāng)前種群中適應(yīng)度最高的可行解W(b),并更新最優(yōu)停站方案集W*=W(b);迭代次數(shù)b=b+ 1。
步驟6:終止檢驗(yàn)。如果迭代次數(shù)b大于迭代上限Ge,輸出最優(yōu)解W*,否則,轉(zhuǎn)步驟5。
圖3 西蘭高速鐵路車(chē)站示意圖Fig.3 Stations on Xi’an-Lanzhou high speed railway
(1)線(xiàn)路和車(chē)站。以西蘭高速鐵路(西安北—蘭州西)為例。為了計(jì)算方便,將蘭州西站編號(hào)為1,按照上行方向依次編號(hào),西蘭高速鐵路車(chē)站示意圖如圖3 所示。
(2)OD 客流需求。為了全面了解旅客出行從出發(fā)到終到的過(guò)程,旅客起訖點(diǎn)的OD 客流需求是研究列車(chē)開(kāi)行方案的基礎(chǔ),它反映了最直接的客流需求。西蘭高速鐵路OD 客流需求如表1 所示。
(3)列車(chē)停站方案?jìng)溥x集。西蘭高速鐵路共設(shè)車(chē)站10 座,其中蘭州西、西安北為始發(fā)、終到車(chē)站,必停車(chē)。另外在4 個(gè)區(qū)域中心所在的定西北站、天水南站、寶雞南站、咸陽(yáng)秦都站必停車(chē)。在其他車(chē)站設(shè)置停車(chē)次數(shù)上限為2 次,則全部停站方案為列車(chē)停站方案如圖4 所示。
其中,每種停站方案的開(kāi)行成本為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è)置。各車(chē)站在不同時(shí)段無(wú)客流加載條件下的時(shí)段阻抗如表2 所示。其中,距離始發(fā)站較遠(yuǎn)的車(chē)站,每日首列車(chē)到達(dá)該站時(shí)的時(shí)段會(huì)相應(yīng)延遲,如車(chē)站3 到9,用M表示該時(shí)段出行阻抗非常大,不可能有流量加載。
(5)其他參數(shù)設(shè)置。采用16 輛編組CRH2 動(dòng)車(chē)組列車(chē),列車(chē)定員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 列車(chē)停站方案Fig.4 Train stopping scheme
表2 各車(chē)站在不同時(shí)段無(wú)客流加載條件下的時(shí)段阻抗Tab.2 Impedance without passenger flow loading in each period
(1)下層配流結(jié)果。通過(guò)軟件編程,對(duì)該算例進(jìn)行求解。下層規(guī)劃計(jì)算數(shù)據(jù)各時(shí)段配流結(jié)果如表3 所示。各上車(chē)站的OD 客流被分配在各個(gè)時(shí)段上出行,各時(shí)段客流具有明顯的波動(dòng)性。
(2)上層開(kāi)行方案優(yōu)化結(jié)果。通過(guò)下層規(guī)劃的配流結(jié)果和上層規(guī)劃開(kāi)行方案的迭代,最終經(jīng)過(guò)50 代的進(jìn)化篩選,得到16 個(gè)時(shí)段11 種列車(chē)的分布情況,第1—8 時(shí)段各種停站方案列車(chē)開(kāi)行數(shù)量如圖5 所示,第9—16 時(shí)段各種停站方案列車(chē)開(kāi)行數(shù)量如圖6 所示。各類(lèi)列車(chē)均有開(kāi)行,能夠服務(wù)沿途所有車(chē)站的旅客乘降。但是各類(lèi)列車(chē)的分布不均勻,這與不同OD 客流量大小有關(guān)。最終優(yōu)化的列車(chē)停站方案,第1—8 時(shí)段列車(chē)停站方案如圖7 所示,第9—16 時(shí)段列車(chē)停站方案如圖8 所示。
表3 各時(shí)段配流結(jié)果 人Tab.3 Distribution result of each period
圖5 第1—8 時(shí)段各種停站方案列車(chē)開(kāi)行數(shù)量Fig.5 The number of trains in various train stopping scheme during periods 1—8
在傳統(tǒng)的列車(chē)開(kāi)行方案設(shè)計(jì)中,區(qū)段內(nèi)開(kāi)行列車(chē)數(shù)是由最大斷面客流需求計(jì)算得到的,這在一定程度上體現(xiàn)了賣(mài)方市場(chǎng)的特點(diǎn),使得旅客出行選擇的方案相對(duì)較少,客流量分配的優(yōu)化目標(biāo)是基于Wardrop 第二原理(系統(tǒng)最優(yōu))的。而由于本次研究模型的流量分配模型是按照交通網(wǎng)絡(luò)配流Wardrop 第一原理——用戶(hù)均衡(UE)進(jìn)行的,其目標(biāo)是要達(dá)到相同OD 的旅客選擇各個(gè)出行方案(不同時(shí)段的不同類(lèi)型列車(chē)出行)的總阻抗(廣義費(fèi)用)相等且最小。當(dāng)阻抗函數(shù)中列車(chē)能力參數(shù)過(guò)小時(shí),在不允許列車(chē)超員的情形下,是不存在“相同OD 客流最小且相等的流量分配方案”的。研究的基礎(chǔ)是為了提供以人為本的優(yōu)質(zhì)服務(wù),以用戶(hù)為中心,并綜合考慮企業(yè)運(yùn)輸成本而設(shè)計(jì)的列車(chē)開(kāi)行方案。
圖6 第9—16 時(shí)段各種停站方案列車(chē)開(kāi)行數(shù)量Fig.6 The number of trains in various train stopping scheme during periods 9—16
圖7 第1—8 時(shí)段列車(chē)停站方案Fig.7 The train stopping scheme during periods 1—8
高速鐵路旅客出行時(shí)段偏好性與可達(dá)性的博弈過(guò)程是一個(gè)特別的切入點(diǎn),通過(guò)研究得出以下結(jié)論。
(1)旅客出行時(shí)段的選擇最終會(huì)形成一個(gè)UE平衡狀態(tài),即旅客選擇出行的任意時(shí)段,其出行阻抗都相同。
(2)根據(jù)客流分時(shí)段制定列車(chē)開(kāi)行方案不僅能最大程度滿(mǎn)足旅客需求,同時(shí)也能合理利用鐵路資源,避免嚴(yán)重的擁擠和運(yùn)能浪費(fèi)現(xiàn)象。
(3)為提高求解效率設(shè)計(jì)了專(zhuān)門(mén)的基于嵌套Frank-Wolfe 配流方法的啟發(fā)式算法對(duì)模型求解,最終得出優(yōu)化的列車(chē)開(kāi)行方案。
研究不足之處在于只考慮了1 條高速鐵路走廊列車(chē)停站方案的優(yōu)化問(wèn)題,并未涉及列車(chē)編組內(nèi)容、座位席別以及帶有換乘站的高速鐵路網(wǎng)絡(luò)列車(chē)開(kāi)行方案優(yōu)化研究,這也將是下一步的研究重點(diǎn)。