公交公司車輛調度設計

1、公交公司車輛調度方案設計2001 年全國大學生數學建模競賽2001 年全國大學生數學建模競賽公交公司車輛調度方案設計參賽隊員：林大海徐文溢賴清文指導老師：江西財經大學建模指導組江西財經大學信息管理學院，江西南昌，330013共10頁第1頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽公交公司車輛調度方案設計【摘要】 公共交通本文根據經驗和所提供的數據的變化規(guī)律，利用三次樣條插值的方法求出了每個車站上下車的流量函數f j(t ) 和 g j (t) ，進而求出描述每個車站的客流量變化的客流密度函數 p j (t) 和 q j (t ) ，根據客流密度函數可以求出任一時間段的候車人數。

2、模型一是一個很直觀的結果，只要逐個滿足各個車站乘客的要求，即從起點站開始只要候車人數超過 120 人或距上次發(fā)車時間超過10 分鐘就發(fā)車，后面的站點若出現有乘客滯留則向起點站要求追加車輛（在現實中則是提前追加），直至所有的乘客被運走。應用模型一，求出了該條線路上共需車輛62 輛，其中上行方向始發(fā)站初始停放57 輛，下行方向始發(fā)站初始停放 5 輛，每天上行方向共需發(fā)車233 次，下行方向共需發(fā)車226 次，顧客不滿意度為：8.21314104 ,公交公司的不滿意度為：62.0459104為了模擬車站、汽車和乘客在整個過程中的動態(tài)過程，建立了模型二，模型二給出了4 個很重要的函數cij ， g j

3、 (tit j ) ， Sj (i ) ， dij ，對這個模型的求解可得到整條線路的調度過程， 同時，該模型不僅可以用來確定發(fā)車的時間和間隔，而且可以用來檢驗一個新的調度方案是否合理。 模型二具有一定的實際意義。另外模型二也給出了求該條線路上需要的汽車數量任務， 將模型二應用于原問題， 得到從任一時刻發(fā)車后的公交公司共需車輛57 輛，上行始發(fā)站初始停48 輛，下行始發(fā)站初始停放9 輛，每天上行和下行均需發(fā)車238 次，模顧客不滿意度為：1.5222 10 4,公交公司的不滿意度為：57.0476 104 附錄 1給出了由模型二制作的發(fā)車時刻表。 只是這張發(fā)車時刻表的時間間隔很不均勻， 既不適

4、合公交公司調度，也不利于乘客搭車， 為了便于實際應用， 對這張時刻表進行了改進， 并經過了模型二的檢驗。改進后的發(fā)車時刻表只要 54 輛甚至更少的車就可以滿足運行要求，并且它的時間也比較有規(guī)律，對調度人員和乘客來說都比較容易掌握，且顧客不滿意度為：8.8648104 ,公交公司的滿意度為：5.405710 4 ，可見公交公司的滿意度提高了。【關鍵詞】 流量，客流密度，三次樣條插值，調度，滿意度共10頁第2頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽公交公司車輛調度方案設計問題的提出優(yōu)先發(fā)展公共交通的交通政策是解決城市交通問題的根本途徑，不論是在我國或者是在外國都是如此。公共交通

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

6、的資料和要求，為該線路設計一個便于操作的全天（工作日） 的公交車調度方案，包括兩個起點站的發(fā)車時刻表；一共需要多少輛車；以使這個方案更大程度上程度照顧到了顧客和公交公司雙方的利益。問題的分析問題相關因素分析：1、與公共汽車有關的因素離開公共汽車總站的時間、到達每一汽車站的時間、在每一汽車站下車的乘客數、在每一汽車站停留的時間、載客總數、最大容量、行進速度、交通條件；2、 與乘客有關的因素到達某一車站的時間、乘車距離（站數）、等車的時間、總的旅行時間；3、 與車站有關的因素線路上汽車站的位置、從上一輛車離開車站后過去的時間、乘客到來的頻率、下一輛車到來時正在等車的乘客數、車站之間的距離。數據的規(guī)

7、律分析與處理：從問題給定的數據中我們可以看出1、 早 500 600 和晚上22 00 23 00乘客較少， 在要求不是很嚴格的情況下， 可以放在一起考慮， 但如果單獨考慮效果可能更佳。2、 早 600 900 和下午16 00 1800正處于上、 下班的時間， 屬客流的高峰期，在這段時間內的發(fā)車密度相對較高，以保證乘客在較快的時間內乘車到達目的地。3、 就下行方向來說在站點 A0 上車的人最多，其次是站點 A6 和站點 A3 ；在站點 A13 下車的人最多，其次是站點 A5 、站點 A6 和站點 A7 。共10頁第1頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽4、 就上行方向

8、來說在站點 A13 上車的人最多，其次是站點A9 、站點 A8 、站點 A6 和站點 A5 ；在站點 A1 下車的人最多，其次是站點A6 、站點 A0 、站點 A8 和站點 A7 。另外，由于題中所給數據均是在一個時組內上下車總人數，而在一個時組內需要發(fā)幾輛車，所以必須將已知數據離散化。分析上行方向起點站A13 在各時段的數據，發(fā)現在：上車的人數呈先遞增后遞減的趨勢，如在7： 00 8： 00 之間共有人上車，而在6 00 7 00之間共有1990 人上車，根據在這段時間內上車人數遞增的趨勢，這些人多數會在后段時間上車，而只有少數在前段時間到達；又如在8 00 9 00 之間的人多數人會在前段

9、時間上車 也就是說相鄰三段時組的客流是相互聯(lián)系、相互影響的。 分析其他時段以及其余車站的情形也是如此。因此，使用已知數據分別進行三次樣條插值可得到上行、下行方向上車和下車的人數各站點隨時間t 的變化函數，對其求導后可得客流密度，而在本題中我們采用三次樣條插值的方法來獲得乘客上車數據。顧客的滿意度：作為顧客，他們所關心的主要是兩個方面的問題：等待時間和所乘汽車的擁擠度.如果我們能保證顧客在十分鐘內能搭上車（早高峰時5 分鐘內能搭上車） ，顧客一般比較滿意，但如果要等的車來了，卻搭不上則會使顧客很不滿意。公交公司的滿意度：作為公交公司由于顧客的總量一般不會發(fā)生變化，即收益不會發(fā)生變化，所以其所追求

10、的是發(fā)出車次及使用車輛數的極小化（但必須保證將所有的顧客運送至目的地），即成本的極小化。模型的假設我們作如下假設：1、不存在交通堵塞；2、大客車按勻速 20 公里 /小時行駛，乘客上下車的時間以及大客車在各個站上的停留時間忽略不計；3、大客車到終點站后的調頭時間忽略不計，司機和售票員的換班時間也忽略不計；4、客流量是連續(xù)變化的，并且客流量的變化率也連續(xù)變化；由于在該線路上的客流量相當大，每天的客流量達到十萬余人，因此可以認為在相鄰的單位時間內到達車站的人數應該近似于連續(xù)變化，這是合理的。5、顧客一般會按先來后到上車。6、乘客不會因為等待時間過長而改乘其它交通工具（例如出租汽車等）；7、表中數據

11、的上車人數為到站人數（由于不改乘其他交通工具，因此上車人數就是到站人數，）。8、每車次的費用相同，與乘客的數量無關；9、為便于操作，發(fā)車的時間間隔為整分鐘。即不會安排在類似于6時 12分 24秒的時間發(fā)車；10、所給的數據能近似代表一般情形；11、在線路的兩端都設有停車場，且容量足夠使用；12、候車時間在早高峰時不超過5 分鐘，其他時刻不超過10 分鐘時認為顧客滿意。共10頁第2頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽客流密度： 在較短的單位時間內（如1 分鐘內）上車（到站）或下車的人數；流量： 指從初始時刻到某時刻的上車（到站）或下車的乘客的累積人數。符號說明a, b ：

12、公交車的頭班車和末班車發(fā)車時間：大客車的限制載客量；t j ：表示從起點站至第j 站大客車運行的時間，t10 ；：采集的樣本容量；：單條線路上的車站數量；aij：表示第 j站第 i時段上車乘客的人數；bij：表示第 j站第 i時段下車乘客的人數；xij：表示第 j站第 1 至第 i 時段上車乘客的流量；yij ：表示第 j站第 1 至第 i 時段下車乘客的流量；f j (t) ：表示第j 站 t 時刻上車乘客的流量；g j (t) ：表示第j 站 t時刻下車乘客的流量；f j (ti )f j (ti )f j (ti 1 ) ：表示時刻 ti 1至 ti 第 j 站新增加的乘客人數；g j

13、(t i )g j (ti) g j (t i 1 ) ：表示時刻 t i 1至t i第 j 站的下車人數；cij ：表示第 i 次發(fā)出的車在?？康趈 個車站時第j 站正在候車的人數，這批乘客應盡量乘坐該次車；dij ：表示第 i 次發(fā)出的車在離開第j 個車站時該車站尚未上車的人數；S j (i) ：表示第 i次發(fā)出的車在離開第j 個車站后車上的乘客數；p j (t )q j (t)：表示第j 站 t 時刻上車乘客的客流密度；：表示第j 站 t 時刻下車乘客的客流密度；模型的建立和求解從初始時刻至i 時段在第j 個車站上車的累積人數為共10頁第3頁公交公司車輛調度方案設計2001 年全國大學生

14、數學建模競賽ixijakji 1,2, , m ， j 1,2, , n -（ 1）k 1從初始時刻至t j 時段在第 i 個車站下車的累積人數為iyijbkji 1,2, m ， j 1,2, , n - （ 2）k 1在問題的分析中我們已經知道，乘客上車或下車的流量變化可近似看作是連續(xù)變化的，并 且 乘 客 的 客 流 密 度 也 可 以 近 似 看 作 是 連 續(xù) 變 化 的 ， 因 此 如 果 分 別 作 xij， yij（ i1,2, , m ）的三次樣條插值，可得第j 個車站在任意時刻 t 的上車流量函數 fj (t ) 和下車流量函數g j (t ) ，并且相應的客流密度函數分別

15、為p j (t )f j(t )j1,2, n-（ 3）q j (t)g j (t)j1,2, n- （ 4）以上結果使用于任意個車站和任意采集數據的情形。用 MA TLAB軟件可以得到上行方向和下行方向各車站上下車的流量和客流密度的數值解，本文取步長為1 分鐘，圖（ 1）和圖（ 2）分別上行方向起點站A13上車的流量和客流密度曲線。x 104上上7021.8601.6501.41.2401300.8200.6100.40.200681012141618202224-1068101214161820222444圖（ 1） 上行方向起點站 A13 的上車流量圖（ 2） 上行方向起點站A13 的上

16、車客流密度模型一 （即時需求法）即時需求法的意思是哪個站點的候車人數達到指定的上限即有車準時到達，故稱為即時需求法。假定問題給出的各時段上車人數近似為相應時段到達車站的人數，為了使乘客盡快上車，假設發(fā)車條件為：（ 1）只要始發(fā)站的候車乘客數累積達到120 人即發(fā)車；（ 2）只要某車站的候車乘客數累積達到120 人即增發(fā)一輛空車到該站；（ 3）或者距離上次發(fā)車時間達到10分鐘；共10頁第4頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽（ 4）5 時整和 23 時整發(fā)首班車和末班車。求出需要多少車次才能運走始發(fā)站的乘客及相應的發(fā)車時間。然后在此基礎上，求出需要追加多少車次才能運走后面

17、車站的乘客及相應的發(fā)車時間。如此反復， 直到求出最后一站所需追加的車次及相應的發(fā)車時間。為了求解的簡便， 假定在各整點時間之間到達車站的人數為問題所給定的相應時段的上車人數。 給出數據時假定了上車人數為到達車站的人數， 求出需要多少車次才能運走始發(fā)站的乘客及相應的發(fā)車時間。 然后在此基礎上， 求出需要追加多少車次才能運走后面車站的乘客及相應的發(fā)車時間。如此反復，直到求出最后一站所需追加的車次及相應的發(fā)車時間。模型設計及求解步驟為：1、首先考慮始發(fā)站點 A13 ，按照時間順序，當站點 A13 的累計候車人數達到 120 人，或發(fā)車時間間隔達到 10 分鐘時，發(fā)出一輛公交車。根據乘客到達車站的時間

18、可以求出發(fā)車時間。2、對于站點A12 ，由于站點A13 發(fā)出的車基本上是滿載（客流量較少時例外），而在A12 下車的乘客留出的空位很難滿足A12 要上車乘客的需求，因此可以求出當A12 的候車累積人數到達120 人的時間，以便提前從A13 向 A12 直接發(fā)出空車運送A12 的乘客，以使A12 的乘客候車時間不要太長。3、依此類推，求出增發(fā)至A11 至 A1 各站的發(fā)車時間，并按此方案設計出全天的公交車調度方案。利用 MATLAB軟件編寫求解模型一的程序，部分結果如下（程序參見附錄）：全天共需發(fā)車總次數為 459 次，其中上行方向由 A13 發(fā)出 233 次，下行方向由 A0 發(fā)出 226 次

19、；上行方向發(fā)出的233 車次中，有51 車次需要直接加發(fā)至其他站點，有191 車次是嚴重滿載，發(fā)車時即為120 人；下行方向發(fā)出的226 車次中，有31 車次需要直接加發(fā)至其他站點，有196 車次是嚴重滿載，發(fā)車時即為120 人；為了保證模型一設計出的調度方案能順利實行，全線路至少需要62 輛大客車，其中在站點 A13 處停放 57 輛，在站點A0 處停放 5 輛。模型二模型一的結果中出現了大量的設第 i 次發(fā)車的時間為ti ，根據符號系統(tǒng)的定義不難得到第 j 站要求上第 i 次車的乘客數cijd( i 1) jf j (t it j )d (i 1) jf j (t it j )f j (t

20、i 1t j ) - （ 5）第 j 站要求下第 i 次車的乘客數g j (tit j )g j (t it j )g j (ti 1t j )-(6)第 i 次車?？康趈 站經過下車后的車上剩余乘客數Sj 1 (i )g j (tit j )第 i 次車停靠第j 站經過上下車后的車上乘客數共10頁第5頁公交公司車輛調度方案設計2001 年全國大學生數學建模競賽MSj 1 (i )g j (tit j ) cijMSj (i)Sj1(i )g j (tit j ) cij0S j1 (i )g j (tit j ) cijM-(7)cijSj 1 (i)g j (t it j )cij0第 i

21、次車離開第 j站時第 j 站尚未上車的人數0dijcij Sj (i) Sj 1 (i )g j (tit j )-(8)i1,2, j1,2, n ,并且規(guī)定 d0 j0, f j(t0t j )0, S0 (i )0, g j(t0t j ) 0 .(5)(8) 式描述了動態(tài)的車站及車上的乘客數量的變化。只要知道有了車輛的調度表，那么每輛車的運行狀態(tài)便可知。我們用單位時間推移搜索法求解該模型設 Tk 為第 k 次發(fā)車的時間，顯然T1a （頭班車），如果確定一個可操作的最小時間間隔為 h ，假設下一次發(fā)車時間為T2T1 h ，如果存在一個站點1 jn ，使 得Sj (2) M ，即保證第2

22、次發(fā)出的車能充分利用，否則T2T12h，并依次類推，直到第2 次發(fā)車時 S j ( 2) M，并且保證 T2T1 小于規(guī)定的發(fā)車間隔，這樣可依次獲得T3 ,T4, ，直到 Tk b, 并令 Tkb （末班車）， k 即為全天所需發(fā)出的車次，對于上行方向和下行方向以上模型和解法都較實用。假設線路兩端都設有停車場，在發(fā)出頭班車前分別有大客車r1和r2 輛，隨著車輛的運行，兩個停車場的車輛數不斷發(fā)生變化，模型求解中已經解出了發(fā)車時間表（調度表），而且車輛在兩停車場之間的運行時間也是確定的，如果發(fā)出一輛車則停車數量減1，而到達一輛車則停車數量加 1，并令兩個停車場的最少停車數量為零，求出r1和r2 ，

23、那么公交公司應投入的并滿足調度表的最少大客車數為r1r2 。根據問題所給的數據和我們的假設，頭班車和末班車的發(fā)車時間分別為a 5 時和b 23 時；發(fā)車最大的間隔時間為10 分鐘，大客車最大限制載客量為M100或120 人，時間推移的最小步長為h1分鐘。應用 MATLAB 軟件可以得到如下結果（具體程序見附錄）應用模型二全天共需發(fā)車總次數為444 次，其中上行方向由A13 發(fā)出 224 次，下行方向由 A0 發(fā)出220 次；為了保證模型二設計出的調度方案能順利實行，全線路至少需要54 輛大客車，其中在站點 A13 處停放 49 輛，在站點A0 處停放 5 輛。共10頁第6頁公交公司車輛調度方案

24、設計2001 年全國大學生數學建模競賽模型三實際生活中，我們發(fā)現公交車發(fā)車的間隔往往較為均勻，因此我們根據模型二的結果確定各個時間段的發(fā)車時間間隔（一個時間段統(tǒng)一使用一個時間間隔） 。并且經過逐步修改使得所需車輛數較少又不會使車次數增加的太多。所得的發(fā)車時刻表如下：模型評價和改進結果評價模型一方法簡單，思路清晰，但也存在與實際嚴重不符的缺點：由于補發(fā)的車輛是從起點站由于補發(fā)的車輛是為運載后面各站上的顧客而發(fā)出的，理論上，我們不希望補發(fā)的車輛在前面的站上載運客人從而減少了后面站點能上車的人數，但實際上補發(fā)車輛在經過前面站點時會裝載少量顧客，至使后面站上一部分顧客等待較長時間，為解決這個問題，我們提出了模型二。采用模型二處理的結果，是將汽車從發(fā)出到到達終點的整個過程作為考慮對象，當其間的車上人數達到最大時，若這個最大值為汽車載客量的限額（120），則發(fā)出汽車（除等待時間超過十分鐘外） ，從而使這個過程更符合實際情況，一般不會發(fā)生