周 楊，王景升

(中國人民公安大學(xué)，北京 100038)

隨著車輛保有量的增加，城市交通壓力不斷增大，交通管理部門對公共出行方式越發(fā)重視。公交系統(tǒng)作為城市公共出行系統(tǒng)的骨架，連接城市的不同分區(qū)，在整合城市資源、提高城市路網(wǎng)運(yùn)行效率等方面起到了重要作用。公交線路設(shè)計(jì)優(yōu)化需要解決居民換乘、等車耗時(shí)和公交運(yùn)行成本等問題，涉及城市居民出行、便利、安全、環(huán)保和效益等方面，是城市公交系統(tǒng)的重點(diǎn)課題。我國關(guān)于公交線路的研究起步較晚，從20世紀(jì)80年代初開始，逐步形成建立數(shù)學(xué)模型，利用算法對模型求解的問題解決模式。

公交線路規(guī)劃問題可以視作最優(yōu)化問題，目前廣泛使用的既有Dijkstra(迪克斯特拉)算法和Floyd(弗洛伊德)算法等最短路徑算法，也有動(dòng)態(tài)規(guī)劃算法、蟻群算法、粒子群算法、遺傳算法以及和聲搜索(harmony search, HS)算法等全局性搜索算法。較為傳統(tǒng)的最短路徑算法可以與圖論方法相結(jié)合，計(jì)算場景內(nèi)節(jié)點(diǎn)之間的最短線路[1-2]。全局性搜索算法通過引入不同參數(shù)對模型進(jìn)行調(diào)節(jié)，在計(jì)算量較大時(shí)，擁有更強(qiáng)的全局搜索能力[3-4]。在大數(shù)據(jù)智能化的條件下，融合遙感技術(shù)、電子信息技術(shù)等技術(shù)理論，分析現(xiàn)有城市交通公交線路節(jié)點(diǎn)，以確定公交線網(wǎng)的優(yōu)化方向，例如：運(yùn)營者運(yùn)營成本最低，公交線路服務(wù)能力最大，居民換乘次數(shù)最少，出行時(shí)間最短等。再根據(jù)優(yōu)化方向建立線路或線網(wǎng)優(yōu)化的數(shù)學(xué)模型，結(jié)合約束條件選擇算法求解，進(jìn)一步分析結(jié)果，進(jìn)而得出公交線路或線網(wǎng)優(yōu)化方案。

但在實(shí)際應(yīng)用過程中，部分算法表現(xiàn)出一些不足。最短路徑算法無法同時(shí)考慮換乘次數(shù)和服務(wù)人數(shù)等問題，在解決多目標(biāo)決策問題時(shí)表現(xiàn)不佳；智能搜索算法依賴參數(shù)設(shè)置，在不同適用條件下的計(jì)算能力有所差異，如：遺傳算法擴(kuò)展性大，搜索能力強(qiáng)，但計(jì)算空間有限，易早熟收斂，形成局部最優(yōu)[4]；粒子群算法只利用最優(yōu)粒子傳遞信息，計(jì)算速度快，但缺乏速度的動(dòng)態(tài)調(diào)節(jié)，易導(dǎo)致收斂精度低或不易收斂，不能有效解決組合優(yōu)化問題。

本文利用和聲搜索算法，基于不同算例和約束條件進(jìn)行公交線路規(guī)劃計(jì)算，并通過與遺傳算法計(jì)算結(jié)果進(jìn)行對比，驗(yàn)證其實(shí)用性。

1 和聲搜索算法

和聲搜索算法是一種新近問世的啟發(fā)性全局搜索算法。靈感源自樂師創(chuàng)作和聲的過程。在音樂演奏中，樂師憑借記憶對不同樂器發(fā)出的音調(diào)進(jìn)行選擇性調(diào)整，最終獲得“完美和聲”。Zong等[5]首先提出和聲搜索算法，該算法結(jié)構(gòu)簡單、需要調(diào)整的參數(shù)少、求解速度快、魯棒性強(qiáng)、全局搜索能力強(qiáng)且通用性高，在解決組合優(yōu)化問題上具有優(yōu)勢。

算法將樂器i(i=1,2,…,n)類比為目標(biāo)方案中的第i個(gè)變量，產(chǎn)生的和聲Hj(j=1,2,…,n)視為優(yōu)化問題的第j個(gè)解向量，對和聲的評價(jià)即為目標(biāo)函數(shù)的函數(shù)值。算法首先產(chǎn)生HMS(harmony memory size，和聲記憶庫大小)個(gè)解，將其放入和聲記憶庫(harmony memory，HM)，類比樂師的初始記憶，作為目標(biāo)方案的初始解。之后隨機(jī)產(chǎn)生(0,1)的參數(shù)rand1和rand2，并引入和聲記憶庫取值概率(harmony memory considering rate, HMCR)和微調(diào)概率(pitch adjusting rate，PAR)。若rand1

有別于其他啟發(fā)式算法，和聲搜索算法的優(yōu)勢在于其包含記憶庫計(jì)算、局部擾動(dòng)與隨機(jī)選擇的即興創(chuàng)作過程，在優(yōu)化算法集約化與多樣化的平衡中發(fā)揮了重要作用。

和聲搜索算法的特征如下：①在所有可能存在的向量中生成新的向量。②針對向量中的每個(gè)決策變量進(jìn)行單獨(dú)考慮。③不需要對變量進(jìn)行初始賦值。④算法中無進(jìn)制轉(zhuǎn)換，計(jì)算速度較快。

和聲搜索算法流程如圖1所示。

圖1 和聲搜索算法流程

2 線路規(guī)劃的數(shù)學(xué)建模與計(jì)算

城市公交線路具有?？抗?jié)點(diǎn)多、總里程短等特點(diǎn)。在二維坐標(biāo)系中放置坐標(biāo)，模擬公交節(jié)點(diǎn)，利用Matlab語言，分別以服務(wù)總?cè)藬?shù)M最大、總行程時(shí)間T最小為目標(biāo)函數(shù)，采用Matlab 2019a編寫和聲搜索算法程序并進(jìn)行計(jì)算。和聲搜索算法對初始解的依賴性較大，且本試驗(yàn)算例的計(jì)算量較小，為避免過早陷入局部最優(yōu)，因此和聲記憶庫及其取值概率較小，設(shè)置參數(shù)HMS為2，HMCR為0.3，PAR為0.1，bw為0.05，N為100。

坐標(biāo)系節(jié)點(diǎn)設(shè)置如圖2所示，其中點(diǎn)1、4、8、11為固定節(jié)點(diǎn)，點(diǎn)2、3、5、6、7、9、10為可以選擇經(jīng)過的節(jié)點(diǎn)。點(diǎn)1和點(diǎn)11為確定的起點(diǎn)和終點(diǎn)。

圖2 坐標(biāo)系節(jié)點(diǎn)設(shè)置

2.1 服務(wù)人數(shù)

公交線路規(guī)劃應(yīng)將服務(wù)更多居民作為重要目標(biāo)之一。當(dāng)前研究成果中通常將公交站點(diǎn)服務(wù)人數(shù)作為重要計(jì)算指標(biāo)[3]，本試驗(yàn)對規(guī)劃線路可能經(jīng)過的節(jié)點(diǎn)進(jìn)行居住人數(shù)賦值，路段服務(wù)人數(shù)計(jì)算見式(1)。

(1)

式中，Mi為路段服務(wù)人數(shù)，人；Pi為路段上各節(jié)點(diǎn)服務(wù)人數(shù)，人/km；Li為路段長度，km；i為節(jié)點(diǎn)。

線路服務(wù)人數(shù)的目標(biāo)函數(shù)見式(2)。

(2)

式中，M為線路總服務(wù)人數(shù)，人。

節(jié)點(diǎn)坐標(biāo)及站點(diǎn)服務(wù)人數(shù)如表1所示。

表1 節(jié)點(diǎn)坐標(biāo)及站點(diǎn)服務(wù)人數(shù)

以每兩個(gè)固定節(jié)點(diǎn)間路段的服務(wù)人數(shù)作為變量，輸入坐標(biāo)及節(jié)點(diǎn)服務(wù)人數(shù)矩陣，經(jīng)過計(jì)算篩選，得出符合條件的最優(yōu)路徑為1-3-4-5-8-10-11，最大服務(wù)人數(shù)為4 582人。服務(wù)人數(shù)最大路徑(HS)如圖3所示，服務(wù)人數(shù)適應(yīng)度曲線(HS)如圖4所示。

圖3 服務(wù)人數(shù)最大路徑(HS)

圖4 服務(wù)人數(shù)適應(yīng)度曲線(HS)

2.2 行程時(shí)間

模型中的行程時(shí)間由換乘時(shí)間和行駛時(shí)間組成，假設(shè)換乘時(shí)間為定量，與上下客人數(shù)無關(guān)。行駛時(shí)間為行程長度與平均車速之比。行程時(shí)間的目標(biāo)函數(shù)為

(3)

式中，T為行程時(shí)間，min；D為公交線路行程長度，km；d(i-1,i)為從第i-1個(gè)節(jié)點(diǎn)到第i個(gè)節(jié)點(diǎn)的距離，m；n為最后一個(gè)經(jīng)過的節(jié)點(diǎn)；v0為城市公交平均車速，km/h，取35 km/h；t0為平均?？繐Q乘時(shí)間，min，取3 min。

公交線路規(guī)劃問題屬于多目標(biāo)決策問題，本試驗(yàn)中的不同目標(biāo)之間具有相對獨(dú)立性。根據(jù)《城市綜合交通體系規(guī)劃標(biāo)準(zhǔn)》(GB/T 51328—2018)[7]，公共交通線路非直線系數(shù)不得大于1.4，即目標(biāo)函數(shù)的約束條件為：D≤1.4×d(0,n)。

不同目標(biāo)路徑結(jié)果如表2所示。

表2 不同目標(biāo)路徑結(jié)果

以圖2場景中線路不固定的3個(gè)路段分別作為3個(gè)變量(樂器)，通過對可選節(jié)點(diǎn)進(jìn)行組合，并對不同組合結(jié)果下的路段長度對比選擇，計(jì)算得到符合條件的行程最短路徑為1-3-4-7-8-9-11，最短行程時(shí)間為39.414 7 min。總行程時(shí)間最短路徑如圖5所示，行程長度適應(yīng)度進(jìn)化曲線(HS)如圖6所示。

圖5 總行程時(shí)間最短路徑

圖6 行程長度適應(yīng)度進(jìn)化曲線(HS)

2.3 遺傳算法對比

本試驗(yàn)采用遺傳算法(GA)進(jìn)行算法效果對比，在相同節(jié)點(diǎn)場景下，以相同大小的初始解集進(jìn)行計(jì)算，遺傳算法的參數(shù)設(shè)置如下：種群數(shù)Popsize為2，復(fù)制概率為0.3，交叉概率PC為0.4，變異概率PM為0.3，N為100。用Matlab進(jìn)行編程，并繪制兩種目標(biāo)函數(shù)情況下的適應(yīng)度曲線，服務(wù)人數(shù)適應(yīng)度進(jìn)化曲線(GA)如圖7所示，行程長度適應(yīng)度進(jìn)化曲線(GA)如圖8所示。

本試驗(yàn)場景較為簡單，兩種算法都能夠在多次迭代后得到最優(yōu)解，因此本文以迭代次數(shù)作為指標(biāo)對比兩種算法優(yōu)劣。對比圖4與圖7，在以最大服務(wù)人數(shù)為目標(biāo)函數(shù)時(shí)，HS約25次迭代后收斂，GA約80次迭代后收斂；對比圖6和圖8，在以最短行程時(shí)間為目標(biāo)函數(shù)時(shí)，HS約35次迭代后收斂，GA約75次迭代后收斂。相較于遺傳算法，和聲搜索算法采用十進(jìn)制編碼，原理簡單，容易實(shí)現(xiàn)。

圖7 服務(wù)人數(shù)適應(yīng)度進(jìn)化曲線(GA)

圖8 行程長度適應(yīng)度進(jìn)化曲線(GA)

3 總結(jié)

本文以假設(shè)條件下的最短行程時(shí)間與最大服務(wù)人數(shù)為約束條件，基于和聲搜索算法提出公交線路規(guī)劃方法，結(jié)合算例，對約束模型下的起訖點(diǎn)及部分節(jié)點(diǎn)固定的公交線路進(jìn)行計(jì)算篩選，采用遺傳算法對同一場景編程計(jì)算作為對照。對比試驗(yàn)結(jié)果表明，和聲搜索算法在收斂速度上明顯優(yōu)于遺傳算法，相較于遺傳算法的二進(jìn)制編碼，和聲搜索的十進(jìn)制編碼方式更適合進(jìn)行快速計(jì)算。和聲搜索算法作為最新的智能優(yōu)化算法，在固定節(jié)點(diǎn)公交線路的規(guī)劃問題上，具有可參考性，類似的規(guī)劃方法可用于解決班車、校車和定制公交等路線規(guī)劃問題。

相較于其他常用的最優(yōu)化算法，和聲搜索算法的參數(shù)設(shè)置較為簡單，一般依靠經(jīng)驗(yàn)確定，在計(jì)算量較小的前提下，嘗試不同參數(shù)可在一定程度上避免陷入局部最優(yōu)，但在較為復(fù)雜的問題上缺乏理論指導(dǎo)，因此，在參數(shù)的選擇、不同選參條件下的結(jié)果對比以及通過融合其他智能優(yōu)化算法的思想進(jìn)行算法改進(jìn)等方面值得深入研究。