楊熙宇， 暨育雄， 王同根

(同濟大學 道路與交通工程教育部重點實驗室， 上海 201804)

?

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

楊熙宇， 暨育雄， 王同根

(同濟大學 道路與交通工程教育部重點實驗室， 上海 201804)

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

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

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

圖1　多服務模式公交服務示意圖

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

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

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

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

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

1.1問題描述

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

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

1.2建模環(huán)境

1.3目標的選取

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

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

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

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

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

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

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

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

2　模型建立

2.1目標函數

建立以公交自身的運營成本、乘客候車時間成本和車內時間成本總和為最小的目標模型.

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

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

(1)

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

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

(2)

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

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

(3)

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

(4)

其中,

(5)

綜合以上論述，目標函數為以上三部分總成本之和的最小值，即

(6)

2.2約束條件

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

(7)

fr≥0, i∈N

(8)

(9)

2.3遺傳算法

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

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

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

步驟2評估染色體.對種群中的每個染色體進行目標值計算.

步驟3檢驗.更新選擇最佳值，如果產生的數量超過了預先設定的門檻，停止計算.

步驟4計算產生的適應性.計算所有的染色體選擇適應性概率.

圖2　遺傳算法過程示意圖

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

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

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

3　實例應用

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

圖3　公交站點間公交客流量示意圖

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

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

表1　公交客流OD矩陣

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

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

圖5　多服務模式公交優(yōu)化設計結果示意圖

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

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

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

圖6　多服務模式公交站點客流競爭百分比示意圖

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

a 全程車

b 大站車

c 區(qū)間車

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

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

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

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

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

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

4　結語

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

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

表3　遺傳算法敏感性分析

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

參考文獻:

[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卡信息的公交客流起止點反推方法[J]．同濟大學學報：自然科學版，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

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

通訊作者：暨育雄(1978—),男,副教授，工學博士,主要研究方向為公交管理與控制.E-mail：yxji@#edu.cn

中圖分類號：U491

文獻標志碼：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—),男,博士生,主要研究方向為交通運輸規(guī)劃與管理.E-mail：yangxiyu001@163.com