許 瑩,鄒常豐,賈佃精,趙博佳,劉 委

(1.東北林業(yè)大學(xué) 交通學(xué)院，哈爾濱 150040；2.遼寧省交通運(yùn)輸事業(yè)發(fā)展中心，沈陽(yáng) 110003)

公交調(diào)度是提高公交運(yùn)營(yíng)效率的重要途徑，具有較大提升潛力，同時(shí)，合理設(shè)計(jì)公交時(shí)刻表不僅可以降低公交公司的運(yùn)營(yíng)成本，而且可以保證乘客的便利性。

近年來(lái)，交通運(yùn)輸領(lǐng)域?qū)W者針對(duì)城市公交調(diào)度優(yōu)化問(wèn)題，從模型優(yōu)化、算法改進(jìn)等方面開(kāi)展了深入研究。Nam等[1]考慮車(chē)輛燃油量和碳排放因素，以環(huán)境成本最小為目標(biāo)函數(shù)建立公交調(diào)度模型；Ibarra-Rojas等[2]對(duì)偏離路線及發(fā)車(chē)間隔的車(chē)輛予以懲罰，建立時(shí)刻表優(yōu)化模型；熊昕宇[3]考慮不同道路情況對(duì)公交車(chē)運(yùn)行的影響，建立了公交車(chē)輛運(yùn)行狀態(tài)預(yù)測(cè)模型；張莉[4]考慮在實(shí)際運(yùn)營(yíng)過(guò)程中的不同條件，建立組合優(yōu)化模型，選用遺傳和模擬退火算法，實(shí)現(xiàn)對(duì)算法的優(yōu)化和模型求解；Saharidis等[5]考慮特定時(shí)間段內(nèi)的高乘客需求，提出以乘客候車(chē)時(shí)間最小為目標(biāo)的混合整數(shù)線性規(guī)劃方案；Kang等[6]提出了一種考慮公交駕駛員休息窗口時(shí)間的公交時(shí)刻表優(yōu)化模型；Carosi等[7]考慮發(fā)車(chē)間隔和車(chē)輛調(diào)度的影響，設(shè)計(jì)了一種區(qū)域公交調(diào)度集成模型；張海燕等[8]將公交時(shí)刻表優(yōu)化轉(zhuǎn)化為發(fā)車(chē)間隔優(yōu)化，建立了公交時(shí)刻表優(yōu)化模型；任俊[9]在公交系統(tǒng)大數(shù)據(jù)背景下，對(duì)公交數(shù)據(jù)進(jìn)行深入分析，在此基礎(chǔ)上構(gòu)建基于動(dòng)態(tài)需求的單線公交時(shí)刻表優(yōu)化模型；Wu等[10]考慮松弛時(shí)間，建立了巴士時(shí)間限制與隨機(jī)旅行時(shí)間隨機(jī)整數(shù)模型，并運(yùn)用GALS與OPM模型進(jìn)行迭代優(yōu)化，最大限度地降低不同類(lèi)型乘客的總等待時(shí)間成本；羅淩珊等[11]考慮疫情對(duì)公交調(diào)度的影響，以降低病毒傳播風(fēng)險(xiǎn)和社會(huì)經(jīng)濟(jì)運(yùn)行損失為目標(biāo)建立非線性時(shí)刻表優(yōu)化模型；胡金成[12]考慮公交運(yùn)行效能，建立雙層規(guī)劃模型；張姚等[13]考慮換乘站點(diǎn)的時(shí)間權(quán)重最小化，建立多目標(biāo)時(shí)刻表優(yōu)化模型。

考慮多線路重疊運(yùn)行情況：湯茹茹[14]建立一種多車(chē)型組合調(diào)度模型，在不同運(yùn)行區(qū)間采取相應(yīng)的車(chē)型運(yùn)行；姜楠[15]考慮公交車(chē)跨站、跳站等車(chē)輛調(diào)度方式對(duì)乘客總出行時(shí)間的影響,建立公交調(diào)度模型；宋現(xiàn)敏[16]考慮在重疊區(qū)間包含多個(gè)運(yùn)營(yíng)商，提出一種雙層規(guī)劃模型。

優(yōu)化算法改進(jìn)方面：朱鷹屏等[17]應(yīng)用改進(jìn)的雙中心粒子群優(yōu)化算法對(duì)建立的電動(dòng)公交車(chē)饋電線路模型進(jìn)行優(yōu)化；滕靖等[18]考慮可調(diào)度車(chē)輛數(shù)對(duì)純電動(dòng)車(chē)?yán)m(xù)航能力的影響，建立公交時(shí)刻表優(yōu)化模型，并利用粒子群算法進(jìn)行求解；賴(lài)元文等[19]以多線路公交公司盈利最大和乘客出行時(shí)間最短為目標(biāo)，建立公交調(diào)度優(yōu)化模型，并利用模擬退火—自適應(yīng)布谷鳥(niǎo)算法對(duì)模型進(jìn)行求解；Jin等[20]根據(jù)公交歷史軌跡數(shù)據(jù)，計(jì)算站間實(shí)際行車(chē)時(shí)間，并基于各站乘客上下車(chē)人數(shù)，運(yùn)用混合算法和模擬退火算法優(yōu)化發(fā)車(chē)時(shí)刻表。

上述文獻(xiàn)中，考慮多線路重疊情況對(duì)公交調(diào)度影響的較少。應(yīng)在保障公交公司基本盈利的情況下，考慮公交廊道的情況，盡可能縮短乘客出行時(shí)間。

文中考慮多線路重疊運(yùn)行情況，根據(jù)乘客的不同出行路徑，將乘客分為兩類(lèi)，并以公交運(yùn)營(yíng)利潤(rùn)最大和乘客出行時(shí)間最小為目標(biāo)函數(shù)，建立多目標(biāo)公交調(diào)度優(yōu)化模型，并通過(guò)模擬退火—非支配排序遺傳算法求解，得到最優(yōu)發(fā)車(chē)間隔。

1 時(shí)刻表優(yōu)化模型建立

1.1 問(wèn)題描述

乘客通過(guò)公共交通完成出行活動(dòng)的出行路徑可根據(jù)其上車(chē)、下車(chē)的站點(diǎn)來(lái)判斷?；诠贿\(yùn)行區(qū)間的重疊情況，將公交運(yùn)行線路劃分為3個(gè)部分，分別為運(yùn)行區(qū)間一、運(yùn)行區(qū)間二和運(yùn)行區(qū)間三，如圖1所示。運(yùn)行區(qū)間一為始發(fā)站到多線路重疊運(yùn)行區(qū)間的前一個(gè)站點(diǎn)；運(yùn)行區(qū)間二為多線路重疊運(yùn)行區(qū)間；運(yùn)行區(qū)間三為多線路重疊運(yùn)行區(qū)間后的第一個(gè)站到終點(diǎn)站。

圖1 公交線路運(yùn)行區(qū)間劃分

根據(jù)出行路徑將乘客分為兩種，第一種為上、下車(chē)行為均在運(yùn)行區(qū)間二內(nèi)站點(diǎn)完成的乘客，第二種為上、下車(chē)行為最多有一個(gè)是在運(yùn)行區(qū)間二內(nèi)站點(diǎn)完成的乘客。其中，第一種乘客在重疊站點(diǎn)內(nèi)可以選擇任意的公交線路完成出行，為節(jié)約乘客出行時(shí)間，可選擇先到達(dá)候車(chē)站點(diǎn)的公交車(chē)完成出行；而第二種乘客只能選擇單一的公交線路完成出行。

為簡(jiǎn)化問(wèn)題并保證模型仿真過(guò)程在穩(wěn)定環(huán)境中進(jìn)行，本文假設(shè)如下：

1)乘客到達(dá)站點(diǎn)服從均勻分布；

2)公交車(chē)輛沿規(guī)定路線行駛；

3)同一線路車(chē)輛經(jīng)過(guò)相同路段所用時(shí)間相同；

4)各線路公交車(chē)的車(chē)廂容量一致。

1.2 模型建立

共有I條公交線路在線網(wǎng)中，用i=1,2,3,…,I表示；公交線路i有Gi個(gè)站點(diǎn)，用g=1,2,3,…,G表示。其中，有O個(gè)站點(diǎn)在多線路重疊運(yùn)行區(qū)間內(nèi)，有Ri個(gè)站點(diǎn)在多線路重疊運(yùn)行區(qū)間前，每條公交線路共有Qi輛公交車(chē)。

乘客出行時(shí)間為站點(diǎn)候車(chē)時(shí)間與車(chē)內(nèi)行程時(shí)間之和，公交運(yùn)營(yíng)利潤(rùn)為公交公司的運(yùn)營(yíng)收益與運(yùn)營(yíng)成本之差。

1.2.1 乘客站點(diǎn)候車(chē)時(shí)間

(1)

(2)

乘客站點(diǎn)候車(chē)時(shí)間為兩種乘客的站點(diǎn)候車(chē)時(shí)間之和。第一種乘客站點(diǎn)候車(chē)時(shí)間t1為新到乘客與上一輛公交車(chē)滯留乘客的站點(diǎn)候車(chē)時(shí)間之和，即

(3)

同理，第二種乘客的站點(diǎn)候車(chē)時(shí)間為

(4)

1)站點(diǎn)?？繒r(shí)間。站點(diǎn)?？繒r(shí)間由車(chē)輛開(kāi)門(mén)時(shí)間、乘客上下車(chē)時(shí)間以及關(guān)門(mén)時(shí)間3部分組成。其中，乘客上下車(chē)時(shí)間由乘客上車(chē)與下車(chē)時(shí)間的最大值決定[21]，即

(5)

2)站點(diǎn)上下車(chē)乘客數(shù)。站點(diǎn)上車(chē)乘客數(shù)由經(jīng)過(guò)站點(diǎn)時(shí)的車(chē)廂容量決定。站點(diǎn)的實(shí)際上車(chē)乘客數(shù)為候車(chē)人數(shù)與車(chē)廂剩余容量的最小值，站點(diǎn)車(chē)廂剩余容量為車(chē)廂總?cè)萘颗c站點(diǎn)下車(chē)人數(shù)之和減去站點(diǎn)車(chē)廂內(nèi)人數(shù)。所以上車(chē)乘客數(shù)表示為

(6)

站點(diǎn)下車(chē)乘客數(shù)與站點(diǎn)的平均下車(chē)率有關(guān)，即

(7)

(8)

(9)

(10)

式中：Si,g為站點(diǎn)g-1到站點(diǎn)g的路段行程時(shí)間；te，tf分別為減速進(jìn)站時(shí)間和加速離站時(shí)間。

1.2.2 乘客車(chē)內(nèi)行程時(shí)間

車(chē)內(nèi)行程時(shí)間t3為乘客在站點(diǎn)上車(chē)后，到達(dá)目的站點(diǎn)下車(chē)這一過(guò)程所需要的時(shí)間，算式為

(11)

1.2.3 公交運(yùn)營(yíng)成本

公交運(yùn)營(yíng)成本C1主要包括車(chē)輛維修費(fèi)、人員薪資和設(shè)備費(fèi)用等固定成本以及車(chē)輛燃油耗能成本，可用單位公交車(chē)每千米的運(yùn)行費(fèi)用[22]表示，即

(12)

(13)

1.2.4 公交運(yùn)營(yíng)利潤(rùn)

公交運(yùn)營(yíng)利潤(rùn)C(jī)2主要為運(yùn)載乘客的收入，為公交線路所有上車(chē)乘客與票價(jià)的乘積，即

(14)

式中：E為票價(jià)。

1.3 建立目標(biāo)函數(shù)

1)乘客出行時(shí)間。乘客出行時(shí)間t由第一種、第二種乘客的站點(diǎn)候車(chē)時(shí)間以及車(chē)內(nèi)行程時(shí)間組成。

mint=t1+t2+t3

(15)

2)公交運(yùn)營(yíng)利潤(rùn)。公交運(yùn)營(yíng)利潤(rùn)C(jī)為公交運(yùn)營(yíng)收益與公交運(yùn)營(yíng)成本之差，即

maxC=C2-C1

(16)

3)約束條件。公交車(chē)的發(fā)車(chē)間隔必須滿足最大和最小發(fā)車(chē)間隔，即

(17)

公交調(diào)度時(shí)，保障公交公司的收入大于支出，公交運(yùn)營(yíng)利潤(rùn)大于0，即

C≥0

(18)

根據(jù)公交車(chē)容量的限制，車(chē)廂內(nèi)乘客數(shù)應(yīng)小于公交車(chē)廂容量，即

(19)

綜合各目標(biāo)函數(shù)，得到多目標(biāo)公交調(diào)度優(yōu)化模型

mint=t1+t2+t3

(20)

(21)

2 模擬退火—非支配排序遺傳算法

非支配排序遺傳算法(NSGAⅡ)[23]是一種基于NSGA改進(jìn)的多目標(biāo)優(yōu)化算法。模擬退火算法(SA)將隨機(jī)因素引入最優(yōu)解搜索過(guò)程中，在迭代更新過(guò)程中，跳脫出局部最優(yōu)解的范圍，以一定概率搜索到全程最優(yōu)解[24]。

模擬退火—非支配排序遺傳算法(SA-NSGAⅡ)具有以下優(yōu)點(diǎn)：

1)相較于非支配排序遺傳算法(NSGA)計(jì)算復(fù)雜度降低、準(zhǔn)確性提高,且pareto解集分布均勻。

2)相較于NSGAⅡ算法，在個(gè)體選擇時(shí)以一定的概率將擁擠度較小的個(gè)體儲(chǔ)存到遴選集中，從而防止丟失非劣解。

3)在MATLAB軟件中進(jìn)行優(yōu)化求解時(shí)，運(yùn)行效率較高、穩(wěn)定性更好。

因此，文中選用模擬退火—非支配排序遺傳算法尋求最優(yōu)發(fā)車(chē)間隔。

2.1 模型在算法中的處理

1)對(duì)于多線路重疊運(yùn)行區(qū)間，第一種乘客和第二種乘客的站點(diǎn)候車(chē)時(shí)間需分別計(jì)算，車(chē)內(nèi)行程時(shí)間需根據(jù)乘客選擇的公交線路路段行程時(shí)間以及站點(diǎn)?？繒r(shí)間確定，選擇的公交線路不同，車(chē)內(nèi)行程時(shí)間也不同。因此，在應(yīng)用MATLAB編寫(xiě)程序時(shí)，綜合考慮乘客在各重疊站點(diǎn)內(nèi)的上下車(chē)情況，計(jì)算站點(diǎn)候車(chē)時(shí)間以及車(chē)內(nèi)行程時(shí)間。

對(duì)于非多線路重疊運(yùn)行區(qū)間，即運(yùn)行區(qū)間一和運(yùn)行區(qū)間三，乘客根據(jù)出行目的僅可選擇固定的公交線路，各站點(diǎn)全部為第二種乘客，只計(jì)算第二種乘客的站點(diǎn)候車(chē)時(shí)間以及車(chē)內(nèi)行程時(shí)間。因此，在應(yīng)用MATLAB編寫(xiě)程序時(shí)，根據(jù)公交車(chē)的運(yùn)行狀況計(jì)算第二種乘客的站點(diǎn)候車(chē)時(shí)間以及車(chē)內(nèi)行程時(shí)間。

2)為方便模型處理，將規(guī)定時(shí)間段內(nèi)發(fā)車(chē)間隔的約束條件轉(zhuǎn)化為最大和最小間隔發(fā)車(chē)數(shù)，確定線路的車(chē)輛數(shù)范圍。

3)因站點(diǎn)乘客候車(chē)乘客數(shù)與車(chē)頭時(shí)距相關(guān)，但每條線路首輛公交車(chē)無(wú)車(chē)頭時(shí)距，所以規(guī)定首輛公交車(chē)的車(chē)頭時(shí)距用路段行程時(shí)間表示，其余車(chē)輛的車(chē)頭時(shí)距用發(fā)車(chē)間隔的相應(yīng)算式表示。

2.2 算法基本步驟

1)設(shè)置算法參數(shù)。初始溫度為T(mén)0，初始化種群為P1，種群規(guī)模為N，初始迭代次數(shù)為0，設(shè)置最大迭代次數(shù)、交叉率、變異率、溫度下降速率。

2)輸入模型參數(shù)。輸入站點(diǎn)上車(chē)率、下車(chē)率、路段運(yùn)行區(qū)間、第一種乘客和第二種乘客比例數(shù)等數(shù)據(jù)。

3)計(jì)算種群P1中所有個(gè)體的非支配排序Kj和擁擠度Rd。

4)個(gè)體選擇。對(duì)任意個(gè)體i1和i2，若Ki1>Ki2，則將個(gè)體i1儲(chǔ)存在遴選集M1中。若Ki1=Ki2，則采用Metropolis準(zhǔn)則進(jìn)行判斷見(jiàn)式(22)，當(dāng)Ri1>Ri2，則將個(gè)體i1儲(chǔ)存到遴選集M1中；當(dāng)Ri1≤Ri2，則以一定概率ρ將個(gè)體i2儲(chǔ)存到遴選集M1中，直至M1的個(gè)體數(shù)達(dá)到N。算式為

(22)

5)通過(guò)交叉、變異等操作使遴選集M1中的個(gè)體產(chǎn)生子代種群Q1。

6)將子代種群Q1與P1合并在一起，組成種群規(guī)模為2N的新種群S1。

7)計(jì)算S1種群個(gè)體的非支配排序和擁擠度，將非支配集的個(gè)體按照從高到低的序列依次放到新的父代種群P2中[25]，若某一層的非支配個(gè)體放到P2后，種群規(guī)模超過(guò)N，則將該層個(gè)體按照擁擠度從大到小的順序放入P2中，直至P2的種群規(guī)模達(dá)到N。

8)達(dá)到最大迭代次數(shù)后終止循環(huán)，輸出帕累托前沿解集；若未完成迭代，循環(huán)步驟4)—步驟7)，直至完成迭代。

3 實(shí)例分析

3.1 案例概述

為驗(yàn)證模型的實(shí)用性，以哈爾濱市10路、56路、68路、75路、117路和102路公交線路為例。以上6條公交線路均在和興路路段有重疊運(yùn)行區(qū)間，重疊運(yùn)行區(qū)間內(nèi)包含林業(yè)大學(xué)、林業(yè)總醫(yī)院、林興路以及哈師大4個(gè)站點(diǎn)。各公交線路的基本信息如表1所示，線路如圖2所示。

表1 公交線路信息表

圖2 公交線路

采用人工調(diào)查法采集公交客流數(shù)據(jù)，調(diào)查時(shí)間選擇晚高峰16:30—17:30，跟車(chē)采集各站點(diǎn)的上下車(chē)乘客數(shù)、站間行程時(shí)間和發(fā)車(chē)間隔等數(shù)據(jù)，駐站調(diào)查多線路重疊區(qū)間第一種乘客、第二種乘客的比例。以10路公交為例，對(duì)調(diào)查數(shù)據(jù)進(jìn)行整理計(jì)算，計(jì)算結(jié)果如表2、表3所示。

表2 哈爾濱10路公交數(shù)據(jù)

表3 第一種乘客比例 %

3.2 模型及算法參數(shù)標(biāo)定

通過(guò)多次測(cè)驗(yàn)，將SA-NSGAⅡ算法中的各個(gè)參數(shù)設(shè)置如表4所示。

表4 部分參數(shù)標(biāo)定

3.3 結(jié)果分析

運(yùn)用MATLAB軟件對(duì)上述模型進(jìn)行優(yōu)化，得到4組發(fā)車(chē)間隔優(yōu)化方案。4組優(yōu)化方案對(duì)應(yīng)的目標(biāo)函數(shù)值如表5所示，并以?xún)?yōu)化方案3為例，得到各線路發(fā)車(chē)時(shí)刻表，如表6所示。

表5 公交線路調(diào)度方案

由表5可知，4種優(yōu)化方案相較于原始方案，乘客出行時(shí)間均縮短，公交運(yùn)營(yíng)利潤(rùn)均有所提升。其中，優(yōu)化方案3縮短乘客出行時(shí)間最多，較原始方案縮短13.8%；優(yōu)化方案4公交運(yùn)營(yíng)利潤(rùn)提升最大，增加6.9%。

表6 發(fā)車(chē)時(shí)刻表

4 結(jié) 論

文中根據(jù)乘客出行路徑不同，將乘客分為兩種，并充分考慮兩種乘客的特點(diǎn)，構(gòu)建公交運(yùn)營(yíng)利潤(rùn)最大和乘客出行時(shí)間最短的多目標(biāo)時(shí)刻表優(yōu)化模型，運(yùn)用模擬退火—非支配排序遺傳算法，以哈爾濱市6條公交線路為例，得出6條公交線路的發(fā)車(chē)間隔以及不同優(yōu)化方案的目標(biāo)函數(shù)值。優(yōu)化結(jié)果表明：4種優(yōu)化方案相較于原始方案，乘客出行時(shí)間均縮短，公交運(yùn)營(yíng)利潤(rùn)均有所提升，驗(yàn)證了模型的有效性和實(shí)用性。