考慮需求起訖點及需求等級的響應型社區公交行車調度優化

趙 靖,葛慶紅,韓 印

(上海理工大學 管理學院，上海 200093)

0 引言

社區規模逐漸擴大，大型社區居民出行“最后一公里”問題愈加凸顯，社區公交的出現有助于解決這一問題，極大地方便居民出行。為進一步滿足居民出行的個性化需求，有必要在目前的需求響應型公交的基礎上進行優化改進，提出一種響應型社區公交，對響應型社區公交行車調度進行優化，有助于減少公交公司的運營成本、居民的步行路程、等待時間，從而提高社區公交服務質量。

社區公交在現實生活中的主要功能是服務社區內部交通和接駁其他交通，優化社區公交的行車調度不僅能提高乘客出行滿意度，而且可以節約公交運營成本[1]。以往的社區公交調度大多沿用了常規公交調度方法，主要集中在固定線路公交的車輛調度上，通過公交時刻表來優化車輛發車間隔來為乘客提供高水平服務[2-5]。近年來，有不少學者開始以社區公交為研究對象對其行車調度進行優化，Verma[6]分析了區域內軌道交通線網的布設和現有的接駁公交運營狀況，基于此建立社區公交行車路徑優化模型，減少需求等待時間。Schittekat[7]針對校車這一特殊社區公交,考慮學生可以選擇的潛在站點，以公交行駛路程最小為目標建立了公交運營路徑規劃模型。Xiong等[8]采用啟發式算法求解了社區公交行車線路優化模型。張思林等[9]以接駁軌道交通的社區公交為研究對象，分析乘客選擇站點的影響因素，考慮公交運營成本和乘客在車時間、步行時間與候車時間的成本建立多目標優化模型研究了社區公交站點的布設。

學者在社區公交行車調度研究領域取得了不錯的成果，但現有的社區公交運營模式對需求波動的適用性不是非常好。為提高公共交通對乘客出行需求空間和時間分布波動性的適應能力，需求響應型公交被提出，提供了更為個性化的服務，更加方便了市民出行[10]。

需求響應型公交，在學界也被稱為定制公交、靈活型公交、可變線路公交[11-13]。關于需求響應型公交的行車調度[14-30]，ANK等[16]研究了需求不確定情況下的靈活型服務公交的線網規劃問題，提出了一種兩階段隨機規劃的解決方案。Nourbakhsh等[18]基于低需求水平區域研究了一種靈活型公交服務系統，以成本為評價指標建立優化模型求解靈活型公交的行車路徑選擇問題。Qiu F等[19]針對站點偏移式的靈活公交服務提出了一種動態站點策略，通過最優化途徑站點來確定車輛的最優行車路徑。Wei T等[20]考慮響應型公交計劃行程時間與實際行程時間存在差值，為減少車輛到站延誤，提出了一種協同調度模型，使模型具有一定的魯棒性。邱豐等[21]考慮動靜態需求對可變線路公交分兩階段建立了行車調度模型。潘述亮等[22]針對確定的車輛規模和需求，綜合考慮乘客和公交公司利益，并以此為目標建立了響應型公交協同調度優化模型。鄭漢等[25]分析了需求響應型公交服務效率和服務質量之間的矛盾，研究了多車型的響應型公交行車調度問題，以最小化使用車輛數目和步行距離建立數學模型，并通過案例分析對模型進行驗證。柳伍生等[26]從綠色交通的角度出發研究了多需求下的定制公交線網優化問題建立線網優化模型。王健等[27]以靜態需求對研究對象，考慮需求起訖點研究了多線路定制公交的調度問題。

學者對響應型公交行車調度做了豐富研究，但以往研究中對于出行需求均假設所有需求都預先給定，較少考慮運行過程中的動態需求，對需求起訖點一般只考慮出行起點需求的響應，出行終點是固定站點，對出行起終點均響應的研究較少，也未檢索到同時考慮動態需求和需求起訖點的響應型公交調度模型。對于需求等級，由于以往研究需求均預先給定，未對不同時刻提出的需求進行等級劃分。針對上述研究的不足，本研究提出一種新的響應型社區公交，統籌考慮需求起訖點、需求等級、動態需求，研究該社區公交的行車調度優化，用來解決社區公交運營中存在的乘客等待時間長、步行距離長、服務時段不合理等問題。

1 優化方法的基本思想

1.1 基于需求起訖點的響應型社區公交

常規的社區公交發車時間固定，運營線路固定，停靠站點固定。其特征主要有：(1)主要功能是服務社區內部交通與接駁其他交通；(2)單次運營線路里程較小；(3)站點密度要求高。

需求響應型公交運營線路由需求決定。本研究在站點偏移式公交的基礎上考慮需求的起訖站點對其運營模式進行優化，將傳統的公交站點分割成上車站點和下車站點，車輛根據需求信息行駛至有需求的站點接客，途中僅經過需求信息中的下車站點，具體如圖1所示。

圖1 基于需求起訖點的響應型社區公交運營Fig.1 Responsive community transit operation based on demand OD

針對社區公交特征，本研究將通過終點站、備選站點和設置運營里程約束進行應對。對于社區公交的接駁功能，通過將其他交通換乘站點設置為需求響應型社區公交的起終點站，實現接駁功能，并且布設高密度備選站點，這些備選站點可根據社區內潛在交通產生吸引點設置，包含居民住宅、超市、醫院、學校等社區居民出行密度較大的區域。在下述模型中，乘客可以根據實際需求在高密度的備選站點中進行選擇。此外，接下來的模型中將考慮車輛單次運營的最長、最短里程，以適應社區公交的特征。

乘客通過手機客戶端或短信發送上車站點、下車站點和接受服務的時間窗等需求信息進行預約出行，公交公司收到請求后將考慮需求等級及相關規則后來判斷是否響應，并將最終結果反饋給乘客，若不響應，公交公司會建議乘客等待下一班次車輛，乘客根據反饋結果決定是否接受建議，并將最終決定反饋至公交公司。

1.2 基于需求等級的響應規則

在車輛行車調度前，對第k班車需要考慮的需求進行分析，如表1所示。

表1 第k班車需求Tab.1 Demand for the kth bus

為避免產生二次等待影響乘客出行，情形Ⅰ的需求，車輛必須響應，優先級最高。情形Ⅱ的需求在情形Ⅰ需求的基礎上根據評價指標的變化進行選擇性響應，優先級僅次于情形Ⅰ的需求。情形Ⅲ的需求發生在情形Ⅰ和Ⅱ需求的后面，在前兩種需求的基礎上，考慮接受此需求后能否進一步優化評價指標，從而來判斷是否接受該點的需求，若可以，則將該需求點考慮到本班次公交的行駛路線中；若不可以，則將該需求點考慮到下一班次公交的行駛路線中。若本次班車已行駛過了該需求預約點，該預約需求點將直接放到下一班車中考慮，故情形Ⅲ的需求優先級最低。

2 行車調度優化模型

2.1 行車調度流程

如上所述，將發車前的預約需求定義為靜態需求(即情形Ⅰ需求、情形Ⅱ需求)，發車后產生的預約需求定義為動態需求(即情形Ⅲ需求)，基于此可以分別建立兩階段行車調度模型(靜態和動態)。兩階段行車調度流程如圖2所示。

圖2 需求響應型社區公交行車調度流程圖Fig.2 Flowchart of demand responsive community transit scheduling

2.2 評價指標

選取空載率最小，乘客不滿意度最小，單次運營里程(歸一化)最小作為目標建立模型。

2.2.1空載率

空載率是指公交的剩余載客容量與公交的額定載客容量比值，如式(1)所示。

(1)

式中，N1為需求點數量；qij為i需求站點上車至j需求站點下車人數；C為公交車輛的額定載客容量；xi,yij為0-1變量，分別如下所示。

2.2.2乘客不滿意度

居民的預約需求被響應后，車輛不能保證在所有乘客期望的時間區間內到達。為盡可能保證公交的準點率和提升乘客乘坐滿意度，本研究從乘客角度出發采取軟時間窗對車輛的到達時間進行約束。

軟時間窗是指車輛能在乘客的期待服務時間窗[Pdi,Qdi]內到達i需求站點時，乘客的滿意度為1；若車輛的到達時間ti早于Pdi或晚于Qdi時，乘客的滿意度將逐漸減小。在可接受的時間窗[Pi,Pdi]和[Qdi,Qi]內，乘客的滿意度將由1逐漸減小到0；在不能接受的時間窗[0,Pi]和[Qi,+∞]內，乘客的滿意度將一直為0。假設乘客不滿意度的波動是按線性變化的[31-32]，對應的乘客不滿意度如式(2)所示。

(2)

考慮不同乘客出行目的不同，將[Pi,Pdi]和[Qdi,Qi]的取值完全交給乘客自主選擇，乘客在提交預約需求信息時可以根據自己的出行目的確定上述時間窗，從而滿足乘客對時間的個性化要求。如圖3所示，虛線線條表示j乘客的不滿意度曲線，實線線條表示i乘客的不滿意度曲線，可以看出，i乘客對時間的要求比j乘客對時間的要求更高。

圖3 乘客不滿意度函數圖Fig.3 Curve of passenger dissatisfaction function

2.2.3單次運營里程歸一化

單次運營里程歸一化后如式(3)所示。

(3)

式中，dij為路網中i需求站點到j需求站點的最短路徑距離；Dmin為社區公交單次運營的最短里程；Dmax為社區公交單次運營的最長里程；zij為0-1變量，如下所示：

2.3 響應型社區公交第1階段靜態調度模型

所有車輛每次必須從起始站出發，終點站停車。k班車需要考慮的需求即上述情形Ⅰ、情形Ⅱ、情形Ⅲ中的需求，這3種預約需求分別用集合M1，M2和M3表示。

第1階段靜態調度的目標函數如式(4)所示。

i∈M1∪M2。

(4)

式(4)由3部分組成，分別是空乘率、乘客不滿意度、單次運營里程。式中，NⅠ為靜態階段的需求點數量；f2i為i號需求站點上乘客的不滿意度。

約束有需求響應約束，要求k-1班次沒響應的需求站點在本班次中必須被響應；且對于任一需求，其對應的上、下車需求站點均應響應，分別如式(5)、式(6)所示：

(5)

(6)

公交車輛載客容量約束，要求第k班次車輛到達需求i時的車內人數不超過車輛的額定載客數，如式(7)所示。

?i,j,l∈M1∪M2。

(7)

公交車輛到達時刻約束，車輛到達需求j的時刻的計算方法如式(8)所示。

i,j,l∈M1∪M2,

(8)

式中，v為公交車輛的平均行駛速度；tu為乘客的平均上車時長；td為乘客的平均下車時長。

2.4 響應型社區公交第2階段動態調度模型

第1階段行車調度(靜態)中必須經過的預約需求用集合M4表示(M4?M1∪M2)，在發車前規劃出一條最優線路將M4中的預約需求點連接起來。第2階段調度(動態)要以第1階段調度(靜態)的行駛線路為初始線路，公交發出時遵循初始線路運營，若有動態需求發出申請，考慮動態需求申請時刻與車輛此刻的位置，借助相關算法來決定是否將該預約需求點放到初始線路中，同時將車輛的運營線路進行實時更新。

第2階段動態調度的目標函數如式(9)所示。

i∈M3∪M4,

(9)

式中，NⅡ為動態需求點的數量；M3為動態需求集合。

約束有需求響應約束，要求第1階段行車調度中已決定響應的需求站點在第2階段動態調度中必須被響應，且對于任一需求，其對應的上、下車需求站點均應響應，分別如式(10)、式(11)所示。

(10)

(11)

公交車輛載客容量約束，要求第k班次車輛到達需求i時的車內人數不超過車輛的額定載客數，如式(12)所示。

?i,j,l∈M3∪M4。

(12)

公交車輛到達時刻約束，車輛到達需求j的時刻的計算方法如式(13)所示。

i,j,l∈M3∪M4。

(13)

動態需求發出時刻約束，要求動態需求i發出需求申請的時間要早于車輛到達i需求站點前方j站點的到達時間，從而保證車輛駕駛人員在行駛至下一站點前有時間做出是否調整線路的決定，如式(14)所示。

tjyjixj≥dti

j∈M4，i∈M3,

(14)

式中dti為動態需求i發出需求申請的時間。

若響應某動態需求后目標函數值得到優化，則重新規劃線路行駛，否則按照初次規劃的線路行駛，即第2階段行車調度模型的目標函數值不能大于第1階段行車調度的目標函數值，如式(15)所示：

z2≤z1。

(15)

3 案例分析

3.1 算法選擇

遺傳算法借鑒生物領域上的優勝劣汰，適者生存遺傳機制，模擬染色體的選擇、交叉、變異，生成有用的解決方案進行優化、搜索問題。量子計算的計算速度較快，量子狀態較多，求解時陷入局部最優解的概率較小。量子遺傳算法綜合了上述優點，所以選取量子遺傳算法進行模型求解。下述案例中，量子遺傳算法的相關參數參數選擇如下：最大代數為500；交叉概率0.9；變異概率0.3；群體規模30；染色體量子位數為2；染色體串長按需求數量取；量子旋轉角度為0.01pi。

3.2 案例分析

3.2.1相關數據收集

本研究以上海市寶山區溫泰線社區公交為研究對象，其現有的運營模式為定時發車定點停車的固定式公交運營，研究區域簡化為一個矩形，其長為橫向邊界距離3.4 km,寬為縱向邊界距離1.4 km，如圖4所示。

圖4 社區公交線路Fig.4 Community transit route

現有的社區公交車輛有兩種車隊規模：1輛18座、4輛20座。公交發車間隔為15 min，平均行駛速度為35 km/h，線路總長4.3 km，周邊為住宅區集聚地，主要服務的小區為泰和新城、共富小區、顧村家園、成億寶盛家苑等。該線路自運營起，方便了居民出行，但運營中存在的公交公司運營虧損、乘客等待時間長、線路覆蓋范圍不完善等問題需要繼續解決。首先，對周邊居民的出行方式進行調查，調查結果如圖5所示。

圖5 周邊居民出行方式分布Fig.5 Distribution of peripheral residents’ trip ways

從圖中可以看出目前社區公交占出行方式的11.2 %，高峰時段(06：30—08：30、16：30—18：30)周邊小區的平均出行密度為860人/h。乘客可接受步行距離設定為0.4 km，乘客的平均上車時長tu為5 s，平均下車時長td為3 s。

3.2.2第1階段模型輸入

以早第1班(06：30)社區公交為例，基于相關數據的收集，在上述矩形路網上利用MATLAB軟件隨機生成一系列有預約需求的站點和人數，需求人數取高峰期發車間隔內乘坐社區公交居民數量的均值，需求分布如圖6所示。

圖6 第1階段預約需求點分布圖Fig.6 Distribution of reservation demand points in stage 1

1號點為社區公交起始站，3號點為社區公交終點站。各預約需求的預約時間信息如表2所示。第1階段需求起訖站點信息如表3所示，采用Floyd算法求得路網中第1階段各需求站點間的最短路徑距離如表4所示。

表2 第1階段靜態需求點時間窗信息Tab.2 Static demand point (stage 1) time window information

表3 第1階段需求起訖站點信息Tab.3 Demand OD information in stage 1

3.2.3第一階段模型求解

借助數學軟件MATLAB2018a求解得到的結果：發車車型為18座型公交車輛，第1階段靜態調度的最優路徑為：1-5-9-6-8-10-2-12-4-7-3，社區公交行駛路徑如圖7所示。最優解的目標函數值為：1.070 6。

表4 第1階段各需求站點間最短路徑距離Tab.4 The shortest route distance between demand stations in stage 1

圖7 第1階段靜態調度路徑圖Fig.7 Static scheduling route (stage 1)

3.2.4第2階段模型輸入

第2階段的動態調度是在第1階段的靜態調度基礎上進行的，在路網上隨機生成動態預約需求如圖8所示。

圖8 第2階段動態需求分布圖Fig.8 Dynamic scheduling route(stage 2)

第2階段新增的動態需求點信息如表5所示。各動態需求起訖站點信息如表6所示。采用Floyd算法求得路網中第2階段各需求站點間的最短路徑距離如表7所示。

3.2.5第2階段模型求解

相關算法參數取值與第1階段靜態調度類似，求得最優解的目標函數值為：0.981 8。第2階段行車調度的最優路徑為：1-14-5-9-6-15-8-10-16-2-12-4-18-7-3，社區公交行駛路徑如圖9所示。

表5 第2階段動態需求點信息Tab.5 Dynamic demand point (stage 2) time window information

表6 第2階段需求起訖站點信息Tab.6 Demand OD information in stage 2

3.2.6結果分析

將上述靜態與動態需求信息放入當前固定線路式路社區公交運營中。考慮對象為同一班次車輛(6：30)，不考慮下一班車的運營，即沒趕上這一班車的乘客數會影響空載率。居民期望乘車時間區間的均值作為居民到達公交車站的時間，本班次的車輛在這個時間或這個時間之后到達該站點，乘客均可以上車；居民的平均步行速度取4.5 km/h,步行到站時間視為乘客耗費的等待時間(即乘客到站時間減去步行時間為模型中的Pi，乘客到站時間加上步行時間為模型中的Qi)；社區公交的單次運營里程為常數4.3 km，其他參數和評價指標的計算方法與模型中相同。求解得到的結果為1.575 4，而本研究中模型得到的結果為0.981 8，評價指標相對優化了37.68%，優化效果顯著。

表7 第2階段各需求站點間最短路徑距離Tab.7 The shortest route distance between demand stations in stage 2

圖9 第二階段動態調度路徑圖Fig.9 Dynamic scheduling route (stage 2)

以往響應型公交行車調度模型的評價指標大多選取價格來衡量公交公司和乘客的成本，對乘客時間成本的差異性與不穩定性考慮不全，且未判斷公交公司成本價格與乘客成本價格兩者之間是否獨立；本研究的模型在評價指標上也統籌考慮了乘客和公交公司利益，選取的是空載率、乘客不滿意度和單次運營里程作為評價指標，并對評價指標歸一化后整合成了單指標優化模型。在約束上，本研究的模型基于需求起訖站點的分析可使車輛不必每次經過所有固定站點，并通過劃分需求等級來避免乘客產生二次等待；以往模型通常采用硬時間窗約束車輛到達需求點時間，而本研究中的模型采用軟時間窗來約束車輛到達時間，并刻畫乘客滿意度，相對符合實際生活中乘客等車場景。

4 結論

(1)針對社區公交運營中乘客等待時間長、步行時間長、服務時段不合理等問題，提出了一種響應型社區公交及其行車調度方法，并基于路網建立了響應型社區公交行車調度優化模型，當設置的起訖站點密度足夠大時，能相對實現居民“零步行”乘車。建立的兩階段調度優化模型是在給定發車時間的情況下，對需求響應和行駛路徑進行優化，適用于乘客需求信息完備的情況，包括乘客起訖站點和可接受時間窗。

(2)針對需求的波動，在常規社區公交上增加需求響應這一特點，在需求響應型公交的基礎上考慮乘客出行的起訖站點，使得車輛不必每次都經過所有固定站點,并劃分需求等級避免乘客產生二次等待。綜合考慮乘客和公交公司利益，以單次運營里程、乘客不滿意度、空載率作為評價目標，分兩階段建立了靜態、動態調度模型，對需求的考慮全面，在靜態調度模型的基礎上實現動態調度。將此響應型社區公交及其行車調度模型應用于文中案例，評價指標的優化效果達到了37.68%。模型中的站點構成包括了公交起始站、終點站和中間備選站點，這些站點可以根據需要靈活設置，對于循環式公交，需要將起始站、終點站設成同一個站點，因此本模型也適用于循環式公交行車調度。

(3)行車調度模型中采用最大/最小單次運營里程對車輛到達終點站的時間進行約束，當決策者設置的最大運營里程值過大時，將減小車輛的空載率，但對先上車且目的地在終點站的乘客不利；當最大運營里程值設置的過小時，單次運營里程會得到減小，但不利于公交公司和未上車乘客。所以在實際應用中，決策者設置最大運營里程時要綜合考慮上述影響。

(4)本研究建立的模型中忽略了社區其他交通和道路設計參數對響應型社區公交車輛行駛的影響，未來的研究可針對此不足進行。