楊熙宇， 暨育雄， 王同根

(同濟(jì)大學(xué) 道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室， 上海 201804)

?

基于遺傳算法的多服務(wù)模式公交優(yōu)化設(shè)計

楊熙宇， 暨育雄， 王同根

(同濟(jì)大學(xué) 道路與交通工程教育部重點(diǎn)實(shí)驗(yàn)室， 上海 201804)

摘要：基于獨(dú)立公交走廊需求特征，利用公交客流起點(diǎn)到終點(diǎn)(OD)數(shù)據(jù)，建立了以發(fā)車頻率和公交車型為主要輸出參數(shù)的多服務(wù)模式公交優(yōu)化設(shè)計模型.針對模型求解的復(fù)雜性，應(yīng)用遺傳算法進(jìn)行求解.最后，結(jié)合上海公交737路公交客流走廊數(shù)據(jù)給出了優(yōu)化算例.結(jié)果表明，模型具有較強(qiáng)的實(shí)用性，能快速有效地求解出多服務(wù)模式的公交優(yōu)化組合.

關(guān)鍵詞：交通規(guī)劃； 多服務(wù)模式公交； 公交走廊； 遺傳算法

城市公共交通在城市客運(yùn)交通體系中處于骨干地位，是大客流輸送的主要方式，其客運(yùn)功能的實(shí)現(xiàn)往往需要多服務(wù)模式公交的緊密配合.目前，除全程公交以外的公交模式主要有大站公交和區(qū)間公交，以下簡稱大站車和區(qū)間車.圖1所示公交線路1為全程車模式，線路服務(wù)沿線有7個公交站點(diǎn)；公交線路2為大站車模式，服務(wù)沿線有3個重要的客流公交站點(diǎn)；公交線路3為區(qū)間車模式，服務(wù)固定區(qū)間段內(nèi)的公交站點(diǎn).以上3種不同公交模式共同設(shè)置在同一公交客流走廊上，如何優(yōu)化協(xié)調(diào)設(shè)計此類多服務(wù)模式公交問題，已經(jīng)成為當(dāng)前研究的重點(diǎn).

圖1　多服務(wù)模式公交服務(wù)示意圖

多服務(wù)模式公交優(yōu)化問題的研究最早可追溯到1987年，F(xiàn)urth[1]將研究的重點(diǎn)集中在多服務(wù)模式公交的優(yōu)化協(xié)調(diào)問題上，以發(fā)車頻率和車頭時距偏差作為模型重要的輸出參數(shù)，但目標(biāo)函數(shù)沒有反映公交總成本對多服務(wù)模式公交優(yōu)化的影響[1].后續(xù)的研究逐漸克服了這一缺點(diǎn)，采用不同的數(shù)理模型優(yōu)化成本目標(biāo)函數(shù)[2-7].其中，Site等[2]在模型中考慮了多服務(wù)模式公交之間換乘時間費(fèi)用，從而使模型更加符合實(shí)際情況.Leiva等[4]將雙層模型的適用性推廣到多服務(wù)模式公交優(yōu)化問題中，并且其適用性和有效性也得到了證明.以上這些研究關(guān)注的重點(diǎn)都在公交服務(wù)主體，對公交服務(wù)客體(乘客)的關(guān)注微乎其微.

直到近些年來，研究的熱點(diǎn)才逐漸由公交服務(wù)主體導(dǎo)向轉(zhuǎn)變?yōu)楣环?wù)客體導(dǎo)向，模型中更加著重考慮公交自身服務(wù)對乘客的影響.2013年，Ceder等[6]通過對公交容量進(jìn)行定義，針對不同的公交模式采用不同的容量公交車，并應(yīng)用公交線路起點(diǎn)到終點(diǎn)(OD)計算出不同模式下的優(yōu)化指標(biāo)，結(jié)果表明乘客對于公交容量的敏感性較高，公交運(yùn)行距離越長，容量要求就越高.2015年，Larrain等[7]利用已知的出行OD，假定公交存在擁擠和非擁擠2種狀態(tài)，分別就兩類狀態(tài)建立優(yōu)化模型求解多服務(wù)模式公交的發(fā)車頻率.

就多服務(wù)模式公交優(yōu)化設(shè)計的方法而言，從國內(nèi)外的研究現(xiàn)狀來看，主要存在如下問題：首先，考慮公交服務(wù)對乘客影響的研究不多；其次，缺少對于多服務(wù)模式公交優(yōu)化組合的深入探討；再者，模型的求解算法大多還停留在傳統(tǒng)的枚舉法，求解過程繁雜且效率低下.

基于以上考慮，本文提出了在OD需求條件下基于遺傳算法的多服務(wù)模式公交優(yōu)化設(shè)計問題.以實(shí)際的公交線路為現(xiàn)實(shí)背景，分析多服務(wù)模式公交特征，解析優(yōu)化設(shè)計的機(jī)理，建立實(shí)用模型，并應(yīng)用遺傳算法求解.

1　多服務(wù)模式公交優(yōu)化設(shè)計問題

1.1問題描述

優(yōu)質(zhì)的多服務(wù)模式公交服務(wù)是體現(xiàn)公交運(yùn)營“以人為本”的重要指標(biāo)之一.多服務(wù)模式公交服務(wù)成本量化過程為將運(yùn)行成本、等候時間成本和車內(nèi)行駛時間成本綜合量化為費(fèi)用成本的過程.研究表明，多服務(wù)模式公交優(yōu)化問題并不是簡單的調(diào)度優(yōu)化問題，更多地需要考慮各種模式之間的組合優(yōu)化[8]，才能有效地提高公交的服務(wù)質(zhì)量，多元化地滿足不同乘客的出行需求.

由此定位，本文研究的是如何有效地在多服務(wù)模式公交優(yōu)化模型中融入公交服務(wù)對乘客的影響，并考慮多服務(wù)模式的組合優(yōu)化，最后應(yīng)用遺傳算法快速高效求解.為簡化敘述起見，將乘客上車點(diǎn)定義為出行的起點(diǎn)O點(diǎn)，乘客下車點(diǎn)定義為終點(diǎn)D點(diǎn)，OD出行疊加到公交線路上，每個出行者在出行過程中都形成一條出行路徑.

1.2建模環(huán)境

1.3目標(biāo)的選取

本次研究目標(biāo)針對多服務(wù)模式公交車輛運(yùn)行，采用協(xié)調(diào)優(yōu)化策略，車輛資源調(diào)度面向指定線路的客運(yùn)運(yùn)輸任務(wù).在線路客流需求確定的情況下，其總成本主要通過優(yōu)化發(fā)車頻率和車型來控制.

以往的研究中[4]，以總成本最小為優(yōu)化目標(biāo)建立了多服務(wù)模式公交模型來提高系統(tǒng)的運(yùn)行效率.因此，下文在以往研究的基礎(chǔ)上考慮公交對乘客的影響，改進(jìn)以往模型，建立以最小總成本為優(yōu)化目標(biāo)的多服務(wù)模式公交優(yōu)化模型.本文對于建模作如下的假設(shè)：

(1) 線路運(yùn)營完全獨(dú)立,不受相鄰線路的影響.

(2) 服務(wù)需求獨(dú)立于發(fā)車頻率和車型.

(3) 乘客服務(wù)服從“先到先服務(wù)” 的原則, 即先到達(dá)車站的乘客先上車.

(4) 站間區(qū)間內(nèi)車輛運(yùn)行速度為恒定值, 且途中無特殊事件發(fā)生.

(5) 研究時段內(nèi)車輛發(fā)車間隔不變, 各公交站點(diǎn)均相同.

(6) 乘客對公交服務(wù)的感知受乘客所處狀態(tài)(座位、站立或擁擠程度)和乘坐公交的時長有關(guān).

2　模型建立

2.1目標(biāo)函數(shù)

建立以公交自身的運(yùn)營成本、乘客候車時間成本和車內(nèi)時間成本總和為最小的目標(biāo)模型.

(1) 單位時間公交運(yùn)營成本c1

單位時間內(nèi)的公交運(yùn)營成本c1與車型大小、公交線路長度和發(fā)車頻率成如下函數(shù)關(guān)系[4]：

(1)

(2) 單位時間乘客候車成本c2

假設(shè)公交車輛到達(dá)公交站點(diǎn)服從泊松分布，候車成本與發(fā)車頻率成反比,和站點(diǎn)上車人數(shù)成正比，且不同模式的公交乘客候車時間還與不同模式的公交發(fā)車間距存在如下關(guān)系[2]：

(2)

式中：hr為全程車的車頭時距，等于全程車發(fā)車頻率的倒數(shù).

基于上述假設(shè)，單位時間乘客候車成本如下所示：

(3)

(3) 單位時間車內(nèi)時間成本c3

(4)

其中,

(5)

綜合以上論述，目標(biāo)函數(shù)為以上三部分總成本之和的最小值，即

(6)

2.2約束條件

上述3個模型中變量存在如下約束條件:

(7)

fr≥0, i∈N

(8)

(9)

2.3遺傳算法

遺傳算法是模擬生物遺傳進(jìn)化機(jī)制而發(fā)展起來的啟發(fā)式算法，是一種模仿生物界自然選擇原理和自然遺傳機(jī)制的隨機(jī)搜索最優(yōu)算法，具有“生物+檢測”特性.遺傳算法的過程主要分為選擇、交叉、變異和用作下一代4個主要步驟，如圖2所示.

基于上述理論，本次研究通過以下7個步驟求解多服務(wù)模式公交優(yōu)化設(shè)計問題：

步驟1初始化.初始化多服務(wù)模式公交初始方案、交叉概率以及變異概率，利用設(shè)定的選擇價值產(chǎn)生種群.

步驟2評估染色體.對種群中的每個染色體進(jìn)行目標(biāo)值計算.

步驟3檢驗(yàn).更新選擇最佳值，如果產(chǎn)生的數(shù)量超過了預(yù)先設(shè)定的門檻，停止計算.

步驟4計算產(chǎn)生的適應(yīng)性.計算所有的染色體選擇適應(yīng)性概率.

圖2　遺傳算法過程示意圖

步驟5選擇父母.基于選擇性概率來選擇優(yōu)秀的父母個體.

步驟6執(zhí)行交叉.交叉父母來產(chǎn)生下一代.只有在產(chǎn)生染色體可行的情況下，下一代染色體才能替代父母.

步驟7執(zhí)行變異.

3　實(shí)例應(yīng)用

以上海公交737路作為研究多服務(wù)模式公交的樣本，該線路途經(jīng)18個公交站，選擇早高峰時刻對該線路各公交站點(diǎn)上下客人數(shù)進(jìn)行多次調(diào)查.經(jīng)統(tǒng)計分析，通過已有的公交OD反推模型得到各站點(diǎn)的OD數(shù)據(jù)[9]，如表1所示，并將OD疊加到公交路段上，各站點(diǎn)間路段客流量統(tǒng)計如圖3所示.

圖3　公交站點(diǎn)間公交客流量示意圖

針對客流量數(shù)據(jù)，采用遺傳算法進(jìn)行計算，種群規(guī)模取18，交叉概率取0.85，變異概率取0.2[7].最終通過不少于180次的收斂計算出最小目標(biāo)函數(shù)值為6 124元，計算收斂迭代過程如圖4所示.

對多模式優(yōu)化計算和單模式(僅全程車模式)計算的結(jié)果進(jìn)行對比，結(jié)果表明，多服務(wù)模式公交優(yōu)化組合比單模式服務(wù)減少總成本約15.4%.如圖5所示，多模式優(yōu)化方案中大站車公交線的服務(wù)站點(diǎn)為1、9、11、12和18，區(qū)間車公交線路的服務(wù)站點(diǎn)為9、10、11、12、13、14和15.

表1　公交客流OD矩陣

圖4　遺傳算法計算收斂過程圖

3條不同模式的公交線路在客流交集的8個站點(diǎn)存在一定的客流競爭，如出行起點(diǎn)為站點(diǎn)9到終點(diǎn)為站點(diǎn)11的乘客，存在3種不同的選擇競爭(全程車、大站車和區(qū)間車).沿線存在客流競爭的8個站點(diǎn)的多服務(wù)模式公交客流競爭結(jié)果如圖6所示.結(jié)果顯示，全程車隨著經(jīng)過站點(diǎn)數(shù)目的增大，客流競爭力下降；反之，大站車和區(qū)間車隨經(jīng)過站點(diǎn)數(shù)目的增加，客流競爭力上升.

圖5　多服務(wù)模式公交優(yōu)化設(shè)計結(jié)果示意圖

本次研究的優(yōu)化模型與Furth提出的傳統(tǒng)模型[1]對比結(jié)果如表2所示.分析表明，車內(nèi)時間成本比Furth模型顯著增加25.95%，同時對車型容量的大小要求下降約6.67%.造成這類差異的主要原因?yàn)槟Ｐ椭屑尤敕?wù)水平對乘客影響這一重要因素，這樣大大提高了公交服務(wù)水平.

對優(yōu)化模型和傳統(tǒng)模型計算結(jié)果在重要節(jié)點(diǎn)的

表2　優(yōu)化模型與傳統(tǒng)模型結(jié)果比較

圖6　多服務(wù)模式公交站點(diǎn)客流競爭百分比示意圖

客流變化進(jìn)行統(tǒng)計分析，結(jié)果如圖7所示.公交車內(nèi)人數(shù)達(dá)到一定數(shù)量，車內(nèi)逐漸擁擠的情況下，優(yōu)化模式的公交車吸引力將下降，也就是說乘客可能會選擇繼續(xù)等候下一輛其他模式的公交車，這也是本次優(yōu)化模型中加入容量參數(shù)，強(qiáng)調(diào)公交服務(wù)水平的原因.這一結(jié)論和現(xiàn)實(shí)情況有很強(qiáng)的一致性.

a 全程車

b 大站車

c 區(qū)間車

在優(yōu)化模型不變的情況下，逐漸放大交通需求量，將原有的矩陣乘以相應(yīng)的系數(shù)進(jìn)行擴(kuò)大，如圖8所示.結(jié)果表明，優(yōu)化模型和傳統(tǒng)模型之間隨需求的增大，計算的函數(shù)值也逐漸加大.

圖8　不同交通需求下優(yōu)化模型和傳統(tǒng)模型的敏感性分析

Fig.8Sensitivity analysis of optimization and traditional models with different demands

對研究案例中的大站車和區(qū)間車線路進(jìn)行組合研究，如圖9所示，當(dāng)大站車的線路為1條，區(qū)間車線路為2條時，目標(biāo)函數(shù)取得最小值.

圖9　不同模式公交線路組合敏感性分析

為了檢驗(yàn)遺傳算法的效率，本文對公交站點(diǎn)個數(shù)從10～18進(jìn)行了不同方案下的計算效率統(tǒng)計,如表3所示.隨著車站數(shù)量的增加，運(yùn)行的次數(shù)并沒有顯著增加，運(yùn)行的誤差率也基本維持在10%左右.

4　結(jié)語

本文基于公交站點(diǎn)OD出行數(shù)據(jù)，考慮公交服務(wù)對乘客的影響，構(gòu)建多服務(wù)模式公交優(yōu)化模型，并應(yīng)用遺傳算法求解.該方法不僅能真實(shí)地反映乘客的出行成本，同時能夠優(yōu)化公交運(yùn)營調(diào)度系統(tǒng)，對發(fā)車頻率和車型大小提出了新的要求，且運(yùn)用遺傳算法克服了傳統(tǒng)枚舉法繁雜、效率低下的特點(diǎn).

本文提出的多服務(wù)模式公交優(yōu)化模型，從理論上可以推廣到多服務(wù)模式公交網(wǎng)絡(luò)的優(yōu)化，但實(shí)際上由于網(wǎng)絡(luò)問題有一定的復(fù)雜性，可能會導(dǎo)致計算過程中收斂于指定線路的最優(yōu)值并非整個系統(tǒng)的最優(yōu)值.同時本文提出的公交服務(wù)對公交乘客的影響中沒有對在車內(nèi)有座位和無座位的人群進(jìn)行區(qū)分，尤其是在考慮先站立到有座的情況下，模型變得相對復(fù)雜，進(jìn)一步的研究工作可以考慮在模型中加入新變量來完善.

表3　遺傳算法敏感性分析

注：誤差指遺傳算法找到的優(yōu)化值與傳統(tǒng)算法之間的差異.

參考文獻(xiàn):

[1]Furth P G. Short turning on transit routes[J]. Transportation Research Record, 1987, 1108: 42.

[2]Site P D, Filippi F. Service optimization for bus corridors with short-turn strategies and variable vehicle size[J]. Transportation Research Part A: Policy & Practice, 1998, 32(1):19.

[3]Homero L, Ricardo G, Juan C M. Choosing the right express services for bus corridor with capacity restrictions[J]. Journal of the Transportation Research Board, 2010, 13(2197):63.

[5]Tirachini A, Cortés C E, Jara-Díaz S R. Optimal design and benefits of a short turning strategy for a bus corridor[J]. Transportation, 2011, 38(1):169.

[6]Ceder A, Hassold S, Dano B. Approaching even-load and even-headway transit timetables using different bus sizes[J]. Public Transport, 2013, 5(3):193.

[7]Larrain H, Muoz J C, Giesen R. Generation and design heuristics for zonal express services[J]. Transportation Research, Part E: Logistics & Transportation Review, 2015, 79:201.

[8]Ibarra-Rojas O J, Delgado F, Giesen R,etal. Planning, operation, and control of bus transport systems: a literature review[J]. Transportation Research Part, B: Methodological, 2015, 77:38.

[9]周雪梅，楊熙宇，吳曉飛. 基于IC卡信息的公交客流起止點(diǎn)反推方法[J]．同濟(jì)大學(xué)學(xué)報：自然科學(xué)版，2012，40(7)：1027.

ZHOU Xuemei, YANG Xiyu, WU Xiaofei. Origin-destination matrix estimation method of public transportation flow based on data from bus integrated-circuit cards [J]. Journal of Tongji University：Natural Science, 2012，40(7)：1027.

收稿日期：2015-08-11

基金項(xiàng)目：國家自然科學(xué)基金(51308410)；上海市科委項(xiàng)目(15DZ1204402)

通訊作者：暨育雄(1978—),男,副教授，工學(xué)博士,主要研究方向?yàn)楣还芾砼c控制.E-mail：yxji@#edu.cn

中圖分類號：U491

文獻(xiàn)標(biāo)志碼：A

Optimization Design of Multiple Services for Urban Bus Corridor With Genetic Algorithm

YANG Xiyu， JI Yuxiong， WANG Tonggen

(Key Laboratory of Road and Traffic Engineering of the Ministry of Education, Tongji University， Shanghai 201804，China)

Abstract：Based on the urban transportation demand of bus corridor, this paper studies the optimization design of multiple services with urban transit. For the operation characteristics of bus lines, the optimization model of minimum costs in terms of waiting time, in-vehicle travel time and operator cost is developed with genetic algorithm(GA). An application of the model to the case of No.737 bus line in Shanghai shows that the optimization model is practical and effective for satisfying the demand of passengers and improving the operating efficiency of bus transit system.

Key words：public transit; multiple services; bus corridor; genetic algorithm(GA)

第一作者： 楊熙宇(1982—),男,博士生,主要研究方向?yàn)榻煌ㄟ\(yùn)輸規(guī)劃與管理.E-mail：yangxiyu001@163.com