基于乘客換乘需求的重疊線路公交調(diào)度優(yōu)化

馮樹民，廖嘉雯，趙 琥

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

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

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

通過以上文獻梳理發(fā)現(xiàn)，對單線路公交調(diào)度和區(qū)域公交調(diào)度的研究已較為成熟，對重疊線路系統(tǒng)內(nèi)公交協(xié)同調(diào)度研究較少，且現(xiàn)有研究僅主要集中在重疊線路間客流競爭關(guān)系，較少涉及重疊區(qū)間乘客協(xié)同換乘?；诖耍猿丝涂偝鲂袝r間最短和公交運營成本最小為優(yōu)化目標(biāo)，建立考慮乘客換乘的重疊線路公交調(diào)度優(yōu)化模型。以哈爾濱市3條重疊公交線路為案例，運用提出的優(yōu)化模型對重疊區(qū)段運行的公交車輛進行優(yōu)化調(diào)度，設(shè)計遺傳算法對模型進行求解，驗證模型的可行性。

1 乘客分類

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

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

圖1 乘客出行路線示意圖

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

輸入：每條線路的發(fā)車間隔和首車發(fā)車時間、各類乘客在各站點的到達(dá)率及下車比例等數(shù)據(jù)。

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

2 問題描述與建模

2.1 問題描述及參數(shù)定義

以I條重疊線路為建模研究對象，以乘客總出行時間(包括候車時間和車上時間)最小和公交運營成本最小為優(yōu)化目標(biāo)，以線路首車發(fā)車時刻和發(fā)車間隔為決策變量，建立重疊線路公交發(fā)車間隔協(xié)同優(yōu)化模型。通過對決策變量進行優(yōu)化，調(diào)整各線路車輛到達(dá)重疊站點的順序和時間差，以此提高公交服務(wù)水平和降低公交運營成本?；趯嶋H場景，作如下簡化和假設(shè)：1)在研究時段內(nèi)，乘客均勻到達(dá)站點；2)不同線路公交車車型、票價均相同；3)在研究時段內(nèi)，公交車輛勻速運行。

2.2 乘客總出行時間分析

乘客總出行時間由候車時間和乘客車內(nèi)時間構(gòu)成。乘客車內(nèi)時間為

(1)

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

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.探索實施領(lǐng)導(dǎo)干部業(yè)績成果公示制度。工作業(yè)績能很好地反映出領(lǐng)導(dǎo)干部的工作能力強弱、執(zhí)政水平高低，通過對各級領(lǐng)導(dǎo)干部工作業(yè)績的公示，與相同、相近崗位工作業(yè)績的比較，給領(lǐng)導(dǎo)干部增加競爭壓力，促進領(lǐng)導(dǎo)干部不斷加強自身建設(shè)，提高領(lǐng)導(dǎo)水平和執(zhí)政能力。

2.3 發(fā)車間隔協(xié)同優(yōu)化模型的構(gòu)建

以乘客總出行時間最小和公交運營成本最小為優(yōu)化目標(biāo)構(gòu)建重疊線路發(fā)車間隔協(xié)同優(yōu)化模型為

minW=W1+W2+W3+WOC

(7)

(8)

s.t.

tmin≤ti≤tmax, ?i∈I

(9)

(10)

(11)

(12)

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

3 模型求解

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

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

步驟1輸入客流特征數(shù)據(jù)及算法參數(shù)數(shù)據(jù)。

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

步驟3評價個體適應(yīng)度。引入權(quán)重系數(shù)，計算系統(tǒng)總成本，將多目標(biāo)規(guī)劃轉(zhuǎn)化為單目標(biāo)優(yōu)化，構(gòu)造適應(yīng)度函數(shù)，如式(13)所示。α、β分別為乘客出行總成本和公交運營成本的期望權(quán)重，滿足α+β=1，0≤α≤1，0≤β≤1。

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

(13)

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

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

步驟6程序結(jié)束，輸出滿意解。

圖3 遺傳算法流程圖

4 算例分析

4.1 算例簡述

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

圖4 重疊區(qū)段示意圖

表1 公交線路信息

4.2 算例求解

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

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

表2 乘客出行時間指標(biāo)對比

表3 調(diào)度方案成本指標(biāo)對比

圖5 優(yōu)化方案1遺傳算法迭代過程

圖6 優(yōu)化方案2遺傳算法迭代過程

表4 優(yōu)化方案2發(fā)車時刻表

4.3 敏感性分析

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

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

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

5 結(jié) 論

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

2) 考慮到乘客換乘過程中乘客候車時間計算的復(fù)雜性，根據(jù)公交乘客出行起訖點與重疊區(qū)域的位置關(guān)系，將乘客分為三類，基于三類乘客各自換乘行為特性，分別構(gòu)建了三類乘客各自候車時間的數(shù)學(xué)表達(dá)式，使乘客出行時間的計算更加合理，同時結(jié)合公交實際運營成本需求，完成公交車輛調(diào)度合理優(yōu)化，減低了公交運營成本，改善了公交運營現(xiàn)狀。

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