薛運(yùn)強(qiáng)，郭軍，鐘蒙，安靜

（1.華東交通大學(xué)，交通運(yùn)輸與物流學(xué)院，南昌 330013；2.北京工業(yè)大學(xué)，城市建設(shè)學(xué)部，北京 100024）

0 引言

成本和效率是常規(guī)公交可持續(xù)運(yùn)營(yíng)的基礎(chǔ)。公交車輛調(diào)度優(yōu)化問(wèn)題是在保證公交公司不虧損、服務(wù)水平合適的前提下，如何計(jì)劃安排車輛發(fā)車間隔和車型配置，使得公交運(yùn)行與乘客出行總成本消耗最低，并降低行車延誤。公交車輛調(diào)度優(yōu)化研究具有積極的理論意義和實(shí)踐價(jià)值[1]。

關(guān)于常規(guī)公交車輛調(diào)度優(yōu)化問(wèn)題，國(guó)內(nèi)外學(xué)者都做了相應(yīng)研究。在車輛調(diào)度優(yōu)化方面，姚恩建[1]為解決單車型運(yùn)營(yíng)模式下的交通擁擠和資源浪費(fèi)問(wèn)題，以公交公司運(yùn)營(yíng)成本和乘客出行成本為優(yōu)化目標(biāo)，提出混合車型運(yùn)營(yíng)模式下常規(guī)公交線路發(fā)車間隔及車型配置優(yōu)化方法。王東[2]為解決固定發(fā)車間隔和單一車型造成的資源浪費(fèi)和交通擁擠問(wèn)題，采用GRNN(Generalized Regression Neural Network)廣義回歸神經(jīng)網(wǎng)絡(luò)對(duì)常規(guī)公交客流進(jìn)行預(yù)測(cè)，建立發(fā)車間隔優(yōu)化模型，最后基于MATLAB求解，可以有效降低公司成本。陳曉旭等[3]為優(yōu)化公交運(yùn)營(yíng)管理，提出基于遺傳算法的公交線路發(fā)車間隔優(yōu)化方法，考慮公交公司和乘客成本，以鄭州市60 路公交為例，有效降低18%～26%線路總成本。在不確定理論研究方面，焦登婭[4]提出了車輛調(diào)度問(wèn)題的兩種新的不確定規(guī)劃模型，考慮了不同卸貨點(diǎn)顧客需求量不同、車輛運(yùn)載量上限，設(shè)計(jì)了一個(gè)能有效解決車輛調(diào)度不確定規(guī)劃模型的遺傳算法。Rongheng He 等[5]研究了不確定因素下的多層倉(cāng)庫(kù)布局問(wèn)題，其中月需求量和水平運(yùn)輸距離由不確定變量描述。此外，還討論了機(jī)會(huì)約束規(guī)劃模型與機(jī)會(huì)最大規(guī)劃模型之間的關(guān)系，為尋找機(jī)會(huì)最大規(guī)劃模型的最優(yōu)解提供了一種有效方法。

國(guó)內(nèi)外對(duì)公交車輛調(diào)度的研究主要集中在成本分析上，缺乏對(duì)公交實(shí)際運(yùn)行中不確定因素的研究。文獻(xiàn)[6]考慮了公交站點(diǎn)乘客不確定因素，構(gòu)建了公交線路配車問(wèn)題的不確定雙層規(guī)劃模型，但是沒(méi)有考慮不同車型和候車時(shí)間、運(yùn)行時(shí)間的不確定性。鑒于此，本文基于不確定理論，以最大化公交效益和最小化乘客成本為目標(biāo)，考慮不同車型建立綜合考慮乘客候車時(shí)間和站間運(yùn)行時(shí)間不確定分布的雙重不確定多目標(biāo)規(guī)劃模型，優(yōu)化公交運(yùn)行調(diào)度方案。

1 不確定理論基礎(chǔ)知識(shí)

不確定性原理(Uncertainty Principle)最早是由海森堡于1927年提出，根據(jù)該理論不可能同時(shí)知道一個(gè)粒子的位置和它的速度。中國(guó)學(xué)者劉寶碇教授深化研究不確定理論，并在2005年出版了《不確定理論教程》，為后來(lái)學(xué)者提供寶貴參考資料?，F(xiàn)今，不確定理論已經(jīng)應(yīng)用到數(shù)學(xué)、運(yùn)籌學(xué)、管理科學(xué)、計(jì)算機(jī)科學(xué)等領(lǐng)域。

不確定理論是概率論、可信性理論、信賴性理論的統(tǒng)稱，同時(shí)還包括其余多種理論[7]。不確定規(guī)劃是處理各種不確定環(huán)境下的優(yōu)化問(wèn)題的理論工具[7]，通?？梢詮钠谕怠C(jī)會(huì)測(cè)度、極大化事件實(shí)現(xiàn)的機(jī)會(huì)這3 種角度考慮處理，最后用遺傳算法、模擬退火、禁忌搜索、神經(jīng)元網(wǎng)絡(luò)或混合智能算法求解。

1.1 不確定理論相關(guān)概念

將優(yōu)化問(wèn)題中出現(xiàn)的不確定變量分為如下3 類：

(1)期望值模型(EVM)

期望值模型基于在滿足期望約束成立的條件下，極大化這些不確定目標(biāo)函數(shù)的期望。

式中：x為決策向量；ξ為不確定變量；f(x,ξ)為目標(biāo)函數(shù)，gi(x,ξ)為不確定約束函數(shù)；i為第幾個(gè)約束函數(shù)；i=1,2,…,p，p為約束函數(shù)總數(shù)；E為期望值算子。

(2)機(jī)會(huì)約束規(guī)劃(CCP)

該不確定規(guī)劃模型允許在一定程度上不滿足約束條件，但該決策使約束條件成立的機(jī)會(huì)不小于某一置信水平，一般地，極大化樂(lè)觀值的機(jī)會(huì)約束規(guī)劃(CCP)模型為

式中：α和β為給定的置信水平；ξ為不確定變量；max為目標(biāo)(收益)函數(shù)的β－樂(lè)觀值；Ch{·} 為可信性測(cè)度。

(3)相關(guān)機(jī)會(huì)規(guī)劃(DCP)

一個(gè)復(fù)雜的決策系統(tǒng)通常要完成多項(xiàng)任務(wù)，稱之為事件，決策者往往希望這些事件實(shí)現(xiàn)的機(jī)會(huì)盡可能的大。常見(jiàn)的DCP可以表示為

式中：hk(x,ξ)≤0 為事件，k=1,2,…,q；k為事件序號(hào)；q為事件總數(shù)。

1.2 乘客候車時(shí)間不確定分布

公交實(shí)際運(yùn)行中，乘客候車時(shí)間是不確定的。它受到發(fā)車間隔、上下客流量以及交通運(yùn)行路況等影響。因此，基于不確定規(guī)劃，將乘客候車時(shí)間作為不確定變量之一。根據(jù)Avishai Ceder 學(xué)者的研究成果[8]，乘客平均候車時(shí)間為

式中：E(w)為乘客平均候車時(shí)間(h)；E(H)為發(fā)車間隔均值(h)；var(H)為發(fā)車間隔方差(h2)。

Avishai Ceder[8]考慮的因素忽略了道路交通情況以及其他不確定因素，在此基礎(chǔ)上，本文將乘客候車時(shí)間不確定分布擬合成正態(tài)分布，其概論密度函數(shù)和正態(tài)不確定分布分別為

式中：?(x)為正態(tài)分布的概率密度函數(shù)；μ和σ分別為均值和標(biāo)準(zhǔn)差；Φ(x)為正態(tài)不確定分布函數(shù)。

1.3 站間運(yùn)行時(shí)間不確定分布

在只考慮同一車型的公交車速影響下，各公交站點(diǎn)之間運(yùn)行時(shí)間可以簡(jiǎn)化為各站點(diǎn)之間距離與該公交運(yùn)行速度的比值。但實(shí)際公交運(yùn)行時(shí)間受多方面影響，不僅受到車速、站距、交通信號(hào)燈、交通狀況的影響，還受到駕駛員、天氣、車輛類型等影響。根據(jù)調(diào)查數(shù)據(jù)，各站間運(yùn)行時(shí)間近似于之字形不確定分布，其之字形不確定分布為

式中：a,b,c均為常數(shù)，且a ＜b ＜c，a和c分別表示變量取值的上、下界。

2 公交車輛調(diào)度優(yōu)化的雙重不確定多目標(biāo)模型

基于乘客候車時(shí)間不確定和站間運(yùn)行時(shí)間不確定雙重不確定變量，考慮發(fā)車間隔和公交車型配置優(yōu)化，建立以公交企業(yè)和乘客多目標(biāo)優(yōu)化模型，參考不確定規(guī)劃模型的第一種規(guī)劃模型——期望值模型(EVM)的復(fù)雜形式，建立不確定多層規(guī)劃模型(MLP)。

2.1 MLP模型結(jié)構(gòu)

不確定多層規(guī)劃模型，為研究分層決策問(wèn)題提供了模型基礎(chǔ)。假設(shè)某最高決策者及其下屬們都有他們各自的決策變量和目標(biāo)函數(shù)。最高決策者可以通過(guò)他的決策變量對(duì)其下屬們施加影響，而下屬們則有充分的權(quán)限決定如何對(duì)他們自己的目標(biāo)函數(shù)進(jìn)行優(yōu)化決策，這些決策又將對(duì)他們各自的上層領(lǐng)導(dǎo)和下屬產(chǎn)生影響。多層規(guī)劃著眼于各層之間的相互反饋，因此，其中通常伴隨著固有的不確定性[7]。

其中，對(duì)于每個(gè)yi(i=1,2,…,m)求解，即

2.2 基本假設(shè)

發(fā)車間隔和車型配置綜合影響著公交公司運(yùn)營(yíng)成本和乘客出行總成本，是雙重不確定多目標(biāo)規(guī)劃模型的決策變量。實(shí)際交通情況中，乘客候車時(shí)間和站間運(yùn)行時(shí)間存在不確定因素，是模型的不確定變量。同時(shí)，公交公司作為決策者，能夠直接改變車輛調(diào)度方案從而影響乘客進(jìn)行決策，即公交公司為上層決策者，乘客為下屬。為了綜合考慮兩方利益，追求公交公司成本最低和乘客出行總成本最低兩個(gè)目標(biāo)，建立雙重不確定多目標(biāo)規(guī)劃模型，求解最科學(xué)合理的發(fā)車間隔和車型配置。

基于以下基本假設(shè)，建立雙重不確定多目標(biāo)規(guī)劃模型。

假設(shè)1 僅考慮單向常規(guī)公交線路的運(yùn)行，不考慮突發(fā)事件。

假設(shè)2 公交車經(jīng)過(guò)站點(diǎn)后，乘客均能搭車，不進(jìn)行二次等待。

假設(shè)3 乘客候車時(shí)間服從正態(tài)分布，站間運(yùn)行時(shí)間服從之字形分布。

假設(shè)4 僅考慮單一公交線路運(yùn)行成本，不考慮其他公交線路的影響。

假設(shè)5 影響公交公司車輛運(yùn)行成本的主要因素取決于行駛里程。

假設(shè)6 全程使用同一票價(jià)。

2.3 符號(hào)定義

模型符號(hào)定義如表1所示。

表1 符號(hào)定義Table 1 Symbol definition

2.4 決策變量分析

(1)發(fā)車間隔

發(fā)車間隔作為影響公司和乘客利益的決策變量之一，它的改變會(huì)造成兩者之間失去原有的平衡。同時(shí)發(fā)車間隔也是影響乘客候車時(shí)間的一個(gè)重要因素。在調(diào)查的發(fā)車間隔范圍內(nèi)，通過(guò)不確定正態(tài)分布函數(shù)對(duì)歷史數(shù)據(jù)進(jìn)行擬合，結(jié)果如圖1所示，可以明顯看出，發(fā)車間隔對(duì)乘客候車時(shí)間的影響。

圖1 不同發(fā)車間隔的乘客候車時(shí)間擬合分布圖Fig.1 Fitting distribution of waiting time of passengers with different departure intervals

發(fā)車間隔為60 min 時(shí)，乘客候車時(shí)間集中在30 min；發(fā)車間隔在6 min時(shí)，乘客候車時(shí)間明顯變小，集中在3 min。由上述結(jié)果可知，發(fā)車間隔越長(zhǎng)，乘客的候車成本越大；反之，公交發(fā)車頻率就越少，其運(yùn)行成本越低，但這也降低了公交對(duì)乘客的吸引。因此需要進(jìn)行合理設(shè)計(jì)，在滿足乘客需求的條件下，尋找帕累托最優(yōu)集。

(2)車型配置

不同公交車型的運(yùn)行速度對(duì)站間運(yùn)行時(shí)間有著重要影響，不考慮路段交通量及信號(hào)燈的影響，以南昌市211路公交車型為例，可以分為A類車、B類車、C 類車，分別對(duì)應(yīng)大（f1）、中（f2）、小（f3）型公交車。通過(guò)調(diào)查數(shù)據(jù)對(duì)不同車型的站間運(yùn)行時(shí)間進(jìn)行擬合，其不確定分布如圖2所示。

圖2 不同車型站間運(yùn)行時(shí)間分布圖Fig.2 Distribution of running time between stations of different models

2.5 公交車輛調(diào)度優(yōu)化的雙重不確定多目標(biāo)模型建立

(1)乘客出行總成本

乘客出行總成本可以分為乘客候車成本和乘客乘坐車輛運(yùn)行成本，即

①乘客候車成本

乘客候車成本受乘客候車時(shí)間、發(fā)車間隔及上客量影響，將乘客候車時(shí)間視為正態(tài)不確定變量，乘客候車成本為

式中：j為發(fā)車車次；n為車站編號(hào)，N為車站總數(shù)。

利用乘客候車時(shí)間調(diào)查數(shù)據(jù)和式(6)進(jìn)行數(shù)據(jù)擬合，得出發(fā)車間隔為xg時(shí)，乘客候車時(shí)間分布函數(shù)為

②乘客乘車成本

乘客乘車成本不僅受到站間運(yùn)行時(shí)間的影響，同時(shí)車內(nèi)載客率的大小也會(huì)影響乘客的心理成本，車內(nèi)滿載時(shí)，乘客乘車心理時(shí)間增加?？紤]不同公交車型的客容量不同，其載客率的影響程度也不同。楊熙宇等[9]研究認(rèn)為公交載客率感知系數(shù)δ的計(jì)算公式為

其中，τ1=0.15，τ2=2 。公交載客率感知系數(shù)，是考慮乘客感受的載客率值，為實(shí)際載客率的倍數(shù)。擁擠程度越大，感知系數(shù)也越大。

站間運(yùn)行時(shí)間視為之字形分布，乘客乘車成本為

式中：I為車輛類型總數(shù)。

利用站間運(yùn)行時(shí)間調(diào)查數(shù)據(jù)和式(7)進(jìn)行數(shù)據(jù)擬合，得出車型為xj,fi的站間運(yùn)行時(shí)間分布函數(shù)為

綜上，乘客出行總成本為

斷面客流量Hjn =Hjn-1+第n站上客量-第n站下客量，可通過(guò)累加求解，且受到發(fā)車間隔影響，由式(15)可體現(xiàn)。發(fā)車間隔越大，單個(gè)的斷面客流增大；但由于最大斷面客流不能超過(guò)公交車最大容量，對(duì)應(yīng)的發(fā)車次數(shù)減少，總的斷面客流就減少。為了模型求解方便，本文不考慮不確定性對(duì)斷面客流的影響。

(2)公交運(yùn)行總成本分析

在多車型公交運(yùn)行中，公交運(yùn)行總成本包括公交公司員工成本和不同車型運(yùn)行成本，即

①公交公司員工成本

公交公司員工成本受到站間運(yùn)行時(shí)間和不同車型的影響，站間運(yùn)行時(shí)間作為不確定變量，公交公司員工成本為

②公交車車輛運(yùn)行成本

公交車車輛運(yùn)行成本與運(yùn)行里程和車輛類型相關(guān)，計(jì)算公式為

綜上，公交運(yùn)行總成本為

(3)模型目標(biāo)

(4)約束條件

①發(fā)車間隔滿足最大最小時(shí)間約束為

③最大斷面載客累計(jì)客流量滿足最大最小約束為

④0-1變量滿足統(tǒng)計(jì)量為1，即

⑤載客率公式等式要求為

(5)雙重不確定多目標(biāo)規(guī)劃模型

將其化為標(biāo)準(zhǔn)不確定多層規(guī)劃模型，即

其中，對(duì)于每個(gè)ji(i=1,2,…,m)求解，即

首先對(duì)式(20)取最優(yōu)期望，再對(duì)式(16)取最優(yōu)期望。

3 模型求解與實(shí)例分析

3.1 模型求解算法

遺傳算法的基本原理就是模仿生物體基因遺傳，優(yōu)勝劣汰，適應(yīng)性較小的個(gè)體被淘汰，最后留下適應(yīng)性較強(qiáng)的個(gè)體，即最優(yōu)解。本文求解的是非線性目標(biāo)規(guī)劃，適合采用遺傳算法求解。在計(jì)算過(guò)程中，首先輸入基本參數(shù)，在求解中調(diào)用遺傳算法得出最優(yōu)解。遺傳算法的基本流程包括：編碼、種群、適應(yīng)、選擇、交叉、變異、迭代、結(jié)束，具體如圖3所示。在求出的解中進(jìn)行擇優(yōu)排序，最終得出最優(yōu)解。

(1)實(shí)數(shù)編碼和初始化種群

調(diào)查階段內(nèi)的發(fā)車間隔為1～35 min之間，取發(fā)車間隔為整實(shí)數(shù)，采用二進(jìn)制編碼。

(2)適應(yīng)度計(jì)算

遺傳算法的適應(yīng)度是用來(lái)判斷群體中個(gè)體優(yōu)劣程度的指標(biāo)[10]，本文遺傳算法求解中以目標(biāo)函數(shù)的相反數(shù)maxS=max{-S1,-S2} 為適應(yīng)度函數(shù)。

(3)選擇、交叉、變異

染色體在遺傳過(guò)程中，選擇優(yōu)秀個(gè)體。交叉率為0.8、變異率為0.1，精英保留率為0.2，使適應(yīng)度高的染色體直接復(fù)制到下一代。在算子選擇方面，采用輪盤賭選擇算子、算術(shù)交叉算子、均勻變異算子。

(4)再次計(jì)算適應(yīng)度

遺傳不斷進(jìn)行，再次計(jì)算適應(yīng)度，從而生成新的種群。

(5)迭代循環(huán)

設(shè)定迭代次數(shù)為200，在遺傳次數(shù)達(dá)到給定值時(shí)停止運(yùn)算，其中運(yùn)行部分迭代如圖3所示。

(6)輸出適應(yīng)度值最優(yōu)個(gè)體

本次的發(fā)車間隔經(jīng)過(guò)遺傳迭代運(yùn)算，求解出最優(yōu)發(fā)車間隔，結(jié)合雙重不確定多目標(biāo)規(guī)劃模型，最終確定最優(yōu)的車型配置。通過(guò)枚舉法求解不同車型配置的最小公交總成本，在確定最小總公交成本后，使用遺傳算法求解同一車型配置下的最小乘客總成本。最后通過(guò)帕累托最優(yōu)求解出最優(yōu)發(fā)車間隔和車型配置。由于遺傳算法取大最優(yōu)，因此在目標(biāo)函數(shù)前加負(fù)號(hào)，所以Z軸顯示負(fù)數(shù)，如圖3(b)所示。通過(guò)人工轉(zhuǎn)換，將目標(biāo)函數(shù)還原正值，其迭代圖如圖3(c)所示。

圖3 遺傳算法求解流程圖及迭代圖Fig.3 Flow chart and iterative diagram of genetic algorithm

3.2 實(shí)例分析

以南昌市211 路公交為例，運(yùn)用遺傳算法求解雙重不確定多目標(biāo)規(guī)劃模型。

(1)參數(shù)設(shè)定

根據(jù)相關(guān)文獻(xiàn)資料[6]、南昌城市發(fā)展現(xiàn)狀及模型公式，對(duì)參數(shù)進(jìn)行賦值，如表2所示。

表2 模型參數(shù)Table 2 Parameter of model

(2)車型配置及發(fā)車間隔求解

根據(jù)調(diào)查數(shù)據(jù)及歷史數(shù)據(jù)，南昌公交211 路上行斷面客流量及上客量如表3所示。

表3 南昌市公交211路上行各時(shí)段斷面客流量及上客量Table 3 Section passenger flow and loading volume of Nanchang bus No.211 in each period

通過(guò)遺傳算法，得出10種不同方案，其對(duì)應(yīng)成本分布如圖4所示，每一點(diǎn)均代表一個(gè)方案。公交運(yùn)行總成本增加，乘客出行總成本降低，在這中間存在一個(gè)平衡值，使得其中一方能達(dá)到最優(yōu)，一方能保證不虧損。

圖4 不同方案的成本分析圖Fig.4 Cost analysis chart of different schemes

經(jīng)過(guò)方案必選及總成本計(jì)算，結(jié)合模型求解排序結(jié)果得出：公交車輛高峰時(shí)段的最優(yōu)發(fā)車間隔為7.5 min，車型配置為11111112；平峰時(shí)段的最優(yōu)發(fā)車間隔為8.6 min，車型配置是為3332333。

3.3 仿真分析

通過(guò)模型已求解出最優(yōu)成本下的發(fā)車間隔和車型配置，如圖5所示，但公交實(shí)際運(yùn)行效率不清楚，極可能出現(xiàn)成本優(yōu)化，而效率降低的情況。因此，利用SUMO 軟件，進(jìn)行現(xiàn)狀及優(yōu)化后的仿真分析，得出延誤數(shù)據(jù)，并進(jìn)行前后對(duì)比分析。在保證公交公司能夠可持續(xù)運(yùn)營(yíng)的前提下，通過(guò)調(diào)整公交車輛的發(fā)車間隔和車輛配置，減少公交運(yùn)行15 s延誤，如圖5(b)所示，提高了公共交通的運(yùn)行效率，證明了模型優(yōu)化結(jié)果的可靠性。

圖5 方案優(yōu)化前后對(duì)比圖Fig.5 Comparison chart before and after optimization

4 結(jié)論

本文考慮候車時(shí)間和運(yùn)行時(shí)間雙重不確定因素，基于不確定理論建立了混合車型下的公交車輛雙層不確定多目標(biāo)優(yōu)化模型，并以南昌市211路公交為例進(jìn)行單條公交的單向線路運(yùn)營(yíng)優(yōu)化，利用遺傳算法python 編碼對(duì)模型求解。通過(guò)對(duì)車輛調(diào)度方案的成本與延誤數(shù)據(jù)對(duì)比來(lái)評(píng)價(jià)方案的優(yōu)化效果，得出了最佳公交車輛調(diào)度方案。

與以往研究不同的是，除了考慮不同車型在公交運(yùn)行中的影響，本文還綜合考慮了雙重不確定因素影響。分別選取平峰時(shí)期和高峰時(shí)期的線路運(yùn)行數(shù)據(jù)為基礎(chǔ)數(shù)據(jù)，對(duì)不同時(shí)段的車型配置分別安排，為公交運(yùn)行提供了不同時(shí)段的車輛配置方案。仿真結(jié)果表明，考慮不確定因素的公交車輛合理調(diào)度安排有利于充分利用公交車輛資源和提高公交運(yùn)行效率。

由于本文數(shù)據(jù)有限，僅考慮了單條公交線路，下一步將對(duì)多條公交線路網(wǎng)絡(luò)運(yùn)行優(yōu)化進(jìn)行研究。此外，公交車內(nèi)擁擠程度對(duì)公交乘客出行選擇的影響也需要考慮，以及不確定因素與乘客出行有限理性選擇行為的關(guān)系，進(jìn)一步影響公交運(yùn)營(yíng)調(diào)度也是有待討論的話題。

致謝

感謝美國(guó)MORPC(Mid-Ohio Regional Planning Commission)的Liu Yan博士潤(rùn)色修改英文摘要。