劉蘭芬 楊信豐

（蘭州交通大學(xué)交通運(yùn)輸學(xué)院 蘭州 730070）

0 引 言

地鐵作為大城市公共交通的重要組成部分，對緩解城市交通擁堵，促進(jìn)城市交通的可持續(xù)發(fā)展有重要作用.地鐵客流在1d內(nèi)隨著人們的生活習(xí)慣和工作需要而變化，工作日的出行規(guī)律和休息日的出行規(guī)律也有著明顯的不同.由于地鐵客流具有動態(tài)性和時變性特點(diǎn)，就需要根據(jù)實(shí)際情況調(diào)整行車間隔時間.發(fā)車間隔的確定是地鐵運(yùn)營中十分重要的組成部分，對于吸引客流和提高服務(wù)水平都具有十分重要的意義.

部分學(xué)者對行車間隔時間進(jìn)行了相關(guān)研究.林震等［1］對影響軌道交通發(fā)車間距的因素進(jìn)行了分析，以運(yùn)營者效益最大化與社會福利最大化為目標(biāo)函數(shù)，建立了發(fā)車間距的優(yōu)化模型.洪玲等［2］分析了不同的行車間隔對實(shí)際客流需求以及系統(tǒng)運(yùn)輸能力的影響，給出變化趨勢曲線，對行車間隔進(jìn)行優(yōu)化調(diào)整.F.J.Vázquez－Abad等［3］建立了乘客等待時間的優(yōu)化模型，使用離散仿真模型對原模型進(jìn)行簡化，通過計(jì)算尋求最優(yōu)的服務(wù)水平.嚴(yán)波［4］提出了以乘客滿意度和企業(yè)滿意度加權(quán)平均值最大為總體目標(biāo)的行車間隔時間優(yōu)化模型，并在一條具體的實(shí)例線路上演示了計(jì)算和分析的過程.徐育鋒等［5］根據(jù)客流在時間上變化的規(guī)律，建立以乘客的等車費(fèi)用、車內(nèi)費(fèi)用和運(yùn)營企業(yè)變動費(fèi)用總和最小為目標(biāo)的軌道線路行車間隔非線性優(yōu)化模型.肖楓［6］以乘客為出發(fā)角度，參考城市公共交通系統(tǒng)，建立了一個以乘客滿意度和企業(yè)滿意度為優(yōu)化目標(biāo)的軌道交通行車間隔時間優(yōu)化理論模型.劉濤等［7］提出了換乘站大客流行車間隔協(xié)調(diào)調(diào)整策略，建立了基于行車間隔協(xié)調(diào)調(diào)整的換乘站大客流處置優(yōu)化模型.L.F.Liu等［8］研究了基于行車間隔城市軌道交通列車在換乘站的換乘協(xié)調(diào)問題.

由于客流的動態(tài)變化，需要根據(jù)實(shí)際情況調(diào)整行車間隔時間，以滿足客流需求.鑒于此，本文綜合考慮列車滿載程度及乘客舒適度，建立多目標(biāo)行車間隔時間優(yōu)化模型；采用基于NSGA－II的多目標(biāo)遺傳算法求解該問題的Pareto解集，綜合考慮相鄰時段發(fā)車間隔的穩(wěn)定性，確定各時間段的發(fā)車間隔.

1 客流分析

1.1 時間分布特性分析

1.1.1 工作日客流時間分布

地鐵客流在1d內(nèi)隨著人們的生活習(xí)慣和工作需要而變化.圖1是某工作日某地鐵2號線工作日的進(jìn)出站客流量分布圖，從圖中可知，該地鐵客流在1d內(nèi)形成2個客流高峰，在早高峰和晚高峰時，同時存在較高的進(jìn)站和出站客流，其他工作日的客流量時間分布規(guī)律與此類似.

圖1 工作日進(jìn)出站客流圖（周二）

由圖1可見，早高峰客流量較大，進(jìn)出站的早高峰客流峰度大于晚高峰客流峰度，但晚高峰的時間跨度大于早高峰，說明早高峰時段客流比較集中，晚高峰峰值相對于早高峰客流變化較緩和；另外，可以看出進(jìn)站客流的早晚高峰均早于出站客流的早晚高峰.由此可知，該地鐵線路客流具有通勤、通學(xué)特性.

1.1.2 周末客流時間分布

圖2為周末客流分布圖，可知周六與周日的客流時間分布規(guī)律有相似之處，均無明顯的早晚高峰，周末客流與工作日客流時間分布存在明顯的差異，周末最高峰沒有工作日客流高，但周末平峰時段的客流量卻大于工作日的客流量，說明周末旅客出行較分散.周六與周日的客流分布規(guī)律亦有不同之處，周六早上進(jìn)出站客流均遠(yuǎn)大于周日的客流，可能是由周末加班的職工和學(xué)生造成.

圖2 周末進(jìn)出站客流對比圖

1.1.3 “五一”客流時間分布

圖3為“五一”客流分布圖.由圖3可見，“五一”與周末的客流時間分布規(guī)律有相似之處，均無明顯的早晚高峰，但“五一”的客流量大于周末的客流量，“五一”的早上進(jìn)出站客流較大.

圖3 “五一”與周末進(jìn)出站客流對比圖

1.2 客流聚類分析

從地鐵客流時間分布特性可知，每日的客流特性并不完全相同，特別是工作日與周末及節(jié)假日.為了提高地鐵服務(wù)質(zhì)量及降低運(yùn)行成本，需要根據(jù)不同的地鐵客流分布特性確定列車的開行間隔.Frey等［9］提出了近鄰傳播聚類算法（affinity propagation，AP算法），該方法能較快地處理大規(guī)模數(shù)據(jù)，可得到比較穩(wěn)定的聚類結(jié)果.因而本文利用AP聚類算法對地鐵客流數(shù)據(jù)進(jìn)行聚類分析，將客流數(shù)據(jù)分為若干個子類，進(jìn)而針對每一子類確定其列車開行間隔.

對于一個有N個樣本的地鐵客流數(shù)據(jù)集，AP算法定義任意2個樣本xi，xk之間的相似度為

AP算法的基本步驟如下.

步驟1 設(shè)m＝0，最大迭代次數(shù)為M，計(jì)算數(shù)據(jù)集的相似度矩陣S，設(shè)定相似度矩陣對角線元素為相同值p，設(shè)定初始可信度和可用度r（0）（i，k）＝0，a（0）（i，k）＝0及阻尼系數(shù)λ.

步驟2 如果m大于M ，則轉(zhuǎn)步驟5，否則，m ＝m＋1按式（2）及（3）計(jì)算r（m）（i，k），a（m）（i，k）；

步驟3 按下式更新可用度和可信度.

步驟4 確定聚類中心，（r（m）（i，k）＋a（m）（i，k）＞0時認(rèn)為是一個聚類中心），返回步驟2.

步驟5 將其余點(diǎn)根據(jù)相似度劃分到各個聚類中，算法結(jié)束.

本文選取某地鐵2號線的站點(diǎn)進(jìn)行觀測，以30min為時間間隔，對2014年4～5月客流數(shù)據(jù)進(jìn)行統(tǒng)計(jì).利用AP算法進(jìn)行聚類分析，取參考度p為－35 000，得到的聚類數(shù)及聚類結(jié)果見表1.從聚類結(jié)果來看，周六和周日在一個聚類內(nèi)，周一至周五的客流數(shù)據(jù)聚集為一類，而“五一”前1d在一個分類內(nèi)，“五一”假期為單獨(dú)一類.

表1 客流聚類結(jié)果表

2 發(fā)車間隔優(yōu)化模型的建立

2.1 模型的假設(shè)

地鐵列車行駛過程受眾多因素影響，模型在建立時考慮了以下假設(shè)：（1）同一時間段的發(fā)車間隔固定；（2）每一時間段內(nèi)客流均勻到達(dá)和離開車站；（3）車輛選型和編組固定列車定員人數(shù)固定；（4）列車全程勻速運(yùn)行，未發(fā)生安全事故；（5）同線路上各列車一次運(yùn)行的運(yùn)營成本相同.

2.2 符號及變量說明

K＝｛k｜k＝1，2，…，N｝為城市軌道交通線路斷面集合，N為斷面數(shù)量；Q為列車定員；q為線路的最大斷面客流量；T為調(diào)度模擬時間段；h1，h2為模擬期間的最小及最大發(fā)車間隔；I為模擬期間線路發(fā)車數(shù)；m1，m2為模擬期間的最小及最大車輛滿載率；d為車內(nèi)乘客站立人員密度.

2.3 模型分析及建立

1）乘客舒適度 地鐵車廂擁擠程度直接影響乘客的乘車舒適度，用車輛內(nèi)乘客站立人員密度作為衡量舒適度的標(biāo)準(zhǔn)，也是定員標(biāo)準(zhǔn)［10］.《城市軌道交通工程項(xiàng)目建設(shè)標(biāo)準(zhǔn)》建議的車輛內(nèi)乘客站立人員密度評價標(biāo)準(zhǔn)見表2.

表2 車內(nèi)乘客站立人員密度評價標(biāo)準(zhǔn)表

車內(nèi)乘客站立人員密度d可表示為

式中：S為列車坐席數(shù)量；A為列車立席區(qū)分配面積.

對于乘客而言，當(dāng)舒適度空間恰好接觸但不擠壓乘客身體，乘客可小幅活動，此時乘客的舒適度良好，隨著乘客數(shù)量的增加，舒適度逐漸降低，根據(jù)表2的標(biāo)準(zhǔn)，可構(gòu)建乘客舒適度的分段效用函數(shù)如下：

2）滿載程度衡量 地鐵運(yùn)營管理者為了降低經(jīng)營成本，往往會增大發(fā)車間隔，以增加列車的滿載程度.滿載率一般可用車內(nèi)實(shí)際的乘客數(shù)與車輛定員的比值來表示，可構(gòu)建以下效用函數(shù)對滿載率進(jìn)行衡量.

式中：α為成本參數(shù)；β為強(qiáng)度系數(shù).本文取α＝40，β＝10.

依據(jù)上述分析，構(gòu)建地鐵列車行車間隔優(yōu)化模型如下.

其中：式（9）為發(fā)車間隔限制約束；式（10）為車輛滿載率約束.

3 求解算法

由于本模型由2個相互沖突的目標(biāo)函數(shù)構(gòu)成，因而需要尋求該模型的Pareto最優(yōu)集.遺傳算法作為一種啟發(fā)式的搜索算法，在多目標(biāo)優(yōu)化問題中得到了廣泛的應(yīng)用.其中，NSGA－II（nondominated sorting genetic algorithm II）采用簡潔明晰的非優(yōu)超排序和排擠機(jī)制，使算法具有逼近Pareto最優(yōu)前沿的能力，并采用排擠機(jī)制保證得到的Pareto最優(yōu)解具有良好的散布，表現(xiàn)出較好的綜合性能［11］.本文基于 NSGA－II設(shè)計(jì)模型的求解算法.

1）染色體的構(gòu)造 采用二進(jìn)制編碼方式表示模擬時間段內(nèi)的發(fā)車數(shù)，發(fā)車數(shù)滿足約束條件（9）及（10）.

2）交叉算子 按交叉概率pc從父代選擇一些染色體，兩兩分組，并對每組染色體進(jìn)行如下操作：隨機(jī)產(chǎn)生兩個交換位，將兩條染色體中的基因進(jìn)行交換，從而得到兩條新的染色體.

3）變異操作 對popsize個染色體以變異概率pm進(jìn)行變異：對被選擇變異染色體的基因，隨機(jī)產(chǎn)生一個變異位置，并重新產(chǎn)生其基因，從而得到一條新的染色體.

4）擁擠度選擇算子 快速非支配排序：設(shè)ni為種群中支配個體i的個體數(shù)，Si為種群中被個體i支配的個體集合.快速非劣分層的具體步驟為［12］.

步驟1 找出種群中所有ni＝0的個體，并保存在當(dāng)前集合F1中.

步驟2 對于當(dāng)前集合F1中每個個體i，遍歷Si中每個個體l，執(zhí)行nl＝nl－1，如果nl＝0，則將l保存在集合H 中.

步驟3 記F1中得到個體為第一個非支配層的個體，并以H為當(dāng)前集合，重復(fù)以上操作，直到整個種群被分層.

確定擁擠度計(jì)算步驟為

步驟1 對同層的個體初始化距離，令每個體i的擁擠度初始值L［i］d＝0.

步驟2 對不同的目標(biāo)函數(shù)，重復(fù)步驟3－1～3－3操作.

步驟3－1 對同層的個體按目標(biāo)m的函數(shù)值進(jìn)行優(yōu)劣排序；

步驟3－2 使得排序邊界上的個體具有選擇優(yōu)勢，給定一個大數(shù)L［0］d＝L［l］d＝∞ ，以確保進(jìn)入下一代；

經(jīng)過快速非支配排序和擁擠度計(jì)算，群體中的每個個體i都得到兩個屬性：非支配序irank和擁擠度id.進(jìn)而可采用輪盤制選擇算子進(jìn)行選擇，具體過程為：對于個體i，j，當(dāng)irank＜jrank或irank＝j(luò)rank且id＞jd時，選擇i，如果2個個體在同一級，取周圍較不擁擠的個體.

4 算例分析

選取某地鐵2號線為例，以30min為時間間隔，對2014年4～5月客流數(shù)據(jù)進(jìn)行統(tǒng)計(jì).利用AP算法進(jìn)行聚類分析，結(jié)果見表1，對應(yīng)時段的最大客流斷面見表3.該線路列車采用6輛編組，定員Q為1 440人，列車坐席數(shù)量S為240，列車立席區(qū)分配面積A為200m2，最大發(fā)車間隔為10 min，最小發(fā)車間隔2min，最大車輛滿載率為1.1，最小車輛滿載率為0.7.利用本文設(shè)計(jì)的模型及算法對4類客流進(jìn)行行車間隔優(yōu)化.

計(jì)算結(jié)果見表3.綜合考慮相鄰時段發(fā)車間隔的穩(wěn)定性，確定4類客流列車開行的間隔見表4.從優(yōu)化結(jié)果來看，該線路各時段乘客的舒適度均較好，在07：00～22：00間滿載率也較高，說明本文設(shè)計(jì)的模型及算法具有較好的適用性.

表3 4類客流優(yōu)化結(jié)果min

表4 4類客流列車開行間隔結(jié)果min

5 結(jié)束語

本文綜合考慮列車滿載程度及乘客舒適度，建立多目標(biāo)行車間隔時間優(yōu)化模型；采用基于NSGA－II的多目標(biāo)遺傳算法求解該問題的Pareto解集，該解集可為運(yùn)營管理者提供多個可選擇方案；最后，綜合考慮相鄰時段的發(fā)車間隔的穩(wěn)定性，確定了各時間段的發(fā)車間隔.算例分析表明本模型在地鐵列車行車間隔調(diào)度方面是合理可行的，但本模型沒有考慮地鐵線路間的乘客換乘影響，需要在今后進(jìn)一步深入研究.

［1］林 震，楊 浩.城市軌道交通發(fā)車間距優(yōu)化模型探討［J］.土木工程學(xué)報，2003，36（1）：1－5.

［2］洪 玲，陳菁菁，徐瑞華.市域快速軌道交通線行車間隔優(yōu)化問題研究［J］.城市軌道交通研究，2006，9（3）：35－37.

［3］VáZQUEZ－ABAD F J，ZUBIETA L.Ghost simulation model for the optimization of an urban subway system［J］.Discrete Event Dynamic Systems，2005，15（3）：207－235.

［4］嚴(yán) 波.城市軌道交通行車間隔時間優(yōu)化模型研究［J］.城市軌道交通研究，2008，11（6）：53－57.

［5］徐育鋒，范炳全，何勝學(xué)，等.單軌道交通線路行車間隔優(yōu)化模型研究［J］.交通與運(yùn)輸，2010，26（12）：104－107.

［6］肖 楓.基于模糊神經(jīng)網(wǎng)絡(luò)的城市軌道交通行車間隔時間優(yōu)化研究［D］.重慶：重慶交通大學(xué)，2013.

［7］劉 濤，徐瑞華.基于行車間隔協(xié)調(diào)調(diào)整的換乘站大客流處置［J］.城市軌道交通研究，2014，17（2）：50－53.

［8］LIU L F，YANG X F，YANG K.Research on the multi－objective transfer coordination optimization of urban rail transit trains［J］.Journal of Information ＆Computational Science，2015，12（5）：1855－1864.

［9］FREY B J，DUECK D.Clustering by passing messages between data points［J］.Science，2007，315（5814）：972－976.

［10］中華人民共和國建設(shè)部.建標(biāo)104－2008城市軌道交通工程項(xiàng)目建設(shè)標(biāo)準(zhǔn)［S］.北京：標(biāo)準(zhǔn)出版社，2008.

［11］王 林，陳 璨.一種基于DE算法和NSGA－II的多目標(biāo)混合進(jìn)化算法［J］.運(yùn)籌與管理，2010（6）：58－64.

［12］KALYANMOY D，AMRIT P，SAMEER A，et al.A fast elitist multi－objective genetic algorithm：NSGA－II［J］.IEEE Transactions on Evolutionary Computation，2002，6（2）：182－197.