（上海理工大學(xué)管理學(xué)院，上海 200093）

0 引言

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

由于居民的出行需求在公交線(xiàn)路上并不是均勻分布的，若公交只采用單一的全程車(chē)運(yùn)營(yíng)模式，會(huì)造成高峰期高客流段內(nèi)車(chē)廂過(guò)于擁擠、低客流段載客率低，平峰期間則產(chǎn)生運(yùn)力浪費(fèi)，直接影響乘客的出行方式選擇，所以公交運(yùn)營(yíng)管理部門(mén)會(huì)采取多樣的公交運(yùn)行模式來(lái)提高其運(yùn)行效率[1]。通常來(lái)說(shuō)，若單線(xiàn)路單向上的客流有較大差異，公交運(yùn)營(yíng)單位會(huì)采取跳站調(diào)度；若單線(xiàn)路雙向的客流分布不對(duì)稱(chēng)同時(shí)某一區(qū)段的客流量較大，則會(huì)采取區(qū)間車(chē)調(diào)度[2]。

部分學(xué)者針對(duì)跳站調(diào)度進(jìn)行了研究，Liu 等人[3]以連續(xù)的3 輛車(chē)為研究對(duì)象，規(guī)定僅第2 輛車(chē)可以跳站且能在除首尾站點(diǎn)外的任意站點(diǎn)跳站，然后以最小化乘客總時(shí)間與公交運(yùn)營(yíng)成本為目標(biāo)建立模型，利用遺傳算法結(jié)合蒙特卡羅模擬對(duì)公交?？糠桨高M(jìn)行求解；Leiva 等人[4]提出了一種考慮車(chē)輛容量約束與換乘的跳站模型，可確定?？糠桨浮l(fā)車(chē)頻率及車(chē)輛類(lèi)型，經(jīng)研究發(fā)現(xiàn)：行駛里程越長(zhǎng)，跳站調(diào)度的效益就越大。在區(qū)間車(chē)調(diào)度研究方面，Site等人[5]以最小化乘客成本與運(yùn)營(yíng)商成本為目標(biāo)，通過(guò)全局搜索法確定區(qū)間車(chē)的最佳?？糠桨概c發(fā)車(chē)頻率，經(jīng)研究發(fā)現(xiàn)：區(qū)間車(chē)運(yùn)行適用于客流高峰時(shí)段；Tirachini等人[6]為提高客流量較大路段的公交服務(wù)效率，以運(yùn)營(yíng)商與乘客的成本最小為優(yōu)化目標(biāo)，建模求解區(qū)間運(yùn)行方案、發(fā)車(chē)頻率和車(chē)內(nèi)容量的最優(yōu)值，通過(guò)研究發(fā)現(xiàn)：出行需求越集中，區(qū)間車(chē)調(diào)度運(yùn)行效益就越大。在組合調(diào)度研究方面，韓笑宓[7]對(duì)跳站車(chē)、區(qū)間車(chē)、全程車(chē)3 種運(yùn)行模式進(jìn)行組合調(diào)度，以發(fā)車(chē)頻率、區(qū)間車(chē)折返的站點(diǎn)及跳站車(chē)的?？空军c(diǎn)為優(yōu)化對(duì)象，對(duì)客流需求與配車(chē)數(shù)這兩個(gè)重要參數(shù)進(jìn)行敏感性分析；Zhang 等人[8]將區(qū)間運(yùn)行與跳站結(jié)合，認(rèn)為在有跳站調(diào)度產(chǎn)生的基礎(chǔ)上，若雙向有相同連續(xù)運(yùn)行的區(qū)段，即可作為區(qū)間車(chē)的運(yùn)行區(qū)間。

不少學(xué)者針對(duì)公交車(chē)尾氣排放特點(diǎn)進(jìn)行了研究。Yu 等人[9]通過(guò)收集道路上的公交排放數(shù)據(jù)，分析得出約50%的公交尾氣排放量產(chǎn)生于站點(diǎn)與交叉口，因?yàn)檫@兩處皆有明顯的停車(chē)與起步過(guò)程。Mahesh 等人[10]通過(guò)分析4 條公交線(xiàn)路在高峰與非高峰時(shí)段的數(shù)據(jù)發(fā)現(xiàn)，公交車(chē)在高峰期的停車(chē)次數(shù)多于非高峰時(shí)期，且怠速時(shí)間更長(zhǎng)，排放量也顯著增加。王志強(qiáng)等人[11]研究發(fā)現(xiàn)，公交變速行駛時(shí)尾氣排放量相對(duì)較高，且處于怠速狀態(tài)時(shí)仍會(huì)產(chǎn)生一定的排放量，故提出可通過(guò)降低行駛加減速比例與怠速行駛時(shí)間來(lái)控制尾氣排放。Alam 等人[12]通過(guò)收集路線(xiàn)上的瞬時(shí)速度等數(shù)據(jù)，估算出路段、車(chē)站處的排放量及人均排放量，發(fā)現(xiàn)采用有限站?？糠桨傅墓晃矚馀欧帕肯啾炔捎萌７桨赣忻黠@降低。

由以上分析可知，大多研究?jī)H分析如何通過(guò)不同的運(yùn)營(yíng)模式提升公交系統(tǒng)效率，或僅探究公交尾氣排放的影響因素，少有研究將公交尾氣排放與調(diào)度聯(lián)系在一起，從規(guī)劃層面將減少尾氣排放作為優(yōu)化目標(biāo)之一[13]。調(diào)度方案決定了公交車(chē)在線(xiàn)路上的運(yùn)行狀態(tài)，對(duì)公交企業(yè)、乘客、環(huán)境都會(huì)產(chǎn)生影響，因此僅考慮公交企業(yè)與乘客兩者的利益是不夠的。

跳站調(diào)度與區(qū)間車(chē)調(diào)度由于只運(yùn)行有限的站點(diǎn)，可適當(dāng)提高車(chē)輛運(yùn)行速度，縮短運(yùn)行時(shí)間與降低行駛過(guò)程中的加減速比例，加快車(chē)輛周轉(zhuǎn)，因此這兩種調(diào)度方案有利于減少尾氣排放。鑒于此，本文根據(jù)已知線(xiàn)路規(guī)劃周期內(nèi)的出行OD 量，以乘客的時(shí)間總成本、公交車(chē)的運(yùn)行總成本與尾氣排放成本之和最小為目標(biāo)，建立一種跳站與區(qū)間車(chē)組合的調(diào)度模型，通過(guò)模型求解確定公交車(chē)的最優(yōu)?？糠桨概c發(fā)車(chē)頻率，旨在優(yōu)化公交運(yùn)營(yíng)模式、提高運(yùn)行效率的同時(shí)，減少尾氣排放。

1 公交組合調(diào)度模型

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

1.1 公交跳站調(diào)度模型

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

針對(duì)同向站點(diǎn)客流分布不均的情況，本文提出一種車(chē)輛調(diào)度方案：A 車(chē)隊(duì)運(yùn)行所有站點(diǎn)，B車(chē)隊(duì)采取跳站運(yùn)行。此時(shí)，A 車(chē)隊(duì)、B 車(chē)隊(duì)均從起始站點(diǎn)運(yùn)行至末尾站點(diǎn)，但不同之處在于：B車(chē)隊(duì)在某些站點(diǎn)不?？浚贿\(yùn)行部分站點(diǎn)。B 車(chē)隊(duì)的運(yùn)行模式如圖1 所示，其在線(xiàn)路上進(jìn)行雙向運(yùn)行，上行方向從第1 站運(yùn)行至第N站，然后掉頭從第N+1 站運(yùn)行至第2N站，不在某些客流集散量較小的站點(diǎn)停靠。

圖1 B車(chē)隊(duì)運(yùn)行示意圖

1.1.1 乘客分類(lèi)分析

首先對(duì)不同OD 的客流進(jìn)行分類(lèi)，第一類(lèi)乘客出行的起始站點(diǎn)與希望到達(dá)的目的地站點(diǎn)間僅由A 車(chē)隊(duì)服務(wù)，所以?xún)H能乘坐A 車(chē)隊(duì)的車(chē)。該類(lèi)乘客客流量為：

第二類(lèi)乘客出行的起始站點(diǎn)與希望到達(dá)的目的地站點(diǎn)間由A 車(chē)隊(duì)與B 車(chē)隊(duì)同時(shí)服務(wù)，所以其既可乘坐A 車(chē)隊(duì)的車(chē)，又可乘坐B(niǎo) 車(chē)隊(duì)的車(chē)。該類(lèi)乘客客流量為：

第三類(lèi)乘客同第二類(lèi)乘客，兩車(chē)隊(duì)的車(chē)都可供其選擇。但由于B車(chē)隊(duì)的車(chē)輛跳過(guò)了某些站點(diǎn)，此時(shí)在A 車(chē)隊(duì)與B 車(chē)隊(duì)中選擇B 車(chē)隊(duì)會(huì)節(jié)省一部分時(shí)間。該類(lèi)乘客客流量為：

1.1.2 乘客總時(shí)間成本模型

假設(shè)乘客在同一站點(diǎn)的到達(dá)率為均勻分布，兩車(chē)隊(duì)以一定的頻率服務(wù)各站點(diǎn)，乘客在站點(diǎn)處的平均等待時(shí)間為1/2 的車(chē)頭時(shí)距。將站點(diǎn)類(lèi)型分為A 類(lèi)站點(diǎn)與B 類(lèi)站點(diǎn)，A 類(lèi)站點(diǎn)僅供A 車(chē)隊(duì)停靠，B類(lèi)站點(diǎn)供A車(chē)隊(duì)與B車(chē)隊(duì)共同?？?。

A類(lèi)站點(diǎn)的乘客等待時(shí)間為：

B類(lèi)站點(diǎn)的乘客等待時(shí)間為：

公交車(chē)在站點(diǎn)處的停靠時(shí)間與乘客上下車(chē)的人數(shù)有關(guān)，而上下車(chē)人數(shù)可以通過(guò)客流OD 矩陣求出，每個(gè)站點(diǎn)上車(chē)人數(shù)為OD 矩陣中的行向量之和，每個(gè)站點(diǎn)的下車(chē)人數(shù)為列向量之和。

A車(chē)隊(duì)在第k站的上車(chē)人數(shù)為：

A車(chē)隊(duì)在第k站的下車(chē)人數(shù)為：

B車(chē)隊(duì)在第k站的上車(chē)人數(shù)為：

B車(chē)隊(duì)在第k站的下車(chē)人數(shù)為：

乘客在車(chē)時(shí)間等于其上車(chē)的起點(diǎn)站到下車(chē)的終點(diǎn)站間的車(chē)輛運(yùn)行時(shí)間加上車(chē)輛在站點(diǎn)處的?？繒r(shí)間。車(chē)輛在站點(diǎn)處的?？繒r(shí)間等于其進(jìn)出每站的加減速時(shí)間與乘客上下車(chē)時(shí)間之和。

故A車(chē)隊(duì)乘客的在車(chē)總時(shí)間為：

B 車(chē)隊(duì)因產(chǎn)生跳站而節(jié)省了在某些站點(diǎn)的?？繒r(shí)間與進(jìn)出站加減速時(shí)間，故其乘客的在車(chē)總時(shí)間為：

則乘客的時(shí)間總成本為：

式（12）中：Z1為乘客的時(shí)間總成本（元）；W為單位時(shí)間乘客在站點(diǎn)處的等待時(shí)間成本（元/min）；V為單位時(shí)間乘客在車(chē)時(shí)間成本（元/min）。

1.1.3 車(chē)隊(duì)運(yùn)行總成本模型

車(chē)隊(duì)的運(yùn)行總成本包括兩部分，一部分是與運(yùn)行時(shí)間相關(guān)的成本，另一部分是與運(yùn)行里程相關(guān)的成本。

A 車(chē)隊(duì)的運(yùn)行總時(shí)間等于其在站間的運(yùn)行時(shí)間與在站點(diǎn)的?？繒r(shí)間之和：

同理，B車(chē)隊(duì)的運(yùn)行總時(shí)間為：

則在規(guī)劃期內(nèi)，與公交運(yùn)行時(shí)間有關(guān)的公交總購(gòu)置成本為：

與公交運(yùn)行總里程相關(guān)的運(yùn)行成本為：

式（16）中：CR為與運(yùn)行里程相關(guān)的公交運(yùn)行成本（元）；R為單位里程的公交運(yùn)營(yíng)成本（元/m），此時(shí)A 車(chē)隊(duì)與B 車(chē)隊(duì)皆運(yùn)行駛過(guò)N站，所以此處的總成本與其發(fā)車(chē)頻率正相關(guān)。

則公交的運(yùn)行總成本Z2為：

1.1.4 車(chē)隊(duì)尾氣排放成本模型

公交在線(xiàn)路上的運(yùn)行過(guò)程包括在站點(diǎn)間的勻速行駛過(guò)程以及站點(diǎn)處的?？窟^(guò)程。而?？窟^(guò)程又由減速進(jìn)站直至速度為零、怠速停站等待乘客上下客、加速離站直至速度恢復(fù)為v三個(gè)階段組成，不同行駛工況下的尾氣污染物排放量各有不同。

在路段行駛時(shí)的排放量與勻速行駛時(shí)間相關(guān)，進(jìn)站出站過(guò)程的排放量與加減速時(shí)間相關(guān)，而怠速停留時(shí)的排放量與乘客的上下車(chē)時(shí)間相關(guān)，則A車(chē)隊(duì)的污染物排放成本為：

此時(shí)，由于B 車(chē)隊(duì)產(chǎn)生了跳站，所以直接節(jié)省某些站點(diǎn)處加減速與怠速時(shí)的尾氣排放量。

故B車(chē)隊(duì)的污染物排放成本為：

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

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

1.1.5 車(chē)內(nèi)容量約束限制

為保證乘客在車(chē)內(nèi)的乘坐舒適性，必須對(duì)車(chē)內(nèi)的乘客人數(shù)進(jìn)行約束，對(duì)A 車(chē)隊(duì)與B 車(chē)隊(duì)采取相同的方法進(jìn)行計(jì)算。

各車(chē)隊(duì)在每站的車(chē)內(nèi)人數(shù)流動(dòng)為在該站的上車(chē)人數(shù)減去下車(chē)人數(shù)：

各車(chē)隊(duì)在第k站的車(chē)內(nèi)人數(shù)等于從首站到第k站的人數(shù)流動(dòng)的累加，即：

在車(chē)輛運(yùn)行過(guò)程中為滿(mǎn)足乘客的舒適度要求，每站的車(chē)內(nèi)人數(shù)不能超過(guò)額定容量的80%，故所有站點(diǎn)的車(chē)內(nèi)負(fù)載人數(shù)要滿(mǎn)足一定的約束，即：

式（21）～式（23）中：qk為第k站的車(chē)內(nèi)人數(shù)流動(dòng)量（人）；為某車(chē)隊(duì)在第k站的上車(chē)人數(shù)（人）；為某車(chē)隊(duì)在第k站的下車(chē)人數(shù)（人）；Qk為某車(chē)隊(duì)在第k站的車(chē)內(nèi)人數(shù)（人）；Qmax為車(chē)內(nèi)負(fù)載人數(shù)的最大值（人）；Q為額定車(chē)內(nèi)容量（人）。

1.2 公交跳站與區(qū)間車(chē)組合調(diào)度模型

若B車(chē)隊(duì)在線(xiàn)路的首尾兩端產(chǎn)生了連續(xù)跳站，則產(chǎn)生區(qū)間車(chē)方案，即B 車(chē)隊(duì)只運(yùn)行當(dāng)前方案雙向運(yùn)行的共同區(qū)間，如圖2所示。

圖2 組合調(diào)度示意圖

在圖2 中，m1為上行方向起始端連續(xù)跳站的站點(diǎn)集合；n1為上行方向末尾端連續(xù)跳站的站點(diǎn)集合；n2為下行方向起始端連續(xù)跳站的站點(diǎn)集合；m2為下行方向末尾端連續(xù)跳站的站點(diǎn)集合；m為m1與m2的交集，表示B車(chē)隊(duì)在公交線(xiàn)路前端略過(guò)的站點(diǎn)數(shù)量；n為n1與n2的交集，表示B 車(chē)隊(duì)在公交線(xiàn)路后端略過(guò)的站點(diǎn)數(shù)量。

此時(shí)，B車(chē)隊(duì)的運(yùn)行路線(xiàn)為從線(xiàn)路的第m+1站運(yùn)行至第N-n站，然后掉頭從第N+n站運(yùn)行至2N-m站，直接略過(guò)不需要?？康膍+n個(gè)站點(diǎn)，縮短了車(chē)輛的空駛距離。

一旦產(chǎn)生了區(qū)間車(chē)方案，又會(huì)減少車(chē)輛的運(yùn)行時(shí)間，減少部分計(jì)算公式為：

更新車(chē)隊(duì)與運(yùn)行里程相關(guān)的成本為：

更新車(chē)隊(duì)與運(yùn)行時(shí)間相關(guān)的成本為：

更新車(chē)隊(duì)的尾氣排放成本為：

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

目標(biāo)函數(shù)F為最小化乘客的時(shí)間總成本、公交的運(yùn)行總成本及尾氣排放成本之和：

2 模型求解算法設(shè)計(jì)

本模型需要對(duì)B 車(chē)隊(duì)的?？糠桨负蛢绍?chē)隊(duì)的發(fā)車(chē)頻率都進(jìn)行優(yōu)化，屬于NP 難題（Non-Deter?ministic Polynomial-Hard,NP-Hard），一般采用啟發(fā)式算法求解。

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

Zhang 等人[8]針對(duì)?？糠桨甘褂眠z傳算法求解，對(duì)發(fā)車(chē)頻率采取窮舉全局搜索法。具體的算法流程如下：

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

（2）編碼：直接使用0,1 編碼生成B 車(chē)隊(duì)的停靠方案，1表示該站停靠，0表示該站跳過(guò)；

（3）設(shè)計(jì)適應(yīng)值：所求的目標(biāo)函數(shù)F為總成本最小值，將適應(yīng)值f設(shè)計(jì)為其倒數(shù)形式，如式（29）所示：

在計(jì)算適應(yīng)值時(shí)，針對(duì)產(chǎn)生的每個(gè)?？空军c(diǎn)方案，帶入{fA,fB}的所有組合進(jìn)行計(jì)算，選擇出該方案下的最佳發(fā)車(chē)頻率組合并存儲(chǔ)。

（4）選擇：采用輪盤(pán)賭選擇法，當(dāng)個(gè)體的適應(yīng)值累積概率大于隨機(jī)產(chǎn)生的累積概率時(shí)，則被選入新的種群。

（5）交叉：采用單點(diǎn)交叉法，隨機(jī)選中1點(diǎn)，兩個(gè)染色體交換關(guān)于此點(diǎn)的左右部分的基因序列。

（6）變異：采用單點(diǎn)變異法，隨機(jī)選中1點(diǎn)，若為1即變異為0，若為0即變異為1。

（7）精英保留策略：選出上一代中的最優(yōu)個(gè)體，放進(jìn)即將產(chǎn)生的下一代種群中。

（8）滿(mǎn)足迭代次數(shù)，則終止算法。

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

該算法有兩點(diǎn)缺陷：①假設(shè)A 車(chē)隊(duì)的頻率區(qū)間內(nèi)有g(shù)1個(gè)數(shù)，B 車(chē)隊(duì)的頻率區(qū)間內(nèi)有g(shù)2個(gè)數(shù)，初始種群中個(gè)體數(shù)設(shè)為u1個(gè)，遺傳操作循環(huán)u2次，整個(gè)尋優(yōu)過(guò)程中需對(duì)適應(yīng)值計(jì)算g1g2u1u2次，計(jì)算規(guī)模龐大、耗時(shí)久；②使用遺傳算法嵌套窮舉搜索的方法相當(dāng)于將?？糠桨概c發(fā)車(chē)頻率分開(kāi)優(yōu)化，沒(méi)有考慮規(guī)劃時(shí)的重要性差異，忽視了發(fā)車(chē)頻率在規(guī)劃中起的決定性作用。

圖3 原算法流程圖

2.2 動(dòng)態(tài)概率改進(jìn)遺傳算法

本文提出了一種將公交?？糠桨概c發(fā)車(chē)頻率同時(shí)優(yōu)化，并將相互影響關(guān)系考慮其中的新遺傳算法。在經(jīng)典的遺傳算法中，交叉率與變異率在算法起始時(shí)就已給定，并在后續(xù)運(yùn)算中不再改變。但在本文的問(wèn)題中，?？糠桨概c發(fā)車(chē)頻率兩要素在規(guī)劃時(shí)明顯存在主次關(guān)系。因此，本文提出的新算法在搜索時(shí)先給予發(fā)車(chē)頻率一個(gè)較大的變化概率，后隨迭代次數(shù)增加不斷減?。唤o予?？糠桨赶鄬?duì)較小的變化概率，后隨迭代次數(shù)增加不斷增大。這樣做的目的是：在搜索前期讓發(fā)車(chē)頻率先大致確定下來(lái)，在搜索中慢慢減小其重要影響程度；而?？糠桨冈谒阉髑捌谝暂^小的概率變化，待發(fā)車(chē)頻率大致確定后，再增加其變化率進(jìn)行逐步確定。具體的算法流程如下。

（1）設(shè)置遺傳參數(shù)：設(shè)種群規(guī)模為G，迭代次數(shù)為M，交叉率變化區(qū)間為[J1,J2]，變異率變化區(qū)間為[B1,B2]，變化率的相關(guān)計(jì)算公式如下。

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

圖4 交叉率變化示意

（2）直接使用0,1 編碼生成B 車(chē)隊(duì)的?？糠桨?，兩車(chē)隊(duì)發(fā)車(chē)頻率采用二進(jìn)制編碼。染色體編碼為[X fA fB]，此處的X代表B車(chē)隊(duì)的?？糠桨?。

（3）設(shè)計(jì)適應(yīng)值：所求的目標(biāo)函數(shù)F為總成本最小值，將適應(yīng)值f設(shè)計(jì)為其倒數(shù)形式（f的計(jì)算公式同式（29））。在計(jì)算前，應(yīng)先提取染色體中的各個(gè)部分，再解碼發(fā)車(chē)頻率。

（4）選擇：采用輪盤(pán)賭選擇方法，當(dāng)個(gè)體的適應(yīng)值累積概率大于隨機(jī)產(chǎn)生的累積概率時(shí)，則被選入加入新的種群中。

（5）交叉：此處采用隨機(jī)單雙點(diǎn)混合交叉，分別產(chǎn)生兩個(gè)隨機(jī)數(shù)與進(jìn)行比較，可能會(huì)在?？糠桨概c發(fā)車(chē)頻率位置都產(chǎn)生交叉點(diǎn)，也可能分別在2個(gè)位置單獨(dú)產(chǎn)生交叉點(diǎn)，如圖5所示。

圖5 交叉點(diǎn)位置圖

（6）變異：此處采用隨機(jī)單雙點(diǎn)混合變異，與交叉模式類(lèi)似，也會(huì)產(chǎn)生3種位置變異的情況。

（7）滿(mǎn)足迭代次數(shù)，則終止算法。

新算法流程如圖7所示。

3 案例分析

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

各站點(diǎn)間距離如表2 所示，反向站間距與正向相同。

表2 站點(diǎn)間距 單位：m

圖7 新算法流程圖

本文采用上午7:30—8:30的客流OD量（見(jiàn)表3）進(jìn)行計(jì)算。

表3 客流OD 單位：人

表3 （續(xù)）

公交車(chē)輛的基礎(chǔ)數(shù)據(jù)[11,14]如表4所示。

表4 公交車(chē)輛基礎(chǔ)數(shù)據(jù)

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

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

3.1 動(dòng)態(tài)概率改進(jìn)遺傳算法求解結(jié)果

本節(jié)采取新算法（動(dòng)態(tài)概率改進(jìn)遺傳算法）對(duì)模型進(jìn)行求解。遺傳參數(shù)的設(shè)定為：迭代次數(shù)G=500，種群內(nèi)個(gè)體數(shù)量M=100，交叉率的取值區(qū)間為[0.5,0.7]，變異率的取值區(qū)間為[0.05,0.07]。優(yōu)化后的B 車(chē)隊(duì)?？糠桨讣皟?yōu)化效果如表6所示。

表6 效益對(duì)比

通過(guò)新算法求解得出：B 車(chē)隊(duì)的運(yùn)行區(qū)間為第5 站～第9 站，其中在上行方向跳過(guò)第6 站與第9 站，在下行方向跳過(guò)第6 站。原先需要14 輛全程車(chē)在該時(shí)段內(nèi)服務(wù)，采取綜合調(diào)度方案后，由12 輛全程車(chē)與2 輛采取跳站的區(qū)間車(chē)進(jìn)行服務(wù)，總成本下降了4.49%，雖然其中乘客的時(shí)間總成本上升了5.04%，但公交的運(yùn)行總成本下降了7.12%，尾氣排放成本下降了8.22%。

3.2 兩種算法效益對(duì)比

（1）新算法效益

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

表7 新算法用時(shí)統(tǒng)計(jì)

在種群規(guī)模為100，迭代次數(shù)為500次的情況下，新算法需對(duì)適應(yīng)值計(jì)算50 100 次，共耗時(shí)95.973s，大約2min 即可求解完畢得到最優(yōu)解。算法的迭代情況如圖8所示。

圖8 新算法迭代圖

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

（2）原算法效益

設(shè)定A車(chē)隊(duì)與B車(chē)隊(duì)發(fā)車(chē)頻率區(qū)間均取[2,20]。若原算法采用與新算法相同的參數(shù)，需對(duì)適應(yīng)值計(jì)算18 050 000 次，耗時(shí)過(guò)長(zhǎng)且無(wú)法運(yùn)行，所以設(shè)置迭代次數(shù)G為100 次，種群內(nèi)個(gè)體數(shù)M取50個(gè)，交叉率取0.7，變異率取0.07。原算法的用時(shí)情況如表8所示。

表8 原算法用時(shí)統(tǒng)計(jì)

在該種情況下，需對(duì)適應(yīng)值計(jì)算1 823 050次，耗時(shí)3 242.312s，約54min。算法的迭代情況如圖9 所示。運(yùn)行中發(fā)現(xiàn)，當(dāng)整個(gè)算法完成時(shí)的目標(biāo)函數(shù)值為536.90，還未搜索到最優(yōu)解，并且計(jì)算時(shí)間過(guò)長(zhǎng)，可見(jiàn)原算法效率相對(duì)較低。

圖9 原算法迭代圖

4 結(jié)語(yǔ)

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