面向OD客流的高速列車開行方案的優(yōu)化

田慧欣，王 帝，帥民偉，李 坤

(1. 天津工業(yè)大學(xué) 電氣工程與自動化學(xué)院, 天津 300387; 2.天津工業(yè)大學(xué) 電工電能新技術(shù)天津重點(diǎn)實(shí)驗(yàn)室, 天津 300387; 3.天津工業(yè)大學(xué) 經(jīng)濟(jì)與管理學(xué)院, 天津 300387)

隨著我國經(jīng)濟(jì)不斷發(fā)展，人們越來越注重出行的便捷性.高密度、高頻率成為我國高速列車的基本特點(diǎn).因此研究基于動態(tài)客流分配的高速鐵路列車開行方案的優(yōu)化，對高速鐵路客運(yùn)效率的提高和旅客滿意度的提升具有十分重要的意義.

在停站方面，國內(nèi)外學(xué)者進(jìn)行了深入的研究.Yang等[1]提出了一種新的列車?？糠桨负土熊囘\(yùn)行時刻表的組合優(yōu)化方法.Chen等[2]將列車運(yùn)行與鐵路收益和旅客出行結(jié)合起來建立多目標(biāo)模型.文獻(xiàn)[3]將收益管理與列車運(yùn)行規(guī)劃相結(jié)合建立模型.在高速鐵路的實(shí)際運(yùn)營過程中，旅客對于乘車的需求不同，會產(chǎn)生誤車以及退票、改簽等情況，表現(xiàn)為旅客客流的不確定性.文獻(xiàn)[4]考慮出行目的地(original destination，OD)旅客的需求，來進(jìn)行列車調(diào)度優(yōu)化分析.文獻(xiàn)[5]基于旅客出行時變的需求，建立了雙層規(guī)劃模型.文獻(xiàn)[6]提出了一種基于時間表的乘客分配方法.雖然國外對動態(tài)客流的研究較為成熟，但是我國鐵路具有客流量多、停靠站點(diǎn)多、路線復(fù)雜等特點(diǎn)，旅客的動態(tài)需求較國外更加明顯.同時我國高速鐵路運(yùn)營時間較短，國內(nèi)學(xué)者多只單一關(guān)注高速鐵路的開行方案，沒有很好地與動態(tài)OD客流相結(jié)合，降低了?？糠桨竷?yōu)化的靈活性，無法滿足旅客出行的多樣化.

本文在上述研究成果基礎(chǔ)上，面向最大化經(jīng)濟(jì)收益和最小化出行費(fèi)用來研究高速鐵路列車開行方案的優(yōu)化問題.以高速鐵路停站表及列車編組數(shù)量為研究對象，綜合考慮不同旅客出行的需求、高速列車運(yùn)行成本、列車運(yùn)行時間和服務(wù)水平，將列車開行方案與OD客流量相結(jié)合，并依據(jù)旅客的購票過程建立了一種基于動態(tài)客流的列車開行方案的多目標(biāo)優(yōu)化模型.對此設(shè)計了一種基于個體信息和改進(jìn)變異算子的多目標(biāo)差分(SG-MOSaDE)算法，力求滿足旅客多樣化的出行需求.

1 高速列車開行方案優(yōu)化模型

1.1 問題分析

高速鐵路網(wǎng)絡(luò)可以表示為G(V,E)，其中車站集合V=(v1,v2,…,vn)，區(qū)間集合E=(eij|i=1,2,…，n-1;j=2,3,…,n).各區(qū)間里程集合D=(deij|i=1,2,…,n-1;j=2,3,…,n).圖1為高速鐵路線路示意圖，共有10個站點(diǎn)，假定車站1為始發(fā)站，車站10為終點(diǎn)站，其余站點(diǎn)為途經(jīng)站點(diǎn).T為開行方案下運(yùn)行在該線路上列車的編號，|T|表示該線路上運(yùn)行列車的數(shù)量.根據(jù)OD客流對現(xiàn)行列車開行方案進(jìn)行優(yōu)化，包括列車編組數(shù)量、列車開行數(shù)量以及停站方案等.

1.2 列車開行方案

1.3 模型建立思路

本文的主要目的是將高速列車開行方案與動態(tài)客流相結(jié)合，通過OD客流量等數(shù)據(jù)建立模型，再進(jìn)行動態(tài)客流的分配，建立列車編組數(shù)量和列車停站方案的優(yōu)化模型，模型綜合考慮了鐵路集團(tuán)的經(jīng)濟(jì)效益和旅客的出行費(fèi)用.

1.4 模型假設(shè)

本文模型的建立與求解基于以下四點(diǎn)假設(shè):

1) 封閉性假設(shè).假設(shè)本文研究的高速鐵路運(yùn)營區(qū)段是封閉、獨(dú)立的.

2) 相似性假設(shè).假設(shè)本文涉及的旅客具有相同的時間價值.

3) 確定性假設(shè).在潛在出行OD客流確定的情況下，具有出行需求的旅客數(shù)量是變化的.

4) 滯留性假設(shè).若旅客超出定員數(shù)量，則產(chǎn)生滯留.

1.5 動態(tài)客流分配

在列車開行方案的制定中，潛在的OD客流通常是其制定的標(biāo)準(zhǔn).但是隨著列車開行方案的變化，旅客對于列車的選擇往往會產(chǎn)生不同的變化.為了能夠滿足旅客的購票心理，以及不同區(qū)間售票時間的不同和各列車出發(fā)時間的不同，設(shè)計了一種動態(tài)客流分配模型.

首先對各列車乘車區(qū)間售票時間和各列車出發(fā)時間進(jìn)行不同的設(shè)計.同時由于旅客對不同列車的心理期望不同，因此將OD客流按一定概率分配給各列車，用來模擬旅客的購票情況.之后按照列車出發(fā)時間對各列車車次中的不同區(qū)間的OD客流進(jìn)行再分配和轉(zhuǎn)換.若該列車某個區(qū)間的選擇人數(shù)過多，則滯留旅客自動分配到之后時間的列車同區(qū)間上.如果之后時間的列車在該區(qū)間均不停車或者余量為0時，則剩余旅客產(chǎn)生滯留.其中，通過基于列車在各區(qū)間運(yùn)行時長的廣義Logit概率模型，來模擬旅客在出行時對列車的初始選擇概率，具體公式為

(1)

式中:tlT0為列車區(qū)間運(yùn)行時間;KL(vi,vj)表示在區(qū)間段vi到vj旅客可以選擇列在的集合.

為了更好地說明OD再分配和轉(zhuǎn)換的過程，假定該線路共有兩輛列車，兩車定員均為600人.T=1的列車停站為1，5，10；T=2的列車停站為1，5，7，10.假定站點(diǎn)1→10的乘客人數(shù)為750人，站點(diǎn)5→10的乘客人數(shù)為600人.為了更清楚說明再分配過程，區(qū)間運(yùn)行時長不再另外計算，假定各區(qū)間的乘客在初始選擇列車時有2/3的概率選擇列車1.則列車1中站點(diǎn)1→10的人數(shù)為500人、站點(diǎn)5→10的人數(shù)為400人.假設(shè)旅客搶到票的概率相同，則列車1會導(dǎo)致站點(diǎn)1→10的滯留旅客為167人，站點(diǎn)5→10的滯留旅客為133人.此時列車2的剩余票量為150張，由于區(qū)間1→10的售票截止時間較早，故首先分配站點(diǎn)1→10的滯留旅客.最終列車2中站點(diǎn)1→10的人數(shù)為400人、站點(diǎn)5→10的人數(shù)為200人.滯留旅客為站點(diǎn)1→10的乘客17人，站點(diǎn)5→10的乘客133人.

1.6 模型決策變量

為了滿足動態(tài)客流的需求，本文關(guān)注于生成列車開行方案中的開行列車數(shù)量、列車編組數(shù)量、以及列車停站方案.因此，本文涉及的三類決策變量為

1) 停站方案:

(2)

式(2)中，i,j分別表示列車與車站的編號，且i∈T.

2) 編組數(shù)量:

(3)

3) 開行數(shù)量(單方向)：|T|，正整數(shù)變量，表示研究區(qū)段上行方向高速列車開行數(shù)量.

1.7 模型目標(biāo)函數(shù)

高速鐵路停站方案的首要目標(biāo)是最大化滿足不同旅客的需求，節(jié)省乘客出行成本的同時能夠?yàn)殍F路系統(tǒng)帶來更大的經(jīng)濟(jì)效益.因此，高速鐵路開行方案的制定應(yīng)綜合考慮經(jīng)濟(jì)效益和出行費(fèi)用兩個方面.

1) 運(yùn)營部門經(jīng)濟(jì)效益最大.本文以高速列車的運(yùn)行費(fèi)用和停站服務(wù)費(fèi)用作為運(yùn)營成本，建立目標(biāo)函數(shù):

高速列車總票價收入為

(4)

高速列車停站服務(wù)費(fèi)用為

(5)

高速列車單位運(yùn)營成本費(fèi)用為

(6)

式中:C2表示高速列車單位里程的運(yùn)營成本;Di表示列車i的運(yùn)營距離.

綜上所述，運(yùn)營高速列車的經(jīng)濟(jì)效益可以表示為Z=Y1-Y2-Y3:

(7)

2) 旅客出行成本最小.本文以旅客出行的時間花費(fèi)作為旅客的出行成本，建立目標(biāo)函數(shù)如下:

出行的時間消耗為

(8)

式中:A表示列車的平均行駛速度;tk表示?？繒r間;td表示列車啟停時間.

在優(yōu)化過程中，由于新生成的列車開行方案可能會產(chǎn)生滯留旅客.為了使滯留旅客最少，故使滯留旅客所帶來的時間損耗具有一個較大的懲罰因子.因此，旅客出行成本最小的目標(biāo)函數(shù)為

(9)

1.8 模型約束條件

1) “0-1”變量約束.

用“0-1”變量表示列車在車站是否?？亢土熊嚨木幗M數(shù)量.

(10)

mi={0,1}.

(11)

2) 列車編組數(shù)量對應(yīng)定員人數(shù)約束.

(12)

3) 各區(qū)間載客量不超過定員人數(shù).

(13)

4) 滿足一定的上座率.

(14)

式中:θd為上座率的下限;θu為上座率的上限.

5) 終到站約束.所有列車在終點(diǎn)站停車，由于本文的研究區(qū)段是多起點(diǎn)，所以沒有嚴(yán)格的始發(fā)站停車約束.

(15)

綜上所述，得到高速列車開行方案優(yōu)化模型，其中目標(biāo)函數(shù)為式(7)和式(9)，約束為式(10)～式(15).

2 改進(jìn)差分進(jìn)化算法設(shè)計

差分進(jìn)化(differential evolution, DE)算法能夠很好地適應(yīng)多目標(biāo)優(yōu)化模型的求解.但是傳統(tǒng)DE算法中也存在很多不足，如對于復(fù)雜模型求解速度慢、精度較低等.而且通常來說，傳統(tǒng)DE算法不用于求解二進(jìn)制變量，并不適用于本文模型.因此本文對傳統(tǒng)DE算法作了改進(jìn).

2.1 編碼設(shè)計

由于傳統(tǒng)DE算法一般用于實(shí)數(shù)的優(yōu)化，但在本文中，編碼方式均為0-1方式.因此，在進(jìn)行本文模型求解之前，需要對差分進(jìn)化中的變異操作進(jìn)行改變，使其適用于0-1變量的求解.

對縮放因子F進(jìn)行設(shè)計，將F轉(zhuǎn)化為0-1變量:

(16)

此時，關(guān)于變異操作中基向量、縮放因子F、差分向量均為0-1變量，為了使變異方法適應(yīng)0-1變量的操作，本文使用一種異或方式進(jìn)行變異操作.公式為

(17)

式中:“∧”為異或運(yùn)算；“&”為與運(yùn)算.

2.2 算法改進(jìn)

首先，傳統(tǒng)DE算法中的種群大小一般是固定的，這意味著每個解決方案的演化過程所攜帶的有用信息不能被保持和用來指導(dǎo)其演化，而這一信息在粒子群優(yōu)化中被證明是非常有用的[7].其次，傳統(tǒng)DE算法的自適應(yīng)策略已經(jīng)投入了大量的工作，但沒有考慮目標(biāo)解的質(zhì)量.此外，DE算法的核心是變異操作，通常情況下變異操作中的父代個體是隨機(jī)選取的，因此，對于當(dāng)前種群中的較優(yōu)秀個體會有一定概率沒有被選上參與變異，從而使進(jìn)化沒有向最優(yōu)方向進(jìn)行.基于上述不足，本文在文獻(xiàn)[8-9]的基礎(chǔ)上提出了一種改進(jìn)差分進(jìn)化算法，即帶有個體信息和改進(jìn)變異操作的改進(jìn)差分進(jìn)化(SG-MOSaDE)算法，其主要特點(diǎn)如下.

1) 本文采用一組最大具體NP個解的個體信息，而不是傳統(tǒng)算法中固定的NP個解集.每次隨機(jī)選擇個體信息中某一個解進(jìn)行變異和交叉操作，若新生成的子代個體能夠不被此解支配，則移除子代個體所有支配的解，并將此子代個體加入個體信息中，生成新的個體信息，并在此個體信息上重新進(jìn)行選擇，循環(huán)NP次，當(dāng)達(dá)到最大數(shù)量后，利用NSGA-II進(jìn)行選擇前NP個解.

2) 控制變異參數(shù)F隨著生成量的增加而減小，從而使每個解的搜索行為能夠向最優(yōu)化靠近.交叉參數(shù)Cr的選擇則設(shè)計一個參數(shù)列表，此列表個數(shù)最多具有l(wèi)k個.它的前l(fā)k個確定方法與MOSaDE算法[10]中使用的方法相同.為了保證Cr參數(shù)更加有效，采用先進(jìn)先出的原則，只選擇更新成功時進(jìn)行Cr列表的更新.

3) 變異操作在父代的選擇上，綜合考慮利用不同個體適應(yīng)度和搜索空間的信息.對于所處不同空間的個體具有不同的能力.對較優(yōu)適應(yīng)度的解希望增強(qiáng)它跳出局部最優(yōu)區(qū)域的能力；相反適應(yīng)度較差的解希望提高它的收斂速度，這樣它就可以更快地向最優(yōu)解進(jìn)化.變異操作的公式為

(18)

首先，依照個體適應(yīng)度將種群中的個體進(jìn)行從優(yōu)到劣的排序，并分為三組.若選擇個體不處于適應(yīng)度最優(yōu)解的組別，即R(Xi)>1，則依照排名越靠前越容易被選中的方法，來選擇適應(yīng)度最優(yōu)組別中的解Xrbest作為差分向量終點(diǎn)，差分向量的起點(diǎn)Xr2，則在適應(yīng)度最差的第三組中隨機(jī)選擇.否則若R(Xi)<1，則在適應(yīng)度較優(yōu)的第二組內(nèi)依照排名來選擇差分向量的終點(diǎn)Xr1.

SG-MOSaDE算法為

1)初始化種群X1,g,X2,g,…,XNP,g，令g=0,Fmean=1.0,andCr,mean=0.5.

2)令Pi,g={Xi,g},i=1,2,…,NP.

3)While迭代次數(shù)未達(dá)到：

4)參數(shù)調(diào)整:設(shè)g

5)利用NSGA-II的快速非支配排序方法對所有Pi,g進(jìn)行解排序，并進(jìn)行個體信息的截斷.

6)fori:= 1 toNPdo

7) 目標(biāo)解選擇:從個體信息Pi,g中隨機(jī)選擇一個解作為目標(biāo)解，記為Xi,g=(xi,1,g,…,xi,D,g).

8) 變異操作：根據(jù)Xi,g從其他個體信息中選擇解，生成F=N(Fmean,0.1)，根據(jù)式(15)生成擾動向量Vi,g=(v1,g,…,vD,g).

9) 交叉操作：取所選突變算子的Cr均值，設(shè)Cr=N(Cr，mean，0.1)，最終生成子代Ui,g=(u1,g,…,uD,g)，其中，

(19)

10) 選擇操作:如果Ui,g不受Xi,g支配，則使用Ui,g更新Pi,g，并將Cr的值添加到列表lk,Cr中(如果lk,Cr超過其最大值，則刪除其中第一項(xiàng)).

11) end for

12) 令g=g+1

13)end while

14)輸出個體信息.

2.3 優(yōu)化設(shè)計

為了能夠使算法更早地尋找到最優(yōu)解，需要使初始種群具有較高的質(zhì)量.故本文采用一種啟發(fā)式來生成初始種群，使其能夠依據(jù)客流量來確定停站次數(shù).

1) 站點(diǎn)權(quán)重系數(shù).根據(jù)每日各站點(diǎn)客流量與所有站點(diǎn)的客流量的比值當(dāng)作各個站點(diǎn)的權(quán)重系數(shù)ω.

2) 停靠次數(shù)衰減比率.不同的停站次數(shù)產(chǎn)生不同的衰減比例λ.

3) 各站點(diǎn)已有?？看螖?shù).記錄各個站點(diǎn)已有列車停站次數(shù)η，來調(diào)整各個站點(diǎn)的停站的概率.

綜上所述，對于列車i各站點(diǎn)j停靠的概率Pij可以表示為

(20)

3 實(shí)驗(yàn)設(shè)計與分析

3.1 算法性能測試

為了驗(yàn)證本文提出的SG-MOSaDE算法的性能，本文采用4個雙目標(biāo)標(biāo)準(zhǔn)測試函數(shù)ZDT1，ZDT2，ZDT3和ZDT6對算法的性能進(jìn)行測試.同時采用反向世代距離(inverted general distance, IGD)指標(biāo)從收斂性、多樣性2個角度對算法進(jìn)行評價.

(21)

式中:P表示真實(shí)Pareto前沿上均勻分布的點(diǎn)的集合；P*為計算得到的一個近似Pareto前沿的解集；min(dis(x,P))表示x與P的最小歐氏距離；|P*|表示優(yōu)化得到的非劣解的個數(shù).IGD指標(biāo)體現(xiàn)的是經(jīng)過算法計算獲得的近似Pareto最優(yōu)解與真實(shí)Pareto最優(yōu)解之間的距離指標(biāo).且該指標(biāo)數(shù)值越小，表明計算得到的Pareto前沿的解集與真實(shí)解越相似，算法也具有更好的收斂性和多樣性.

為了評價所提出的SG-MOSaDE算法的有效性，本文將所提出的SG-MOSaDE算法與NSGA-II算法[11]在相同的種群數(shù)量和迭代次數(shù)下進(jìn)行比較.將各測試函數(shù)的20次獨(dú)立實(shí)驗(yàn)的平均值和標(biāo)準(zhǔn)差作為最終結(jié)果進(jìn)行評價.種群規(guī)模NP設(shè)為300，最大迭代次數(shù)Tmax設(shè)為250.比較結(jié)果如表1所示，實(shí)驗(yàn)結(jié)果表明，所提出的SG-MOSaDE算法在IGD指標(biāo)均明顯優(yōu)于NSGA-II算法，具有較好的收斂性和多樣性.最后，SG-MOSaDE算法Pareto前沿對比結(jié)果如圖2～圖5所示，可以看出，SG-MOSaDE算法能夠找到Pareto最優(yōu)解.

表1 不同優(yōu)化算法的IGD對比

3.2 高速鐵路開行方案優(yōu)化分析

3.2.1 算例OD數(shù)據(jù)

本文選擇廣州市某線路2018年1月1日OD客流量為例，通過本文模型確定高速列車最佳開行方案，包括高速列車編組數(shù)量和停站方案，以此驗(yàn)證本文模型的正確性和可行性.此線路共有15個站點(diǎn)，其中站點(diǎn)1與站點(diǎn)2均能夠當(dāng)作列車開行的起點(diǎn).其中站點(diǎn)3,10,12,13,共4個站點(diǎn)無客流，不具備高速列車停站資格.故其運(yùn)營線路如圖6所示，“●”表示列車停靠點(diǎn)，“〇”表示列車不?？奎c(diǎn).本線路該日客流總數(shù)是56 660人，各列車站點(diǎn)的當(dāng)天客流量可見圖7，由圖可得，站點(diǎn)2,5,8,15的客流量較高.

當(dāng)日各區(qū)段OD客流量如表2所示.客票率、列車運(yùn)營成本以及車站服務(wù)費(fèi)用等數(shù)據(jù)可見文獻(xiàn)[12].另外，令列車的停車時間和起、停附加時間均為5 min.設(shè)置高鐵站點(diǎn)的?？克p比率λ為0.7.乘客對于時間花費(fèi)的價值設(shè)置為0.1 元/min.

3.2.2 開行方案的優(yōu)化

根據(jù)本文已經(jīng)建立的列車開行方案優(yōu)化模型和改進(jìn)設(shè)計算法，將表2的OD客流數(shù)據(jù)代入，同時，利用初始化種群的啟發(fā)式算法來進(jìn)行初始解的生成，樣本總數(shù)為30，迭代次數(shù)為1 000.經(jīng)優(yōu)化求解后的停站方案如圖8所示，其中左側(cè)0-1變量代表列車編組數(shù)量.

表2 各區(qū)段OD客流量

3.2.3 優(yōu)化方案分析

將本文建立的高速列車開行方案與實(shí)際列車開行方案進(jìn)行對比分析，結(jié)果如下所示:

1) 車站服務(wù)頻率.車站服務(wù)頻率對比如圖9所示.現(xiàn)行高速列車運(yùn)行方案中，停站方案與客流沒有很好地結(jié)合起來，導(dǎo)致列車運(yùn)能過剩同時不能完全滿足旅客出行需求.因此根據(jù)客流特點(diǎn)制定停站方案，將有效提升列車的上座率同時使旅客出行需求得到充分滿足.由圖9可得，本文方案中高客流站點(diǎn)的服務(wù)頻率會有大幅下降，而低客流節(jié)點(diǎn)的服務(wù)頻率有了小幅上升.因此采用優(yōu)化后的高速列車停站方案能夠有效降低運(yùn)營成本，同時更好地滿足旅客的出行需求.

2) 其余指標(biāo)統(tǒng)計.鐵路部門經(jīng)濟(jì)收益和旅客出行花費(fèi)等指標(biāo)統(tǒng)計見表3.由表3可知，本文的開行方案在不同指標(biāo)上均優(yōu)于實(shí)際方案.其中高速列車經(jīng)濟(jì)收益增加了1.74×105元，旅客出行總花費(fèi)降低了6.111×105元,在提高經(jīng)濟(jì)效益的同時，降低了旅客出行的花費(fèi).列車總停站次數(shù)減少了16次，平均停站次數(shù)減少了0.57站，同時滯留旅客減少了421人，不僅節(jié)約了停站成本而且更大程度上滿足了旅客的出行需求.綜上本文提供了一種基于客流的不同指標(biāo)都優(yōu)于現(xiàn)行方案的列車停站方案.

表3 列車開行方案評價指標(biāo)

4 結(jié) 語

本文在已有研究成果的基礎(chǔ)上，建立了一種基于動態(tài)客流的列車開行方案的多目標(biāo)優(yōu)化模型.并提出了一種改進(jìn)差分進(jìn)化算法來進(jìn)行模型的求解.研究結(jié)果表明，優(yōu)化后的開行方案不僅最大化滿足了旅客出行需求，而且在提高鐵路部門經(jīng)濟(jì)收益的同時降低了旅客的出行花費(fèi),并且優(yōu)化后的列車總停站次數(shù)較原來有所下降，停站方案更加均衡.