第19 卷 建模專輯
2002 年02 月
工 程 數 學 學 報
JOURNAL OF EN GINEERIN G MATHEMATICS
Vol. 19 Supp.
Feb. 2002
文章編號:100523085 (2002) 0520059208
公交車調度問題的研究
董 強, 劉超慧, 馬 熠
指導教師: 吳孟達
(國防科技大學,長沙410073)
編者按: 該論文建立了兩個多目標規劃模型,尤其是選擇運力與運量的平衡作為目標函數有新意。尋找最小車輛數的方
法正確。單車場模型作為雙車場模型的補充,雖然簡單,也有自身特點。運行發車時刻表切實可行,接近最優解。
摘 要:本題為帶軟時間窗的單線路單車型的公交調度問題,針對其多目標、多變量的動態特點,我們為滿足不同的實際需
求建立兩個多目標規劃模型:雙車場模型和單車場模型。雙車場模型的主要目標是使運客能力與運輸需求(實際客
運量) 達到最優匹配,單車場模型的主要目標是使乘客的平均不方便程度和公交公司的成本達最小,其目的都是為
了兼顧乘客與公司雙方的利益。兩個模型的主體都是采用時間步長法,模擬實際的運營過程,從而得出符合實際要
求的調度方案:靜態調度和動態調度方案。
關鍵詞: 公交車調度;軟時間窗;滿載率;時間步長法
分類號: AMS(2000) 90C08 中圖分類號: TB114. 1 文獻標識碼: A
1 問題分析
我們分析該問題為壹帶軟時間窗的單車型運輸問題。由已知條件無法確定是單車場問題
還是多車場問題,故我們分別建立兩個模型:雙車場模型和單車場模型。其中,雙車場模型認為
車站A 13 和車站A 0 分別有車場A 和B 存車,即均可作為始發站和終點站,上行和下行路線獨
立運行;單車場模型認為A 0 車站有轉運能力但沒有存車能力,這樣實際上可將單車場方式理
解為環線行駛。
2 模型假設(略)
3 模型的建立與求解
壹 雙車場模型
1) 模塊壹:發車時刻表的確定
依據前面的分析,兼顧乘客與公交公司雙方的利益,分別對單程的上行路線和下行路線建
立如下的多目標規劃模型:
目標函數: Ⅰ 供求的最優匹配 min ∑( Qi ×βi - V i) 2
Ⅱ 各時段的發車車次均最小min{ Ni}
約束條件: ① 各時段的平均滿載率限制015 ≤βi ≤112
② 供求匹配比限制α ≤ k
1. 1 符號說明:
Ni 第i 時段發車次數
βi
第i 時段的平均滿載率
βi
= Ri / ( c ×Ni) Ri 為第i 時段的總上車人數, c = 100 人/ 車次
α 供求匹配比 α = ( ∑V i) / ( ∑Qi)
k 控制參數
Qi 第i 時段運客能力(人×公裏)
Qi = 第i 時段發車次數Ni ×每輛車標準載客量c ×單程(上行或下行) 總運行距離
L 。其中,上行時, L = 14. 58 公裏; 下行時, L = 14. 61 公裏
V i 第i 時段的需要運客量(人×公裏)
V i = ∑j
( x ji
2yji) L j j ∈(13 ,12 ?,1 ,0) , 上行方向; j ∈ (0 ,2 ,3 , ?13) , 下行方
向。
其中, x ji 為第i 時段內A j 站的上車人數; yji為第i 時段內A j 站的下車人數
L j 為A j 站距該單程方向上終點站的距離。
112 目標函數說明:
目標函數Ⅰ使第i 時段的運客能力Qi 與運輸需求(實際客運量) V i 達到最優匹配,βi 反
映滿載率高低的影響。
目標函數Ⅱ使各時段所需的最大發車次,在滿足約束條件下盡可能少, 以使總車輛數較
少。
113 約束條件說明:
條件①是限制滿載率滿足運營調度要求,是考慮了乘客的利益。
條件②是限制供求匹配比α小於常數k 。我們根據參數k 的變動量分別進行模擬,從而篩
選最恰當的k 值。
補充約束條件:為使始發站車場的每天起始時刻的車輛數保持不變,需使總發車次數與總收車
次數相等,即必須使單程車次總數達到匹配( N1 = N2) ,而N1 不能減少(受滿
載率限制) ,因此我們在求解下行方向的Ni 時增加約束∑N2 i = N1. 在增添
約束條件∑N2 i = N1 之後,用二次規劃求得各時段發車次數N1 i 和N2 i 。
2) 模塊二:運營過程的模擬
在這部分,我們采用時間步長法,根據假設壹個時段內發車間隔時間t i 相等,則t i 可由Ni
確定,從而得到發車時刻表。按此發車時刻表模擬實際運行過程, 目標是確定滿足時刻表的最
小車輛數n ,統計各項運營指標,搜索最優調度方案解。
211 模擬子程序壹:確定最小車輛數目n
根據“按流發車”和“先進先出”的原則,對起點站, 在發車時刻應至少有壹輛車可以發出
(處於等待發車狀態) 。若有多輛車,則先進站者先發車,其余車輛“排隊”等候;若無車可發,則
出現“間斷”。完整的運營過程應保證車輛嚴格按時刻表發車,不發生間斷。
設A 13 站和A 0 站分別有車場A 和B ,從車場中不斷有車發出,同時接受車進場,則車場
中的車的數目是隨時間變化的狀態量。用Na 和Nb 來描述車場A 和車場B 中要滿足車流不間
斷所需的最小數目,分別搜索其在運行過程中的最大值,則所需最小車量數目n = Na + Nb。
2. 2 模擬子程序二:統計各項運營指標
60 工 程 數 學 學 報 第19 卷
確定各項運營指標,采用模擬統計的計算方法, 對不同的運營指標進行定量計算, 主要功
能是通過定量分析運營指標來檢驗方案的可行性,以確定方案調整。
由於車次與發車時刻壹壹對應,而車輛的隊列順序是不發生改變,因而對所需車輛進行統
壹編號,則對每壹車次,與其對應的車輛編號是確定的,故我們直接對第k 次車進行考察。
我們統計的指標及其定義如下:
平均滿載率 上行方向 β01 = ( ∑k
∑j
1
β( k , j1) / ( N1 ·J1)
下行方向β02 = ( ∑k
∑j
2
β( k , j2) / ( N2 ·J2)
滿載率分布可以由β( k , j) 確定。
平均候車時間上行方向T1 = ( ∑k
∑j
1
T ( k , j1) / ( N1 ·J1)
下行方向T2 = ( ∑k
∑j
2
T ( k , j2) / ( N2 ·J2)
符號說明:
D ( k , j) 第k 次車到第j 站時上車與下車的人數之差; (已知)
C( k , j) 第k 次車離開第j 站時站臺上的滯留人數; C( k , j) = C( k - 1 , j) + D ( k , j) -
(120 - B ( k , j - 1)
B ( k , j) 第k 次車離開第j 站時車上的人數; B ( k , j) = B ( k , j - 1) + D ( k , j) + C( k -
1 , j) - C( k , j)
T ( k , j) 為第k 次車離開第j 站時站臺上滯留者的滯留時間; T ( k , j) = C( k , j) ·t i
β( k , j) 為第k 次車離開第j 站時的滿載率,β( k , j) = B ( k , j) / 100 ;
N1 , N2 為壹天單程所發的車次總數; J1 , J2 為單程站臺總數;
2. 3 模擬結果及統計指標分析
我們選取參數k = 018 ,0185 ,019 進行模擬運行,所得結論如表1 。(表中只給出上行方向
值) :
表1 模擬上行方向所得營運指標值
參數k 平均滿載率β0 平均候車時間T 所需總車輛n 總發車次數N1
018 6817 % 3188 63 270
0185 7218 % 3188 63 255
019 7614 % 4124 62 243
0195 8014 % 7123 62 231
綜合考慮以上參數,當k = 019 時,各項指標比較適當,平均滿載率較高,平均候車時間較
短,所需車輛與總發車次數適中,所以我們選取k = 019 。
下面我們給出k = 019 時的具體模擬結果及統計指標。
結果:
⑴ 各時段內單程發車次數(見表2)
總車次N1 = N2 = 243 。
建模專輯 公交車調度問題的研究61
表2 k = 0. 9 時各時段中的發車次數
時段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
上行7 28 41 23 13 11 13 11 11
下行3 12 21 26 16 11 10 9 10
時段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
上行9 9 19 24 8 5 5 4 2
下行11 13 19 30 19 11 9 8 5
⑵ 各時段單程發車時間間隔
由於壹個時段內的發車間隔已假設為等距,所以由所得的車次很容易確定發車時間間隔。
⑶ 單程發車時刻表(數據量太大,故略)
⑷ 總車輛數n = 62 ,其中場A 存車57 輛,場B 存車5 輛。
統計指標:
⑴ 平均滿載率 上行方向 β01 = 76. 4 % 下行方向 β02 = 7019 %
⑵ 平均候車時間上行方向T1 = 4. 24 分下行方向T2 = 3148 分
3) 調度方案
我們由不同的理解得到兩種調度方案,其***同點是都必須形成完整的運營過程,使車流不
間斷。
3. 1 靜態調度方案:
認為在該路線上運行的總車數固定不變,形成序貫流動的車流,依照“按流開車”和“先進
先出”的原則,按發車時刻表發車。
所需總車輛數為62 ,其中從A 13 站的車場A 始發的車數為57 ,從A 0 站的車場B 始發的
車數為5 。
3. 2 動態調度方案:
考慮高峰期與低谷期實際需要的車輛數目不同, 為了滿足高峰期而求得的車輛數目必然
大與其他時間需要的車輛數,即62 輛車只在高峰期得到充分利用,造成資源浪費。我們認為公
交公司可進行車輛動態調度,讓壹些車輛可以在特殊原因下進行修理調整, 並節約運營成本。
由此我們在保證車流不間斷的條件下,計算得出各個時段內實際所需的最小車輛數。如表3 所
示: (同時給出A 、B 車場的存車狀態,可以自由支配的車輛數目)
表3 動態調度中各時段的車輛數
時段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需車數9 34 56 48 38 22 20 19 18
A 場狀態51 28 2 0 0 11 12 11 9
B 場狀態2 0 4 14 24 29 30 32 35
時段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
所需車數17 20 29 42 41 25 17 14 10
A 場狀態9 10 9 5 6 25 37 43 48
B 場狀態36 32 24 15 15 12 8 5 4
由上表我們得出:在總車輛數目可變動的情況下,所需的最大車輛數為7 :008 :00 間的56
輛,在非高峰期時所需車輛數目都較小, A 車場和B 車場都有較多車輛庫存著,可以根據實際
情況挪作它用。公交公司只需按表中所給的每個時段的所需車輛數進行調度,按發車時刻表發
62 工 程 數 學 學 報 第19 卷
車即可。
二 單車場模型
1) 模型的建立
根據問題分析,公交營運方式按單車場組織後我們建立如下帶軟時間窗口的單車型運輸
問題多目標優化模型:
目標函數: Ⅰ y1 = min { n}
Ⅱ y2 = min ∑Ni
Ⅲ y3 = min ( ∑j
∑k
∑r
P( Ti) ) / ( R ·K ·M)
約束條件: ①平均滿載率限制50 % ≤β ≤120 %
②發車間隔時間限制t i ≤5 + 5 k ; k =
0 i 為早高峰期時;
1 i 為非早高峰期時。
③ t i ∈{ 1 ,2 ,3 ?}
1. 1 目標函數說明: 目標函數Ⅰ使總車輛數目最小,即使公司的投資成本達到最小。
目標函數Ⅱ使總車次數最小,即使公司的運營成本達到最小。
目標函數Ⅲ是使所有顧客的平均不方便程度達到最小。
112 約束條件說明: 條件③主要是考慮到可操作性,發車間隔劃分到秒壹級,公交司機是沒
法把握的,故最小只能劃分到分壹級, 那麽發車間隔就應是1 分的整數
倍
2) 模型的求解
本模型是多目標、多約束的優化模型,很難求出全局最優解,所以我們先將多目標規化簡,
再仿真模擬運營過程求解。求解思路如下:
給出初始發車時刻表
客運數據
客流分布(平均分布)
v
v
v
模擬
運營
數據
v 統計指標v 結論w 人工分析
2. 1 模型化簡
化簡多目標問題,我們可以有三個出發點: ①分析各目標之間相關聯的數學關系,減少目
標函數數目或約束條件數目。②依限定條件,針對具體數據挖掘隱含信息以降低求解難度。③
分析各目標權重,去掉影響很小的目標函數,從而達到簡化目的。
分析目標Ⅱ與Ⅲ存在數學關聯,發現總車次越多,乘客不方便程度越小。因此y2 與y3 不
能同時取最小值。我們認為Ⅲ為主要目標,故主要考慮目標函數Ⅲ。從具體數據可知,在上行
方向7 :00 ～ 8 :00 , A 13 站上車人數達3626 人,平均每分鐘到達60 人, A 12 站上車634 人而下
車僅205 人,為客流量最大的時段,發車間隔時間至少需要2 分鐘。由平均速度20 公裏/ 小時
及環行距離,可得到此時至少需45 輛車。
由以上分析將原模型簡化為:
目標函數: y1 = min ( ∑j
∑k
∑r
P( Ti) ) / ( R ·K ·M)
y2 = min M
約束條件: 同上
建模專輯 公交車調度問題的研究63
2. 2 運營過程模擬
⑴ 初始時刻表的產生方法
原則上初始時刻表可以隨機產生,然後模擬判斷搜索出較優解, 但這樣搜索量太大, 且很
難保證有壹個收斂結果。因此我們采用人機交互的方式,首先分析數據得出比較合理的發車時
間間隔的近似值,產生初始時刻表(見表4) ,然後在其附近搜索局部最優解。
表4 初始發車時刻表
時段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
ti (分) 10 3 2 3 8 8 8 8 8
時段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
ti (分) 8 8 3 2 3 10 10 10 10
⑵ 模擬運營過程,統計各指標,搜索最優解
由於模擬運營過程與雙車場模型大同小異,故我們在此不再詳述。
2. 3 結果及統計分析
對仿真產生的多組發車時刻表進行模擬獲得最小的Y = 516 分,我們把這壹組解做為我
們的局部最優解,其結果(其中統計指標用來描述我們以怎樣的程度照顧雙方利益) 如下:
⑴ 總車數
理想的理解平均速度可得所需總車數為45 輛,加2 輛應急,為47 輛;
考慮高峰期車速小於20km/ h , 高峰期人流量大是造成高峰期速度稍低於20km/ h 的主
因,那麽通過人流量數據和20km/ h 就可大致推算7 :00 - 8 :00 速度約為18km/ h 。這樣高峰期
的最小總車數45 輛,應修正為50 輛,加2 輛應急最終為52 輛。
⑵ 全天總車次M = 253 ×2 = 506 次
⑶ 發車時刻表見表5 (用各時段發車間隔時間簡述)
表5 單車場模型最優發車時刻表
時段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
ti (分) 10 2 2 2 4 6 6 6 8
時段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
ti (分) 8 6 3 2 3 7 10 10 10
註:5 :00 - 6 :00 只是壹種統計劃分,首發車可以在5 :00 之前,也可在5 :00 之後。當然當不
知道其它原則時可以假設首發車為5 :00 發。對單車場下行線始發為5 :45 與數據相吻
合。5 :00 - 6 :00 上行線***855 人上車;下行線***50 人。其可能原因之壹就是上行在5 :
00 - 6 :00 都有車可統計;而下行只在5 :45 - 6 :00 中可實際統計到車。
統計指標: ⑴乘客平均候車時間 y3 = 516 分
⑵平均滿載率 β0 = 66. 4 %
結論分析:由上面兩個圖表可見我們的調度方案基本上能滿足乘客候車時間的限制,高峰期乘
客在5 分鐘內等到車的概率為9219 % ,非高峰期乘客在10 分鐘內等到車的概率為
8917 %。
調度方案: (見表6)
64 工 程 數 學 學 報 第19 卷
表6 單車場動態調度方案
時段5 ～ 6 6 ～ 7 7 ～ 8 8 ～ 9 9 ～ 10 10 ～ 11 11 ～ 12 12 ～ 13 13 ～ 14
所需車輛數10 46 52 46 24 16 16 16 14
時段14 ～ 15 15 ～ 16 16 ～ 17 17 ～ 18 18 ～ 19 19 ～ 20 20 ～ 21 21 ～ 22 22 ～ 23
所需車輛數14 16 30 46 30 14 10 10 8
4 模型的進壹步討論
1) 關於采集運營數據的討論
由於我們假設在壹個時段內乘客到站服從均勻分布, 而實際中乘客到站時間不可能都服
從均勻分布。特別是在高峰期的情況下, 乘客到站時間的不均勻分布就會使模型結論誤差較
大。我們建議以下幾種改進采集方式的方法:
⑴ 采取不等的統計人數的間隔時間
在高峰期的情況下,為削弱乘客到站時間不均勻分布帶來的影響,可適當減小統計的間隔
時間但統計時間加密應有壹定限度。對客流量很小的時段,我們可適當增大統計的間隔時間。
⑵ 增加能反應有關滯留人數的統計數據。
⑶ 按相等到站人數來區分時間段的統計
方法是統計達到壹定到站人數時的時間點,其優點是能較為準確地反映客流量的變化情
況,有利於按其分布的疏密進行車輛調度,以更好的滿足乘客的需要。
2) 單車場調度方案與雙車場調度方案的選用
由結果分析可知單車場調度方案減少了公司的前期投資成本;雙車場調度方案的運營成
本小,更好的兼顧到乘客與公司雙方的利益。我們建議, 在有雙車場的條件下選取雙車場調度
方案更好。當需進行路線規劃,需要選取單車場或雙車場時, 建議根據實際所需成本來選取方
案。
5 模型的評價
本文的優點如下:
1) 模型的主體是采用時間步長法,模擬生成的發車時刻表的實際運行過程,準確性高,
容量大,邏輯性嚴格,計算速度快,具有較強的說服力和適應能力。
2) 定義了能定量衡量我們的調度方案對乘客和公交公司雙方利益滿足程度的統計指
標。
3) 在求最少車輛數時,將兩個車場看作兩個發射源, 通過對兩個車場的存車狀態的實
時模擬,形成不間斷的運營過程,從而求得所需車輛數目。
本文的缺點是:
1) 對於運營數據的采集方式,只給出了壹些原則和想法,沒有經過仿真驗證。
2) 對於乘客到站的分布,直接假設為均勻分布,沒有對其他分布的情況再作討論。
建模專輯 公交車調度問題的研究65
參考文獻:
[ 1 ] 錢 湔. 運籌學[M] . 北京:科學出版社,2000
[ 2 ] 肖 雁,符 卓,李育安. 帶軟時間窗口的車輛路徑問題及其應用前景探討[J ] . 中國運籌學會第六屆學術交流會論文
集,下卷,634 - 638
Study on the Schedul ing Problem
DONG Qiang , L IU Chao2hui , MA Yi
Instructor : WU Meng2da
(National University of Defence Technology , ChangSha 410073)
Abstract : As it’s a vehicle2scheduling problem with soft time windows , we established two multiple objective programming mod2
els to satisfy different practical conditions : double2parking2lot model and single2parking2lot model. The main objective of the former
was to match the capacity of passengers holding with the real demand , while the objective of the latter was to minimize the average
inconvenience of passengers and the cost of transit companies. Both of the two models considered for benefits of both passengers and
companies. By using the method of step2by2step time , we simulated the practical procedure and drew two dispatching plans : static
dispatching and dynamic dispatching.
Key words : scheduling ; step2by2step time ; dispatching plans
66 工 程 數 學 學 報 第19 卷