基于乘客換乘需求的重疊線路公交調度優化

馮樹民，廖嘉雯，趙 琥

(哈爾濱工業大學 交通科學與工程學院，哈爾濱 150090)

科學合理的公交時刻表有利于提高公交系統運營效率、增加公交出行吸引力。針對公交時刻表優化問題，國內外學者進行了大量研究，目前研究主要集中在單線路調度和區域調度兩方面。單線路調度方面，文獻[1-2]主要以乘客出行時間和公交企業運營成本最小為優化目標，對發車頻率進行優化；文獻[3]提出了“滿意度的概念”，對乘客候車時間、車廂擁擠程度及公交企業利潤之間的量綱進行了統一，建立了發車間隔優化模型，并采用一維搜索法進行求解；文獻[4-5]采用遺傳算法對公交調度優化問題進行了求解。區域調度方面，公交協同換乘研究引起了很多學者的關注，主要以乘客同步換乘概率最大或乘客換乘候車時間最小為優化目標，構建優化模型，文獻[6]首次提出了同步換乘的概念，文獻[7]在文獻[6]基礎上以車輛駐站時間和發車間隔為優化變量，車輛在換乘站點相遇次數最大為優化目標建立了優化模型；文獻[8]引入換乘站點重要度和線路換乘吸引度兩個指標來研究公交乘客時刻表優化問題，以乘客換乘過程中候車時間最短為優化目標對發車時刻表進行優化；文獻[9]在考慮車輛容量限制的條件下，以換乘點之間平均換乘時間最小為優化目標構建了優化模型。

近幾年，隨著城市公交線網規模的擴大，線路重疊現象非常普遍，部分學者對公交線路重疊區段運行車輛優化調度研究進行了嘗試，文獻[10-11]針對重疊區段上乘客選擇行為，基于乘客選擇概率分布理論構建了客流分配模型；文獻[12]對重疊線路進行聯合調度，使各線路車輛在重疊區段載客量均衡；文獻[13]基于雙層規劃、Logit模型等基礎理論，建立了考慮重疊區段客流特征的車輛配置協同優化模型；文獻[14]研究了多運營商在重疊區間公交調度優化問題，并對重疊區間線路客流競爭關系進行了深入研究；文獻[15]通過調整發車頻率同步多組公交線路到站時刻，使同步站點的乘客候車時間和公交運營成本降到最低，引入時間索引將其轉化混合整數線性規劃問題進行求解；文獻[16-17]基于重疊線路間的競爭關系，分別提出了基于全程車和跨站車的混合公交調度方法和基于乘客出行數據的多車型調度方法。

通過以上文獻梳理發現，對單線路公交調度和區域公交調度的研究已較為成熟，對重疊線路系統內公交協同調度研究較少，且現有研究僅主要集中在重疊線路間客流競爭關系，較少涉及重疊區間乘客協同換乘。基于此，以乘客總出行時間最短和公交運營成本最小為優化目標，建立考慮乘客換乘的重疊線路公交調度優化模型。以哈爾濱市3條重疊公交線路為案例，運用提出的優化模型對重疊區段運行的公交車輛進行優化調度，設計遺傳算法對模型進行求解，驗證模型的可行性。

1 乘客分類

為了便于對乘客的候車行為進行數學描述，根據乘客乘車起訖站點與重疊區段的相對位置關系，將乘客劃分為三類：1)出行起訖點均位于重疊區段內的為第一類乘客，如圖1(a)所示，第一類乘客可乘坐重疊區段內任一線路的車輛完成出行任務，針對該類乘客，重疊區段內的線路之間存在競爭關系；2)需要在重疊區段內站點進行換乘的乘客為第二類乘客，如圖1(b)所示，第二類乘客的出行起訖點分別位于不同線路的非重疊區段，需要通過在重疊區段內換乘才能完成出行任務，重疊區段內的線路間存在合作關系；3)出行起訖點位于同一線路上且起點和訖點至少一個不在重疊區段上的乘客為第三類乘客，如圖1(c)所示，第三類乘客只能乘坐該特定線路的車輛完成出行任務，針對該類乘客，重疊區線路間既不存在競爭也不存在合作關系。

由于存在容量限制，當車輛到站后，站點的候車乘客包括兩部分：1)當前候車時段內到達的乘客，即前一車輛離開站點后到達站點的乘客；2)上一候車時段滯留乘客，即由于容量限制，未能乘坐前車而在車站滯留的乘客。

圖1 乘客出行路線示意圖

以線路i車輛m在站點s接載乘客為例，基于“先到先服務”原則的站點乘客滯留人數計算過程如下。

輸入：每條線路的發車間隔和首車發車時間、各類乘客在各站點的到達率及下車比例等數據。

圖2 三類乘客站點候車人數變化曲線

2 問題描述與建模

2.1 問題描述及參數定義

以I條重疊線路為建模研究對象，以乘客總出行時間(包括候車時間和車上時間)最小和公交運營成本最小為優化目標，以線路首車發車時刻和發車間隔為決策變量，建立重疊線路公交發車間隔協同優化模型。通過對決策變量進行優化，調整各線路車輛到達重疊站點的順序和時間差，以此提高公交服務水平和降低公交運營成本。基于實際場景，作如下簡化和假設：1)在研究時段內，乘客均勻到達站點；2)不同線路公交車車型、票價均相同；3)在研究時段內，公交車輛勻速運行。

2.2 乘客總出行時間分析

乘客總出行時間由候車時間和乘客車內時間構成。乘客車內時間為

(1)

乘客候車時間與站點乘客到達規律有關，當乘客均勻到達時，每位乘客的平均候車時間為連續公交車頭時距的一半[18]，三類乘客候車總時間計算表達式如下。

1)第一類乘客候車總時間為

(2)

式中：Δti,m,s指線路i車輛m在站點s與前車的車頭時距，所有線路車輛按同一站點到站時間進行升序排列，線路i車輛m在站點s的新車序可通過映射f(i,m)得到，則Δti,m,s=tf(i,m),s-tf(i,m)-1,s。

(3)

(4)

(5)

3)第三類乘客候車時間及換乘乘客等候第一輛車的時間為

(6)

1.探索實施領導干部業績成果公示制度。工作業績能很好地反映出領導干部的工作能力強弱、執政水平高低，通過對各級領導干部工作業績的公示，與相同、相近崗位工作業績的比較，給領導干部增加競爭壓力，促進領導干部不斷加強自身建設，提高領導水平和執政能力。

2.3 發車間隔協同優化模型的構建

以乘客總出行時間最小和公交運營成本最小為優化目標構建重疊線路發車間隔協同優化模型為

minW=W1+W2+W3+WOC

(7)

(8)

s.t.

tmin≤ti≤tmax, ?i∈I

(9)

(10)

(11)

(12)

式(7)、(8)是問題的目標函數，式(7)表示乘客總出行時間最小化；式(8)表示公交運營成本最小化，Ci為線路i單位里程運營成本，包括固定折舊維修成本、人員工資成本、停靠怠速成本及運行能耗成本[19]。式(9)～(12)為約束條件，式(9)為發車間隔約束，公交發車間隔須滿足最大和最小發車間隔限制；式(10)為始發站首車發車時間約束，公交線路首車發車時間作為優化變量時須小于發車間隔取值；式(11)為0-1變量約束，用于判斷兩線路是否構成換乘關系，線路i與線路j表示不同線路時Xi,j為1，否則為0；式(12)為0-1變量約束，當滿足tj,n-1,s

3 模型求解

所提出的考慮乘客換乘的重疊線路發車間隔協同優化模型屬于非線性整數規劃問題，是一類典型的NP-hard問題，其計算量隨著重疊線路數量的增多而呈指數形式增長。因此，該類問題通常采用可同時保證計算速度和計算精度的啟發式算法求解。遺傳算法具有過程簡單、計算時間少、魯棒性高、延展性強等優點，故采取遺傳算法對本模型進行求解。

本模型采用遺傳算法進行求解，算法流程如圖3所示，決策變量為重疊線路的發車間隔和首車發車時間，采取多參數級聯編碼的方式進行組合編碼，其求解步驟如下。

步驟1輸入客流特征數據及算法參數數據。

步驟2生成原始線路首車發車時刻及發車間隔，得到初始種群。

步驟3評價個體適應度。引入權重系數，計算系統總成本，將多目標規劃轉化為單目標優化，構造適應度函數，如式(13)所示。α、β分別為乘客出行總成本和公交運營成本的期望權重，滿足α+β=1，0≤α≤1，0≤β≤1。

minZtotal=α·θ·(W1+W2+W3+WOC)+β·C

(13)

步驟4判斷是否滿足迭代終止條件。若滿足，跳到步驟6;若不滿足，轉至步驟5。

步驟5進行選擇、交叉、變異等操作形成新個體，操作完成后轉步驟3。

步驟6程序結束，輸出滿意解。

圖3 遺傳算法流程圖

4 算例分析

4.1 算例簡述

選取哈爾濱市98路、106路、114路公交為仿真研究對象，圖4展示了這3條線路的重疊區段分布情況，重疊區段內共有12個重疊站點。以11：00—12：00為調查時段，采用人工調查法獲得各站點的上下車乘客數，根據上車客流和乘客下車概率表推算各公交線路的OD客流數據表，根據三類乘客的起訖點特征，分別得到各類乘客的上車乘客數，進而可得到其到達率，經統計三類乘客的客流比例為0.18∶0.05∶0.77。參數設置如下：最小發車間隔tmin和最大發車間隔tmax分別取3 min和20 min，研究時段內的總時間T為60 min，乘客候車平均成本θ為0.32 元/min，權重系數α=0.6、β=0.4，各線路車輛單位距離運營成本為13.6 km/h，公交車額定載客數B為100 人，其他公交線路信息見表1。

圖4 重疊區段示意圖

表1 公交線路信息

4.2 算例求解

以所建立的發車間隔協同優化模型為依據，結合3條公交線路的相關數據，利用遺傳算法進行求解。為了確定遺傳算法基本參數進行了大量的實驗，最終得到如下較好的參數取值，其中種群規模為20、交叉概率為0.7、變異概率為0.1、最大迭代次數為150。優化方案1發車間隔不變，以首車發車時間為優化變量；優化方案2以首車發車時間和發車間隔為優化變量。對兩種優化方案進行求解并與原方案對比，其中乘客出行時間指標對比結果見表2，調度方案成本指標對比結果見表3，遺傳算法迭代過程如圖5、6所示。

由表2和表3可知，優化方案1僅以線路首車發車時間為優化變量，優化效果有限，第二、三類乘客候車時間分別下降12.9%和7.7%，第一類乘客候車時間上升8.5%，這是由于第一乘客所占比重較小，在優化過程中未能起到決定性作用；優化方案2以首車發車時間和發車間隔為優化變量，可尋求到更佳滿意解，優化效果較為明顯，公交運營成本降低了15.2%，第一、二、三類乘客候車總時間分別減少了3.2%、33.2%、18.6%，乘客車上時間變化不大，優化后的發車時刻表見表4。

表2 乘客出行時間指標對比

表3 調度方案成本指標對比

圖5 優化方案1遺傳算法迭代過程

圖6 優化方案2遺傳算法迭代過程

表4 優化方案2發車時刻表

4.3 敏感性分析

不同城市人均收入水平存在差距，乘客的單位時間價值也不相等。研究以線路首車發車時間和發車間隔為優化變量時乘客單位時間價值θ變化對各類乘客候車時間、乘客車上時間、乘客出行總時間、公交運營成本和系統總成本的影響。θ以0.2的步長由0.1逐漸增加至1.5，其余輸入參數取值不變，決策變量為常數且為最優解。圖7展示了不同θ值下各指標的變化情況(θ=0.1時各項指標值為基數1，取其他θ值時各項指標值進行相應換算)。由圖7可知：1)隨著θ逐漸增大，三類乘客候車時間及乘客候車總時間呈下降趨勢，公交運營成本及系統總成本呈上升趨勢；2)由于線路站間距、車輛速度、乘客到達率不變，僅第一類乘客在重疊線路上的客流分配發生了變化，故乘客車上時間變化不大；3)三類乘客候車時間的變化趨勢基本相同，在其他條件不變的情況下，乘客總出行時間成本占系統總成本的比例與θ值正相關，隨著θ值增大，優化結果中各線路發車間隔取值減小，各類乘客的候車時間隨之減小。

(a) W1、W2、W3與θ的關系

(b) WOC、W、C、Ztotal與θ的關系

5 結 論

1) 建立了一種考慮乘客換乘行為的重疊區公交車輛調度優化模型，通過哈爾濱市3條重疊公交線路對模型進行了驗證，采用兩種優化方案，將兩種優化方案中乘客出行時間與優化前對比可得，同時優化首車發車時刻和車輛發車間隔，可以減少乘客出行時間，降低公交運營成本，乘客總出行時間降低了6.7%，公交運營成本降低了15.2%。

2) 考慮到乘客換乘過程中乘客候車時間計算的復雜性，根據公交乘客出行起訖點與重疊區域的位置關系，將乘客分為三類，基于三類乘客各自換乘行為特性，分別構建了三類乘客各自候車時間的數學表達式，使乘客出行時間的計算更加合理，同時結合公交實際運營成本需求，完成公交車輛調度合理優化，減低了公交運營成本，改善了公交運營現狀。

3)考慮到模型的可移植性，對乘客單位時間成本進行敏感性分析，結果表明，三類乘客候車時間的敏感性變化趨勢大體相同，三類乘客候車時間對乘客單位時間的變化均表現為彈性，乘客車上時間及乘客總出行時間則表現為非彈性。