公交車調度問題的數(shù)學模型

1、第19卷建模專輯2002年02月工程數(shù)學學報J OU RNAL OF EN GIN EERIN G MA THEMA TICSVol.19Supp.Feb.2002文章編號:100523085(20020520101206公交車調度問題的數(shù)學模型譚澤光,姜啟源(清華大學,北京100084摘要:給出本問題的背景、建模思路、一個具體的確定性數(shù)學模型,及相應的計算結果。關鍵詞:公交車調度;運行模型;多目標規(guī)劃分類號:AMS(200090C08中圖分類號:TB114.1文獻標識碼:A1問題的背景和要求公交車調度問題的背景是某大城市公交部門提出的一個實際科研課題。該課題要求對一條確定的公交路線,解決三個

2、方面的問題:第一,根據(jù)歷史積累和必要的補充調查數(shù)據(jù),提出沿路各站來站與離站的乘客分布規(guī)律;第二,研制一個模擬該線路公交運行過程的數(shù)學模型;第三,在前兩條的基礎上為該線路提出一個配備車輛和司(機售(票員人員數(shù)目的方案,以及一個在通常情況下車輛的運行時間表。根據(jù)這個背景,我們在有關人員的大力支持下,對問題作了大幅度的簡化,提出了如下建模問題。首先選擇了該市一條比較典型的公交線路,沿線上行方向共14站,下行方向共13站,根據(jù)多年來沿線各站乘客來、離站的人數(shù)調查數(shù)據(jù),給出了該線一個工作日兩個運行方向各站上下車的乘客數(shù)量按時間的分布。為簡單明確起見,同時假設:公交公司配給該線路同一型號的大客車,每輛標準

3、載客100人;客車在該線路上運行的平均速度為20公里/小時;并顧及社會效益對運營調度提出的基本要求為:乘客候車時間一般不要超過10分鐘,早高峰時一般不要超過5分鐘,車輛滿載率不應超過120%;同時又考慮到提高公交公司運營效益,提出了車輛滿載率一般也不要低于50%的指標。問題要求根據(jù)上述數(shù)據(jù),在盡可能適當考慮公交社會效益和公交公司利益的目標下,為該線路設計一個便于操作的全天(工作日的公交車調度方案,即兩個起點站的發(fā)車時刻表,并指出實現(xiàn)這個方案至少需要配備多少輛車;給出這種方案照顧乘客和公交公司雙方的利益程度的數(shù)量指標,從而將這個調度問題抽象成一個明確、完整的數(shù)學模型,并指出求解模型的方法。2建立

4、模型的思路和框架該調度問題可分成三個子問題:1建立模擬公交車運營時的運行模型,即在某一確定調度方案下,公交車在該線路上運行過程的數(shù)學描述。一種比較切合實際一些的是隨機模型,通過隨機模擬來模擬運行過程,由決策變量及原始數(shù)據(jù)取得要求的各種目標數(shù)值。另一種是建立確定性模型,把運行過程看作一個按一定時間表發(fā)車的公交車,在一定要求下,順序將沿線乘客送達預定地點的確定過程。2通過運行模型優(yōu)化所需的目標。本問題實際上是一個多目標規(guī)劃,至少有二個目標要考慮:一個是反映乘客利益的乘客等待時間;另一個是反映公交公司利益的載客率。如何通過優(yōu)化算法,求解這個雙目標規(guī)劃是該模型的第二個問題。3配車模型,即確定實現(xiàn)調度方

5、案所需的最少車輛數(shù)。這是一個帶時序的分配問題。3建立確定性模型的一個例子1運行模型及其求解(1己知數(shù)據(jù)車站標記:j =1,2,n ;來客密度:在時刻t 到達j 站乘客的密度u j (t ,j =1,2,n ;下車乘客密度:在時刻t 從j 站下車乘客的密度d j (t ,j =1,2,n ; 站間行車時間:從j -1站到j 站站間行車時間(包括在j 站的仃車時間:j ,j =2,n ;每輛車的載客容量:B ;載客容量上限 B ;交通高峰時段等待時間上界t ;交通平峰時段等待時間上界 t ;(2決策變量及相關變量決策變量:發(fā)車時刻表,向量T =(T 0,T 1,T 2,T k ,T m ,其中,T

6、 0:第一輛車到達起點站j =1的時刻;T k :第k 輛車駛離起點站j =1的時刻,k =1,2,m相關變量: 第k 輛車駛離j 站的時刻:T k 1=T k ,T kj =T k 1+j -1=1 ,j =2,3,n -1; 第k 輛車駛離j 站時該車上的乘客數(shù):P k (T kj ,k =1,2,m ;j =1,2,n -1;第k 輛車駛到j 站時,該站上候車乘客的分布函數(shù):W kj (0:從T k -1j 到T kj 時段的來客數(shù);W kj (h :第k 輛車駛到j 站時,該站上己等候過h 趟車仍未能上車的乘客數(shù);h kj :第k 輛車駛到j 站時,該站上等待最久乘客的候車趟數(shù),W k

7、j (h kj >0,W kj (h kj +1=0運行模型框圖(圖1見下頁圖:(3相關變量的計算公式第k 輛車駛到j 站后,等到該站的乘客下完后,車上仍留下的乘客數(shù):a kj =max (P k (T k j -1-T kjT k -1jd j (t dt ,0 第k 輛車駛到j 站后,等到該站的乘客下完后,j 站可容納的上車乘客數(shù)上界:b kj = B -a kj ,第k -1輛車駛離j 站到第k 輛車駛到j 站時段內,該站的乘客到達量:201工程數(shù)學學報第19卷 圖1W kj (0=T kjK k -1j u j (t dt ; 計算第k 輛車駛到j 站后,在該站實際上車的乘客數(shù)P

8、 kj :第一步:按先到先上車的排隊原則,確定j 在站的乘客當?shù)?k +1輛車到達時,仍要等候車輛數(shù)的最大值h 3kj ,為此解如下問題( 參看圖2:max 0h h kjh s.t.h kjr =h W kj (r b kj圖2第二步:若h 3kj =0,說明此時該站上所有候車人全能上車,這樣,301建模專輯公交車調度問題的數(shù)學模型P kj =h kj h =0W kj (h ;同時令:h k +1j =0;第三步:若h 3kj >0,說明此時該站上候車人不能全上車,這樣,P kj =b kj ;同時令:h k +1j =h 3kj +1,且置:W k +1j (h +1=W kj (

9、h ,h =0,1,(h 3kj -1W k +1j (h 3kj =h kjh =h 3kjWkj (h -b kj .這樣,我們有:第k 輛車駛離j 站的時該車上的乘客數(shù):P k (T kj =a kj +P kj=a kj +h kjh =0W kj (h ,若h 3kj =0,B ,若h 3kj >0,k =1,2,m ;j =1,2,n -1。(4 第k 輛車駛到j 站時,該站上己等候h 趟車的乘客數(shù)是:W kj (h ,h =1,h kj他們已等候的時間是:W T kj (h =T kj -T k -h j ,h =1,h kj .確定交通高峰時段:T 1,T ,整個時段T

10、1,T m ,則交通高峰時段候車超時率=高峰時段,候車超過5分鐘的總人數(shù)高峰時段,上車總人數(shù),記作Over W 1(T =T kj T 1,T 2W kj (h |W T kj (h 5,h =1,h kj T kj T 1,T 2P k (T kj 交通平峰時段候車超時率=平嶠時段,候車超過10分鐘的總人數(shù)平峰時段,上車總人數(shù),記作Over W 2(T =T kj T 1,T 2W kj (h |W T kj (h 10,h =1,h kj T kj T 1,T 2P k (T kj 滿載率低于50%的段數(shù)百分比=滿載率低于50%的段數(shù)發(fā)車次數(shù)×(車站數(shù)-1,記作Cap -low

11、(T =kj1B -P k (T kj B015m ×(n -1401工程數(shù)學學報第19卷(5優(yōu)化模型求T =(T 0,T 1,T 2,T k ,T m ,使得:min TC =Over W 1(T +Over W 2(T +Cap -low (T ,其中,為給定的權重系數(shù)。關于決策變量可以簡化為:分段等時分布:即先確定高峰時段和平峰時段,在這兩種時段內等間隔發(fā)車,這樣變量就少多了。(6模型求解無約束優(yōu)化問題:直接法:如復合形方法,數(shù)值微分的下降方法等。在實際求解中,如果決策變量不多,利用求出一系列可行解的方法,求出近似最優(yōu)解,也是可取的。2配車模型及其求解在分別求出上、下行兩個方向

12、的優(yōu)化后的調度時間表之后,就可以進行配車。該模型可圖示如圖3,其中兩個時間軸,軸上虛線表示上行車輛,虛線帶箭頭的線表示上行轉為下行;軸上實線表示下行車輛,實線帶箭頭的線表示下行轉為上行 。圖3這里只是一種模型,實際上做法是多種多樣的。從建模的角度看,把上、下行分開,將運行與配車兩個模型分開,都是簡化。不過這可能是必要的,否則問題會變得很復雜,以至于無法求解。3數(shù)值計算結果根據(jù)所給數(shù)據(jù),按照上述模型的基本思路,用給定發(fā)車間隔,計算目標函數(shù),通過比較選優(yōu)的辦法,提供合適的方案。(1假設用所給數(shù)據(jù)中每時段(1小時在每一站的上車人數(shù)和下車人數(shù)就是該時段到達該站和離去的人數(shù),即通過這些數(shù)據(jù)計算出u j

13、(t 和d j (t 。(2用所給數(shù)據(jù)中站間距和平均車速(忽略上下車時間得到j ;B =100, B =120。(3根據(jù)所給數(shù)據(jù)中始發(fā)站的上車人數(shù),確定早、晚高峰時段為:早高峰640940;晚高峰15501850。于是全天分為3個時段:平峰時段I 1,早高峰時段I 2,晚高峰時段I 3。高峰時段等待時間上界t =5(分鐘;平峰時段等待時間上界 t =10(分鐘。(4給定決策變量為3個時段的發(fā)車間隔:J 1,J 2,J 3,由此可計算出T 0,T 1,T m 。(5對于上行和下行方向均可計算,得到如下結果:記Over W 1=早高峰時段候車超時率,Over W 2=平峰時段候車超時率,Cap -

14、low =滿載率低于50%的段數(shù)百分比,選擇權重系數(shù),均為1/3,得目標函數(shù)C 。計算中可記錄:Total =上下行方向全天發(fā)車總輛數(shù);按照全程行車時間(考慮每輛車反復501建模專輯公交車調度問題的數(shù)學模型106 工 19 卷 程 數(shù) 學 學 報 第 運行 可記錄 : 上行方向所需車輛數(shù) ( up - bus ,下行方向所需車輛數(shù) ( down - bus 。 為保證每個始發(fā)站每天早發(fā)車前與晚收車后的車輛狀態(tài)都不變 , 給定的發(fā)車間隔有下列 兩種 : A . 上行與下行方向發(fā)車時間間隔相同 : ( J1 , J2 , J3 ( 3 , 2 , 2 ( 4 , 2 , 3 ( 4 , 3 , 3

15、 ( 5 , 2 , 3 ( 5 , 3 , 3 ( 5 , 2 , 4 ( 6 , 2 , 2 ( 6 , 3 , 3 Over W 2 0 . 0006 0 . 0488 0 . 1016 0 . 0517 0 . 1204 0 . 1565 0 . 0364 0 . 1344 Over W 1 0 . 0941 0 . 1161 0 . 3194 0 . 1336 0 . 3585 0 . 1336 0 . 1632 0 . 3704 Cap - low 0 . 6175 0 . 4140 0 . 4031 0 . 3390 0 . 3150 0 . 3301 0 . 3414 0 .

16、2547 C Total 420 331 301 295 265 280 299 240 up - bus 22 22 15 22 15 22 22 15 down - bus 22 22 15 22 15 22 22 15 0 . 2374 0 . 1930 0 . 2747 0 . 1748 0 . 2646 0 . 2067 0 . 1803 0 . 2532 B . 上行與下行方向早高峰和晚高峰時間間隔對換 , 如 ( 4 , 3 , 2 表示 : 上行為 ( 4 , 3 , 2 , 下行為 ( 4 , 2 , 3 。 ( J1 , J2 , J3 ( 4 , 3 , 2 ( 4 ,

17、2 , 3 ( 5 , 3 , 1 ( 5 , 3 , 2 ( 5 , 2 , 3 ( 5 , 3 , 3 ( 5 , 4 , 2 ( 6 , 3 , 2 Over W 2 0 . 0184 0 . 0860 0 . 0252 0 . 0250 0 . 1035 0 . 1204 0 . 0922 0 . 0528 Over W 1 0 . 1733 0 . 2547 0 . 0842 0 . 1912 0 . 2933 0 . 3585 0 . 2912 0 . 2203 Cap - low 0 . 4126 0 . 4507 0 . 5672 0 . 3341 0 . 3790 0 . 3

18、150 0 . 3260 0 . 2793 C Total 330 331 385 295 295 265 280 269 up - bus 45 15 135 45 15 15 56 45 down - bus 15 45 15 15 45 15 11 15 0 . 2014 0 . 2638 0 . 2255 0 . 1834 0 . 2586 0 . 2646 0 . 2365 0 . 1841 從以上各種方案的目標函數(shù) C 及所需車輛數(shù)看 , A 中的 ( 5 , 2 , 3 較優(yōu) ( 黑體 。 最后 , 特別要提及的是 , 該問題的基本數(shù)據(jù)和參數(shù)由北京市地鐵研究所康海燕同志提供 , 編程及計算由清華大學數(shù)學科學系研究生完成 , 在此對他們表示感謝 。 A Mathematical Model of Bus Schedul ing TAN Ze2guang ,