公交車調(diào)度問題

1、 關(guān)于公交車的調(diào)度問題摘 要：本文主要是研究公交車調(diào)度的最優(yōu)策略問題。我們建立了一個以公交車的利益為目標(biāo)函數(shù)的優(yōu)化模型，同時保證等車時間超過10分鐘或者超過5分鐘的乘客人數(shù)在總的等車乘客數(shù)所占的比重小于一個事先給定的較小值。首先，利用最小二乘法擬合出各站上下車人數(shù)的非參數(shù)分布函數(shù)，求解時先用一種簡單方法估算出最小配車數(shù)43 輛。然后依此為參照值，利用Maple優(yōu)化工具得到一個整體最優(yōu)解：最小配車數(shù)為 48 輛，并給出了在公交車載客量不同條件下的最優(yōu)車輛調(diào)度方案，使得公司的收益得到最大，并且乘客等車的時間不宜過長，最后對整個模型進(jìn)行了推廣和評價，指出了有效改良方向。關(guān)鍵詞：公交車調(diào)度；優(yōu)化模型；

2、最小二乘法問題的重述：公共交通是城市交通的重要組成局部，作好公交車的調(diào)度對于完善城市交通環(huán)境、改良市民出行狀況、提高公交公司的經(jīng)濟(jì)和社會效益，都具有重要意義。下面考慮一條公交線路上公交車的調(diào)度問題，其數(shù)據(jù)來自我國一座特大城市某條公交線路的客流調(diào)查和運營資料。該條公交線路上行方向共14站，下行方向共13站，第3-4頁給出的是典型的一個工作日兩個運行方向各站上下車的乘客數(shù)量統(tǒng)計。公交公司配給該線路同一型號的大客車，每輛標(biāo)準(zhǔn)載客100 人，據(jù)統(tǒng)計客車在該線路上運行的平均速度為20公里/小時。運營調(diào)度要求，乘客候車時間一般不要超過10分鐘，早頂峰時一般不要超過5分鐘，車輛滿載率不應(yīng)超過 120%，一般

3、也不要低于50%。試根據(jù)這些資料和要求，為該線路設(shè)計一個便于操作的全天工作日的公交車調(diào)度方案，包括兩個起點站的發(fā)車時刻表；一共需要多少輛車；這個方案以怎樣的程度照顧到了乘客和公交公司雙方的利益；等等。如何將這個調(diào)度問題抽象成一個明確、完整的數(shù)學(xué)模型，指出求解模型的方法；根據(jù)實際問題的要求，如果要設(shè)計更好的調(diào)度方案，應(yīng)如何采集運營數(shù)據(jù)。 根本假設(shè)1 該公交路線不存在堵塞現(xiàn)象，且公共汽車之間依次行進(jìn)，不存在超車現(xiàn)象。2 公共汽車滿載后，乘客不能再上，只得等待下一輛車的到來。3 上行、下行方向的頭班車同時從起始站出發(fā)。4 該公交路線上行方向共 14站，下行方向共 13站。5 公交車均為同一型號，每輛

4、標(biāo)準(zhǔn)載客 100名，車輛滿載率不應(yīng)超過 120%，一般也不要低于 50%。6 客車在該路線上運行的平均速度為 20公里/小時，不考慮乘客上下車時間。7 乘客侯車時間一般不超過 10分鐘，早頂峰時一般不超過 5分鐘。8 一開始從A出發(fā)的車輛，與一開始從 A出發(fā)的車輛不發(fā)生交替，兩循環(huán)獨立。9) 題目所給的數(shù)據(jù)具有一定的代表性,可以做為各種計算的依據(jù)。 符號說明N：從總站A 始發(fā)出的公交車的總次數(shù)上行方向N：從總站A 始發(fā)出的公交車的總次數(shù)下行方向T：上行方向早頂峰發(fā)車間隔時間T：上行方向平時發(fā)車間隔時間T：上行方向晚頂峰發(fā)車間隔時間T：下行方向早頂峰發(fā)車間隔時間T：下行方向平時發(fā)車間隔時間T：下

5、行方向晚頂峰發(fā)車間隔時間Ti，j：第i 輛車到達(dá)第j 站的時刻Ni ，j：在 j站離開第 i輛車的乘客數(shù)Ni ，j：在 j站上第i 輛車的乘客數(shù)D j，j-1 ：第j 站與第j-1 站間距fj ：上行方向第j 站的上車乘客的密度函數(shù)g j：上行方向第 j站的下車乘客的密度函數(shù)f j：下行方向第 j站的上車乘客的密度函數(shù)g j：下行方向第j 站的下車乘客的密度函數(shù)G：一天內(nèi)公交公司的總收入A：公交車出車一次的支出，為定值B：公交公司每天的固定支出，為定值：i=1,2,3,為一小概率事件的概率Nt ：某車站全天的上下車乘客數(shù)q：第t 時間段此站的上下車人數(shù)Qi ，j：第i 輛車到達(dá)第 j站時的車上

6、人數(shù)建模前的準(zhǔn)備：1 對問題的初步分析我們考慮三組相關(guān)的因素：公共汽車，汽車站與乘客對模型的影響。 與公共汽車有關(guān)的因素：離開公共汽車總站的時間，到達(dá)每一站的時間，在每一站下車的乘客數(shù)，在每一站的停留時間，載客總數(shù)，行進(jìn)速度等。 與車站有關(guān)的因素：線路上汽車的位置，車站間距，乘客到來的函數(shù)表示，等車的乘客數(shù)，上一輛車離開車站過去的時間等。 與乘客有關(guān)的因素：到達(dá)某一車站的時間，乘車距離站數(shù)，侯車時間等。2 曲線的擬合分析樣本數(shù)據(jù)，可知對于某車站全天的上下車乘客數(shù) Nt 是時間t 的遞增函數(shù)，Nt =Nt-1+ q，其中q 為第t 時間內(nèi)此站的上下車人數(shù)，我們可以由此來擬合其分布函數(shù)。由樣本數(shù)據(jù)

7、知每一車站每天有兩次波峰，故根據(jù)最小二乘法將分布函數(shù)擬合為關(guān)于t的五次多項式。分析與建模分析樣本數(shù)據(jù)，在上行方向 22：00 23：00 和下行方向5 ：00 6：00 的上、下車人數(shù)較其它時段偏小，為使模型更好地表達(dá)普遍性，我們單獨討論上面的兩個時段。易知各站只需一輛車就可以滿足需求。由題設(shè)要求可知，所求方案須兼顧乘客和公交公司的利益，但實際上，不可能同時使雙方都到達(dá)最優(yōu)值。因此我們將公司利益作為目標(biāo)函數(shù)，將乘客利益作為約束條件。公司利益Z=G-( N+N)*A-B其中G為總收入，因樣本數(shù)據(jù)為典型工作日，因而可以看作定值，( N+N)*A+B 為支出。 N=+ N=+乘客的利益在此處即為侯車

8、時間，由于乘客侯車時間帶有隨機(jī)性，不可能總小于或大于某個定值，因而可用概率來描述乘客的利益，得如下模型： I：maxZ= G-( N+N)*A-B s.t. P等待時間t>10分鐘的人< P Qi ，j+ Ni ，j Ni ，j>120<P Qi ，j+ Ni ，j Ni ，j<50<或 P等待時間t>5分鐘的人< P Qi ，j+ Ni ，j Ni ，j>120<P Qi ，j+ Ni ，j Ni ，j<50<模型的簡化與求解：對于原模型，由于約束條件難以表示為明確的函數(shù)表達(dá)式，給實際求解過程中帶來相當(dāng)大的困難，因而對其

9、簡化。1 發(fā)生間距時間的求解分析原目標(biāo)值 Z，易知maxZ ómaxT其中T 為發(fā)車間距時間，它因不同的時間段而不同。下面我們就以每小時為一時間段來求解，且假設(shè)乘客上下車瞬間完成，即不考慮上下車時間。應(yīng)題設(shè)要求，乘客侯車時間一般不超過 10分鐘，早頂峰時一般不超過5 分鐘。我們引進(jìn)概率參數(shù)，用以控制侯車時間超過10分鐘或5分鐘的人數(shù)在總侯車人數(shù)的比重。對于滿載率不低于50% ，由于目標(biāo)值為maxZ ，那么可以忽略不考慮，可得如下模型：: maxT=ts.t. Q(i,j)+ -120或Q(i,j)+ -120t>0, i=1,2分析樣本數(shù)據(jù)可以發(fā)現(xiàn)： 對于上行車道，A，A，A，

10、A，A的上車人數(shù)>下車人數(shù)，對于其余站點那么相反； 對于下行車道，A，A，A，A的上車人數(shù)>下車人數(shù)，而其余站點那么相反；因而對于約束條件，只需取前5個或4個，對于模型，我們可以根據(jù)擬合分布函數(shù)F，G將約束條件轉(zhuǎn)化為T的函數(shù)，利用Matlab軟件容易求解。分析所得結(jié)果，易知在頂峰時間段中，結(jié)果T有較大誤差，是由于擬合函數(shù)的誤差而引起的。為了減小誤差，可以分段擬合分布函數(shù)F，G 。為計算方便，可以認(rèn)為在每小時內(nèi)，每站的到達(dá)人數(shù)與時間成正比，每站的下車人數(shù)亦與時間成正比，即Ft=k*t ，Gt=p*t, k, p為斜率，令=5% ，于是將模型簡化為：maxT=ts.t. 19t-200

11、0(或19t-1000) k*t-1200 k*t+ k*t - p*t- 1200 k*t+ k*t - p*t + k*t - p*t -1200 k*t+ k*t - p*t + k*t - p*t +k*t - p*t -1200 k*t+ k*t - p*t + k*t - p*t +k*t - p*t+ k*t - p*t -1200 t>0 平時及晚頂峰取19t-2000，早頂峰取19t-1000當(dāng)上行時，取所有約束條件，下行時取前5個約束條件。模型為線性規(guī)劃，利用Matlab求解，結(jié)果如下：發(fā)車間距時間表單位皆為分鐘時段56677889910101111121213131

12、4上行10.522.451.4342.8485.49626.03525.31375.64796.9231下行/6.9292.6162.23393.9516.58747.30228.67478.08時段141515161617171818191920202121222223上行8.17258.26643.37552.59748.026810.52610.52610.526/下行7.0795.533.27871.99342.97896.59959.2199.302310.5263對模型、進(jìn)行誤差分析在上文中，我們已提及到模型的誤差，究其原因主要是由于擬合函數(shù)的誤差引起的。如上行方向A站7：008：

13、00 ，發(fā)車間距T=5.26分，顯然此時的T無法使3626名乘客正常運行，而此時由擬合函數(shù)算出來的乘客總數(shù)為2023。誤差=3626-2023=1603(人。為使誤差減小，因而可以對函數(shù)進(jìn)行分段擬合。如模型中，以每小時為一段。此時求解的結(jié)果，能很好的使樣本數(shù)據(jù)的乘客正常運行。當(dāng)然此時的解亦有誤差 ，因而T可有一波動范圍。在此解的情況下，容易知道客車滿載率120%約束條件。乘客等待時間過長的概率5%。空載情形，大局部只有在最后一站方出現(xiàn)空載情形滿載率50% 。2 對無滯留乘客條件下的最小配車數(shù)初步求解我們對數(shù)據(jù)作進(jìn)一步的處理，估算出每一段上、下行所需的最小配車數(shù)，從而得出一天內(nèi)所需配備的最小車輛

14、數(shù)。為最小配車數(shù)的求解找到一個參照值。我們首先考慮以一小時為時間間距來考查一天的最小配車數(shù)即設(shè)公交車在各車站所停的時間為一定值。分析數(shù)據(jù)可知滿足各站均無滯留乘客，各發(fā)車時刻均有車可發(fā)的最小配車數(shù)應(yīng)為65輛車。這只是一個初步解，為得到進(jìn)一步的精確解，我們考慮以44分為一時間間距，通過擬合的分布函數(shù)得到各車滿載時各時段的所需最小配車數(shù)。滿足各站無滯留乘客，各發(fā)車時刻均有車可發(fā)的最小配車數(shù)為43輛。3 公交公司調(diào)度方案模型的建立與求解 我們制訂調(diào)度方案，應(yīng)使公交公司和乘客雙方的利益到達(dá)均衡。一方面公交公司希望配置盡可能少的汽車以降低固定本錢，又要在保證接送全部乘客的前提下盡可能減小出車次數(shù)，以降低可

15、變本錢；另一方面，應(yīng)實現(xiàn)乘客滿意，即規(guī)定發(fā)車時段必定有車可乘，盡可能縮短等車時間。)制訂調(diào)度方案時，我們發(fā)現(xiàn)有下難點：A一方車站到了發(fā)車時間但沒有車可發(fā)，另一方面卻有囤積。此問題有兩種解法：一是購置新車，二是調(diào)節(jié)班次。前者使本錢變高，后者引起連鎖反響，使整個計算量變大且有可能求不出最優(yōu)解。B 假設(shè)迫不得已要改變總車配置數(shù)，必須調(diào)動各個時間間隔使車優(yōu)化配置，全局最優(yōu)化。這是一個最優(yōu)問題。C 總配置數(shù)一定，調(diào)節(jié)總車班次使總車次數(shù)增加越少，總車班次數(shù)越小，那么求得的解越優(yōu)。這又是一個極值優(yōu)化問題。為解決以上難點，我們建立了一個線性規(guī)劃模型，用Maple優(yōu)化軟件求解。設(shè)某j時間段發(fā)車數(shù)為X，車站內(nèi)車輛

16、總數(shù)為C。i= m為總配置數(shù)， z為總班次min z=s.t. C+C=m X=C- X0 X=C- X0 X= C+-0 X= C+-0=1 60分120人調(diào)度方案模型假設(shè)考慮到各站點乘客上下車時間相等，總行程總需耗時60分，每輛車都載120人。在初步解的模型中，配置最小車輛為60，用Maple軟件包開始搜索優(yōu)化選擇，j=2，318。搜索出整體最優(yōu)解為：C=62，C=4，m=66，z=476。244分 120人調(diào)度方案模型考慮乘客上下車瞬間完成，公交車駛完全程需44分。每輛車均載120人，此模型中步長為44分鐘，所考慮時段的乘客數(shù)均由擬合函數(shù)給出，初始值為43輛，由Maple軟件包優(yōu)化選擇，

17、得到：C=42，C=6，m=48，z=590。模型的推廣與改良在設(shè)計公交車調(diào)度方案時，并未充分考慮乘客利益，在進(jìn)行改良時，可以試著想其它方法找到一些更好的規(guī)那么來進(jìn)行比照與評價，從而得到更加優(yōu)化的方案，使雙方利益到達(dá)充分均衡，這是模型改良的方向。另外，模型求得的數(shù)據(jù)相對精確度較高，在現(xiàn)實生活中不太實用。問題的關(guān)鍵是所給的數(shù)據(jù)太少，所得到的調(diào)度方案穩(wěn)定性很差，靈敏度較高，可以試著找其它方法解決，從而求解。我們建立了一個調(diào)度方案的一般模型，并提出了一個較普遍與實用的方法，故此模型可用于現(xiàn)實生活中其它運輸業(yè)的調(diào)配，類似交通運輸之類的調(diào)配問題，從而到達(dá)資源的優(yōu)化配置。模型的自我評價：我們通過一些合理的

18、假設(shè)，針對公交車調(diào)度問題建立了一般模型。先對模型進(jìn)行了簡化，采用由簡單到復(fù)雜，逐步深入的方法，充分利用Maple優(yōu)化軟件包進(jìn)行搜索，優(yōu)化求解，從而得到一個整體最優(yōu)解。在求解2小題時，提出一個方法，即每次都從每段時間的起點均有車發(fā)出，到最后一班車持續(xù)等時段發(fā)出，最后剩余小段時間丟去不予考慮。列出了不同時段的公交車調(diào)度時刻表。同時引入概率來刻劃顧客利益，從而可以使抽象概念定性分析定量化，也是本模型的一大優(yōu)點。但此題中因只給了某一個工作日的數(shù)據(jù)樣本，具有典型性，得出的結(jié)果在長時間內(nèi)可行性較差，其次設(shè)計調(diào)度方案時著重考慮公司利益與大局部顧客利益，使雙方利益趨于均衡，并未同時到達(dá)雙方滿意，這是我們模型的缺點所在。參考文獻(xiàn)：1 姜啟源 數(shù)學(xué)模型M北京：高等教育出版社2 葉其孝 大學(xué)生數(shù)學(xué)建模競賽輔導(dǎo)教材M長沙：湖南教育出版社3 王淥然 與科學(xué)計算M北京：清華大學(xué)出版社4 費培之，程中瑗 數(shù)學(xué)模型實用教程M成都：四川大學(xué)出版社附錄 :表格 1 上行方向前五站各時段上車人數(shù)站名A13A12A11A10A95:00-6:00371605243766:00-7:001990376333