基于遺傳禁忌算法的公交線路發(fā)車間隔優(yōu)化

周 騫，韋鳳連，劉 菊

（長沙理工大學(xué)交通運(yùn)輸工程學(xué)院，湖南長沙 410004）

隨著中國經(jīng)濟(jì)的迅猛發(fā)展、城市規(guī)模的快速擴(kuò)張及私家車擁有量爆發(fā)式增長，城市客、貨運(yùn)輸總量和機(jī)動化出行量急劇增長。城市交通供需關(guān)系打破了既有的平衡，產(chǎn)生了交通擁堵，導(dǎo)致城市經(jīng)濟(jì)等社會功能衰退和城市生存環(huán)境持續(xù)惡化。發(fā)展公共交通是城市交通系統(tǒng)的主流方向，城市公共交通能否正常和高效地運(yùn)轉(zhuǎn)，不僅取決于道路、車輛及場站等技術(shù)和設(shè)施條件，而且依賴于科學(xué)有效的運(yùn)營組織與管理。

公交車輛發(fā)車間隔優(yōu)化是公交運(yùn)營組織和管理的核心工作，許多學(xué)者對此進(jìn)行了研究［1－5］。需要建立適合客流量變化且滿足乘客和企業(yè)效益最優(yōu)的公交發(fā)車間隔優(yōu)化模型，以實現(xiàn)車輛資源的有效利用，提高公交服務(wù)水平和企業(yè)經(jīng)濟(jì)效益。在公交系統(tǒng)中，運(yùn)營者和乘客的利益是既相互矛盾又相互制約的兩個因素。在乘客數(shù)量不變的情況下，用延長發(fā)車間隔來減少發(fā)車次數(shù)，這種做法延長了乘客的等車時間，有利于減少企業(yè)單車營運(yùn)成本，但最終會造成乘客的流失。而乘客希望在享受公交服務(wù)時能夠盡量減少等待時間（即到即走），這就要求公交企業(yè)增加發(fā)車密度，提高公交企業(yè)的營運(yùn)成本。作者擬根據(jù)中國城市公共交通以線路調(diào)度為主的實際情況，從乘客和企業(yè)二維度建立公交線路發(fā)車間隔優(yōu)化模型，以期達(dá)到乘客和企業(yè)雙贏的目標(biāo)。

1 模型的建立

1.1 模型的假設(shè)

公交車輛發(fā)車間隔優(yōu)化涉及的影響因素較多，在建立發(fā)車間隔優(yōu)化模型時，假設(shè)：①車輛都沿著規(guī)定路線行駛且車型統(tǒng)一，線路車輛數(shù)不變；②以線路單向的發(fā)車間隔為決策變量，且同一時段采取相同的發(fā)車間隔；③各時段內(nèi)乘客到站服從泊松分布；④乘客在各站點上、下客流情況為已知；⑤道路暢通、天氣環(huán)境良好，無意外事故發(fā)生。

1.2 乘客時間費(fèi)用函數(shù)

與公交運(yùn)營調(diào)度相關(guān)的乘客時間費(fèi)用C乘由乘客等車費(fèi)用Cw和乘客乘車費(fèi)用Cr兩部分費(fèi)用組成［6］。表示為：

1）乘客等車費(fèi)用

乘客等車費(fèi)用Cw包括：①在發(fā)車間隔Δti內(nèi)，到站等車的乘客均能乘上第1輛車；②未能乘上第1輛到達(dá)的車輛，出現(xiàn)2次等車并且均能乘上第2輛車。

根據(jù)乘客到達(dá)的特點分析，乘客的到站數(shù)服從泊松分布［7］。假設(shè)在第i時段的發(fā)車間隔為Δti，設(shè)第i時段內(nèi)在第j站乘客平均到達(dá)率為λij，那么，第i時段內(nèi)在第j站的乘客等待數(shù)為：

當(dāng)乘客到達(dá)服從泊松分布時，乘客等車時間服從負(fù)指數(shù)分布。那么，第i時段在第j站的乘客等待時間為：

已知在第i時段內(nèi)第j站上車的乘客數(shù)為Oij，那么，在第j站因無法上車而滯留的乘客數(shù)為：

乘客等車費(fèi)用為：

式中：Cw為乘客等車費(fèi)用；tij為第i時段內(nèi)第j站點的乘客等待時間，min；λij為第i時段內(nèi)第j站點的乘客平均到達(dá)率，人／min；Cα為乘客時間費(fèi)用系數(shù)（元／min），由城市居民人均日工資折算得到；Pij為第i時段內(nèi)第j站的乘客等待數(shù)；Oij為第i時段內(nèi)第j站的乘客上車數(shù)；φ為公交車輛最大擁擠度；P′ij為第i時段內(nèi)第j站因無法上車的乘客滯留數(shù)；Cα為懲罰系數(shù)，用于反映由于車輛容量不足時乘客無法全部上第1輛車的乘客的額外等車費(fèi)用，可用發(fā)車頻率乘以等待車輛數(shù)表示。

2）乘客在途乘車費(fèi)用

乘客在途乘車時間費(fèi)用Cr是指乘客乘上公交車后在途消耗時間的費(fèi)用［8］。已知Oij為第i時段內(nèi)第j站乘客的上車數(shù)，Uij為第i時段在第j站乘客的下車數(shù)，那么車輛從第Cm站到第j＋1站車上的乘客數(shù)即斷面流量為：

假設(shè)車輛從第Cm站到第j＋1站的平均運(yùn)行時間為那么，乘客在途乘車時間費(fèi)用為：

式中：Cr為乘客乘車費(fèi)用為在第i時段車輛從第j站到第j＋1站平均運(yùn)行時間為在第i時段車輛從第j站到第j＋1站車上的乘客數(shù)。

將式（2）～（7）代入式（1），得：

1.3 公交企業(yè)營運(yùn)成本函數(shù)

公交企業(yè)營運(yùn)成本是指在城市公交運(yùn)輸過程中，實際發(fā)生的與營運(yùn)直接有關(guān)的各項費(fèi)用和支出［9］。將企業(yè)線路營運(yùn)成本分為燃油消耗費(fèi)、駕駛員薪酬費(fèi)、車輛折舊費(fèi)及維修保養(yǎng)費(fèi)用。

1）燃油消耗費(fèi)

公交車輛平均燃油實際消耗量指標(biāo)用公里油耗量（車輛行駛100km平均消耗實際的燃油量）表示。已知線路單程長度為L，設(shè)車輛每公里油耗為Oe，那么，每趟車單程行駛總油耗為：

某線路每天正常營運(yùn)時間為Tr，假設(shè)在第i時段的發(fā)車間隔為Δti，在第i時段內(nèi)總油耗只與該時段內(nèi)的發(fā)車頻率fi有關(guān)。全天內(nèi)總的發(fā)車次數(shù)為：

因此，公交車輛每天燃油消耗費(fèi)為：

2）駕駛員薪酬費(fèi)

公交企業(yè)根據(jù)線路車隊規(guī)模的最小配車數(shù)Nmin來購置車輛，對每輛車分配司售人員，而公交企業(yè)支付給駕駛?cè)藛T的薪酬費(fèi)與每輛車配備的司機(jī)人數(shù)R有關(guān)。每輛車每天所需支付給司機(jī)駕駛員薪酬費(fèi)用為：

式中：CR為車隊每天所需司機(jī)的總工資費(fèi)用；CR0為每位司機(jī)每天所獲得的工資費(fèi)用。

3）車輛折舊費(fèi)

公交車輛使用年限為6～8a，是使用頻率高、消耗度大的公共產(chǎn)品。盡管隨著使用年限的增加，車輛性能會下降，但由于公交車需求的平穩(wěn)性，公交車的使用率和客流量不會隨著公交車輛的性能下降而減少。

車輛折舊費(fèi)按其購入時的固定成本百分比計算，以彌補(bǔ)車輛作為固定資產(chǎn)的貶值。采用直線法確定折舊費(fèi)，折舊費(fèi)與公交車價格、折舊年限和殘值都有關(guān)系。每輛車每天正常營運(yùn)的車輛折舊費(fèi)用為：

式中：Ta為車輛總投資額，與該線路配置的最小車輛數(shù)有關(guān)（扣除政府補(bǔ)貼后所要支付的購車金額）；Rγ為殘值系數(shù)；θ為每輛車規(guī)定的使用年限，年；RN為年利用率。

4）維修保養(yǎng)費(fèi)

維修費(fèi)用包括公交車輛維修和養(yǎng)護(hù)費(fèi)用，按每輛車每天例行的保養(yǎng)維護(hù)費(fèi)用S0計算。

則公交企業(yè)每天營運(yùn)成本為：

1.4 發(fā)車間隔優(yōu)化模型

為了使得整個公交系統(tǒng)的總費(fèi)用最低，本研究采用線性加權(quán)的方法，將乘客的等車成本和車輛營運(yùn)成本兩種費(fèi)用轉(zhuǎn)化為單目標(biāo)優(yōu)化問題，目的是在乘客總時間費(fèi)用和公交企業(yè)營運(yùn)費(fèi)用之間找出均衡點，引入加權(quán)因子α和β，將乘客時間費(fèi)用函數(shù)與公交線路營運(yùn)成本函數(shù)轉(zhuǎn)化為單目標(biāo)函數(shù)，得到公交發(fā)車間隔優(yōu)化模型為：

將式（8），（15）代入式（16），得：

該目標(biāo)函數(shù)必須滿足4個約束條件：

1）公交車輛最大擁擠度φ的約束

用平均滿載率η表示公交車輛最大擁擠度φ的約束，也就是全天內(nèi)所有公交車輛的平均滿載率η不能超過公交車輛最大擁擠度φ，而平均滿載率η與公交車輛最大非擁擠容量Cmax、全天內(nèi)上車的乘客數(shù)及發(fā)車總次數(shù)f有關(guān)。

2）公交線路配車規(guī)模的約束

確定某時段配車數(shù)的原則是，既要保證有足夠的服務(wù)質(zhì)量，又要保證配車數(shù)最小，因此該線路的配車數(shù)受到最大配車數(shù)Nmax和最小配車數(shù)Nmin的約束。其中線路某時段配車數(shù)與該時段最高斷面通過量Hi，max、期望滿載率ηi及車容量C有關(guān)。

3）對相鄰兩車最大與最小發(fā)車間隔的約束

若公交車發(fā)車間隔過長，則會導(dǎo)致乘客候車時間增長；若公交車發(fā)車間隔過短，則會導(dǎo)致公交運(yùn)營成本增加。因此公交車的發(fā)車間隔受到最大和最小發(fā)車間隔的約束：

4）對任意相鄰兩車之間發(fā)車時間間隔之差的約束

為了確保發(fā)車時間的連續(xù)性，對研究時段內(nèi)相鄰的兩輛公交車的發(fā)車間隔之差進(jìn)行一定范圍的限制，取ε為趨于零的一個數(shù)，即：

2 遺傳禁忌算法設(shè)計

2.1 遺傳禁忌算法的適應(yīng)性分析

遺傳算法（簡稱為GA算法）與其他優(yōu)化算法相比，其優(yōu)點是具有內(nèi)在的隱并行性，有較好的全局尋優(yōu)能力；其缺點是不能充分利用系統(tǒng)的反饋信息，同一種群的個體一旦出現(xiàn)大量被繁殖的情況就很容易形成近親繁殖，造成算法的局部搜索及過早收斂，這種現(xiàn)象對于多峰值函數(shù)特別容易出現(xiàn)。

禁忌算法（簡稱為TS算法）是對局部鄰域搜索的一種擴(kuò)展，是一種全局逐步尋優(yōu)算法，也是一種模擬智力過程的“爬山”算法［10］。它可以模仿人類的記憶功能，使用禁忌表來封鎖剛剛搜索過的區(qū)域以避免迂回搜索，同時赦免被禁忌的一些局部最優(yōu)的對象，進(jìn)而使得搜索途徑多樣化，實現(xiàn)全局優(yōu)化。

為了保持GA算法與TS算法各自的特點，將這兩種算法有機(jī)結(jié)合組成混合算法。遺傳禁忌算法（簡稱為GATS）的混合結(jié)構(gòu)如圖1所示。即先用GA算法進(jìn)行全局搜索，就是將GA算法在交叉和變異操作中產(chǎn)生的多個新個體看作TS算法中當(dāng)前解x的鄰域Xi（1≤i≤n），然后對鄰域Xi（1≤i≤n）中的每一個個體用TS算法進(jìn)行局部搜索。將GA算法并行的大范圍搜索能力和TS算法的局部搜索能力結(jié)合起來，既保證了混合算法的收斂性能，又避免了局部出現(xiàn)極小值。

圖1 GATS算法的混合結(jié)構(gòu)Fig.1 The hybrid structure of GATS

2.2 GATS混合算法設(shè)計

2.2.1 確定編碼方案

采用浮點數(shù)編碼的真實值編碼方法，即各個染色體中各個基因座上的值就是決策變量的真實值。例如：與染色體X＝［x1x2… xn］T相對應(yīng)的編碼串為［x1，x2，…，xn］。采用編碼位置即基因座上的值就表示該時刻距離首發(fā)時刻的時間，其單位為min。

2.2.2 構(gòu)造適用度函數(shù)

計算個體適應(yīng)度的函數(shù)或過程稱為適應(yīng)度函數(shù)（Fitness Function），記為F（x）。為了選擇算子設(shè)計的方便，要求適應(yīng)度為非負(fù)值.本研究中的發(fā)車間隔問題屬于求解目標(biāo)函數(shù)最小的優(yōu)化問題，轉(zhuǎn)換規(guī)則為：

其中Cmax為同一代群體中全部目標(biāo)函數(shù)相對比較大的數(shù)，故這里適應(yīng)度函數(shù)為：

2.2.3 遺傳算子操作

遺傳算子操作過程是模擬生物繁衍、進(jìn)化的過程，體現(xiàn)了優(yōu)勝劣汰的基礎(chǔ)思想。遺傳算子包括選擇算子、交叉算子和變異算子。

1）選擇算子

用適應(yīng)度比例的方法來計算。設(shè)群體規(guī)模為Npop，設(shè)個體Xi的適應(yīng)度為f（xi）（1≤i≤Npop），則個體Xi被選擇的概率為：

在選擇算子中加入懲罰算子，對于不能滿足公交發(fā)車間隔優(yōu)化條件的劣解，下一代將不能遺傳到。在交配池中，放入按照截斷方式選出的Npop個染色體。

2）交叉、變異

①隨機(jī)生成［0，1］之間的數(shù)ri，i＝1，2，…，Npop。如果ri≤pc，則交配池中第i個染色體作為交叉的父代，產(chǎn)生pc×Npop個父代染色體。②對每對雙親進(jìn)行交叉操作，產(chǎn)生2個子代。③調(diào)用禁忌搜索法（簡稱為TSR），重組交叉后得到的子代。④若ri≤pm，則調(diào)用禁忌搜索變異法（簡稱為TSM），對交配池中第i個染色體進(jìn)行變異操作。

3）停止運(yùn)算

對全天峰值時段發(fā)車間隔進(jìn)行優(yōu)化運(yùn)行，改進(jìn)發(fā)車間隔的質(zhì)量，約定最大迭代次數(shù)為終止條件，則最終輸出每個時段的最優(yōu)解x＊為近似最優(yōu)的方案。

3 案例分析

3.1 案例背景

南寧市67路（金橋站－安吉站），上行方向全程14.3km，公共汽車統(tǒng)一票價1元／人次，行車方向共28個站（Z1～Z28），其中第21站為友愛大樹腳站，因軌道二號線的修建暫時停用。首班車發(fā)車時間為早上6∶15，末班車為晚上23∶00，車型為10m宇通ZK6108HGB，計劃車容量為40人。經(jīng)跟蹤調(diào)查與既有統(tǒng)計資料處理后，得到各個時段年平均日最高乘客通過量，如圖2所示。

3.2 決策變量的確定

1）時間價值系數(shù)Cα的確定

圖2 各時間段年平均日最高乘客通過量Fig.2 The amount of maximum passenger per day at each period

根據(jù)本研究的調(diào)查，2013年南寧市用人單位發(fā)布職位的平均薪酬為3 064元／mon，按照周末兩天休息及國家法定節(jié)假日的放假時間，一年有115d的休息時間，有250d為正常工作日，平均每天按工作8h計算，得到員工平均每分鐘的工資為：

2）GATS混合算法參數(shù)的確定

為了確定交叉概率和變異概率等GA算法的參數(shù)以及TS算法中禁忌表的長度和破禁準(zhǔn)則，作者進(jìn)行了大量調(diào)試，并兼顧計算量和運(yùn)算效果，采用基于適值的準(zhǔn)則為破禁策略，最終確定了效果較好的參數(shù)：交叉概率pm取0.005，變異概率pc取0.75，群體規(guī)模Npop取100，遺傳迭代次數(shù)Ngen取100，禁忌表規(guī)模取Npop×0.6。

3.3 運(yùn)算結(jié)果

根據(jù)已知資料和所建模型，利用計算機(jī)進(jìn)行了仿真實驗。實驗結(jié)果表明：①GATS算法收斂快，在公交調(diào)度優(yōu)化求解問題上具有一定的優(yōu)越性，如圖3所示。②用GATS算法計算，得到了南寧市67路優(yōu)化后的發(fā)車間隔。優(yōu)化后的乘客時間費(fèi)用和企業(yè)營運(yùn)成本明顯低于優(yōu)化前的，乘客等車時間過長或公交車輛滿載率不均形成的資源浪費(fèi)現(xiàn)象均得到了改善，乘客和公交公司的整體利益取得了較好的效果，見表1。

圖3 GATS與GA收斂過程的比較Fig.3 The convergences of GATS and GA

表1 優(yōu)化前、后發(fā)車間隔及費(fèi)用參數(shù)對比Table 1 The grid spacing and cost parameters before and after the optimization

4 結(jié)語

通過對城市現(xiàn)狀公交運(yùn)營調(diào)度的分析，建立了以乘客等車時間和公交線路運(yùn)營費(fèi)用為優(yōu)化目標(biāo)的調(diào)度模型。利用遺傳算法融合禁忌算法，對公交線路發(fā)車間隔問題進(jìn)行了優(yōu)化，將遺傳算法并行的全局搜索能力和禁忌算法的局部搜索能力有效結(jié)合起來，為公交線路發(fā)車間隔優(yōu)化問題的求解提供了合理、有效的新方法。研究結(jié)果表明：GATS混合算法比標(biāo)準(zhǔn)GA算法具有更好的效果，是解決公交線路發(fā)車間隔優(yōu)化問題的一個有效方法。

（References）：

［1］Zhong－h(huán)ua W，Xia Z，Ke－wen W，et al.Bus dispatching interval optimization based on adaptive bacteria foraging algorithm［J］.Mathematical Problems in Engineering，2012，583（3）：295－308.

［2］Wagale M，Singh A P，Sarkar A K，et al.Real－time optimal bus scheduling for a city using ADTR model［J］.Procedia－Social and Behavioral Sciences，2013，104：845－854.

［3］Luhua S，Yin H，Xinkai J.Study on method of bus service frequency optimal model based on genetic algorithm［J］.Procedia Environmental Sciences，2011，10：869－874.

［4］賀堯成，葉明，楊明.基于客流量變化的智能公交調(diào)度問題研究［J］.中國制造業(yè)信息化，2011，40（11）：8－12.（HE Yao－cheng，YE Ming，YANG Ming.Research on dynamic bus scheduling based on passenger flow fluctuation［J］.Journal of Chinese Manufacturing Informatization，2011，40（11）：8－12.（in Chinese））

［5］Sun C J，Zhou W，Wang Y Q.Scheduling combination and headway optimization of bus rapid transit［J］.Journal of Transportation Systems，Engineering and Information Technology，2008，8（5）：61－67.

［6］姚錦寶，姚寶珍，于濱.基于雙種群遺傳算法的公交線路發(fā)車間隔優(yōu)化［J］.深圳大學(xué)學(xué)報，2012，29（6）：559－564.（YAO Jin－bao，YAO Bao－zhen，YU Bin.A bus headway optimization model with dual－population genetic algorithm［J］.Journal of Shenzhen University Science and Engineering，2012，29（6）：559－564.（in Chinese））

［7］程杰，鄧衛(wèi)，蒯婷婷.基于期望滿足概率的公交發(fā)車間隔計算模型［J］.現(xiàn)代交通技術(shù)，2006（4）：46－49.（CHENG Jie，DENG Wei，KUAI Ting－ting.The calculation model of bus frequency based on expected probability［J］.Journal of Modern Transportation Technology，2006（4）：46－49.（in Chinese））

［8］曹蓮英，侯琳，李文勇.多目標(biāo)演化算法在公交車輛發(fā)車間隔優(yōu)化中的應(yīng)用［J］.東南大學(xué)學(xué)報：自然科學(xué)版，2009，39（增刊（I））：260－265.（CAO Lian－ying，HOU Lin，LI Wen－yong.Application of multi－objective evolutionary algorithm in bus departing interval optimization［J］.Journal of Southeast University：Natural and Science Edition，2009，39（Sup（Ⅰ））：260－265.（in Chinese））

［9］黃海南，翁劍成.劉力力.基于多源數(shù)據(jù)的常規(guī)公交運(yùn)營成本測算方法研究［J］.交通信息與安全.2013，31（6）：6－10.（HUANG Hai－nan，WENG Jian－cheng.A method for bus operation cost calculation based on multisource date［J］.Journal of Transport Information and Safety，2013，31（6）：6－10.（in Chinese））

［10］周媛，鄧衛(wèi)，胡啟洲.基于遺傳禁忌算法的城市公交線網(wǎng)優(yōu)化研究［J］.武漢理工大學(xué)學(xué)報，2011，35（1）：42－45.（ZHOU Yuan，DENG Wei，HU Qi－zhou.Study on the optimization of public transit network based on genetic algorithm and taboo search algorithm［J］.Journal of Wuhan University of Technology，2011，35（1）：42－45.（in Chinese））