馮樹民，廖嘉雯，趙 琥

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

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

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

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

1 乘客分類

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

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

圖1 乘客出行路線示意圖

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

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

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

2 問題描述與建模

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

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

2.2 乘客總出行時間分析

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

(1)

乘客候車時間與站點乘客到達規(guī)律有關，當乘客均勻到達時，每位乘客的平均候車時間為連續(xù)公交車頭時距的一半[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.探索實施領導干部業(yè)績成果公示制度。工作業(yè)績能很好地反映出領導干部的工作能力強弱、執(zhí)政水平高低，通過對各級領導干部工作業(yè)績的公示，與相同、相近崗位工作業(yè)績的比較，給領導干部增加競爭壓力，促進領導干部不斷加強自身建設，提高領導水平和執(zhí)政能力。

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

以乘客總出行時間最小和公交運營成本最小為優(yō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)是問題的目標函數(shù)，式(7)表示乘客總出行時間最小化；式(8)表示公交運營成本最小化，Ci為線路i單位里程運營成本，包括固定折舊維修成本、人員工資成本、?？康∷俪杀炯斑\行能耗成本[19]。式(9)～(12)為約束條件，式(9)為發(fā)車間隔約束，公交發(fā)車間隔須滿足最大和最小發(fā)車間隔限制；式(10)為始發(fā)站首車發(fā)車時間約束，公交線路首車發(fā)車時間作為優(yōu)化變量時須小于發(fā)車間隔取值；式(11)為0-1變量約束，用于判斷兩線路是否構成換乘關系，線路i與線路j表示不同線路時Xi,j為1，否則為0；式(12)為0-1變量約束，當滿足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評價個體適應度。引入權重系數(shù)，計算系統(tǒng)總成本，將多目標規(guī)劃轉化為單目標優(yōu)化，構造適應度函數(shù)，如式(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條線路的重疊區(qū)段分布情況，重疊區(qū)段內共有12個重疊站點。以11：00—12：00為調查時段，采用人工調查法獲得各站點的上下車乘客數(shù)，根據(jù)上車客流和乘客下車概率表推算各公交線路的OD客流數(shù)據(jù)表，根據(jù)三類乘客的起訖點特征，分別得到各類乘客的上車乘客數(shù)，進而可得到其到達率，經(jīng)統(tǒng)計三類乘客的客流比例為0.18∶0.05∶0.77。參數(shù)設置如下：最小發(fā)車間隔tmin和最大發(fā)車間隔tmax分別取3 min和20 min，研究時段內的總時間T為60 min，乘客候車平均成本θ為0.32 元/min，權重系數(shù)α=0.6、β=0.4，各線路車輛單位距離運營成本為13.6 km/h，公交車額定載客數(shù)B為100 人，其他公交線路信息見表1。

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

表1 公交線路信息

4.2 算例求解

以所建立的發(fā)車間隔協(xié)同優(yōu)化模型為依據(jù)，結合3條公交線路的相關數(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)化方案進行求解并與原方案對比，其中乘客出行時間指標對比結果見表2，調度方案成本指標對比結果見表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 乘客出行時間指標對比

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

圖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展示了不同θ值下各指標的變化情況(θ=0.1時各項指標值為基數(shù)1，取其他θ值時各項指標值進行相應換算)。由圖7可知：1)隨著θ逐漸增大，三類乘客候車時間及乘客候車總時間呈下降趨勢，公交運營成本及系統(tǒng)總成本呈上升趨勢；2)由于線路站間距、車輛速度、乘客到達率不變，僅第一類乘客在重疊線路上的客流分配發(fā)生了變化，故乘客車上時間變化不大；3)三類乘客候車時間的變化趨勢基本相同，在其他條件不變的情況下，乘客總出行時間成本占系統(tǒng)總成本的比例與θ值正相關，隨著θ值增大，優(yōu)化結果中各線路發(fā)車間隔取值減小，各類乘客的候車時間隨之減小。

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

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

5 結 論

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

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

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