基于高平峰劃分的寧波公交調(diào)度優(yōu)化

王惠敏,楊青萍,林婉婷,朱銘慧,王立洪

（寧波大學(xué) 數(shù)學(xué)與統(tǒng)計(jì)學(xué)院,浙江 寧波 315211）

0 引言

隨著社會(huì)經(jīng)濟(jì)的快速發(fā)展和人口的倍增，我國(guó)機(jī)動(dòng)車擁有量急劇上升，交通問題日益嚴(yán)重[1]，“優(yōu)先發(fā)展城市公共交通”戰(zhàn)略成為共識(shí)[2]。據(jù)《統(tǒng)計(jì)公報(bào)》顯示，2015年至2019年寧波常規(guī)公交客運(yùn)量連續(xù)下降，究其原因，一方面在于近年來由于地鐵、網(wǎng)約車等交通方式的崛起，給公交運(yùn)營(yíng)帶來了一定的沖擊；另一方面在于寧波公交運(yùn)營(yíng)排班中全面智能化有所欠缺，高峰期發(fā)車間隔最高達(dá)30 min，且發(fā)車間隔不規(guī)律，無法靈活應(yīng)對(duì)由于上下班、節(jié)假日等造成的潮汐交通現(xiàn)象，以致公交運(yùn)營(yíng)出現(xiàn)高峰期出行供應(yīng)不足和平峰期資源浪費(fèi)的問題；此外，因高峰期交通擁堵，公交運(yùn)行速度較低，準(zhǔn)點(diǎn)率下降[3]，公交對(duì)乘客吸引力不足。截至2018年底，寧波市民選擇公交出行比例僅占21.70%。據(jù)國(guó)內(nèi)外研究表明，高峰期發(fā)車間隔應(yīng)少于10 min，過久的發(fā)車間隔無法滿足乘客出行需求，過短的發(fā)車間隔會(huì)導(dǎo)致交通擁堵且造成資源浪費(fèi)，如何合理調(diào)度公交是提升公交運(yùn)營(yíng)服務(wù)水平的重要課題。

國(guó)內(nèi)對(duì)于公交調(diào)度研究中多采用遺傳算法，目前已有人提出基于遺傳算法以乘客等車時(shí)間成本最小和收益最大為目標(biāo)研究公交智能排班方法[4,5]；孫志田、張建梅等人提出在傳統(tǒng)遺傳算法中加入優(yōu)先級(jí)編碼方式以及染色體結(jié)構(gòu)，以提高傳統(tǒng)遺傳算法效率[6]；劉繼國(guó)[7]在基于遺傳算法的公交排班系統(tǒng)研究中表明遺傳算法能有效解決公交調(diào)度問題。

目前鮮有針對(duì)寧波地區(qū)公交調(diào)度的研究，本文將分析寧波公交高平峰狀況，通過建立數(shù)學(xué)模型研究如何在兼顧“提升乘客滿意度”和“降低運(yùn)營(yíng)成本”下對(duì)公交調(diào)度進(jìn)行優(yōu)化。

1 數(shù)據(jù)獲取及預(yù)處理

申請(qǐng)寧波市數(shù)據(jù)開放平臺(tái)[8]賬號(hào)，以獲取寧波市公交GPS數(shù)據(jù)、公交線路和公交站點(diǎn)等相關(guān)信息，并從寧波市數(shù)據(jù)開放平臺(tái)申請(qǐng)由寧波市經(jīng)信局提供的市民卡消費(fèi)記錄信息數(shù)據(jù)接口，登錄賬號(hào)通過數(shù)據(jù)接口用Python爬蟲技術(shù)獲取自2015年6月19日至2018年6月19日寧波市民卡消費(fèi)記錄信息共355 523 000條作為乘客數(shù)量的原始數(shù)據(jù)，約19.77 GB，數(shù)據(jù)類型包括交易流水、消費(fèi)時(shí)間、消費(fèi)金額、線路編號(hào)、車輛編號(hào)、站點(diǎn)編號(hào)等，見表1。

表1 寧波市民卡消費(fèi)記錄信息部分示例

對(duì)原始數(shù)據(jù)中缺失值、重復(fù)值及離群值進(jìn)行數(shù)據(jù)清洗和整理，由公交線路標(biāo)識(shí)號(hào)在市民卡消費(fèi)記錄信息數(shù)據(jù)中篩選出覆蓋寧波主城區(qū)公交線路數(shù)據(jù)，隨機(jī)挑選7條線路進(jìn)行研究，共30 458 400條，統(tǒng)計(jì)所選線路對(duì)應(yīng)日期中各時(shí)段的有效數(shù)據(jù)條數(shù)作為公交上車客流量數(shù)據(jù)，以“1路”公交線路為例，上車客流量在1 603人(2018年1月10日)至6 777人(2017年10月4日)之間波動(dòng)。

2 公交在高平峰轉(zhuǎn)換期的調(diào)度

本文將通過建立數(shù)學(xué)模型進(jìn)行相關(guān)研究：給出公交線路上客流量高平峰的劃分方法和預(yù)測(cè)方法，設(shè)計(jì)優(yōu)化的高平峰公交調(diào)度方案，并用寧波公交客流量數(shù)據(jù)做實(shí)例分析。

2.1 公交車不同時(shí)段的高平峰劃分

對(duì)于劃分公交線路上不同時(shí)段的高平峰，采用費(fèi)歇最優(yōu)分割法，算法設(shè)計(jì)步驟見表2，即對(duì)每個(gè)時(shí)段的上車人數(shù)所組成的序列進(jìn)行分段，每一分段為一類，通過計(jì)算損失函數(shù)，尋找一個(gè)分割，使類內(nèi)樣品之間差異最小，而類間樣品差異最大[9-11]。

表2 費(fèi)歇最優(yōu)分割法設(shè)計(jì)步驟

定義閾值即高平峰劃分標(biāo)準(zhǔn)，本文認(rèn)為最直觀的劃分依據(jù)為客流量大小，由于各時(shí)段上下車人數(shù)高度相關(guān)，因此用上車人數(shù)作為客流量數(shù)據(jù)，定義閾值μ為各時(shí)段內(nèi)客流量均值，當(dāng)天內(nèi)某個(gè)時(shí)段客流量大于μ時(shí)定義為高峰期，小于μ時(shí)為平峰期，公式為：

其中，n為時(shí)段數(shù)，ri為第i個(gè)時(shí)段的上車總?cè)藬?shù)。

2.2 運(yùn)用遺傳算法對(duì)公交車發(fā)車時(shí)刻表的規(guī)劃

對(duì)于公交調(diào)度問題，分別考慮不同高峰期和平峰期下的客流情況，采用遺傳算法進(jìn)行規(guī)劃，見圖1。遺傳算法是一種以數(shù)學(xué)方式通過計(jì)算機(jī)仿真，模擬自然選擇及遺傳歷程中的繁衍、突變以及雜交的現(xiàn)象來尋求最優(yōu)解的搜索算法[4-7]。

圖1 遺傳算法流程圖

適應(yīng)度函數(shù)是用來判斷群體中個(gè)體的優(yōu)劣程度，由目標(biāo)函數(shù)來評(píng)估，乘客滿意度由乘客總等車時(shí)間決定，公交公司滿意度由運(yùn)營(yíng)利潤(rùn)決定，因此通過兩方面來建立目標(biāo)函數(shù)，一是使調(diào)度周期內(nèi)乘客的總等車時(shí)間最短，二是公交運(yùn)營(yíng)利潤(rùn)最大。

①計(jì)算調(diào)度周期內(nèi)乘客總等待時(shí)間

在發(fā)車間隔內(nèi)乘客到達(dá)站點(diǎn)的等車時(shí)間服從均勻分布，因此乘客總平均等待時(shí)間為：

rij為第j站等第i趟車客流量，tij為在第j站第i趟車發(fā)車間隔。

將乘客等車時(shí)間換算成工資成本，設(shè)w為乘客平均每分鐘工資，則乘客總時(shí)間成本為：

②計(jì)算公交運(yùn)營(yíng)利潤(rùn)

公交運(yùn)營(yíng)成本由車輛油耗費(fèi)及乘務(wù)員工資構(gòu)成，公交運(yùn)營(yíng)利潤(rùn)為票價(jià)收益與成本之差。

Cb為運(yùn)營(yíng)成本；Lr為運(yùn)營(yíng)利潤(rùn)；p為票價(jià)；L為運(yùn)行一趟的里程數(shù)；m為發(fā)車次數(shù)；n為公交站點(diǎn)數(shù)；t為運(yùn)行一趟的時(shí)間；pc為每公里行駛成本；pt為乘務(wù)員每小時(shí)工資。

為找到使乘客等車時(shí)間最少與公交運(yùn)營(yíng)利潤(rùn)最大的最優(yōu)平衡點(diǎn)，將乘客等待時(shí)間轉(zhuǎn)換為工資成本如公式(3)，此時(shí)乘客等待時(shí)間成本和公交運(yùn)營(yíng)利潤(rùn)為同一量綱，分別賦予不同的加權(quán)系數(shù)，則將雙目標(biāo)規(guī)劃優(yōu)化問題轉(zhuǎn)變?yōu)閱文繕?biāo)優(yōu)化問題：

③目標(biāo)函數(shù)的約束條件

i車輛平均滿載率的約束

ii最大最小發(fā)車間隔的約束

iii相鄰兩車發(fā)車間隔時(shí)間在一定限度內(nèi)

通過目標(biāo)函數(shù)(6)來確定適應(yīng)度函數(shù)，即：

Q為車容量；H（x）為適應(yīng)度函數(shù)；y為單目標(biāo)函數(shù)值；Cmin為一代群體中所有目標(biāo)函數(shù)的最小值。

2.3 對(duì)未來某一天的高平峰時(shí)段劃分預(yù)測(cè)

對(duì)于未來某一天公交線路上客流量的預(yù)測(cè)，采用BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型，模型設(shè)計(jì)步驟見表3，BP神經(jīng)網(wǎng)絡(luò)是一種按照信號(hào)正向傳播和誤差逆向反饋的多層前饋神經(jīng)網(wǎng)絡(luò)，經(jīng)過充分訓(xùn)練的神經(jīng)網(wǎng)絡(luò)可獲取客流量樣本特征，以對(duì)未學(xué)習(xí)的樣本進(jìn)行預(yù)測(cè)[12-14]。

表3 BP神經(jīng)網(wǎng)絡(luò)預(yù)測(cè)模型設(shè)計(jì)步驟

3 寧波市公交運(yùn)營(yíng)實(shí)例分析

3.1 數(shù)據(jù)分析

對(duì)選取的7條線路所有日期各時(shí)段的客流量進(jìn)行高平峰劃分，實(shí)驗(yàn)結(jié)果表明，公交線路上客流量極少出現(xiàn)劇增或驟減的情況，運(yùn)營(yíng)情況相對(duì)穩(wěn)定，公交線路上客流量高平峰據(jù)不同的日期屬性（工作日、周末、節(jié)假日）呈現(xiàn)出周期性和時(shí)序性。

周期性表現(xiàn)：不同工作日高峰期和平峰期時(shí)段相似；周末高峰期時(shí)段集中在下午1點(diǎn)到5點(diǎn)；不同節(jié)假日高峰期時(shí)段出現(xiàn)較早，客流量大且持續(xù)時(shí)間長(zhǎng)。

時(shí)序性表現(xiàn)：不同工作日一天內(nèi)高平峰時(shí)段交替出現(xiàn)，呈現(xiàn)出早高峰和晚高峰狀態(tài)。

選取“1路”公交線路2017年10月11日星期三（工作日）、2017年10月14日星期六（周末）與2017年10月4日星期三（中秋節(jié)）不同日期屬性各時(shí)段的上車客流量數(shù)據(jù)進(jìn)行可視化來表明其周期性與時(shí)序性，如圖2所示。

圖2 “1路”公交不同日期屬性下的客流量對(duì)比圖

3.2 高平峰的時(shí)段劃分

下面以寧波市“1路”公交2017年11月1日星期三（工作日）的數(shù)據(jù)為例進(jìn)行模型驗(yàn)證，共計(jì)2 187條，公交運(yùn)營(yíng)時(shí)間從早上6點(diǎn)開始到晚上11點(diǎn)結(jié)束，將相鄰兩個(gè)整點(diǎn)劃分為一個(gè)時(shí)段，共劃分為1~17共17個(gè)時(shí)段，即時(shí)段數(shù)為n=17，建立費(fèi)歇最優(yōu)分割法模型，得到“1路”公交時(shí)段分類數(shù)與損失函數(shù)關(guān)系曲線見圖3。

圖3 2017年11月1日“1路”公交時(shí)段分類數(shù)與損失函數(shù)關(guān)系曲線圖

當(dāng)k≤5時(shí)增加一段分類數(shù)線段斜率絕對(duì)值較大，損失函數(shù)下降明顯，當(dāng)k＞5時(shí)增加一段分類數(shù)線段斜率絕對(duì)值較小，對(duì)損失函數(shù)值改善微弱且增加分類的復(fù)雜程度，因此將17個(gè)時(shí)段劃為5個(gè)時(shí)區(qū)最優(yōu)，總客流量2 187人，由(1)式設(shè)閾值129人/時(shí)，結(jié)果見表4。

表4 2017年11月1日“1路”公交高平峰劃分結(jié)果

3.3 公交發(fā)車間隔規(guī)劃

3.3.1 運(yùn)用寧波市實(shí)際數(shù)據(jù)進(jìn)行仿真模擬

取每月工作22天，每日工作8小時(shí)，設(shè)乘客平均工資為31.05元/時(shí)[15]；乘務(wù)員平均工資為41.94元/時(shí)[16]。據(jù)刷卡記錄，刷普通卡票價(jià)為2元人數(shù)占75%，刷老年卡免費(fèi)人數(shù)占18%，刷學(xué)生卡票價(jià)為0.60元人數(shù)占7%，平均票價(jià)約1.54元/人；公交乘客數(shù)日均約4 000人。至2018年，寧波市主城區(qū)標(biāo)準(zhǔn)運(yùn)營(yíng)車輛7 315.80輛，新能源純電動(dòng)公交車占比約21.25%，以波谷時(shí)段充電為主，谷電電價(jià)約0.29元/度，充電損耗5%~10%，實(shí)際續(xù)航約120千米，開空調(diào)續(xù)航約減少28%，即電費(fèi)成本約0.64元/千米，普通柴油燃油成本約2元/千米，則一輛公交平均行駛成本約1.71元/千米。此條線路里程數(shù)約12.80千米，運(yùn)行一趟約1.33小時(shí)。將上述數(shù)據(jù)代入(5)式得，發(fā)車次數(shù)最多為92次時(shí)，公交運(yùn)營(yíng)不虧損。

為確定最優(yōu)發(fā)車次數(shù)，計(jì)算不同發(fā)車次數(shù)與乘客等待時(shí)間成本見公式(3)、公交運(yùn)營(yíng)成本見公式(4)、平均成本的關(guān)系曲線見圖4，因發(fā)車次數(shù)只能取整，由此可知在保證公交運(yùn)營(yíng)不虧損的范圍內(nèi)隨著發(fā)車次數(shù)的增加平均成本降低，因此取發(fā)車次數(shù)為92次。為提升公交運(yùn)營(yíng)服務(wù)水平，提高乘客等待時(shí)間成本權(quán)重，設(shè)(6)式加權(quán)系數(shù)α=0.70，β=0.30，經(jīng)過大量試驗(yàn)，選定交叉概率0.70，變異概率0.10%，迭代次數(shù)2 000，建立遺傳算法模型，經(jīng)過迭代算法趨于穩(wěn)定，規(guī)劃結(jié)果見表5：

圖4 發(fā)車次數(shù)與成本關(guān)系曲線圖

表5 2017年11月1日“1路”公交發(fā)車間隔規(guī)劃結(jié)果

此模型優(yōu)化的各時(shí)段發(fā)車間隔結(jié)果比實(shí)際公交運(yùn)營(yíng)平均發(fā)車間隔縮短了5~15 min。

3.3.2 穩(wěn)健性與靈敏度分析

對(duì)實(shí)際情況下可能出現(xiàn)較大波動(dòng)的影響因素進(jìn)行穩(wěn)健性檢驗(yàn)，因此對(duì)客流量、油耗費(fèi)及乘務(wù)員工資進(jìn)行穩(wěn)健性檢驗(yàn)，控制其他影響因素不變，分別將客流量、公交行駛成本及乘務(wù)員工資數(shù)據(jù)在合理范圍內(nèi)波動(dòng)，模型仍能平穩(wěn)運(yùn)行，說明模型有較強(qiáng)的穩(wěn)健性。

對(duì)于靈敏度，分別考慮速度、票價(jià)以及發(fā)車次數(shù)對(duì)模型的影響，控制其他變量，在合理范圍內(nèi)進(jìn)行調(diào)節(jié)，比較適應(yīng)度函數(shù)值及各時(shí)段發(fā)車間隔，得到公交調(diào)度模型對(duì)發(fā)車次數(shù)的靈敏性較高。

3.4 對(duì)未來一天的高平峰劃分預(yù)測(cè)

將客流量對(duì)應(yīng)日期屬性特征進(jìn)行獨(dú)熱編碼處理作為輸入變量，客流量為輸出變量，在試湊范圍內(nèi)分別計(jì)算不同的隱藏層節(jié)點(diǎn)數(shù)下的平均判定系數(shù)見表6，當(dāng)隱藏層節(jié)點(diǎn)數(shù)為6時(shí)，平均判定系數(shù)趨近于1，說明回歸平方和在總誤差平方和比例越大，模型擬合程度越好。

表6 不同隱藏層節(jié)點(diǎn)數(shù)下的平均判定系數(shù)

設(shè)定學(xué)習(xí)速率為0.01，最小均方誤差為10-8，最大的訓(xùn)練次數(shù)為1 000次，運(yùn)用2017年8月7日至2017年12月28日“1路”公交線路不同時(shí)段的上車客流量數(shù)據(jù)作為訓(xùn)練樣本，對(duì)數(shù)據(jù)歸一化處理后建立模型，來預(yù)測(cè)2017年12月29日“1路”公交不同時(shí)段的客流量，并計(jì)算各時(shí)段的實(shí)際客流量與預(yù)測(cè)客流量的差值以檢驗(yàn)預(yù)測(cè)誤差，結(jié)果見圖5。

圖5 2017年12月29日“1路”公交預(yù)測(cè)客流量與實(shí)際客流量對(duì)比圖

結(jié)果表明預(yù)測(cè)誤差最小值為1.75，最大值為43.97，平均誤差值為17.92，標(biāo)準(zhǔn)方差為19.11，平均誤差范圍為14.21%。

誤差分析：由于缺少天氣、溫度等數(shù)據(jù)，簡(jiǎn)化了一些影響因素；數(shù)據(jù)采集為刷卡的乘客客流量，忽略了手機(jī)支付及付現(xiàn)金的乘客數(shù)量；獲取的數(shù)據(jù)中沒有明確區(qū)分公交運(yùn)行的方向。這些因素造成了理論值與實(shí)際值的偏差。

4 結(jié)論

本文對(duì)寧波市公交數(shù)據(jù)進(jìn)行實(shí)例研究，考慮因不同日期及時(shí)間段造成的客流量潮汐現(xiàn)象，對(duì)傳統(tǒng)的公交調(diào)度模型進(jìn)行了優(yōu)化，得到如下結(jié)論：

（1）根據(jù)建立的公交線路上客流量高平峰的劃分模型進(jìn)行實(shí)測(cè)，結(jié)果表明公交線路上客流量高平峰存在較為明顯的周期性和時(shí)序性。

（2）建立了基于高平峰劃分結(jié)果下控制公交公司成本同時(shí)提高乘客滿意度的公交調(diào)度優(yōu)化模型；根據(jù)實(shí)測(cè)分析可知此模型優(yōu)化的各時(shí)段發(fā)車間隔結(jié)果比實(shí)際公交運(yùn)營(yíng)平均發(fā)車間隔縮短了5~15 min。隨新能源公交車的普及，公交行駛成本將逐漸降低，公交發(fā)車間隔可縮短，用此模型可進(jìn)一步優(yōu)化。

（3）根據(jù)建立的公交線路上客流量的預(yù)測(cè)模型進(jìn)行預(yù)測(cè)，結(jié)果表明預(yù)測(cè)結(jié)果與實(shí)際值存在偏差，平均誤差范圍為14.21%。