基于改進遺傳算法并考慮尾氣排放的公交組合調度

（上海理工大學管理學院，上海 200093）

0 引言

隨著城市化進程的加快，我國汽車保有量不斷攀升，交通需求與供給之間的不平衡導致了城市交通擁堵問題。公交車因其容量大、人均占用道路資源少等特點成為解決交通問題的重要方式之一。然而現階段城市復雜的交通環境使得公交運行效率較低，無法滿足人們多樣的出行需求。另外，公交在相同路段的行駛時間遠超私家車，且與私家車點對點的運行模式不同，其運行中產生的額外的尾氣排放問題也不容忽視。因此，在提高公交運行效率、緩解城市交通擁堵的同時減少其尾氣排放，成為亟需解決的問題。

由于居民的出行需求在公交線路上并不是均勻分布的，若公交只采用單一的全程車運營模式，會造成高峰期高客流段內車廂過于擁擠、低客流段載客率低，平峰期間則產生運力浪費，直接影響乘客的出行方式選擇，所以公交運營管理部門會采取多樣的公交運行模式來提高其運行效率[1]。通常來說，若單線路單向上的客流有較大差異，公交運營單位會采取跳站調度；若單線路雙向的客流分布不對稱同時某一區段的客流量較大，則會采取區間車調度[2]。

部分學者針對跳站調度進行了研究，Liu 等人[3]以連續的3 輛車為研究對象，規定僅第2 輛車可以跳站且能在除首尾站點外的任意站點跳站，然后以最小化乘客總時間與公交運營成本為目標建立模型，利用遺傳算法結合蒙特卡羅模擬對公交停靠方案進行求解；Leiva 等人[4]提出了一種考慮車輛容量約束與換乘的跳站模型，可確定停靠方案、發車頻率及車輛類型，經研究發現：行駛里程越長，跳站調度的效益就越大。在區間車調度研究方面，Site等人[5]以最小化乘客成本與運營商成本為目標，通過全局搜索法確定區間車的最佳停靠方案與發車頻率，經研究發現：區間車運行適用于客流高峰時段；Tirachini等人[6]為提高客流量較大路段的公交服務效率，以運營商與乘客的成本最小為優化目標，建模求解區間運行方案、發車頻率和車內容量的最優值，通過研究發現：出行需求越集中，區間車調度運行效益就越大。在組合調度研究方面，韓笑宓[7]對跳站車、區間車、全程車3 種運行模式進行組合調度，以發車頻率、區間車折返的站點及跳站車的停靠站點為優化對象，對客流需求與配車數這兩個重要參數進行敏感性分析；Zhang 等人[8]將區間運行與跳站結合，認為在有跳站調度產生的基礎上，若雙向有相同連續運行的區段，即可作為區間車的運行區間。

不少學者針對公交車尾氣排放特點進行了研究。Yu 等人[9]通過收集道路上的公交排放數據，分析得出約50%的公交尾氣排放量產生于站點與交叉口，因為這兩處皆有明顯的停車與起步過程。Mahesh 等人[10]通過分析4 條公交線路在高峰與非高峰時段的數據發現，公交車在高峰期的停車次數多于非高峰時期，且怠速時間更長，排放量也顯著增加。王志強等人[11]研究發現，公交變速行駛時尾氣排放量相對較高，且處于怠速狀態時仍會產生一定的排放量，故提出可通過降低行駛加減速比例與怠速行駛時間來控制尾氣排放。Alam 等人[12]通過收集路線上的瞬時速度等數據，估算出路段、車站處的排放量及人均排放量，發現采用有限站停靠方案的公交尾氣排放量相比采用全停方案有明顯降低。

由以上分析可知，大多研究僅分析如何通過不同的運營模式提升公交系統效率，或僅探究公交尾氣排放的影響因素，少有研究將公交尾氣排放與調度聯系在一起，從規劃層面將減少尾氣排放作為優化目標之一[13]。調度方案決定了公交車在線路上的運行狀態，對公交企業、乘客、環境都會產生影響，因此僅考慮公交企業與乘客兩者的利益是不夠的。

跳站調度與區間車調度由于只運行有限的站點，可適當提高車輛運行速度，縮短運行時間與降低行駛過程中的加減速比例，加快車輛周轉，因此這兩種調度方案有利于減少尾氣排放。鑒于此，本文根據已知線路規劃周期內的出行OD 量，以乘客的時間總成本、公交車的運行總成本與尾氣排放成本之和最小為目標，建立一種跳站與區間車組合的調度模型，通過模型求解確定公交車的最優停靠方案與發車頻率，旨在優化公交運營模式、提高運行效率的同時，減少尾氣排放。

1 公交組合調度模型

本文將對Zhang等人[8]建立的組合調度模型進行改進。原模型細致地劃分了乘客的出行需求，并分析了不同調度模式下公交載客量的變化及公交車在線路上的運行過程。本文將在此基礎上分析公交車減速進站、在站點怠速停留、加速出站及在路段上勻速行駛過程中的尾氣排放量變化情況，引入不同污染物的尾氣排放成本與公交購置成本，綜合考慮調度策略對環境、乘客與公交企業的影響。

1.1 公交跳站調度模型

建模前作如下假設：①路段上公交以勻速行駛；②車隊內所有車輛均為同一車型；③每個車隊所接受的客流量由發車頻率決定，發車頻率越高的車隊所承載的乘客數量越多。

針對同向站點客流分布不均的情況，本文提出一種車輛調度方案：A 車隊運行所有站點，B車隊采取跳站運行。此時，A 車隊、B 車隊均從起始站點運行至末尾站點，但不同之處在于：B車隊在某些站點不停靠，只運行部分站點。B 車隊的運行模式如圖1 所示，其在線路上進行雙向運行，上行方向從第1 站運行至第N站，然后掉頭從第N+1 站運行至第2N站，不在某些客流集散量較小的站點停靠。

圖1 B車隊運行示意圖

1.1.1 乘客分類分析

首先對不同OD 的客流進行分類，第一類乘客出行的起始站點與希望到達的目的地站點間僅由A 車隊服務，所以僅能乘坐A 車隊的車。該類乘客客流量為：

第二類乘客出行的起始站點與希望到達的目的地站點間由A 車隊與B 車隊同時服務，所以其既可乘坐A 車隊的車，又可乘坐B 車隊的車。該類乘客客流量為：

第三類乘客同第二類乘客，兩車隊的車都可供其選擇。但由于B車隊的車輛跳過了某些站點，此時在A 車隊與B 車隊中選擇B 車隊會節省一部分時間。該類乘客客流量為：

1.1.2 乘客總時間成本模型

假設乘客在同一站點的到達率為均勻分布，兩車隊以一定的頻率服務各站點，乘客在站點處的平均等待時間為1/2 的車頭時距。將站點類型分為A 類站點與B 類站點，A 類站點僅供A 車隊停靠，B類站點供A車隊與B車隊共同停靠。

A類站點的乘客等待時間為：

B類站點的乘客等待時間為：

公交車在站點處的停靠時間與乘客上下車的人數有關，而上下車人數可以通過客流OD 矩陣求出，每個站點上車人數為OD 矩陣中的行向量之和，每個站點的下車人數為列向量之和。

A車隊在第k站的上車人數為：

A車隊在第k站的下車人數為：

B車隊在第k站的上車人數為：

B車隊在第k站的下車人數為：

乘客在車時間等于其上車的起點站到下車的終點站間的車輛運行時間加上車輛在站點處的停靠時間。車輛在站點處的停靠時間等于其進出每站的加減速時間與乘客上下車時間之和。

故A車隊乘客的在車總時間為：

B 車隊因產生跳站而節省了在某些站點的停靠時間與進出站加減速時間，故其乘客的在車總時間為：

則乘客的時間總成本為：

式（12）中：Z1為乘客的時間總成本（元）；W為單位時間乘客在站點處的等待時間成本（元/min）；V為單位時間乘客在車時間成本（元/min）。

1.1.3 車隊運行總成本模型

車隊的運行總成本包括兩部分，一部分是與運行時間相關的成本，另一部分是與運行里程相關的成本。

A 車隊的運行總時間等于其在站間的運行時間與在站點的停靠時間之和：

同理，B車隊的運行總時間為：

則在規劃期內，與公交運行時間有關的公交總購置成本為：

與公交運行總里程相關的運行成本為：

式（16）中：CR為與運行里程相關的公交運行成本（元）；R為單位里程的公交運營成本（元/m），此時A 車隊與B 車隊皆運行駛過N站，所以此處的總成本與其發車頻率正相關。

則公交的運行總成本Z2為：

1.1.4 車隊尾氣排放成本模型

公交在線路上的運行過程包括在站點間的勻速行駛過程以及站點處的停靠過程。而停靠過程又由減速進站直至速度為零、怠速停站等待乘客上下客、加速離站直至速度恢復為v三個階段組成，不同行駛工況下的尾氣污染物排放量各有不同。

在路段行駛時的排放量與勻速行駛時間相關，進站出站過程的排放量與加減速時間相關，而怠速停留時的排放量與乘客的上下車時間相關，則A車隊的污染物排放成本為：

此時，由于B 車隊產生了跳站，所以直接節省某些站點處加減速與怠速時的尾氣排放量。

故B車隊的污染物排放成本為：

式（18）～式（19）中：EA為A 車隊的污染物排放成本（元）；EB為B 車隊的污染物排放成本（元）；e1為公交怠速時的排放率（g/s）；e2為公交減速時的排放率（g/s）；e3為公交加速時的排放率（g/s）；e4為公交勻速行駛時的排放率（g/s）；s為污染物的種類，s=1,2,3，1 為NOX，2 為HC，3為CO；U為不同污染物單位質量下的社會影響成本（元/g）。

則公交的污染排放總成本Z3為：

1.1.5 車內容量約束限制

為保證乘客在車內的乘坐舒適性，必須對車內的乘客人數進行約束，對A 車隊與B 車隊采取相同的方法進行計算。

各車隊在每站的車內人數流動為在該站的上車人數減去下車人數：

各車隊在第k站的車內人數等于從首站到第k站的人數流動的累加，即：

在車輛運行過程中為滿足乘客的舒適度要求，每站的車內人數不能超過額定容量的80%，故所有站點的車內負載人數要滿足一定的約束，即：

式（21）～式（23）中：qk為第k站的車內人數流動量（人）；為某車隊在第k站的上車人數（人）；為某車隊在第k站的下車人數（人）；Qk為某車隊在第k站的車內人數（人）；Qmax為車內負載人數的最大值（人）；Q為額定車內容量（人）。

1.2 公交跳站與區間車組合調度模型

若B車隊在線路的首尾兩端產生了連續跳站，則產生區間車方案，即B 車隊只運行當前方案雙向運行的共同區間，如圖2所示。

圖2 組合調度示意圖

在圖2 中，m1為上行方向起始端連續跳站的站點集合；n1為上行方向末尾端連續跳站的站點集合；n2為下行方向起始端連續跳站的站點集合；m2為下行方向末尾端連續跳站的站點集合；m為m1與m2的交集，表示B車隊在公交線路前端略過的站點數量；n為n1與n2的交集，表示B 車隊在公交線路后端略過的站點數量。

此時，B車隊的運行路線為從線路的第m+1站運行至第N-n站，然后掉頭從第N+n站運行至2N-m站，直接略過不需要停靠的m+n個站點，縮短了車輛的空駛距離。

一旦產生了區間車方案，又會減少車輛的運行時間，減少部分計算公式為：

更新車隊與運行里程相關的成本為：

更新車隊與運行時間相關的成本為：

更新車隊的尾氣排放成本為：

1.3 目標函數

目標函數F為最小化乘客的時間總成本、公交的運行總成本及尾氣排放成本之和：

2 模型求解算法設計

本模型需要對B 車隊的停靠方案和兩車隊的發車頻率都進行優化，屬于NP 難題（Non-Deter?ministic Polynomial-Hard,NP-Hard），一般采用啟發式算法求解。

2.1 遺傳算法嵌套全局搜索算法

Zhang 等人[8]針對停靠方案使用遺傳算法求解，對發車頻率采取窮舉全局搜索法。具體的算法流程如下：

（1）設置遺傳參數，包括：種群數量G、迭代次數M、交叉率、變異率、fA與fB的取值區間；

（2）編碼：直接使用0,1 編碼生成B 車隊的停靠方案，1表示該站停靠，0表示該站跳過；

（3）設計適應值：所求的目標函數F為總成本最小值，將適應值f設計為其倒數形式，如式（29）所示：

在計算適應值時，針對產生的每個停靠站點方案，帶入{fA,fB}的所有組合進行計算，選擇出該方案下的最佳發車頻率組合并存儲。

（4）選擇：采用輪盤賭選擇法，當個體的適應值累積概率大于隨機產生的累積概率時，則被選入新的種群。

（5）交叉：采用單點交叉法，隨機選中1點，兩個染色體交換關于此點的左右部分的基因序列。

（6）變異：采用單點變異法，隨機選中1點，若為1即變異為0，若為0即變異為1。

（7）精英保留策略：選出上一代中的最優個體，放進即將產生的下一代種群中。

（8）滿足迭代次數，則終止算法。

具體的算法流程如圖3所示。

該算法有兩點缺陷：①假設A 車隊的頻率區間內有g1個數，B 車隊的頻率區間內有g2個數，初始種群中個體數設為u1個，遺傳操作循環u2次，整個尋優過程中需對適應值計算g1g2u1u2次，計算規模龐大、耗時久；②使用遺傳算法嵌套窮舉搜索的方法相當于將停靠方案與發車頻率分開優化，沒有考慮規劃時的重要性差異，忽視了發車頻率在規劃中起的決定性作用。

圖3 原算法流程圖

2.2 動態概率改進遺傳算法

本文提出了一種將公交停靠方案與發車頻率同時優化，并將相互影響關系考慮其中的新遺傳算法。在經典的遺傳算法中，交叉率與變異率在算法起始時就已給定，并在后續運算中不再改變。但在本文的問題中，停靠方案與發車頻率兩要素在規劃時明顯存在主次關系。因此，本文提出的新算法在搜索時先給予發車頻率一個較大的變化概率，后隨迭代次數增加不斷減小；給予停靠方案相對較小的變化概率，后隨迭代次數增加不斷增大。這樣做的目的是：在搜索前期讓發車頻率先大致確定下來，在搜索中慢慢減小其重要影響程度；而停靠方案在搜索前期以較小的概率變化，待發車頻率大致確定后，再增加其變化率進行逐步確定。具體的算法流程如下。

（1）設置遺傳參數：設種群規模為G，迭代次數為M，交叉率變化區間為[J1,J2]，變異率變化區間為[B1,B2]，變化率的相關計算公式如下。

由于變異率與交叉率的變化機理相同，此處只展示交叉率變化示意圖（見圖4）。從圖中可看出，隨著迭代次數的不斷增加，從J1增大到J2，而從J2減小到J1，在迭代的過程中都呈線性變化。

圖4 交叉率變化示意

（2）直接使用0,1 編碼生成B 車隊的停靠方案，兩車隊發車頻率采用二進制編碼。染色體編碼為[X fA fB]，此處的X代表B車隊的停靠方案。

（3）設計適應值：所求的目標函數F為總成本最小值，將適應值f設計為其倒數形式（f的計算公式同式（29））。在計算前，應先提取染色體中的各個部分，再解碼發車頻率。

（4）選擇：采用輪盤賭選擇方法，當個體的適應值累積概率大于隨機產生的累積概率時，則被選入加入新的種群中。

（5）交叉：此處采用隨機單雙點混合交叉，分別產生兩個隨機數與進行比較，可能會在停靠方案與發車頻率位置都產生交叉點，也可能分別在2個位置單獨產生交叉點，如圖5所示。

圖5 交叉點位置圖

（6）變異：此處采用隨機單雙點混合變異，與交叉模式類似，也會產生3種位置變異的情況。

（7）滿足迭代次數，則終止算法。

新算法流程如圖7所示。

3 案例分析

假設存在某條雙向公交路線，共有10 個站點，全長8 660m。公交車在站點處的加減速時間和為0.2min，人均上車時間為0.03min/人，人均下車時間為0.02min/人，車輛在路段上的行駛速度為334m/min。人均等車時間成本為0.13元/min，人均車內時間成本為0.12 元/min。3 要素比例取0.1∶0.5∶1。

各站點間距離如表2 所示，反向站間距與正向相同。

表2 站點間距 單位：m

圖7 新算法流程圖

本文采用上午7:30—8:30的客流OD量（見表3）進行計算。

表3 客流OD 單位：人

表3 （續）

公交車輛的基礎數據[11,14]如表4所示。

表4 公交車輛基礎數據

公交尾氣中不同污染物的排放率如表5[15]所示。

表5 尾氣中不同污染物的排放率

3.1 動態概率改進遺傳算法求解結果

本節采取新算法（動態概率改進遺傳算法）對模型進行求解。遺傳參數的設定為：迭代次數G=500，種群內個體數量M=100，交叉率的取值區間為[0.5,0.7]，變異率的取值區間為[0.05,0.07]。優化后的B 車隊停靠方案及優化效果如表6所示。

表6 效益對比

通過新算法求解得出：B 車隊的運行區間為第5 站～第9 站，其中在上行方向跳過第6 站與第9 站，在下行方向跳過第6 站。原先需要14 輛全程車在該時段內服務，采取綜合調度方案后，由12 輛全程車與2 輛采取跳站的區間車進行服務，總成本下降了4.49%，雖然其中乘客的時間總成本上升了5.04%，但公交的運行總成本下降了7.12%，尾氣排放成本下降了8.22%。

3.2 兩種算法效益對比

（1）新算法效益

使用本文提出的新算法的用時情況如表7所示。

表7 新算法用時統計

在種群規模為100，迭代次數為500次的情況下，新算法需對適應值計算50 100 次，共耗時95.973s，大約2min 即可求解完畢得到最優解。算法的迭代情況如圖8所示。

圖8 新算法迭代圖

從圖8 中可看出，大約在100 次不到的情況下算法就已收斂，證明了該算法的有效性。

（2）原算法效益

設定A車隊與B車隊發車頻率區間均取[2,20]。若原算法采用與新算法相同的參數，需對適應值計算18 050 000 次，耗時過長且無法運行，所以設置迭代次數G為100 次，種群內個體數M取50個，交叉率取0.7，變異率取0.07。原算法的用時情況如表8所示。

表8 原算法用時統計

在該種情況下，需對適應值計算1 823 050次，耗時3 242.312s，約54min。算法的迭代情況如圖9 所示。運行中發現，當整個算法完成時的目標函數值為536.90，還未搜索到最優解，并且計算時間過長，可見原算法效率相對較低。

圖9 原算法迭代圖

4 結語

本文分析了不同調度策略下乘客在站點處的等待時間與在車時間、公交的運行過程及其在運行線路上的尾氣排放情況，建立以乘客時間總成本、公交運行總成本與尾氣排放成本三者之和最小為目標的組合調度模型。通過算例分析得出：此種組合調度模型可使總成本降低4.49%，能提升公交系統的運行效率。另外，本文提出的基于動態概率改進的遺傳算法考慮了不同要素在優化過程中的重要性差異及主次關系，在算法搜索過程中使要素的變化率隨著迭代次數的變化而不斷改變。算例求解結果表明，該算法能在2min內迅速找到最優解，大幅縮減了求解時間，說明其對于求解關聯性較大的多要素優化問題具有很好的效果。但是，本文在模型研究中假設乘客在同一站點的到達率為均勻分布，與實際情況存在出入，未來可針對動態客流對公交實時組合調度方案進行研究。在算法研究方面，還可針對交叉變異概率的不同取值范圍對求解效率的影響進行深入研究。