賴元文，張杰

(1.福州大學(xué)，土木工程學(xué)院，福州350116；2.寧德師范學(xué)院，信息與機(jī)電工程學(xué)院，福建寧德352100)

0 引言

公交調(diào)度作為優(yōu)化公交運營效率，增大公交出行吸引力的重要手段，具有較大提升潛力，國內(nèi)外諸多學(xué)者對公交調(diào)度優(yōu)化模型及求解算法展開研究。TANG等[1]通過公交車歷史軌跡估算公交行程時間，建立以實際出行時間最短為目標(biāo)，車內(nèi)容量限制為約束條件的公交調(diào)度模型。NAM 等[2]從環(huán)保角度入手，建立以燃油消耗、碳排放為指標(biāo)的環(huán)境成本最小公交調(diào)度模型。王鳳剛[3]考慮駕駛員成本，建立以司機(jī)數(shù)量最少的最小費用流公交調(diào)度模型。SONG 等[4]提出加入基因重組的改進(jìn)遺傳算法，求解公交調(diào)度問題。陳少華[5]設(shè)計改進(jìn)鄰域搜索模擬退火算法用于公交發(fā)車時刻表優(yōu)化。張莉[6]針對遺傳算法“早熟”特點，在過程中加入退火操作，尋找發(fā)車時刻全局最優(yōu)解。

國內(nèi)外學(xué)者在公交調(diào)度模型構(gòu)建上，假設(shè)條件較多，且與調(diào)度線路實際客流特征聯(lián)系較少。在模型求解算法上，改進(jìn)傳統(tǒng)算法占多數(shù)，新興算法在公交調(diào)度中的應(yīng)用還存在較大研究空間。因此，本文提出一個公交調(diào)度優(yōu)化模型，并設(shè)計一個啟發(fā)式算法對模型求解，將線路客流特征數(shù)據(jù)應(yīng)用于公交調(diào)度優(yōu)化模型構(gòu)建，加強模型與實際客流聯(lián)系的基礎(chǔ)上，減少模型假設(shè)條件，并采用改進(jìn)新興仿生群算法-布谷鳥算法求解模型，加強尋優(yōu)效率，以期得到更好的模型優(yōu)化效果。

1 考慮客流特征的公交調(diào)度模型構(gòu)建

1.1 建模思路

不同時段客流需求不同，構(gòu)建與線路實際客流特征相關(guān)的公交調(diào)度模型更具實用性。因此，考慮如下因素：

(1)發(fā)車時段

乘客不同時刻出行需求不同，對客流量相似時段進(jìn)行整合，將結(jié)果應(yīng)用于公交調(diào)度發(fā)車時段劃分，優(yōu)化公交資源利用率。

(2)站點上、下客量

現(xiàn)有公交調(diào)度模型，多將站點無滯留乘客作為假設(shè)條件。本文結(jié)合客流特征及車輛核定載客人數(shù)，計算車內(nèi)空余可乘車人數(shù)，與等車人數(shù)對比反映站點滯站人數(shù)，減少模型假設(shè)條件；同時，通過車內(nèi)人數(shù)設(shè)計約束條件，界定平均滿載率，防止載客量過低，浪費公交資源。

(3)區(qū)間載客量

定義經(jīng)過某斷面所有班次車內(nèi)人數(shù)為該條線路在該研究時段的區(qū)間載客量，計算方法為在該斷面前所有站點上車人數(shù)減去下車人數(shù)。區(qū)間載客量反映該時段車內(nèi)乘客擁擠程度，進(jìn)而求出不同擁擠程度下所需發(fā)車次數(shù)。

(4)乘客舒適性

每個人與陌生人都存在一定的心理安全間距，當(dāng)間距小于可接受范圍，人會產(chǎn)生煩躁、不安、排斥等心理抗拒現(xiàn)象。因此，當(dāng)公交車內(nèi)過于擁擠時，人與人間距小于心理安全間距，乘客會產(chǎn)生心理抗拒現(xiàn)象，導(dǎo)致公交吸引力降低。

1.2 模型構(gòu)建

(1)假設(shè)條件

①出行人員到達(dá)站點規(guī)律服從均勻分布，不會被其他線路車輛干擾；

②研究線路所有車輛均依據(jù)運營計劃定時出站、到站運行；

③相同研究時段內(nèi)發(fā)車間隔相同。

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

對于公交公司，利益主要與收入掛鉤，將運營成本作為優(yōu)化目標(biāo)；對于乘客，搭乘公交希望在節(jié)約成本的同時有良好的出行體驗，采用乘客滿意程度作為優(yōu)化目標(biāo)。

①公交公司運營成本

將班次運行帶來的資源消耗費用與人工費用統(tǒng)一為車輛每行駛1 km 產(chǎn)生的費用，公交公司全天運營成本為

式中：Cb為一天內(nèi)公交公司運營總成本(元)；Cv為研究線路公交車運行1 km產(chǎn)生的費用(元)；L為研究線路總長度(km)；Tj為j時段總時長(min)；tj為j時段的發(fā)車間隔(min)；J為發(fā)車時段總數(shù)，發(fā)車時段數(shù)集合M={1 ,2,…,J} ，j為第j個研究時段。

②乘客滿意程度

乘客在公交出行中，對出行體驗感知最大的部分為站臺等車時間及乘車過程中車內(nèi)環(huán)境舒適程度。

將乘客等車時間造成的不滿意程度量化為乘客等車過程中損失的價值成本。對于正常上車無滯站乘客，乘客等車成本通過線路全天所有班次乘客等車時間總成本進(jìn)行度量。根據(jù)假設(shè)條件，每個乘客平均等車時間等于泊松分布期望值，平均1 min等車狀態(tài)下?lián)p失成本由城鎮(zhèn)居民人均可支配收入確定，全天候等車成本為

式中：Cp為研究線路全天所有班次乘客等車時間總成本(元)；Cw為每位乘客1 min等車狀態(tài)下的損失成本(元?min-1)，根據(jù)城鎮(zhèn)居民人均可支配收入確定；I為所研究線路總站點數(shù)，站點數(shù)集合N={1 ,2,…,I}，i為線路上第i個站點；Pij為第j個時段下位于i站點等車人數(shù)(人)。

乘客乘車過程舒適度與公交調(diào)度相關(guān)的是車內(nèi)擁擠程度。因此，通過乘客在車內(nèi)感受到的擁擠程度對自身舒適感差異，定義乘客在乘車過程中因擁擠造成的價值懲罰為擁擠成本。

用立席密度表征乘客活動空間，通過確定乘客開始感受擁擠時立席密度下限值及乘客無法忍受擁擠情況時的上限值及公交車有效站立面積，計算擁擠成本。當(dāng)乘客未感知到擁擠，不產(chǎn)生擁擠成本；當(dāng)乘客開始感受擁擠時，擁擠成本隨乘客數(shù)量增加而變大。當(dāng)車內(nèi)擁擠程度超過乘客忍受極限，擁擠成本懲罰值變?yōu)闊o窮大，即

式中：Bpd、Bpu分別為公交車內(nèi)載客人數(shù)引起乘客產(chǎn)生不適感時下限人數(shù)，不適感難以忍受的上限人數(shù)(人)；V為公交車輛有效站立面積(m2)；Vd、Vu分別為乘客開始感受到擁擠的立席密度下限值、乘客無法忍受擁擠情況的上限值(m2)。

式中：Ch為乘客擁擠成本(元)；Bpmax為該公交車上人數(shù)最多時的人數(shù)(人)；γ1、γ2為兩個狀態(tài)下對應(yīng)的擁擠度系數(shù)。

公交決策人員在權(quán)衡雙方利益時需要從不同角度考慮，通過賦予權(quán)重的方式實現(xiàn)，即

式中：Z為目標(biāo)函數(shù)；z1、z2為加權(quán)系數(shù)，z1、z2＞0且z1+z2=1。

1.3 約束條件及處理

模型滿足以下約束條件：

(1)收支平衡約束

在調(diào)度時至少要保障公交公司收入大于支出。

式中：Pu，ij為j時段i站點上車人數(shù)(人)。

(2)載客人數(shù)約束

為避免出現(xiàn)空載，需保證車輛平均滿載率不低于最低滿載率要求。同時，為保障乘客舒適體驗，乘客能夠一次上車避免滯留，需保證車內(nèi)最大乘車人數(shù)小于額定載客人數(shù)。

式中：Pcˉ為一趟班次平均滿載率；Pcmin為一趟班次平均最小滿載率；Pr為研究線路車輛額定載客人數(shù)(人)；Pc,i為一趟班次在第i個站點時車內(nèi)載客人數(shù)(人)。

通過懲罰函數(shù)將約束條件轉(zhuǎn)化為帶懲罰系數(shù)項加入目標(biāo)函數(shù)，即

式中：minZ′為帶懲罰項的新目標(biāo)函數(shù)；δ1、δ2、δ3為懲罰系數(shù)，取值大于0，根據(jù)實驗確定。

2 模擬退火-自適應(yīng)布谷鳥算法設(shè)計

布谷鳥算法[7]具有參數(shù)少、局部搜索能力強的優(yōu)點，但其搜索步長為定值，并且布谷鳥萊維(levy)飛行習(xí)性造成長距離步長占比較少，容易陷入局部最優(yōu)解，成為算法短板。

2.1 算法設(shè)計

(1)改進(jìn)算法步長

構(gòu)造步長值先大后小的自適應(yīng)步長，算法執(zhí)行前期，通過跨度大的步長擴(kuò)大搜索范圍；算法執(zhí)行后期，步長變小，在全局最優(yōu)范圍內(nèi)精細(xì)化求解，表示為

式中：Tmax為總迭代次數(shù)；tap為當(dāng)前迭代次數(shù)；α(t)為當(dāng)前迭代次數(shù)下步長值；αmin為最小步長；αmax為最大步長；t為迭代次數(shù)。

(2)增加退火操作

引入模擬退火算法中退火階段操作，使布谷鳥算法在更新鳥窩位置時存在接受較差解的概率，增加全局尋優(yōu)概率。退火過程為

式中：f0為當(dāng)前最優(yōu)解x0對應(yīng)目標(biāo)函數(shù)值；f0′為新解x′0所對應(yīng)目標(biāo)函數(shù)值；Tap為當(dāng)前狀態(tài)溫度。

2.2 算法流程

模擬退火-自適應(yīng)布谷鳥算法步驟如下：

Step 1 設(shè)置算法參數(shù)。包括：鳥巢個數(shù)N、發(fā)現(xiàn)概率Pa、迭代精度或次數(shù)Tmax、初始溫度T0、退火系數(shù)Tα、最低溫度Tmin、擾動次數(shù)Tk等參數(shù)，并初始化種群，計算相應(yīng)函數(shù)值，作為當(dāng)前最優(yōu)解。

Step 2 根據(jù)式(10)更新鳥窩位置，計算更新后鳥窩函數(shù)值，和上一代鳥窩函數(shù)值對比，保留當(dāng)前最好鳥窩。

Step 3 將較差一組鳥窩進(jìn)行模擬退火操作，若新解對應(yīng)函數(shù)值比現(xiàn)解更好，則更新當(dāng)前最優(yōu)解；否則，依照概率接受新解，并讓當(dāng)前溫度在退火系數(shù)Tα下執(zhí)行退火操作并更新當(dāng)前最優(yōu)解。

Step 4 對每個鳥巢，任選其他2 個不同鳥巢，按照文獻(xiàn)[7]位置更新公式計算。當(dāng)新解比舊解好時，更新當(dāng)前最優(yōu)解。

Step 5 記錄當(dāng)前最優(yōu)解，若滿足停止條件，輸出最優(yōu)解；否則，返回Step 2繼續(xù)尋優(yōu)。

2.3 仿真實驗

選取3個算法測試常用標(biāo)準(zhǔn)函數(shù)，驗證改進(jìn)算法尋優(yōu)性能，選取函數(shù)為

式中：x1、x2、xi為自變量；d為自變量x的總個數(shù)。具體參數(shù)如表1所示。

迭代結(jié)果如圖1所示。圖中，SA為模擬退火算法(Simulated Annealing)，CS 為布谷鳥算法(Cuckoo Search)，SA-ACS 為模擬退火-自適應(yīng)布谷鳥算法(Simulated Annealing-Adaptive Cuckoo Search)。由圖1可知，模擬退火-自適應(yīng)布谷鳥算法未陷入局部最優(yōu)解，在較小的迭代次數(shù)下逼近全局最優(yōu)解，具備求解全局最優(yōu)的能力，傳統(tǒng)布谷鳥算法的缺陷得到改善。因此，采用改進(jìn)的模擬退火-自適應(yīng)布谷鳥算法對公交調(diào)度模型優(yōu)化是可行的。

表1 測試函數(shù)屬性Table 1 Test function properties

3 模型應(yīng)用與驗證

福州市125 路公交線路途經(jīng)學(xué)校、商業(yè)區(qū)、工業(yè)區(qū)、行政區(qū)、大型居民區(qū)、醫(yī)院，以及風(fēng)景區(qū)，且與地鐵1 號、2 號線路重復(fù)率低，涵蓋各種出行目的，因此，選取該線路作為實例研究。

圖1 迭代結(jié)果Fig.1 Iterative results

3.1 線路客流特征

(1)客流區(qū)間劃分

以125路2020年10月15日-17日，即周二-周四客流為例，挖掘乘客刷卡數(shù)據(jù)獲取客流數(shù)據(jù)，各時段平均客流如圖2所示。

圖2 125路全天客流Fig.2 No.125 bus line throughout passenger flow

由圖2可知，125 路上、下行上車客流趨勢相近，故選用上行方向研究。

125 路運營時段為6:00-21:00，將運營時間分為：6:00-7:00，7:00-8:00，…，20:00-21:00，采用Fisher 最優(yōu)分割法對客流進(jìn)行處理，得到誤差函數(shù)變化，如圖3所示。

由圖3可知，當(dāng)分類數(shù)取7時，誤差值變化已經(jīng)非常小，故分類數(shù)取7 作為客流峰值劃分區(qū)間數(shù)。125路客流區(qū)間劃分如表2所示。

圖3 誤差函數(shù)曲線Fig.3 Error function curve

表2 125路客流區(qū)間劃分情況Table 2 Specific situation of section division of No.125 bus line passenger flow

(2)線路客流特征分析

125 路全天各站點客流情況如圖4所示?？芍?，從首站開始，直到第19 個站點，下車人數(shù)才逐漸高于上車人數(shù)，中途站點車內(nèi)載客人數(shù)一直處于較大狀態(tài)。若發(fā)車頻率低，可能造成第12 個站點至第18 個站點區(qū)間車內(nèi)乘客擁擠程度較高，導(dǎo)致乘客舒適度較低。

早高峰時段各站點上、下客及區(qū)間載客量情況如圖5所示。

圖4 125路全天各站點上下客情況Fig.4 No.125 bus line throughout day on and off at each station

由圖5可知，早高峰時段居民出行量大，前幾站上車人數(shù)多，較早產(chǎn)生擁擠情況，且擁擠過程持續(xù)時間長。因此，考慮乘客滿意程度，關(guān)注車內(nèi)最擁擠時客流峰值，保證最擁擠站點的乘客舒適度在乘客可接受范圍內(nèi)。

3.2 模型求解及分析

(1)模型及算法參數(shù)輸入

每公里公交車輛產(chǎn)生費用Cv、公交車有效站立面積V、座位數(shù)S由公交公司提供，結(jié)合文獻(xiàn)[8]，立席密度下限值、上限值分別為0.250、0.125，通過該取值計算得出Bpd、Bpu，Cw參照2019年福州市城鎮(zhèn)居民人均可支配收入，最低平均滿載率要求為座位數(shù)的70%，故Pcmin取15人，懲罰系數(shù)δ1、δ2、δ3經(jīng)試驗均取1000。經(jīng)反復(fù)試驗，步長更新參數(shù)λmin取0.005，具體參數(shù)及取值如表3所示。

圖5 早高峰時段各站點上、下客及區(qū)間載客量Fig.5 Loading and unloading and carrying capacity of morning peak period

(2)求解結(jié)果分析

通過調(diào)整權(quán)重，分析側(cè)重公交公司、乘客不同利益方情況下發(fā)車情況，按表4方案進(jìn)行仿真實驗。仿真結(jié)果如表5和圖6所示。

由圖6可知：

①改進(jìn)模擬退火-自適應(yīng)布谷鳥算法在求解結(jié)果及尋優(yōu)效率上均優(yōu)于傳統(tǒng)布谷鳥算法及模擬退火算法，模擬退火算法雖然在反復(fù)迭代下逼近全局最優(yōu)解，但尋優(yōu)效率要低于布谷鳥算法，驗證了改進(jìn)模擬退火-自適應(yīng)布谷鳥算法在算法性能上的優(yōu)越性。

②將實例仿真結(jié)果與實際調(diào)度情況相比，125路公交月均發(fā)車5479次，上行方向日均發(fā)車96次，各時段發(fā)車次數(shù)對比如圖7所示。

由圖7可知，不同權(quán)重比例下平峰時段發(fā)車次數(shù)均小于現(xiàn)狀發(fā)車次數(shù)，有效節(jié)約資源，驗證了算法在求解結(jié)果上的有效性。且高峰期發(fā)車頻率大于其他時期，10:00-16:00 發(fā)車次數(shù)最少，尋優(yōu)結(jié)果符合實際。

表3 模型及算法參數(shù)輸入Table 3 Value of model and algorithm parameters

表4 不同權(quán)重仿真方案Table 4 Simulation schemes with different weights

表5 各時段發(fā)車情況Table 5 Each time period starts

圖6 不同權(quán)重下的仿真結(jié)果Fig.6 Simulation results under different weights

(3)由仿真結(jié)果可知，z1、z2取值差異對仿真結(jié)果影響較大，當(dāng)z1大于z2，目標(biāo)函數(shù)更側(cè)重于公交公司利益，公交發(fā)車間隔大、發(fā)車頻率低。反之，發(fā)車間隔減小、發(fā)車頻率增大，目標(biāo)函數(shù)朝乘客利益傾斜。隨著發(fā)車次數(shù)增多，公交公司運營費用不斷提高，在進(jìn)行實際調(diào)度時，可根據(jù)不同線路實際情況，采用不同權(quán)重進(jìn)行調(diào)度安排。

圖7 發(fā)車次數(shù)對比Fig.7 Start times comparison

4 結(jié)論

本文以常規(guī)公交為研究對象，利用挖掘線路客流特征，減少模型假設(shè)條件。在模型指標(biāo)選取上，創(chuàng)新地考慮了基于乘客心理空間的乘車舒適性，將其轉(zhuǎn)化為擁擠成本進(jìn)行量化。設(shè)計了模擬退火-自適應(yīng)布谷鳥算法，使算法具備全局尋優(yōu)能力。以福州市125 路公交為例，求解基于Fisher 最優(yōu)分割法所劃分7 個時段的公交發(fā)車間隔，設(shè)置3 種不同權(quán)重方案對目標(biāo)函數(shù)進(jìn)行仿真，實驗結(jié)果表明，不同權(quán)重下模擬退火-自適應(yīng)布谷鳥算法的尋優(yōu)結(jié)果均為最佳，發(fā)車次數(shù)均小于現(xiàn)狀發(fā)車次數(shù)，并且仿真結(jié)果符合實際客流情況，驗證了優(yōu)化模型及算法的可行性。本文僅考慮常規(guī)公交調(diào)度，如何與城市軌道交通進(jìn)行協(xié)調(diào)調(diào)度將是未來研究方向。