基于雙指標(biāo)帶權(quán)線性規(guī)劃的公交車調(diào)度模型研究

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

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

中圖分類號(hào)：O221.1 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：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 引言

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

1 問(wèn)題的分析與假設(shè)

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

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

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

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

⑵ 每輛車經(jīng)過(guò)各車站時(shí)不留候車乘客；車輛上行或下行到達(dá)終點(diǎn)站時(shí)，所有乘客全部下車；

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

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

2 模型的建立與化簡(jiǎn)

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

2.1 公交車調(diào)度模型的符號(hào)定義

i表示第i個(gè)時(shí)間段，每日有m個(gè)時(shí)間段，時(shí)間間隔為h；

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

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

ki表示i時(shí)間段第k班車；

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

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

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

ci表示i時(shí)間段乘客等待的最長(zhǎng)時(shí)間；

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

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

Ti總表示某時(shí)間段所有班車行駛時(shí)間；

T表示從始發(fā)站到終點(diǎn)站所需時(shí)間

M表示最大載客量；

V表示公交車行駛速度。

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

2.2.1 指標(biāo)一：公交車載客率[2]

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

T=Ps/Pm

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

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

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

當(dāng)Tijk≤Ti+1時(shí)pijk=pij-1k+qij，當(dāng)Tijk>Ti+1時(shí)pijk=pij-1k+qi+1j。

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

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

2.2.2 指標(biāo)二：乘客不滿率[3]

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

C=Cs/Ps

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

3 模型的求解與驗(yàn)證

3.1 建立雙指標(biāo)優(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…}

引入兩個(gè)非負(fù)加權(quán)因子a1，a2，轉(zhuǎn)化為單目標(biāo)優(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…}

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

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

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

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

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

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

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

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

3.3 使用實(shí)際數(shù)據(jù)進(jìn)行模型驗(yàn)證

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

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

（下行線路S0開往S8）

[站編號(hào)＼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＼＼行駛時(shí)間（分鐘）＼1.74＼3.15＼2.4＼1.2＼3.6＼3＼6.9＼3.9＼＼累計(jì)時(shí)間＼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 模型方程組的化簡(jiǎn)與求解

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

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

當(dāng)ni=時(shí)取得最小值。

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

經(jīng)計(jì)算得出表2的數(shù)據(jù)。

表2 各時(shí)段最佳發(fā)車數(shù)量與對(duì)應(yīng)指標(biāo)

[時(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%＼]

該結(jié)果在誤差范圍內(nèi)符合實(shí)際結(jié)果，說(shuō)明模型準(zhǔn)確有效。

4 模型改進(jìn)

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

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

Ps=

Cs=

Pm=M*l*

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

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

實(shí)際應(yīng)用中，需要把數(shù)學(xué)模型轉(zhuǎn)換為程序語(yǔ)言，這里將模型求解過(guò)程歸納為算法描述：

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

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

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

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

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

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

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

⑻ 驗(yàn)證ni≥max{Pi1，…Pij}/M且T

⑼ 解方程組：

X上＼下=max{X1…Xm}

Xi=

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

bi=*ni/（V*h），i=0時(shí)bi=0

6 結(jié)束語(yǔ)

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

參考文獻(xiàn)：

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

與安全，2009.4：48-51

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

經(jīng)濟(jì)，2008.5：23-25

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

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

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

輸工程學(xué)報(bào)，2003.4：42-44

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

[6] 劉紅，張強(qiáng)，杜瑜.全國(guó)大學(xué)生數(shù)學(xué)建模競(jìng)賽中公交車調(diào)度問(wèn)題的求

解[J].成都航空職業(yè)技術(shù)學(xué)院學(xué)報(bào)，2002.6：20-22