基于雙指標帶權線性規(guī)劃的公交車調度模型研究

摘 要： 公交車輛調度系統(tǒng)的優(yōu)化可以提高公交車輛的運營效率，緩解城市交通壓力，改善交通環(huán)境。針對公交車輛調度的現(xiàn)狀，首先引入了公交車載客率和乘客不滿率兩個指標，并為這兩個指標建立了帶權優(yōu)化模型；然后求得每個時間段最佳公交車發(fā)車數(shù)量，獲得最優(yōu)解；最后通過帶入最優(yōu)解，求得封閉線路（有來回）的最少備車數(shù)。通過代入數(shù)據驗證，所得解在允許誤差范圍內符合實際結果，因此模型準確可靠，且基于本模型算法實現(xiàn)的程序能夠應用于公交車調度系統(tǒng)。

關鍵詞： 公交車調度； 線路優(yōu)化； 線性規(guī)劃； 加權模型

中圖分類號：O221.1 文獻標志碼：A 文章編號：1006-8228（2013）12-01-03

Study of bus scheduling model based on double index weighted linear programming

Chen Xiangyu， Ge Yinglong， Chen Weixin

（Hangzhou Dianzi University， Software Engineering， Hangzhou， Zhejiang 310018， China）

Abstract： Bus scheduling system can be optimized to maximize the operational efficiency of public transport vehicles which are able to relieve traffic pressure and improve the traffic environment. Aiming at the current situation of bus scheduling， two indicators， bus passenger vehicle rate and the unsatisfactory rate of passengers， are used to establish a weighted optimization model. Then the best number of bus departure for each time period is calculated and the optimal solution is obtained. Finally， the optimal solution is inserted to obtain the minimum number of buses prepared on closed circuit （with back and forth）. By substituting data and validating， the result meets the actual needs in allowed range of deviation， so the model is credible and can be used in bus scheduling system.

Key words： bus scheduling； route optimization； linear programming； weighted model

0 引言

合理的公交調度，可以充分發(fā)揮城市交通系統(tǒng)的最大效益，便于居民出行，減輕城市道路系統(tǒng)的交通壓力。而線路上公交車輛使用的效率也決定了企業(yè)的運營成本、道路的占有率和社會的公共交通出行費用，對提高整個城市的交通效率具有重要意義。目前，有很多針對這方面的研究，本文提出了基于公交車載客率和乘客不滿率的加權優(yōu)化方案，采用線性規(guī)劃方法求出最優(yōu)解，并將求解過程化簡、歸納為算法，求得上、下行線路所需最少預備車輛數(shù)（以下簡稱備車數(shù)）。

1 問題的分析與假設

我們根據公交車運營中公交公司與乘客之間普遍存在的利益矛盾，建立問題模型。該模型的目標是在一定的權重比下，實現(xiàn)公交公司與乘客利益之和最大化[1]，故引入兩個待優(yōu)化指標：公交車載客率與乘客不滿率。在實際情況中，一般通過控制公交車的發(fā)車時間間隔來調整兩指標。因此，模型的目標即為求得合理范圍內的公交車發(fā)車時間間隔，使得加權后公交車載客率與乘客不滿率倒數(shù)之和取最大值。

通常情況下，每日不同時刻同一公交車站單位時間上下車乘客數(shù)量不定。為簡化問題模型，我們將每日公交車的運營時刻分成均等時間段，使得每個時間段內同一公交車站單位時間上下車乘客數(shù)量基本不變，且時間段長度大于公交車從始發(fā)站到終點站所需的時間。在求解公交車上下行線路最少備車數(shù)問題時，應當保證上下行線路同時發(fā)車，那么在已求得最佳公交車的發(fā)車時間間隔后，即可根據各時間段上下行線路車輛數(shù)求解。

此外，要解決公交車調度問題還需要公交車線路的基礎數(shù)據，即各站之間的距離，公交車行駛速度，公交車最大載客量和各站不同時間段內乘客上下車數(shù)量，不同時間段乘客的最長等待時間。至此，我們作出如下假設：

⑴ 所有公交車規(guī)格一樣，最大載客量、行車速度完全相同；

⑵ 每輛車經過各車站時不留候車乘客；車輛上行或下行到達終點站時，所有乘客全部下車；

⑶ 公交車始終保持理想狀態(tài)運行，在同一個時間段內，相鄰兩班車發(fā)車時間間隔相等，保持勻速行駛，乘客上下車時間忽略不計；

⑷ 每日公交車運營時間劃分為均等時間段，同一時間段內各站單位時間上下車乘客數(shù)量固定。

2 模型的建立與化簡

基于以上假設，問題模型可以歸納為：在一條已知站臺數(shù)量與相鄰站臺距離的公交線路上，具有相同規(guī)格的公交車以勻速從始發(fā)站發(fā)車，裝載沿途各站所有候車乘客，上下車時間忽略不計，到達終點站后所有乘客必須下車。將該線路每日運營時間分為有限個等長時間段，已知各時間段各站上下車乘客數(shù)，求各時段最佳發(fā)車頻率以及每日上下行線最少備車數(shù)。

2.1 公交車調度模型的符號定義

i表示第i個時間段，每日有m個時間段，時間間隔為h；

j表示第j站，一條單向線路共l站；

d表示第j站與前一站之間的距離；

ki表示i時間段第k班車；

ni表示i時間段發(fā)車數(shù)量；

vij表示i時間段第j站單位時間上下車乘客數(shù)量；

ti表示i時間段發(fā)車時間間隔；

ci表示i時間段乘客等待的最長時間；

qij表示i時間段在j站每班車需要裝載的乘客數(shù)量；

pijk表示i時間段k班車到達j站時車上乘客數(shù)量；

Ti總表示某時間段所有班車行駛時間；

T表示從始發(fā)站到終點站所需時間

M表示最大載客量；

V表示公交車行駛速度。

2.2 量化公交車載客率與乘客滿意率

2.2.1 指標一：公交車載客率[2]

公交車實際運載乘客數(shù)與標稱最大載客數(shù)的比值稱為載客率用T表示，于是有：

T=Ps/Pm

其中，Ps指每日實際運載乘客，Pm指每日公交車最大運載量。那么Pm=M*（l-1）*，即最大載客量與停靠車站數(shù)和每日各時間段發(fā)車數(shù)量之和的積；而Ps=，即各時間段各班公交車在各站的載客數(shù)之和。

接下來求pijk，已知公交車每次到站都要保證接走所有乘客，而且有在每個時間段靠后的班次發(fā)車有可能在下個時間段抵達目標站，所以這里分類討論如下：

顯然第i時間段第k班公交車到達第j站時的時間Tijk=h*（i+k/n）+/V；

當Tijk≤Ti+1時pijk=pij-1k+qij，當Tijk>Ti+1時pijk=pij-1k+qi+1j。

qij=vij*ti，vij*ti表示i時間段第j站每班車到達這里后需要裝載的乘客數(shù)量。其中vij=vij上-vij下，ti=h/ni；而每日的頭班車所需要裝載的乘客qij=vij*/V。

為了便于實際應用中的統(tǒng)計，這里通過記錄第i時間段在第j站累計上下車人數(shù)x上、x下，然后除以時間段的長度，得出vij上、vij下，即：vij=x/h。

2.2.2 指標二：乘客不滿率[3]

模型中，當乘客候車時間超出規(guī)定值時，被認定為不滿意乘客。不滿意乘客占候車乘客總體的比例定義為乘客不滿率，用C表示；于是有：

C=Cs/Ps

其中，Cs是指不滿意的乘客數(shù)量總和，由于每個時間段每個站單位時間內上車人數(shù)不變，故等待上車人數(shù)呈線性增加，可得Cs=；其中cijk=max{vij上（ti-ci），0}，且對于每日首班車來說ti=/V。

3 模型的求解與驗證

3.1 建立雙指標優(yōu)化模型

最大化載客率：maxT=M*l*/

最小化乘客不滿率：minC=/

pijk≤M，h>/V，cijk>0，ni>0，i∈{1，2，…，m}，j∈{1，2，…，l}，k∈{1，2…}

引入兩個非負加權因子a1，a2，轉化為單目標優(yōu)化模型[4]：

min（a1/Z+a2C）

pijk≤M，h>/V，cijk>0，ni>0，i∈{1，2，…，m}，j∈{1，2，…，l}，k∈{1，2…}

將以上條件代入基礎數(shù)據便可以求解各時間段的發(fā)車時間間隔ti。

3.2 求封閉線路（有來回）的最少備車數(shù)[5]

公交車線路根據行車方向分為上下行線，要保證線路正常運行，每日各時間段末班車到終點站時，站內備車數(shù)量都須大于零，同時保證在對應線路第一班到來之前有足夠的車輛發(fā)車。

第i時間段結束時上行線在路上的車輛bi=*ni/（V*h），i=0時bi=0

第i個時間段上行線公交車數(shù)量變化量xi=ni-ni'+bi-bi-1（ni'表示i時間段內下行線發(fā)車數(shù)量）

第i個時間段上行線公交車數(shù)量累計變化量Xi=

上行線所需備車數(shù)X上=max{X1…Xm}

同理可求下行線所需備車數(shù)X下。

3.3 使用實際數(shù)據進行模型驗證

設公交車最大載客量M為100，公交車平均行駛速度為20KM/H，從每日上午六點開始，每個時間段長一小時，共十四個時間段，乘客各時間段最大等待時間ci設為5分鐘，模型加權因子a1=0.1，a2=0.9。經實際統(tǒng)計，得到某線路公交車上下車客流量，如表1所示。

表1 某公交車線路每日各時段各站上下車客流量統(tǒng)計表

（下行線路S0開往S8）

[站編號＼S0＼S1＼S2＼S3＼S4＼S5＼S6＼S7＼S8＼站間距（KM）＼0.58＼1.05＼0.8＼0.4＼1.2＼1＼2.3＼1.3＼＼行駛時間（分鐘）＼1.74＼3.15＼2.4＼1.2＼3.6＼3＼6.9＼3.9＼＼累計時間＼1.74＼4.89＼7.29＼8.49＼13.09＼16.09＼22.18＼26.08＼＼6：00～7：00＼上＼90＼48＼83＼85＼26＼45＼45＼11＼0＼下＼0＼32＼71＼52＼43＼61＼73＼28＼73＼pijk＼90＼106＼118＼151＼134＼118＼90＼73＼0＼7：00～8：00＼上＼868＼523＼958＼904＼259＼465＼454＼99＼0＼下＼0＼105＼421＼406＼928＼582＼875＼403＼810＼pijk＼868＼1286＼1823＼2321＼1652＼1535＼1114＼810＼0＼8：00～9：00＼上＼594＼315＼622＼510＼176＼308＼307＼68＼0＼下＼0＼79＼260＼261＼605＼314＼592＼378＼411＼pijk＼594＼830＼1192＼1441＼1012＼1006＼721＼411＼0＼9：00～10：00＼上＼549＼271＼486＼439＼157＼275＼234＼60＼0＼下＼0＼62＼275＼286＼405＼314＼398＼360＼371＼pijk＼549＼758＼969＼1122＼874＼835＼671＼371＼0＼10：00～11：00＼上＼304＼172＼324＼267＼78＼143＼162＼36＼0＼下＼0＼54＼208＼103＼327＼178＼254＼260＼102＼pijk＼304＼422＼538＼702＼453＼418＼326＼102＼0＼11：00～12：00＼上＼214＼119＼212＼201＼75＼123＼112＼26＼0＼下＼0＼45＼103＼171＼208＼155＼137＼41＼222＼pijk＼214＼288＼397＼427＼294＼262＼237＼222＼0＼12：00～13：00＼上＼264＼135＼253＼260＼74＼138＼117＼30＼0＼下＼0＼65＼120＼242＼197＼155＼120＼67＼305＼pijk＼264＼334＼467＼485＼362＼345＼342＼305＼0＼13：00～14：00＼上＼204＼129＼232＼221＼65＼103＼112＼26＼0＼下＼0＼47＼135＼189＼206＼97＼132＼82＼204＼pijk＼204＼286＼383＼415＼274＼280＼260＼204＼0＼14：00～15：00＼上＼185＼103＼211＼173＼66＼108＼97＼23＼0＼下＼0＼43＼129＼206＼150＼101＼130＼69＼138＼pijk＼185＼245＼327＼294＼210＼217＼184＼138＼0＼15：00～16：00＼上＼178＼90＼185＼70＼49＼75＼85＼20＼0＼下＼0＼38＼114＼82＼137＼61＼90＼45＼185＼pijk＼178＼230＼301＼289＼201＼215＼210＼185＼0＼16：00～17：00＼上＼180＼80＼185＼50＼49＼85＼85＼20＼0＼下＼0＼37＼120＼61＼128＼44＼117＼63＼164＼pijk＼180＼223＼288＼277＼198＼239＼207＼164＼0＼17：00～18：00＼上＼404＼210＼428＼390＼120＼208＼197＼49＼0＼下＼0＼132＼263＼405＼358＼173＼204＼129＼342＼pijk＼404＼482＼647＼632＼394＼429＼422＼342＼0＼18：00～19：00＼上＼479＼296＼586＼508＼140＼250＼259＼61＼0＼下＼0＼157＼308＼512＼495＼278＼244＼152＼423＼pijk＼479＼618＼896＼892＼537＼509＼524＼433＼0＼19：00～20：00＼上＼165＼108＼201＼194＼53＼93＼82＼22＼0＼下＼0＼71＼89＼135＼194＼110＼65＼83＼171＼pijk＼165＼202＼314＼373＼232＼215＼232＼171＼0＼]

3.4 模型方程組的化簡與求解

方程組化簡后，ci=max{1/ni-1/12，0}（c1的常數(shù)部分不影響求最優(yōu)解，這里可以忽略），這說明乘客不滿率只與某時間段內的發(fā)車數(shù)量有關；而載客率Ti=Psi/（800*ni），故問題模型求解的關鍵就在于求出Psi，Psi=，pijk需要分情況討論，這里首先求出某時間段發(fā)出的所有班車在下個時間段行駛的時間占總行駛時間的比例：x=T（i+1）總/（T（i+1）總+Ti總）=ni*T2/120*ni*T=T/120≈0.2173，則Psi=Psi理+（Psi+1理-Psi理）*x，特別地，對于每日的首個時間段和最后一個時間段則為Psi=Psi理+Psi+1理*x和Psi=Psi理*（1-x）；最后，代入以上條件得：

min（a1/Z+a2C）=min（10*ni/psi+max{9/（10*ni）-3/40，0}）

當ni=時取得最小值。

此外，在假設中要求每班車到終點站后不留乘客，故要滿足ni≥max{Pi1，…Pij}/M，同時T=26.08

經計算得出表2的數(shù)據。

表2 各時段最佳發(fā)車數(shù)量與對應指標

[時間段 i＼發(fā)車數(shù)量 ni＼理想載客量 Psi理＼載客量 Psi＼載客率 Ti＼乘客不滿率 ci＼6：00～7：00＼7＼880＼3360＼60%＼16.28%＼7：00～8：00＼14＼11409＼10496＼93.71%＼0%＼8：00～9：00＼9＼7207＼6987＼90.04%＼2.78%＼9：00～10：00＼8＼6149＼5523＼86.3%＼4.17%＼10：00～11：00＼6＼3265＼3065＼63.85%＼8.33%＼11：00～12：00＼6＼2341＼2464＼51.33%＼8.33%＼12：00～13：00＼6＼2904＼2775＼57.81%＼8.33%＼13：00～14：00＼5＼2306＼2197＼54.93%＼11.67%＼14：00～15：00＼5＼1800＼1802＼45.05%＼11.67%＼15：00～16：00＼5＼1809＼1802＼45.05%＼11.67%＼16：00～17：00＼5＼1776＼2206＼55.15%＼11.67%＼17：00～18：00＼7＼3752＼3999＼71.41%＼6.95%＼18：00～19：00＼7＼4888＼4240＼75.71%＼6.95%＼19：00～20：00＼5＼1904＼1491＼37.28%＼11.67%＼]

該結果在誤差范圍內符合實際結果，說明模型準確有效。

4 模型改進

若想進一步優(yōu)化模型，可以先根據相鄰車站間距離，賦予各車站載客率不同的權值[6]，再求載客率。

顯然總路程L總=，各站權重等于前后站點距離的平均值比上總路程wj=dj+dj-1/（2*L總+d1+dl），其中始發(fā)站和終點站取后（前）站距離，那么加權之后有：

Ps=

Cs=

Pm=M*l*

此外，在實際情況中乘客不滿率C和乘客滿意度CC并非線性關系。若要精確求解兩者關系，首先可根據實際調研數(shù)據繪制C-CC曲線圖，然后確定正整數(shù)n，使得CC≈an*（C-bn）n+an-1*（C-bn-1）n-1…a*（C-b）+c，最后代入數(shù)據建立方程組求解系數(shù)an，bn…。利用求得的方程組求出CC的計算公式，最終問題轉換為求解min（a1/Z+a2CC）成立時ni的取值。

5 模型求解算法的實現(xiàn)

實際應用中，需要把數(shù)學模型轉換為程序語言，這里將模型求解過程歸納為算法描述：

⑴ 輸入最大載客量M，行車速度V，時段數(shù)m，時段長h，公交站數(shù)量l，乘客各時間段最大等待時間ci，執(zhí)行⑵；

⑵ 驗證⑴中輸入數(shù)據合法性，若合法則執(zhí)行⑶，否則執(zhí)行⑴；

⑶ 輸入相鄰車站間距離dj，各時段各站上下車人數(shù)p上p下，計算出各站間所需行駛時間；

⑷ 輸入要計算的時間段以及Ti和Ci的權重系數(shù)a0，a1，如果是第一個時間段則執(zhí)行⑸，如果是最后一個時間段則執(zhí)行⑹，都不是則執(zhí)行⑺；

⑸ 根據Csi=x上（ni-h*ci），Pmi=M*（l-1），Psi=Psi理+Psi+1理*x，求ni的最優(yōu)解；

⑹ 根據Csi=x上（ni-h*ci），Pmi=M*（l-1），Psi=Psi理*（1-x），求ni的最優(yōu)解；

⑺ 根據Csi=x上/h[/（V*l）-ci]，Pmi=M*（l-1），Psi=Psi理+（Psi+1理-Psi理）*x，求ni的最優(yōu)解；

⑻ 驗證ni≥max{Pi1，…Pij}/M且T

⑼ 解方程組：

X上＼下=max{X1…Xm}

Xi=

xi=ni-ni'+bi-bi-1，（ni'表示i時間段內上＼下行線發(fā)車數(shù)量）

bi=*ni/（V*h），i=0時bi=0

6 結束語

本文雙參數(shù)線性規(guī)劃模型除了擁有較高的準確度，還易于在計算機程序中實現(xiàn)。根據本模型算法編寫的代碼擁有較高的執(zhí)行效率，故可以廣泛地應用于各種車量調度系統(tǒng)。使用此類系統(tǒng)的公司可以有效降低公交系統(tǒng)運營成本，同時可避免超載、空載現(xiàn)象，保障了乘客利益，有助于交通運輸行業(yè)良性發(fā)展。但是，因為雙指標模型的優(yōu)化指標僅有兩個，而實際情形中需要考慮的因素往往更多，所以在未來的研究中將嘗試使用多指標非線性模型進行更準確的建模。

參考文獻：

[1] 姚俊，呂智林，葉嫣.基于滿意度的公交車調度模型研究[J].交通信息

與安全，2009.4：48-51

[2] 張榮杰，李鐵柱.基于運輸效益的城市公交發(fā)車頻率[J].交通科技與

經濟，2008.5：23-25

[3] 程杰，鄧衛(wèi)，蒯婷婷.基于期望滿足概率的公交發(fā)車間隔計算模型[J].

現(xiàn)代交通技術，2006.4：71-73

[4] 牛學勤，陳茜，王煒.城市公交線路調度發(fā)車頻率優(yōu)化模型[J].交通運

輸工程學報，2003.4：42-44

[5] 楊啟帆.數(shù)學建模[M].高等教育出版社，2005.

[6] 劉紅，張強，杜瑜.全國大學生數(shù)學建模競賽中公交車調度問題的求

解[J].成都航空職業(yè)技術學院學報，2002.6：20-22