馮樹民，廖嘉雯，趙 琥

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

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

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

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

1 乘客分類

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

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

圖1 乘客出行路線示意圖

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

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

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

2 問題描述與建模

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

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

2.2 乘客總出行時(shí)間分析

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

(1)

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

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

(2)

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

(3)

(4)

(5)

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

(6)

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

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

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

3 模型求解

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

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

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

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

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

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

(13)

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

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

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

圖3 遺傳算法流程圖

4 算例分析

4.1 算例簡述

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

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

表1 公交線路信息

4.2 算例求解

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

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

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

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

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

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

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

4.3 敏感性分析

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

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

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

5 結(jié) 論

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

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

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