公交車(chē)調(diào)度問(wèn)題的數(shù)學(xué)模型

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

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

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

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

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

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

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

8、 kj :第一步:按先到先上車(chē)的排隊(duì)原則,確定j 在站的乘客當(dāng)?shù)?k +1輛車(chē)到達(dá)時(shí),仍要等候車(chē)輛數(shù)的最大值h 3kj ,為此解如下問(wèn)題( 參看圖2:max 0h h kjh s.t.h kjr =h W kj (r b kj圖2第二步:若h 3kj =0,說(shuō)明此時(shí)該站上所有候車(chē)人全能上車(chē),這樣,301建模專(zhuān)輯公交車(chē)調(diào)度問(wèn)題的數(shù)學(xué)模型P kj =h kj h =0W kj (h ;同時(shí)令:h k +1j =0;第三步:若h 3kj >0,說(shuō)明此時(shí)該站上候車(chē)人不能全上車(chē),這樣,P kj =b kj ;同時(shí)令: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 輛車(chē)駛離j 站的時(shí)該車(chē)上的乘客數(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 輛車(chē)駛到j(luò) 站時(shí),該站上己等候h 趟車(chē)的乘客數(shù)是:W kj (h ,h =1,h kj他們已等候的時(shí)間是:W T kj (h =T kj -T k -h j ,h =1,h kj .確定交通高峰時(shí)段:T 1,T ,整個(gè)時(shí)段T

10、1,T m ,則交通高峰時(shí)段候車(chē)超時(shí)率=高峰時(shí)段,候車(chē)超過(guò)5分鐘的總?cè)藬?shù)高峰時(shí)段,上車(chē)總?cè)藬?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 交通平峰時(shí)段候車(chē)超時(shí)率=平嶠時(shí)段,候車(chē)超過(guò)10分鐘的總?cè)藬?shù)平峰時(shí)段,上車(chē)總?cè)藬?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ā)車(chē)次數(shù)×(車(chē)站數(shù)-1,記作Cap -low

11、(T =kj1B -P k (T kj B015m ×(n -1401工程數(shù)學(xué)學(xué)報(bào)第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 ,其中,為給定的權(quán)重系數(shù)。關(guān)于決策變量可以簡(jiǎn)化為:分段等時(shí)分布:即先確定高峰時(shí)段和平峰時(shí)段,在這兩種時(shí)段內(nèi)等間隔發(fā)車(chē),這樣變量就少多了。(6模型求解無(wú)約束優(yōu)化問(wèn)題:直接法:如復(fù)合形方法,數(shù)值微分的下降方法等。在實(shí)際求解中,如果決策變量不多,利用求出一系列可行解的方法,求出近似最優(yōu)解,也是可取的。2配車(chē)模型及其求解在分別求出上、下行兩個(gè)方向

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

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

14、low =滿載率低于50%的段數(shù)百分比,選擇權(quán)重系數(shù),均為1/3,得目標(biāo)函數(shù)C 。計(jì)算中可記錄:Total =上下行方向全天發(fā)車(chē)總輛數(shù);按照全程行車(chē)時(shí)間(考慮每輛車(chē)反復(fù)501建模專(zhuān)輯公交車(chē)調(diào)度問(wèn)題的數(shù)學(xué)模型106 工 19 卷 程 數(shù) 學(xué) 學(xué) 報(bào) 第 運(yùn)行 可記錄 : 上行方向所需車(chē)輛數(shù) ( up - bus ,下行方向所需車(chē)輛數(shù) ( down - bus 。 為保證每個(gè)始發(fā)站每天早發(fā)車(chē)前與晚收車(chē)后的車(chē)輛狀態(tài)都不變 , 給定的發(fā)車(chē)間隔有下列 兩種 : A . 上行與下行方向發(fā)車(chē)時(shí)間間隔相同 : ( 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 . 上行與下行方向早高峰和晚高峰時(shí)間間隔對(duì)換 , 如 ( 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 從以上各種方案的目標(biāo)函數(shù) C 及所需車(chē)輛數(shù)看 , A 中的 ( 5 , 2 , 3 較優(yōu) ( 黑體 。 最后 , 特別要提及的是 , 該問(wèn)題的基本數(shù)據(jù)和參數(shù)由北京市地鐵研究所康海燕同志提供 , 編程及計(jì)算由清華大學(xué)數(shù)學(xué)科學(xué)系研究生完成 , 在此對(duì)他們表示感謝 。 A Mathematical Model of Bus Schedul ing TAN Ze2guang ,