公交車(chē)調(diào)度問(wèn)題

公交車(chē)調(diào)度問(wèn)題關(guān)于公交車(chē)的調(diào)度問(wèn)題摘要:本文主要是研究公交車(chē)調(diào)度的最優(yōu)策略問(wèn)題。我們建立了一個(gè)以公交車(chē)的利益為目標(biāo)函數(shù)的優(yōu)化模型，同時(shí)保證等車(chē)時(shí)間超過(guò) 10分鐘（或者超過(guò) 5分鐘）的乘客人數(shù)在總的等車(chē)乘客數(shù)所占的比重小于一個(gè)事先給定的較小值。首先，利用最小二乘法擬合出各站上（下）車(chē)人數(shù)的非參數(shù)分布函數(shù)，求解時(shí)先用一種簡(jiǎn)單方法估算出最小配車(chē)數(shù)43輛。然后依此為參照值，利用Maple優(yōu)化工具得到一個(gè)整體最優(yōu)解：最小配車(chē)數(shù)為48輛，并給出了在公交車(chē)載客量不同條件下的最優(yōu)車(chē)輛調(diào)度方案，使得公司的收益得到最大，并且乘客等車(chē)的時(shí)間不宜過(guò)長(zhǎng)，最后對(duì)整個(gè)模型進(jìn)行了推廣和評(píng)價(jià)，指出了有效改進(jìn)方向。關(guān)鍵詞：公交車(chē)調(diào)度；優(yōu)化模型；最小二乘法問(wèn)題的重述 :公共交通是城市交通的重要組成部分， 作好公交車(chē)的調(diào)度對(duì)于完善城市交通環(huán)境、改進(jìn)市民出行狀況、提高公交公司的經(jīng)濟(jì)和社會(huì)效益，都具有重要意義。下面考慮一條公交線路上公交車(chē)的調(diào)度問(wèn)題，其數(shù)據(jù)來(lái)自我國(guó)一座特大城市某條公交線路的客流調(diào)查和運(yùn)營(yíng)資料。該條公交線路上行方向共 14站，下行方向共13站，第3-4頁(yè)給出的是典型的一個(gè)工作日兩個(gè)運(yùn)行方向各站上下車(chē)的乘客數(shù)量統(tǒng)計(jì)。公交公司配給該線路同一型號(hào)的大客車(chē)，每輛標(biāo)準(zhǔn)載客100人，據(jù)統(tǒng)計(jì)客車(chē)在該線路上運(yùn)行的平均速度為20公里 /小時(shí)。運(yùn)營(yíng)調(diào)度要求，乘客候車(chē)時(shí)間一般不要超過(guò) 10分鐘，早高峰時(shí)一般不要超過(guò)5分鐘，車(chē)輛滿載率不應(yīng)超過(guò) 120%，一般也不要低于50%。試根據(jù)這些資料和要求，為該線路設(shè)計(jì)一個(gè)便于操作的全天（工作日）的公交車(chē)調(diào)度方案，包括兩個(gè)起點(diǎn)站的發(fā)車(chē)時(shí)刻表；一共需要多少輛車(chē)；這個(gè)方案以怎樣的程度照顧到了乘客和公交公司雙方的利益；等等。如何將這個(gè)調(diào)度問(wèn)題抽象成一個(gè)明確、 完整的數(shù)學(xué)模型，指出求解模型的方法；根據(jù)實(shí)際問(wèn)題的要求，如果要設(shè)計(jì)更好的調(diào)度方案，應(yīng)如何采集運(yùn)營(yíng)數(shù)據(jù)?；炯僭O(shè)1） 該公交路線不存在堵塞現(xiàn)象，且公共汽車(chē)之間依次行進(jìn)，不存在超車(chē)現(xiàn)象。2） 公共汽車(chē)滿載后，乘客不能再上，只得等待下一輛車(chē)的到來(lái)。3） 上行、下行方向的頭班車(chē)同時(shí)從起始站出發(fā)。4） 該公交路線上行方向共14站，下行方向共13站。5） 公交車(chē)均為同一型號(hào)，每輛標(biāo)準(zhǔn)載客 100名，車(chē)輛滿載率不應(yīng)超過(guò) 120%，一般也不要低于50%。6） 客車(chē)在該路線上運(yùn)行的平均速度為20公里/小時(shí)，不考慮乘客上下車(chē)時(shí)間。7） 乘客侯車(chē)時(shí)間一般不超過(guò)10分鐘，早高峰時(shí)一般不超過(guò)5分鐘。8） 一開(kāi)始從 A13出發(fā)的車(chē)輛，與一開(kāi)始從A0出發(fā)的車(chē)輛不發(fā)生交替，兩循環(huán)獨(dú)立。9） 題目所給的數(shù)據(jù)具有一定的代表性，可以做為各種計(jì)算的依據(jù)。符號(hào)說(shuō)明Na：從總站A13始發(fā)出的公交車(chē)的總次數(shù)（上行方向）Nb:從總站A0始發(fā)出的公交車(chē)的總次數(shù)（下行方向）T1:上行方向早高峰發(fā)車(chē)間隔時(shí)間T2:上行方向平時(shí)發(fā)車(chē)間隔時(shí)間T3:上行方向晚高峰發(fā)車(chē)間隔時(shí)間T4：下行方向早高峰發(fā)車(chē)間隔時(shí)間T5：下行方向平時(shí)發(fā)車(chē)間隔時(shí)間T6:下行方向晚高峰發(fā)車(chē)間隔時(shí)間Ta（i,j）:第i輛車(chē)到達(dá)第j站的時(shí)刻N(yùn)1（i,j）:在j站離開(kāi)第i輛車(chē)的乘客數(shù)Ne（i，j）:在j站上第i輛車(chē)的乘客數(shù)D（j，j-1）:第j站與第（j-1）站間距f1（j）:上行方向第j站的上車(chē)乘客的密度函數(shù)g1（j）：上行方向第j站的下車(chē)乘客的密度函數(shù)f2（j）:下行方向第j站的上車(chē)乘客的密度函數(shù)g2（j）:下行方向第j站的下車(chē)乘客的密度函數(shù)G：一天內(nèi)公交公司的總收入A：公交車(chē)出車(chē)一次的支出，為定值B：公交公司每天的固定支出，為定值i: i=1,2,3，為一小概率事件的概率N（t）:某車(chē)站全天的上（下）車(chē)乘客數(shù)qt：第t時(shí)間段此站的上（下）車(chē)人數(shù)Q（i,j）:第i輛車(chē)到達(dá)第j站時(shí)的車(chē)上人數(shù)建模前的準(zhǔn)備:1） 對(duì)問(wèn)題的初步分析我們考慮三組相關(guān)的因素：公共汽車(chē)，汽車(chē)站與乘客對(duì)模型的影響。i） 與公共汽車(chē)有關(guān)的因素：離開(kāi)公共汽車(chē)總站的時(shí)間，到達(dá)每一站的時(shí)間，在每一站下車(chē)的乘客數(shù)，在每一站的停留時(shí)間，載客總數(shù)，行進(jìn)速度等。ii）與車(chē)站有關(guān)的因素： 線路上汽車(chē)的位置，車(chē)站間距， 乘客到來(lái)的函數(shù)表示，等車(chē)的乘客數(shù)，上一輛車(chē)離開(kāi)車(chē)站過(guò)去的時(shí)間等。iii）與乘客有關(guān)的因素：到達(dá)某一車(chē)站的時(shí)間，乘車(chē)距離（站數(shù)），侯車(chē)時(shí)間等。2） 曲線的擬合分析樣本數(shù)據(jù)，可知對(duì)于某車(chē)站全天的上（下）車(chē)乘客數(shù) N（t）是時(shí)間 t的遞增函數(shù)，N（t）=N（t-1）+qt,其中qt^第t時(shí)間內(nèi)此站的上（下）車(chē)人數(shù)，我們可以由此來(lái)擬合其分布函數(shù)。由樣本數(shù)據(jù)知每一車(chē)站每天有兩次波峰，故根據(jù)最小二乘法將分布函數(shù)擬合為關(guān)于t的五次多項(xiàng)式。分析與建模分析樣本數(shù)據(jù)， 在上行方向 22：00—23：00和下行方向 5:00—6：00上、下車(chē)人數(shù)較其它時(shí)段偏小，為使模型更好地體現(xiàn)普遍性，我們單獨(dú)討論上面的兩個(gè)時(shí)段。易知各站只需一輛車(chē)就可以滿足需求。由題設(shè)要求可知，所求方案須兼顧乘客和公交公司的利益，但實(shí)際上，不可能同時(shí)使雙方都達(dá)到最優(yōu)值。因此我們將公司利益作為目標(biāo)函數(shù)，將乘客利益作為約束條件。公司利益Z=G-（Na+Nb）*A-B（其中G為總收入，因樣本數(shù)據(jù)為典型工作日，因而可以看作定值，（Na+Nb）*A+B為支出。）4*607*602*605*60

NaNa=[ +T1T2T3+ ]T2kl7*60+3*60+4*604*60Nb二 T5 T4 匚 T6乘客的利益在此處即為侯車(chē)時(shí)間，由于乘客侯車(chē)時(shí)間帶有隨機(jī)性，不可能總小于(或大于)某個(gè)定值，因而可用概率來(lái)描述乘客的利益，得如下模型：I:maxZ=G-(Na+Nb)*A-Bs.t.P{等待時(shí)間 t>10分鐘的人}<1P{Q（iP{Q（i，j）+Ne（i，j）—N1（i，j）>120}<2P{Q（i，j）+Ne（i，j）—N1（ i，j）<50}<或P{等待時(shí)間t>5分鐘的人}<1P{Q（i，j）+Ne（i，j）—N1（ i，j）>120}<P{Q（i，j）+Ne（i，j）—N1（ i，j）<50}<模型的簡(jiǎn)化與求解：對(duì)于原模型，由于約束條件難以表示為明確的函數(shù)表達(dá)式，給實(shí)際求解過(guò)程中帶來(lái)相當(dāng)大的困難，因而對(duì)其簡(jiǎn)化。1)發(fā)生間距時(shí)間的求解分析原目標(biāo)值Z，易知maxZmaxT其中T為發(fā)車(chē)間距時(shí)間，它因不同的時(shí)間段而不同。下面我們就以每小時(shí)為一時(shí)間段來(lái)求解，且假設(shè)乘客上下車(chē)瞬間完成，即不考慮上下車(chē)時(shí)間。 應(yīng)題設(shè)要求， 乘客侯車(chē)時(shí)間一般不超過(guò) 10分鐘，早高峰時(shí)一般不超過(guò)5分鐘。我們引進(jìn)概率參數(shù)，用以控制侯車(chē)時(shí)間超過(guò)10分鐘(或5分鐘)的人數(shù)在總侯車(chē)人數(shù)的比重。對(duì)于滿載率不低于50%，由于目標(biāo)值為maxZ，則可以忽略不考慮，可得如下模型：II:maxT=tT(i1,j)10fi(j)dtstT(i,j)S.? T(i1,j)千i(j)dtT(i,j)T(i1,j)T(i1,j)Q(i,j)+fi(j)dt- gi(j)dt120T(i,j) T(i,j)T(i1,j)5fi(j)dtT（i,j）T(i1,j)f1i(j)T(i,j)T(i1,j) T(i1,j)Q(i,j)+fi(j)dt-gi(j)dt120T(i,j0 T(i,j)t>0,i=1,2分析樣本數(shù)據(jù)可以發(fā)現(xiàn)：對(duì)于上行車(chē)道，A13，A12，A11，A10，A9的上車(chē)人數(shù)〉下車(chē)人數(shù)，對(duì)于其余站點(diǎn)則相反；對(duì)于下行車(chē)道，A0, A2, A3,A4的上車(chē)人數(shù)〉下車(chē)人數(shù)，而其余站點(diǎn)則相反；因而對(duì)于約束條件，只需取前5個(gè)(或4個(gè))，對(duì)于模型II,我們可以根據(jù)擬合分布函數(shù)Fj,Gj將約束條件轉(zhuǎn)化為 T的函數(shù)，利用Matlab軟件容易求解。分析II所得結(jié)果，易知在高峰時(shí)間段中，結(jié)果T有較大誤差，是由于擬合函數(shù)的誤差而引起的。為了減小誤差，可以分段擬合分布函數(shù)Fi,Gio為計(jì)算方便，可以認(rèn)為在每小時(shí)內(nèi)，每站的到達(dá)人數(shù)與時(shí)間成正比，每站的下車(chē)人數(shù)亦與時(shí)間成正比，即 F,(t)=ki*t,Gi(t)=pi*t,ki,pi為斜率， 令=5%,于是將模型簡(jiǎn)化為：III：maxT=ts.t.19t-2000(或19t-1000)k1*t-1200k1*t+k2*t-p2*t-1200k1*t+k2*t-p2*t+k3*t-p3*t-1200k1*t+k2*t -p2*t+k 3*t-p3*t +k4*t- p4*t-120 0k1*t+k2*t -p2*t+k 3*t-p3*t +k4*t- p4*t+k5*t -p5*t -1200t>0

（平時(shí)及晚高峰取19t-2000,早高峰取19t-1000）當(dāng)上行時(shí)，取所有約束條件，下行時(shí)取前5個(gè)約束條件。模型川為線性規(guī)劃，利用Matlab求解，結(jié)果如下：發(fā)車(chē)間距時(shí)間表（單位皆為分鐘）910101111121213131491010111112121313145.49626.03525.31375.64796.92315.49626.03525.31375.64796.92316.2.6162.6..6747111116.2.6162.6..67471111110.5^ 3.27871.99342.97896.59959.2199.302310.52637.079.||、|||進(jìn)行誤差分析在上文中，我們已提及到模型II的誤差，究其原因主要是由于擬合函數(shù)的誤差引起的。如上行萬(wàn)向 A13站7：00—8：00，發(fā)車(chē)間距 T=5.26分，顯然此時(shí)的T無(wú)法使3626名乘客正常運(yùn)行，而此時(shí)由擬合函數(shù)算出來(lái)的乘客總數(shù)為2023。誤差△=3626-2023=1603（人）。為使誤差減小，因而可以對(duì)函數(shù)進(jìn)行分段擬合。如模型川中，以每小時(shí)為一段。此時(shí)求解的結(jié)果，能很好的使樣本數(shù)據(jù)的乘客正常運(yùn)行。當(dāng)然此時(shí)的解亦有誤差，因而T可有一波動(dòng)范圍。在此解的情況下，容易知道客車(chē)滿載率120%（約束條件）。乘客等待時(shí)間過(guò)長(zhǎng)的概率5%?？蛰d情形，大部分只有在最后一站方出現(xiàn)空載情形（滿載率50%）。2） 對(duì)無(wú)滯留乘客條件下的最小配車(chē)數(shù)初步求解我們對(duì)數(shù)據(jù)作進(jìn)一步的處理，估算出每一段上、下行所需的最小配車(chē)數(shù)，從而得出一天內(nèi)所需配備的最小車(chē)輛數(shù)。為最小配車(chē)數(shù)的求解找到一個(gè)參照值。我們首先考慮以一小時(shí)為時(shí)間間距來(lái)考查一天的最小配車(chē)數(shù)（即設(shè)公交車(chē)在各車(chē)站所停的時(shí)間為一定值）。分析數(shù)據(jù)可知滿足各站均無(wú)滯留乘客，各發(fā)車(chē)時(shí)刻均有車(chē)可發(fā)的最小配車(chē)數(shù)應(yīng)為65輛車(chē)。這只是一個(gè)初步解，為得到進(jìn)一步的精確解，我們考慮以44分為一時(shí)間間距，通過(guò)擬合的分布函數(shù)得到各車(chē)滿載時(shí)各時(shí)段的所需最小配車(chē)數(shù)。滿足各站無(wú)滯留乘客，各發(fā)車(chē)時(shí)刻均有車(chē)可發(fā)的最小配車(chē)數(shù)為43輛。3） 公交公司調(diào)度方案模型的建立與求解i）我們制訂調(diào)度方案，應(yīng)使公交公司和乘客雙方的利益達(dá)到均衡。一方面公交公司希望配置盡可能少的汽車(chē)以降低固定成本，又要在保證接送全部乘客的前提下盡可能減小出車(chē)次數(shù)，以降低可變成本；另一方面，應(yīng)實(shí)現(xiàn)乘客滿意，即規(guī)定發(fā)車(chē)時(shí)段必定有車(chē)可乘，盡可能縮短等車(chē)時(shí)間。ii）制訂調(diào)度方案時(shí)，我們發(fā)現(xiàn)有下難點(diǎn)：A） -方車(chē)站到了發(fā)車(chē)時(shí)間但沒(méi)有車(chē)可發(fā)，另一方面卻有囤積。此問(wèn)題有兩種解法：一是購(gòu)置新車(chē)，二是調(diào)節(jié)班次。前者使成本變高，后者引起連鎖反應(yīng)，使整個(gè)計(jì)算量變大且有可能求不出最優(yōu)解。B） 若迫不得已要改變總車(chē)配置數(shù)，必須調(diào)動(dòng)各個(gè)時(shí)間間隔使車(chē)優(yōu)化配EXT3直，全局最優(yōu)化。這是一個(gè)最優(yōu)問(wèn)題。C） 總配置數(shù)一定， 調(diào)節(jié)總車(chē)班次使總車(chē)次數(shù)增加越少，總車(chē)班次數(shù)越小，則求得的解越優(yōu)。這又是一個(gè)極值優(yōu)化問(wèn)題。為解決以上難點(diǎn)， 我們建立了一個(gè)線性規(guī)劃模型， 用Maple優(yōu)化軟件求解。設(shè)某j時(shí)間段發(fā)車(chē)數(shù)為,車(chē)站內(nèi)車(chē)輛總數(shù)為設(shè)某j時(shí)間段發(fā)車(chē)數(shù)為,車(chē)站內(nèi)車(chē)輛總數(shù)為Cijm為總配置數(shù)，z為總班次181minz=X..ijj1j0s.七C0+Ci=mX11=q-XuX01=C0-X01m1X1mm1X1mX1j=C1+X0mm1TOC\o"1-5"\h\zj1 jX0j=C0+X1m-X0m0m1 m118 18X0m二^m1 m11)60分一120人調(diào)度方案模型若考慮到各站點(diǎn)乘客上下車(chē)時(shí)間相等，總行程總需耗時(shí)60分，每輛車(chē)都載120人。在初步解的模型中，配置最小車(chē)輛為 60，用Maple軟件包開(kāi)始搜索優(yōu)化選擇，j=2，3 18。搜索出整體最優(yōu)解為：C0=62，C1=4，m=66，z=476。2)44分一120人調(diào)度方案模型考慮乘客上下車(chē)瞬間完成， 公交車(chē)駛完全程需44分。每輛車(chē)均載 120人，此模型中步長(zhǎng)為 44分鐘，所考慮時(shí)段的乘客數(shù)均由擬合函數(shù)給出， 初始值為4輛，由Maple軟件包優(yōu)化選擇，得到：C0=42，C1=6，m=48，z=590。模型的推廣與改進(jìn)在設(shè)計(jì)公交車(chē)調(diào)度方案時(shí)，并未充分考慮乘客利益，在進(jìn)行改進(jìn)時(shí)，可以試著想其它辦法找到一些更好的規(guī)則來(lái)進(jìn)行對(duì)比與評(píng)價(jià)，從而得到更加優(yōu)化的方案，使雙方利益達(dá)到充分均衡，這是模型改進(jìn)的方向。另外，模型求得的數(shù)據(jù)相對(duì)問(wèn)題的關(guān)鍵是所給的數(shù)據(jù)太少，所得到的調(diào)度方案穩(wěn)定性很差，靈敏度較高，可以試著找其它方法解決，從而求解。我們建立了一個(gè)調(diào)度方案的一般模型，并提出了一個(gè)較普遍與實(shí)用的方法，故此模型可用于現(xiàn)實(shí)生活中其它運(yùn)輸業(yè)的調(diào)配，類(lèi)似交通運(yùn)輸之類(lèi)的調(diào)配問(wèn)題，從而達(dá)到資源的優(yōu)化配置。模型的自我評(píng)價(jià)：我們通過(guò)一些合理的假設(shè)，針對(duì)公交車(chē)調(diào)度問(wèn)題建立了一般模型。先對(duì)模型進(jìn)行了簡(jiǎn)化，采用由簡(jiǎn)單到復(fù)雜，逐步深入的方法，充分利用Maple優(yōu)化軟件包進(jìn)行搜索，優(yōu)化求解，從而得到一個(gè)整體最優(yōu)解。在求解（2）小題時(shí)，提出一個(gè)方法，即每次都從每段時(shí)間的起點(diǎn)均有車(chē)發(fā)出，到最后一班車(chē)持續(xù)等時(shí)段發(fā)出，最后剩余小段時(shí)間丟去不予考慮。列出了不同時(shí)段的公交車(chē)調(diào)度時(shí)刻表。同時(shí)引入概率來(lái)刻劃顧客利益，從而可以使抽象概念定性分析定量化，也是本模型的一大優(yōu)點(diǎn)。但本題中因只給了某一個(gè)工作日的數(shù)據(jù)樣本，具有典型性，得出的結(jié)果在長(zhǎng)時(shí)間內(nèi)可行性較差，其次設(shè)計(jì)調(diào)度方案時(shí)著重考慮公司利益與大部分顧客利益，使雙方利益趨于均衡，并未同時(shí)達(dá)到雙方滿意，這是我們模型的缺點(diǎn)所在。參考文獻(xiàn):［1］姜啟源數(shù)學(xué)模型［M］北京：高等教育出版社［2］ 葉其孝大學(xué)生數(shù)學(xué)建模競(jìng)賽輔導(dǎo)教材［M］長(zhǎng)沙：湖南教育出版社［3］ 王淥然與科學(xué)計(jì)算［M］北京：清華大學(xué)出版社［4］ 費(fèi)培之，程中瑗數(shù)學(xué)模型實(shí)用教程［M］成都：四川大學(xué)出版社附錄：表格1上行方向前五站各時(shí)段上車(chē)人數(shù)站危危名312111095:00-6:00371605243766:00-199373325587:00063697:00-362635244948:00648788:009:00206