基于隨機(jī)網(wǎng)絡(luò)的公交運(yùn)營優(yōu)化模型

基于隨機(jī)網(wǎng)絡(luò)的公交運(yùn)營優(yōu)化模型

0基于隨機(jī)期望利益的公交運(yùn)營設(shè)計模型公交運(yùn)營設(shè)計是一個復(fù)雜的決策過程，具有多變量、多限制、多階段的特點?？紤]到的因素包括運(yùn)營時間和成本。在公交服務(wù)中,公交乘客總是期望尋求一個最小的旅行時間來完成自己的行程,而公交企業(yè)總是以最有效的經(jīng)營方式來達(dá)到利益的最大化。由于客流OD量一般具有比較明顯的隨機(jī)特征,需要在運(yùn)營設(shè)計中加以充分考慮,才能夠構(gòu)造出科學(xué)的切合實際的公交運(yùn)營方案,所以公交運(yùn)營優(yōu)化設(shè)計模型的構(gòu)建必須平衡公交乘客和公交企業(yè)之間的隨機(jī)期望利益,使兩者均盡量達(dá)到極大化。在以往的研究中,對公交運(yùn)營設(shè)計中的運(yùn)行線路、時刻表以及車輛路徑等問題分別進(jìn)行過有益的探索,但這些決策彼此間具有很強(qiáng)的相關(guān)性,如何在考慮隨機(jī)需求條件下,實現(xiàn)公交時刻表設(shè)計與車輛運(yùn)用的綜合優(yōu)化,一直是該領(lǐng)域研究尚待解決的問題。1時空有向圖的形式公交路徑選擇和調(diào)度安排任務(wù)的公交服務(wù)網(wǎng)絡(luò)通常都能被抽象為一個時空網(wǎng)絡(luò)結(jié)構(gòu)圖G(N,V),即一個有向圖,其中N為一系列的表示公交站點特性的節(jié)點的集合,V為一系列表示節(jié)點間時空聯(lián)系的弧的集合。1.1物理網(wǎng)絡(luò)的類型這里定義時空網(wǎng)絡(luò)圖中每一個節(jié)點包括3個狀態(tài),即i、s、tk,其中i表示該節(jié)點代表的公交車站的序列號,i∈P,P為時空網(wǎng)絡(luò)圖所表示的公交物理網(wǎng)絡(luò)中所有公交車站的集合;s為該節(jié)點所屬的公交線路的類型,s∈S,S為時空網(wǎng)絡(luò)圖所表示的公交物理網(wǎng)絡(luò)中所有公交線路類型的集合;tk表示時間索引,為兩個參數(shù)k和d的乘積,即tk=kd,其中d為時空網(wǎng)絡(luò)圖中公交車輛發(fā)車時間的最小間隔(如1min),k為一個整數(shù)并且在區(qū)間[0,m]內(nèi)取值,m為時空網(wǎng)絡(luò)圖的車輛發(fā)車服務(wù)次數(shù)上限。1.2公交車輛運(yùn)行參數(shù)的定義定義Tij為公交車輛在公交車站i、j之間的行程時間,?i,j∈P且i≠j,為了方便和簡化時空網(wǎng)絡(luò)圖,本文中定義Tij的值為d值的整數(shù)倍,即Tij=ndn=1,2,…,m當(dāng)i=j時,定義Tii=Tjj=d,表示某公交車輛在車站i或j無服務(wù)的停留等待時間為單位時間d,這里以離散的方法來表示公交服務(wù),即在當(dāng)前時刻,公交車輛或者發(fā)車,或者再等待時間d后進(jìn)行下一次決策(發(fā)車或等待)。1.3基于時空網(wǎng)絡(luò)的公交車輛運(yùn)行模擬時空網(wǎng)絡(luò)圖中的弧表示了不同節(jié)點之間的時空聯(lián)系,根據(jù)公交運(yùn)行服務(wù)的自身特點,可以把時空網(wǎng)絡(luò)結(jié)構(gòu)圖G(N,V)中的連接弧分為以下7種類型,表示為V={Lp,Ls,Lt,Lw,Lc,Le,Lo}以s、s1、s2表示不同的公交線路類型,l為時空網(wǎng)絡(luò)圖G(N,V)上的任一條弧,即?l∈V。弧l∈Lp表示公交車輛在某線路類型s上,從時刻tk開始到時刻tk+Tij,由車站i行駛到車站j;弧l∈Ls表示公交車輛在時刻tk,在車站i,由依線路類型s1行駛轉(zhuǎn)為依線路類型s2行駛;弧l∈Lt表示公交乘客流的換乘,即在車站i,公交乘客由沿公交線路s1乘車轉(zhuǎn)為沿公交線路s2乘車;弧l∈Lw表示公交車輛或公交乘客在車站i,由時刻tk到時刻tk+Tii的等待過程;弧l∈Lc表示在時刻tk,車站i上的公交乘客流的匯集過程(上車客流)或公交車輛流的匯集過程;弧l∈Le表示在時刻tk,車站i上的公交乘客流的到達(dá)過程(下車客流)或公交車輛流的到達(dá)過程;如果把時空網(wǎng)絡(luò)圖看作一個系統(tǒng),Lc和Le可以視為時空網(wǎng)絡(luò)圖和外界環(huán)境進(jìn)行交互的兩種弧;弧l∈Lo表示乘客以非公交方式出行,即公共交通所損失的客流。在以上對網(wǎng)絡(luò)圖元素節(jié)點、行程時間矩陣和連接弧等符號進(jìn)行說明的基礎(chǔ)上,可以構(gòu)建出給定公交物理網(wǎng)絡(luò)的公交車輛運(yùn)行服務(wù)的時空網(wǎng)絡(luò)結(jié)構(gòu)圖。為了研究和建模的方便,本文中利用一個比較簡單的公交物理網(wǎng)絡(luò),如圖1所示。該網(wǎng)絡(luò)是一個簡單的直線式的物理網(wǎng)絡(luò),沿線共有3個公交車站,分別表示為a、b、c,有兩條公交線路運(yùn)行于該物理網(wǎng)絡(luò)上,即線路類型1(a-b-c-b-a)和線路類型2(a-b-a)。根據(jù)上述的元素屬性和公交物理網(wǎng)絡(luò)構(gòu)建公交車輛運(yùn)行的時空網(wǎng)絡(luò)結(jié)構(gòu)圖,將各弧依次構(gòu)造在三維圖上,形成了如圖2所示的公交車輛運(yùn)行的時空網(wǎng)絡(luò)結(jié)構(gòu)圖。在圖2外構(gòu)造兩個超級節(jié)點,一個表示客流和車流的總出發(fā)地節(jié)點O,另一個表示客流和車流的總目的地節(jié)點D。設(shè)置弧Lc,由超級節(jié)點O指向圖2中表示不同車站的時空節(jié)點。設(shè)置弧Le,由圖2中表示不同車站的時空節(jié)點指向超級節(jié)點D。設(shè)置弧Lo,由O直接指向D,表示了公共交通所損失的客流以其他交通方式出行。為了繪圖的方便和圖形的直觀,圖2中,O和D兩個超級節(jié)點以及弧Lc、Le與Lo沒有表現(xiàn)出來,主要是由于這些元素表示的是該圖和外界環(huán)境的輸入和輸出關(guān)系;另外,圖2中x軸表示時間,y軸表示線路類型,z軸表示公交車站。2公共汽車的隨機(jī)期望模型在圖2的基礎(chǔ)上,先給出公交調(diào)度的一個混合多目標(biāo)整數(shù)規(guī)劃模型,然后分析OD流的隨機(jī)性,得出公交調(diào)度的隨機(jī)期望值模型。2.1混合多目標(biāo)規(guī)劃模型2.1.1時空網(wǎng)絡(luò)結(jié)構(gòu)及主要功能(1)時空網(wǎng)絡(luò)元素參數(shù)。設(shè)n為時空網(wǎng)絡(luò)圖G(N,V)中某個時空節(jié)點(i,s,tk),這里n∈N,集合N中不包括兩個超級節(jié)點O和D;l為時空網(wǎng)絡(luò)圖G(N,V)中某條弧,這里l∈V;Li為時空網(wǎng)絡(luò)中i類型弧的集合,Li∈{Lp,Ls,Lt,Lw,Lc,Le,Lo};An為時空網(wǎng)絡(luò)中所有“到達(dá)”時空節(jié)點n的弧(弧頭指向時空節(jié)點n)的集合;Bn為時空網(wǎng)絡(luò)中所有從時空節(jié)點n“出發(fā)”的弧(弧尾連接時空節(jié)點n)的集合;An∩Li為時空網(wǎng)絡(luò)中所有“到達(dá)”時空節(jié)點n的i類型弧的集合;Bn∩Li為時空網(wǎng)絡(luò)中所有從時空節(jié)點n“出發(fā)”的i類型弧的集合。(2)輸入?yún)?shù)。設(shè)Cl,p為弧l容納客流量的上限;Cl,v為弧l容納車流量的上限;C為一輛公交車的滿載乘客量;Nqnqn為一支OD流的客流量,該OD流起自時空網(wǎng)絡(luò)中n節(jié)點,止于公交車站q;Mn為時空節(jié)點n可用的車輛數(shù);M為整個時空網(wǎng)絡(luò)結(jié)構(gòu)中安排投入的車輛總數(shù)。(3)變量參數(shù)。設(shè)Xl為弧l上的實際客流量;Yl為弧l上的實際車流量。2.1.2決策方程(1)客流總量的平衡關(guān)系在時空節(jié)點n,所有的欲上車乘客數(shù)滿足∑l∈An∩LcXl=Νqn(1)∑l∈An∩LcXl=Nqn(1)由客流總量的平衡關(guān)系還可知,流入時空節(jié)點n的客流量應(yīng)該恒等于流出時空節(jié)點n的客流量,即如下約束條件成立∑l∈An∩(Lc∪Lp∪Lw∪Lt)Xl=∑l∈Bn∩(Le∪Lp∪Lw∪Lt)Xl(2)∑l∈An∩(Lc∪Lp∪Lw∪Lt)Xl=∑l∈Bn∩(Le∪Lp∪Lw∪Lt)Xl(2)由客流總量的平衡關(guān)系還可知,出發(fā)地超級節(jié)點O向時空網(wǎng)絡(luò)圖輸出客流量和目的地超級節(jié)點D從時空網(wǎng)絡(luò)圖輸入客流量之間的關(guān)系應(yīng)滿足以下兩個約束條件∑n∑l∈An∩LcXl=∑n∑l∈Bn∩LeXl(3)∑n∑l∈An∩LcXl=∑n∑l∈Bn∩LeXl(3)∑n∑l∈Bn∩LeXl=∑n∑qΝqn(4)∑n∑l∈Bn∩LeXl=∑n∑qNqn(4)對于弧l有如下的客流量能力限制Xl≤Cl,pl∈Lp∪Lw(5)同時Xl也應(yīng)該滿足約束Xl≥0l∈Lc∪Lp∪Lw∪Le∪Lt(6)(2)客車總量的平衡關(guān)系在時空節(jié)點n,可用公交車數(shù)的限制∑l∈An∩LcYl=Μn(7)∑l∈An∩LcYl=Mn(7)由車流總量的平衡關(guān)系還可知,流入時空節(jié)點n的車流量應(yīng)該恒等于流出時空節(jié)點n的車流量,即如下約束條件成立∑l∈An∩(Lc∪Lp∪Lw∪Ls)Yl=∑l∈Bn∩(Le∪Lp∪Lw∪Ls)Yl(8)∑l∈An∩(Lc∪Lp∪Lw∪Ls)Yl=∑l∈Bn∩(Le∪Lp∪Lw∪Ls)Yl(8)由車流總量的平衡關(guān)系還可知,出發(fā)地超級節(jié)點O向時空網(wǎng)絡(luò)圖輸出車流量和目的地超級節(jié)點D從時空網(wǎng)絡(luò)圖輸入車流量之間的關(guān)系應(yīng)滿足∑n∑l∈An∩LcYl=∑n∑l∈Bn∩LeYl(9)∑n∑l∈An∩LcYl=∑n∑l∈Bn∩LeYl(9)∑n∑l∈Bn∩LeYl=Μ(10)∑n∑l∈Bn∩LeYl=M(10)若設(shè)T為時空網(wǎng)絡(luò)圖中時間軸上的任意一個定值,則Mn和M之間有以下關(guān)系Μ=∑tk=ΤΜn(11)對于弧l有如下的車流量能力限制Yl≤Cl,vl∈Lp∪Lw(12)同時Yl應(yīng)該滿足約束Yl≥0l∈Lc∪Lp∪Lw∪Le∪Ls(13)另外Yl也應(yīng)該滿足整型約束Yl=0,1,2,…l∈Lc∪Lp∪Lw∪Le∪Ls(14)(3)合同約束條件車流數(shù)量和客流數(shù)量存在如下的關(guān)系Yl≥Xl/Cl∈Lp(15)2.1.3基于wol的乘客滿意度模型公交企業(yè)運(yùn)營的目標(biāo)是盡量實現(xiàn)企業(yè)經(jīng)濟(jì)效益的最大化;同時,乘客的目標(biāo)是盡量實現(xiàn)公交服務(wù)的最優(yōu)化,即公交運(yùn)營社會效益的最大化。在目標(biāo)函數(shù)中必須對以上的經(jīng)濟(jì)效益和社會效益兩個因素進(jìn)行平衡處理。首先,定義wel為時空網(wǎng)絡(luò)圖中對應(yīng)于弧l的公交線路上公交車輛的運(yùn)營流動成本;定義wcl為對應(yīng)于弧l的公交線路上一輛公交車的運(yùn)營固定成本。另外,定義一個表示公交乘客對公交服務(wù)的滿意程度的效用系數(shù)wsl,其值利用對應(yīng)于弧l的公交線路上乘客的等待和換乘時間來衡量,時間愈長,則效用系數(shù)的值愈小,反之,愈大;定義wfl為對應(yīng)于弧l的公交線路上乘客的旅行費(fèi)用。對于公交企業(yè),其運(yùn)營的經(jīng)濟(jì)效益可用如下函數(shù)表示Ζ1=∑l∈LpXlwfl-∑l∈LpYlwel-∑l∈LcYlwcl(16)對于公交乘客,其乘車服務(wù)的量化值,即運(yùn)營的社會效益可表示為Ζ2=∑l∈Lw∪LtXlwsl-∑l∈LpXlwfl(17)則最終的目標(biāo)函數(shù)可以綜合表示為max{Z1,Z2}(18)即整個混合多目標(biāo)整數(shù)規(guī)劃模型的一般形式表示為max{Ζ1,Ζ2}s.t.式(1)~(15)}(19)這里也可以將多目標(biāo)規(guī)劃模型轉(zhuǎn)變?yōu)閱文繕?biāo)規(guī)劃模型,引入?yún)?shù)φ(0≤φ≤1)表示多目標(biāo)中Z1的權(quán)重,則可得單目標(biāo)規(guī)劃模型max{φΖ1+(1-φ)Ζ2}s.t.式(1)~(15)}(20)2.2隨機(jī)向量的實現(xiàn)下面將在以上所建立的混合多目標(biāo)整數(shù)規(guī)劃模型的基礎(chǔ)上,建立隨機(jī)期望值模型。在時空網(wǎng)絡(luò)圖上節(jié)點n處的去往公交車站q的OD流客流量Nqn為一個隨機(jī)變量參數(shù),該值滿足概率密度為f(t)的隨機(jī)分布,可表示為Nqn=∫tktk-1f(t)dt,從而上述的混合多目標(biāo)整數(shù)規(guī)劃模型不能夠完全反映公交調(diào)度的隨機(jī)性和實時動態(tài)特征,因此這里給出對上述模型改進(jìn)后的隨機(jī)期望值模型。定義客流量Nqn為概率空間(Ω,A,Pr)上的一個隨機(jī)向量ξ,ξ=(ξ1,ξ2,ξ3,…,ξN),這里Ω為一個隨機(jī)試驗結(jié)果的集合,A為Ω的一些子集構(gòu)成的σ代數(shù),Pr為概率測度。定義客流向量X和車流向量YX=(…,Xl,…),Y=(…,Yl,…)對于每一個隨機(jī)試驗ω∈Ω,ξ(ω)都是隨機(jī)向量ξ的一個實現(xiàn)。當(dāng)X滿足式(2)~(6)時,稱X為一個可行的客流分配,即定義可行的客流分配方案為X(ω)={X|∑l∈LcXl=ξj(ω)?j=1,2,?,Ν;式(2)~(6)}(21)對于每一個ω∈Ω,目標(biāo)函數(shù)應(yīng)該使得客流分配方案和車流運(yùn)營效益達(dá)到最優(yōu),則經(jīng)濟(jì)效益和社會效益分別為Ζ1(X,Y|ω)=∑l∈LpXlwfl-∑l∈LpYlwel-∑l∈LcYlwclX∈X(ω)(22)Ζ2(X,Y|ω)=∑l∈Lw∪LtXlwsl-∑l∈LpXlwflX∈X(ω)(23)對式(22)、(23)中的隨機(jī)變量取期望值可得E[Ζ1(X,Y|w)]=∫Ω(∑l∈LpXlwfl)Ρrdω-∑l∈LpYlwel-∑l∈LcYlwcl(24)E[Ζ2(X,Y|ω)]=∫Ω(∑l∈Lw∪LtXlwsl-∑l∈LpXlwfl)Ρrdω(25)則在以上分析的基礎(chǔ)上可得隨機(jī)期望值目標(biāo)函數(shù)為max{E[Z1(X,Y|ω)],E[Z2(X,Y|ω)]}(26)因此整個公交調(diào)度隨機(jī)期望值規(guī)劃模型的一般形式可表示為max{E[Ζ1(X,Y|ω)],E[Ζ2(X,Y|ω)]}s.t.式(7)~(15)}(27)同樣可以將式(27)轉(zhuǎn)換為一個單目標(biāo)隨機(jī)期望值模型max{φE[Ζ1(X,Y|ω)]+(1-φ)E[Ζ2(X,Y|ω)]}s.t.式(7)~(15)}(28)上述模型不同于傳統(tǒng)的隨機(jī)期望值模型,因為當(dāng)Y值給定的條件下,該模型存在一個子問題,設(shè)定Ζ′1=∑l∈LpXlwfl(29)Ζ′2=∑l∈Lw∪LtXlwsl-∑l∈LpXlwfl(30)則子問題可以表示為max{Ζ′1,Ζ′2}s.t.∑l∈Bn∩(Lc∪Le)Xl=ξj(ω)j=1,2,?,Ν式(2)~(6)、(15)}(31)對應(yīng)單目標(biāo)模型為max{φΖ′1+(1-φ)Ζ′2}s.t.∑l∈Bn∩(Lc∪Le)Xl=ξj(ω)j=1,2,?,Ν式(2)~(6)、(15)}(32)在這個子問題中,ξj(ω)(j=1,2,…,N)的值固定為整型數(shù)據(jù)。3基于啟發(fā)式算法的公交運(yùn)行規(guī)劃本文中建立的隨機(jī)期望值規(guī)劃模型屬于一類大規(guī)模的帶有整數(shù)變量的隨機(jī)規(guī)劃問題。現(xiàn)有的分枝定價法(BranchPriceMethod)等算法求精確解時,遠(yuǎn)遠(yuǎn)超過研究者所能夠容忍的時間和存儲空間的限制,因此這里需要一個解決帶有隨機(jī)參數(shù)的規(guī)劃問題的啟發(fā)式算法,可利用公交運(yùn)營的特點和公交車輛運(yùn)行的時空網(wǎng)絡(luò)結(jié)構(gòu)圖進(jìn)行啟發(fā)式算法設(shè)計。公交服務(wù)的頻次分配方案(發(fā)車間隔)的確定應(yīng)該是算法的關(guān)鍵所在,在該啟發(fā)式算法中確定這一分配方案時,采用了以特定的車輛滿載率來確定發(fā)車間隔的方法。為了判斷啟發(fā)式算法所得解的可接受程度,應(yīng)該先給出一個公交調(diào)度模型解的可接受上限。3.1車輛滿載率為100%時的公交服務(wù)頻次分配算法步驟1:給定循環(huán)模擬的次數(shù)上限,初始化當(dāng)前循環(huán)次數(shù)值為0。步驟2:利用隨機(jī)數(shù)發(fā)生程序模擬客流的產(chǎn)生,當(dāng)客流的積累可使車輛滿載率達(dá)到100%時,確定一個發(fā)車點;如此重復(fù),直到完成整個車輛滿載率為100%時的公交服務(wù)頻次分配方案。步驟3:對步驟2所形成的公交服務(wù)頻次分配方案進(jìn)行勾畫連接,形成完整的公交車輛服務(wù)網(wǎng)絡(luò);同時也確定了執(zhí)行行車時刻表所需要的公交車輛數(shù),即車隊規(guī)模。這是一個比較典型的單商品網(wǎng)絡(luò)流問題,可用網(wǎng)絡(luò)單純形算法解決。步驟4:目標(biāo)函數(shù)值的計算,即對所形成的行車時刻表方案的目標(biāo)效益值進(jìn)行計算并保存,計算社會效益部分時假定乘客的等待時間為0;同時當(dāng)前循環(huán)次數(shù)值加1,如果當(dāng)前循環(huán)次數(shù)值沒有達(dá)到步驟1所確定的循環(huán)次數(shù)上限,轉(zhuǎn)到步驟2。步驟5:對所有保存的目標(biāo)效益值求期望值,所得的期望值為公交調(diào)度模型解的可接受上限。3.2基于目標(biāo)效益期望的出行時刻表優(yōu)化整個算法分解為4個部分:算法Ⅰ為主算法,用于比較一系列公交車輛滿載率中各自對應(yīng)的公交調(diào)度模型的目標(biāo)效益期望值,并從中選擇目標(biāo)滿載率,利用目標(biāo)滿載率得到合理的行車時刻表。算法Ⅱ、Ⅳ均被算法Ⅰ所調(diào)用,為子算法;算法Ⅱ用來求解公交客流OD量的發(fā)生期望值方案;算法Ⅲ用來求解在給定的公交車輛滿載率情況下的行車時刻表方案和公交調(diào)度模型的目標(biāo)效益值。算法Ⅳ利用目標(biāo)滿載率尋求行車時刻表方案。3.2.1創(chuàng)建目標(biāo)完滿率集合步驟1:給定一個車輛滿載率集合。步驟2:根據(jù)算法Ⅱ計算公交OD流的發(fā)生期望值方案。步驟3:根據(jù)算法Ⅲ計算所確定車輛滿載率集合中各滿載率對應(yīng)的目標(biāo)效益值,從而得到目標(biāo)效益值集合。步驟4:從目標(biāo)效益值集合中選擇最優(yōu)值所對應(yīng)的車輛滿載率作為目標(biāo)滿載率。步驟5:根據(jù)算法Ⅳ,利用目標(biāo)滿載率模擬得到可行的行車時刻表方案。3.2.2客流發(fā)生規(guī)律步驟1:給定模擬循環(huán)的次數(shù)上限,初始化當(dāng)前循環(huán)次數(shù)值為0。步驟2:依靠符合客流發(fā)生規(guī)律的隨機(jī)數(shù)發(fā)生程序模擬客流OD的產(chǎn)生,形成一套客流發(fā)生方案,并保存;同時當(dāng)前循環(huán)次數(shù)值加1。步驟3:如果當(dāng)前循環(huán)次數(shù)值小于模擬循環(huán)的次數(shù)上限,則轉(zhuǎn)到步驟2。步驟4:計算所有客流發(fā)生方案的期望值作為客流OD發(fā)生的期望值方案。3.2.3od流發(fā)生的模擬步驟1:給定公交車輛的滿載率。步驟2:公交服務(wù)頻次分配。這一步驟的主要目標(biāo)是在平衡考慮公交企業(yè)經(jīng)濟(jì)效益和公交服務(wù)質(zhì)量的基礎(chǔ)上制定出合理的公交服務(wù)頻次分配方案,即制定出合理的公交發(fā)車間隔、車輛運(yùn)行時間等安排方案。這里采用以步驟1給定的車輛滿載率來確定發(fā)車間隔的方法,即在各個發(fā)車站點,根據(jù)公交客流的積累情況,當(dāng)其積累量達(dá)到給定滿載率后確定發(fā)車,然后在此基礎(chǔ)上勾畫出各始末站點之間的車輛運(yùn)行線。公交客流OD量依靠隨機(jī)數(shù)發(fā)生程序來模擬產(chǎn)生。步驟3:公交車輛分配。這一步驟的主要目標(biāo)是在滿足公交乘客需求的基礎(chǔ)上盡量減少公交企業(yè)的運(yùn)營成本和運(yùn)營車輛數(shù)量,確定合理的公交運(yùn)營車輛數(shù)量,并將其分配到步驟2所形成的公交服務(wù)頻次網(wǎng)絡(luò)(公交運(yùn)行線)上,這是一個比較典型的單商品網(wǎng)絡(luò)流問題,可用網(wǎng)絡(luò)單純形算法解決。步驟4:確定是否需要進(jìn)行公交服務(wù)頻次分配和車輛分配的有效調(diào)整,如果不需要,則這時已經(jīng)形成一套行車時刻表方案,并轉(zhuǎn)到步驟6。步驟5:公交服務(wù)頻次分配和車輛分配的調(diào)整。這一步驟的主要目標(biāo)是對步驟2、3中不合理部分進(jìn)行合理化的微調(diào),經(jīng)過調(diào)整后形成一套行車時刻表方案。步驟6:將公交OD流發(fā)生的期望值方案分配到所形成的行車時刻表方案上。步驟7:根據(jù)所形成的帶有客流分布的行車時刻表方案,計算出公交企業(yè)的經(jīng)濟(jì)效益值和公交服務(wù)的社會效益值。步驟8:將經(jīng)濟(jì)效益值和社會效益值相加,所得值為對應(yīng)給定車輛滿載率的目標(biāo)效益值。3.2.4可接受的解步驟1:給定目標(biāo)滿載率作為車輛滿載率,給定模型解的可接受上限。步驟2~7:同算法Ⅲ的步驟2~7。步驟8:將經(jīng)濟(jì)效益值和社會效益值相加得到目標(biāo)效益值。如果該目標(biāo)函數(shù)值和解的可接受上限的差值在一個可接受的范圍內(nèi),則以當(dāng)前得到的行車時刻表方案作為可接受方案,算法結(jié)束;否則轉(zhuǎn)到步驟2。利用上述的啟發(fā)式算法,雖然不太可能求得公交調(diào)度模型的最優(yōu)解,卻可以在可接受的時間和存儲空間內(nèi)得到一個可接受的可行解。4計算示例4.1客觀單元客流分布情況選擇北京市公共交通總公司開行在二里莊—西便門的公交線路為例進(jìn)行模型和算法的分析。該線路沿途經(jīng)過了二里莊、中國農(nóng)業(yè)大學(xué)……西便門車站,線路全長20.10km?，F(xiàn)場調(diào)研發(fā)現(xiàn)客流分布規(guī)律大體是:二里莊—西外大街區(qū)段客流量密集,而西外大街—西便門區(qū)段客流量則相對較少,沿途沒有大的客流發(fā)生地和到達(dá)地,并且在西外大街車站,公交車輛有掉頭、返行的條件?；诖嗽诙锴f—西便門區(qū)段可以開行兩種線路類型,線路類型1為二里莊—西外大街—西便門—西外大街—二里莊,線路類型2為二里莊—西外大街—二里莊,如圖3所示。4.2計算機(jī)求解程序根據(jù)本文中的公交調(diào)度隨機(jī)期望值模型的啟發(fā)式求解算法和北京市公共交通總公司16路支線運(yùn)營的具體數(shù)據(jù),利用C++語言實現(xiàn)計算機(jī)求解程序,程序依靠合理的隨機(jī)數(shù)的生成來模擬公交OD流的流量,在PⅢ800微機(jī)上,滿意期望值計劃生成時間一般控制在10min之內(nèi)。通過控制模擬時間和計劃參數(shù),對行車時刻表和車輛路徑方案求解結(jié)果進(jìn)行數(shù)據(jù)分析。4.2.1車輛滿載率對車輛管理的影響圖4為在乘客最大等待時間為8min的情況下,公交車輛的滿載率和公交車隊規(guī)模的大小之間的關(guān)系。開行方案