基于遺傳禁忌算法的公交線路發車間隔優化

周 騫，韋鳳連，劉 菊

（長沙理工大學交通運輸工程學院，湖南長沙 410004）

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

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

1 模型的建立

1.1 模型的假設

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

1.2 乘客時間費用函數

與公交運營調度相關的乘客時間費用C乘由乘客等車費用Cw和乘客乘車費用Cr兩部分費用組成［6］。表示為：

1）乘客等車費用

乘客等車費用Cw包括：①在發車間隔Δti內，到站等車的乘客均能乘上第1輛車；②未能乘上第1輛到達的車輛，出現2次等車并且均能乘上第2輛車。

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

當乘客到達服從泊松分布時，乘客等車時間服從負指數分布。那么，第i時段在第j站的乘客等待時間為：

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

乘客等車費用為：

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

2）乘客在途乘車費用

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

假設車輛從第Cm站到第j＋1站的平均運行時間為那么，乘客在途乘車時間費用為：

式中：Cr為乘客乘車費用為在第i時段車輛從第j站到第j＋1站平均運行時間為在第i時段車輛從第j站到第j＋1站車上的乘客數。

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

1.3 公交企業營運成本函數

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

1）燃油消耗費

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

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

因此，公交車輛每天燃油消耗費為：

2）駕駛員薪酬費

公交企業根據線路車隊規模的最小配車數Nmin來購置車輛，對每輛車分配司售人員，而公交企業支付給駕駛人員的薪酬費與每輛車配備的司機人數R有關。每輛車每天所需支付給司機駕駛員薪酬費用為：

式中：CR為車隊每天所需司機的總工資費用；CR0為每位司機每天所獲得的工資費用。

3）車輛折舊費

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

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

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

4）維修保養費

維修費用包括公交車輛維修和養護費用，按每輛車每天例行的保養維護費用S0計算。

則公交企業每天營運成本為：

1.4 發車間隔優化模型

為了使得整個公交系統的總費用最低，本研究采用線性加權的方法，將乘客的等車成本和車輛營運成本兩種費用轉化為單目標優化問題，目的是在乘客總時間費用和公交企業營運費用之間找出均衡點，引入加權因子α和β，將乘客時間費用函數與公交線路營運成本函數轉化為單目標函數，得到公交發車間隔優化模型為：

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

該目標函數必須滿足4個約束條件：

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

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

2）公交線路配車規模的約束

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

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

若公交車發車間隔過長，則會導致乘客候車時間增長；若公交車發車間隔過短，則會導致公交運營成本增加。因此公交車的發車間隔受到最大和最小發車間隔的約束：

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

為了確保發車時間的連續性，對研究時段內相鄰的兩輛公交車的發車間隔之差進行一定范圍的限制，取ε為趨于零的一個數，即：

2 遺傳禁忌算法設計

2.1 遺傳禁忌算法的適應性分析

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

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

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

圖1 GATS算法的混合結構Fig.1 The hybrid structure of GATS

2.2 GATS混合算法設計

2.2.1 確定編碼方案

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

2.2.2 構造適用度函數

計算個體適應度的函數或過程稱為適應度函數（Fitness Function），記為F（x）。為了選擇算子設計的方便，要求適應度為非負值.本研究中的發車間隔問題屬于求解目標函數最小的優化問題，轉換規則為：

其中Cmax為同一代群體中全部目標函數相對比較大的數，故這里適應度函數為：

2.2.3 遺傳算子操作

遺傳算子操作過程是模擬生物繁衍、進化的過程，體現了優勝劣汰的基礎思想。遺傳算子包括選擇算子、交叉算子和變異算子。

1）選擇算子

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

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

2）交叉、變異

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

3）停止運算

對全天峰值時段發車間隔進行優化運行，改進發車間隔的質量，約定最大迭代次數為終止條件，則最終輸出每個時段的最優解x＊為近似最優的方案。

3 案例分析

3.1 案例背景

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

3.2 決策變量的確定

1）時間價值系數Cα的確定

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

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

2）GATS混合算法參數的確定

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

3.3 運算結果

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

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

表1 優化前、后發車間隔及費用參數對比Table 1 The grid spacing and cost parameters before and after the optimization

4 結語

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

（References）：

［1］Zhong－hua 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］賀堯成，葉明，楊明.基于客流量變化的智能公交調度問題研究［J］.中國制造業信息化，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］姚錦寶，姚寶珍，于濱.基于雙種群遺傳算法的公交線路發車間隔優化［J］.深圳大學學報，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］程杰，鄧衛，蒯婷婷.基于期望滿足概率的公交發車間隔計算模型［J］.現代交通技術，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］曹蓮英，侯琳，李文勇.多目標演化算法在公交車輛發車間隔優化中的應用［J］.東南大學學報：自然科學版，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］黃海南，翁劍成.劉力力.基于多源數據的常規公交運營成本測算方法研究［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］周媛，鄧衛，胡啟洲.基于遺傳禁忌算法的城市公交線網優化研究［J］.武漢理工大學學報，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））