公交車調度問題的研究

1、 公交車調度問題的研究 董強， 劉超慧， 馬熠 指導教師：吳孟達 （國防科技大學，長沙 410073）編者按：該論文建立了兩個多目標規(guī)劃模型，尤其是選擇運力與運量的平衡作為目標函數有新意。尋找最小車輛數的方法正確。單車場模型作為雙車場模型的補充，雖然簡單，也有自身特點。運行發(fā)車時刻表切實可行，接近最優(yōu)解。摘要: 本題為帶軟時間窗的單線路單車型的公交調度問題，針對其多目標、多變量的動態(tài)特點，我們?yōu)闈M足不同的實際需求建立兩個多目標規(guī)劃模型：雙車場模型和單車場模型。雙車場模型的主要目標是使運客能力與運輸需求（實際客運量）達到最優(yōu)匹配，單車場模型的主要目標是使乘客的平均不方便程度和公交公司的成本達最小

2、，其目的都是為了兼顧乘客與公司雙方的利益。兩個模型的主體都是采用時間步長法，模擬實際的運營過程，從而得出符合實際要求的調度方案：靜態(tài)調度和動態(tài)調度方案。關鍵字： 公交車調度；軟時間窗；滿載率；時間步長法一、問題分析我們分析該問題為一帶軟時間窗的單車型運輸問題。由已知條件無法確定是單車場問題還是多車場問題，故我們分別建立兩個模型：雙車場模型和單車場模型。其中，雙車場模型認為車站A13和車站A0分別有車場A和B存車，即均可作為始發(fā)站和終點站，上行和下行路線獨立運行；單車場模型認為A0同時為上行終點和下行起點，它有轉運能力但沒有存車能力，這樣實際上可將單車場方式理解為環(huán)線行駛。二、模型假設 （略）三

3、、模型的建立與求解雙車場模型模塊一：發(fā)車時刻表的確定依據前面的分析，兼顧乘客與公交公司雙方的利益，分別對單程的上行路線和下行路線建立如下的多目標規(guī)劃模型：目標函數 供求的最優(yōu)匹配 min(Qi×i -Vi)2 各時段的發(fā)車車次均最小 minNi約束條件 各時段的平均滿載率限制 0.5i1.2 供求匹配比限制 k符號說明：Ni 第i時段發(fā)車次數i 第i時段的平均滿載率 i=Ri/(c×Ni) Ri為第i時段的總上車人數, c=100人/車次 供求匹配比 =(Vi)/(Qi)k 控制參數Qi 第i時段運客能力（人×公里）Qi=第i時段發(fā)車次數Ni×每輛車標準

4、載客量c×單程(上行或下行)總運行距離L其中，上行時，L= 14.58公里; 下行時，L=14.61 公里Vi 第i時段的需要運客量（人×公里） Vi= j(13,12,1,0) ,上行方向；j(0，2，3，13) ,下行方向。 其中，xji 為第i時段內Aj站的上車人數；yji 為第i時段內Aj站的下車人數 Lj為Aj站距該單程方向上終點站的距離。 即認為上車乘客的運載距離為正，下車乘客的運載距離為負。1.2 目標函數說明：目標函數使第i時段的運客能力Qi與運輸需求（實際客運量）Vi達到最優(yōu)匹配,i反映滿載率高低的影響。目標函數使高峰期所發(fā)車次，即單位時段所發(fā)的最大車次，

5、在滿足約束條件下盡可能少，以使總共需要的車輛數較少。1.3 約束條件說明：條件是限制滿載率滿足運營調度要求，是考慮了乘客的利益。條件是限制供求匹配比小于常數k。我們根據參數k的變動量分別進行模擬，從而篩選最恰當的k值。注：為使始發(fā)站車場的每天起始時刻的車輛數保持不變，需使總發(fā)車次數與總收車次數相等，即必須使單程車次總數達到匹配（N1=N2），而N1不能減少（受滿載率限制），因此我們在求解下行方向的Ni時增加約束Ni2=N1. 在增添約束條件Ni2=N1之后，用二次規(guī)劃求得各時段發(fā)車次數Ni1和Ni2.模塊二 運營過程的模擬在這部分，我們采用時間步長法，根據假設一個時段內發(fā)車間隔時間ti相等，則

6、ti可由Ni確定，從而得到發(fā)車時刻表。按此發(fā)車時刻表模擬實際運行過程，目標是確定滿足時刻表的最小車輛數n，統(tǒng)計各項運營指標，搜索最優(yōu)調度方案。2.1 模擬子程序一：確定最小車輛數目n 根據“按流發(fā)車”和“先進先出”的原則，對起點站，在發(fā)車時刻應至少有一輛車可以發(fā)出（處于等待發(fā)車狀態(tài)）。若有多輛車，則先進站者先發(fā)車，其余車輛“排隊”等候；若無車可發(fā)，則出現“間斷”。完整的運營過程應保證車輛嚴格按時刻表發(fā)車，不發(fā)生間斷。設A13站和A0站分別有車場A和B,從車場中不斷有車發(fā)出，同時接受車進場，則車場中的車的數目是隨時間變化的狀態(tài)量。用Na和Nb來描述車場A和車場B中要滿足車流不間斷所需的最小數目，

7、分別搜索其在運行過程中的最大值，則所需最小車量數目n=Na+Nb。 模擬子程序二：統(tǒng)計各項運營指標確定各項運營指標，采用模擬統(tǒng)計的計算方法，對不同的運營指標進行定量計算，主要功能是通過定量分析運營指標來檢驗方案的可行性，以確定方案調整。注：由于車次與發(fā)車時刻一一對應，而車輛的隊列順序是不發(fā)生改變，因而對所需車輛進行統(tǒng)一編號，則對每一車次，與其對應的車輛編號是確定的，故我們直接對第k次車進行考察。我們統(tǒng)計的指標及其定義如下：平均滿載率 上行方向 01=下行方向 02=滿載率分布 可以由（k,j）確定。平均候車時間 上行方向T1=下行方向T2=滯留乘客候車時間分布： 假設乘客在第i站有k次滯留到k

8、+1次，他增加的等候時間為:ti(k), 其概率為（1-(B(k,i)-B(k,i-1)/(D(k,i)+C(k-1,i)，有k次滯留到更后的車次的概率可由此遞推，那么我們就可以得到滯留時間的分布。符號說明：B(k,j) 第k次車離開第j站時車上的人數；D(k,j) 第k次車到第j站時上車與下車的人數之差；C(k,j) 第k次車離開第j站時站臺上的滯留人數；（由于車已達最大滿載率以至乘客不能上車，故稱“滯留”）T(k,j) 為第k次車離開第j站時站臺上滯留者的滯留時間；(k,j)為第k次車離開第j站時的滿載率，（k,j）=B(k,j)/100 ;N1，N2為一天單程所發(fā)的車次總數；J1,J2為

9、單程站臺總數；2.3 模擬結果及統(tǒng)計指標分析我們選取參數k=0.8,0.85,0.9進行模擬運行，所得結論如表一。（表中只給出上行方向值）： 表一：模擬上行方向所得營運指標值參數k平均滿載率0平均候車時間T所需總車輛n總發(fā)車次數N10.868.7%3.88632700.8572.8%3.88632550.976.4%4.24622430.9580.4%7.2362231綜合考慮以上參數，當k0.9時，各項指標比較適當，平均滿載率較高，平均候車時間較短，所需車輛與總發(fā)車次數適中，所以我們選取k=0.9.下面我們給出k=0.9時的具體模擬結果及統(tǒng)計指標。結果：各時段內單程發(fā)車次數（見表二）總車次N

10、1=N2=243。 表二：k0.9時各時段中的發(fā)車次數時段566778899101011111212131314上行72841231311131111下行3122126161110910時段141515161617171818191920202121222223上行99192485542下行111319301911985各時段單程發(fā)車時間間隔由于一個時段內的發(fā)車間隔已假設為等距，所以由所得的車次很容易確定發(fā)車時間間隔。單程發(fā)車時刻表（數據量太大，故略）總車輛數 n=62 ,其中場A 存車57輛，場B存車5輛。統(tǒng)計指標：平均滿載率 上行方向 01=76.4% 下行方向 02=70.9%平均候車時

11、間 上行方向 T1=4.24 下行方向 T2=3.483. 調度方案我們由不同的理解得到兩種調度方案，其共同點是都必須形成完整的運營過程，使車流不發(fā)生間斷。3.1靜態(tài)調度方案：認為在該路線上運行的總車數固定不變，形成序貫流動的車流，依照“按流開車”和“先進先出”的原則，按發(fā)車時刻表發(fā)車。所需總車輛數目為62，其中從A13站的車場A始發(fā)的車數為57，從A0站的車場B始發(fā)的車數為5 。3.2動態(tài)調度方案：考慮高峰期與低谷期實際需要的車輛數目不同，為了滿足高峰期而求得的車輛數目必然大與其他時間需要的車輛數，即62輛車只在高峰期得到充分利用，造成資源浪費。我們認為公交公司可進行車輛動態(tài)調度，讓一些車輛

12、可以在特殊原因下進行修理調整，并節(jié)約運營成本。由此我們在保證車流不間斷的條件下，計算得出各個時段內實際所需的最小車輛數。如表三所示：（同時給出A、B車場的存車狀態(tài)，可以自由支配的車輛數目） 表三：動態(tài)調度中各時段的車輛數時段566778899101011111212131314車數93456483822201918A場51282001112119B場204142429303235時段141515161617171818191920202121222223車數172029424125171410A場91095625374348B場363224151512854由上表我們得出：在總車輛數目可變動的

13、情況下，所需的最大車輛數為7:008:00間的56輛，在非高峰期時所需車輛數目都較小，A車場和B車場都有較多車輛庫存著，可以根據實際情況挪作它用。公交公司只需按表中所給的每個時段的所需車輛數進行調度，按發(fā)車時刻表發(fā)車即可。單車場模型 模型的建立根據問題分析，公交營運方式按單車場組織后我們建立如下的帶軟時間窗口的單車型運輸問題的多目標優(yōu)化模型：目標函數 y1=min n y2=min Ni y3=min 約束條件 平均滿載率限制50%120%發(fā)車間隔時間限制ti 5 +5k; 0 i為早高峰期時；1 i為非早高峰期時。ti1,2,3注: 1.目標函數說明： 目標函數使總車輛數目最小，即使公司的投

14、資成本達到最小。目標函數使總車次數最小，即使公司的運營成本達到最小。目標函數是使所有顧客的平均不方便程度達到最小。2.約束主要是考慮到可操作性,發(fā)車間隔劃分到秒一級，公交司機是沒法把握的,故最小只能劃分到分一級,那么發(fā)車間隔就應是1分的整數倍2.模型的求解本模型是多目標、多約束的優(yōu)化模型，很難求出全局最優(yōu)解，所以我們先將多目標規(guī)化簡，再仿真模擬運營過程求解。轉化為單目標的求解思路如下：給出初始發(fā)車時刻表 模擬客運數據 運營 統(tǒng)計指標 結論人工分析客流分布（平均分布） 數據2.1 模型化簡化簡多目標問題，我們可以有三個出發(fā)點：分析各目標之間相關聯(lián)的數學關系，減少目標函數數目或約束條件數目。依限定

15、條件，針對具體數據挖掘隱含信息以降低求解難度。分析各目標權重，去掉影響很小的目標函數，從而達到簡化目的。分析目標與存在數學關聯(lián)，發(fā)現總車次越多，乘客不方便程度越小。因此y2與y3不能同時取最小值。我們認為為主要目標，故主要考慮目標函數。從具體數據可知，在上行方向7:008:00,A13站上車人數達3626人，平均每分鐘到達60人，A12站上車634人而下車僅205人，為客流量最大的時段，發(fā)車間隔時間至少需要2分鐘。由平均速度20公里/小時及環(huán)行距離，可得到此時至少需45輛車。.由以上分析將原模型簡化為： 目標函數：y1= min y2=min Ms.t. 同上運營過程模擬初始時刻表的產生方法原

16、則上初始時刻表可以隨機產生，然后模擬判斷搜索出較優(yōu)解，但這樣搜索量太大，且很難保證有一個收斂結果。因此我們采用人機交互的方式，首先分析數據得出比較合理的發(fā)車時間間隔的近似值，再在其附近搜索，產生初始時刻表。表四為初始發(fā)車時間間隔 表四：初始發(fā)車時刻表時段566778899101011111212131314ti1032388888時段141515161617171818191920202121222223ti8832310101010模擬運營過程，統(tǒng)計各指標由于模擬運營過程與雙車場模型大同小異，故我們在此不再詳述。結果及統(tǒng)計分析對仿真產生的多組發(fā)車時刻表進行模擬獲得最小的Y=5.6分,我們把這

17、一組解做為我們的局部最優(yōu)解,其結果(其中統(tǒng)計指標用來描述我們以怎樣的程度照顧雙方利益)如下:總車數理想處理平均速度得總車數為45輛，加2輛應急，為47輛；考慮高峰期車速小于20km/h，高峰期人流量大，是造成高峰期速度稍低于20公里/小時的主因，那么通過人流量數據和20公里/小時就可大致推算7：00-8：00速度約為18公里/小時。這樣高峰期的最小總車數45修正為50輛，加2輛應急最終為52輛。全天總車次 M=253×2=506次發(fā)車時刻表見表五 （用各時段發(fā)車間隔時間簡述） 表五：單車場各時段的發(fā)車間隔時段566778899101011111212131314ti102224666

18、8時段141515161617171818191920202121222223ti863237101010注：5：00-6：00只是一種統(tǒng)計劃分，首發(fā)車可以在5：00之前，也可在5：00之后。當然當不知道其它原則時可以假設首發(fā)車為5：00發(fā)。對單車場下行線始發(fā)為5：45與數據相吻合。5：00-6：00 上行線共855人上車；下行線共50人。其可能原因之一就是上行在5：00-6：00都有車可統(tǒng)計；而下行只在5：45-6：00中有車可統(tǒng)計統(tǒng)計指標：乘客平均候車時間 y3=5.6分平均滿載率 0=66.4%結論分析：由上面兩個圖表可見我們的調度方案基本上能滿足乘客候車時間的限制，高峰期乘客在5分鐘內

19、等到車的概率為92.9%,非高峰期乘客在10分鐘內等到車的概率為89.7%.調度方案：（見表六） 表六：單車場動態(tài)調度方案時段566778899101011111212131314所需車輛數104652462416161614時段141515161617171818191920202121222223所需車輛數14163046301410108 五、模型的進一步討論1.關于采集運營數據的討論由于我們假設乘客到站服從均勻分布，而實際中乘客到站時間不可能都服從均勻分布。特別是在高峰期的情況下，乘客到站時間的不均勻分布就會使模型結論誤差較大。我們建議以下幾種改進采集方式的方法：采取不等的統(tǒng)計人數的間

20、隔時間在高峰期的情況下，為削弱乘客到站時間的不均勻分布帶來的影響，可適當減小統(tǒng)計的間隔時間但統(tǒng)計時間加密應有一定限度。對客流量很小的時段，我們可適當增大統(tǒng)計的間隔時間，不必要每小時都統(tǒng)計一次。增加能反應有關滯留人數的統(tǒng)計數據。按相等到站人數來區(qū)分時間段的統(tǒng)計方法是統(tǒng)計達到一定到站人數時的時間點，即可由此判斷乘客到站的大概分布情況，有利于按其分布的疏密進行車輛調度，以更好的滿足乘客的需要。其缺點是不易確定相等人數間隔的大小，可操作性不高；其優(yōu)點是能較為準確地反映客流量的變化情況。2.對調度方案的進一步討論我們依據假設：各時段內乘客到站時間服從均勻分布，從而認為各時段內的發(fā)車時間間隔相等。我們在模

21、型的改進中，可考慮對不等的發(fā)車時間間隔進行模擬，并與等間距的結果進行比較。3.單車場調度方案與雙車場調度方案的選用由結果分析可知單車場調度方案減少了公司的前期投資成本；雙車場調度方案的運營成本小，更好的兼顧到乘客與公司雙方的利益。我們建議，在有雙車場的條件下選取雙車場調度方案更好。當需進行路線規(guī)劃，需要選取單車場或雙車場時，建議根據實際所需成本來選取方案。 六、模型的評價本文的優(yōu)點如下：模型的主體是采用時間步長法，模擬生成的發(fā)車時刻表的實際運行過程，準確性高，容量大，邏輯性嚴格，計算速度快，具有較強的說服力和適應能力。定義了能定量衡量我們的調度方案對乘客和公交公司雙方利益滿足程度的統(tǒng)計指標。在

22、求最少車輛數時，將兩個車場看作兩個發(fā)射源，通過對兩個車場的存車狀態(tài)的實時模擬，形成不間斷的運營過程，從而求得所需車輛數目。本文的缺點是：對于運營數據的采集方式，只給出了一些原則和想法，沒有經過仿真驗證。對于乘客到站的分布，直接假設為均勻分布，沒有對其他分布的情況再作討論。參考文獻：1：錢湔.運籌學M.北京：科學出版社，20002：肖雁，符卓，李育安.帶軟時間窗口的車輛路徑問題及其應用前景探討J.中國運籌學會第六屆學術交流會論文集，下卷，634638 STUDY ON THE SCHEDULING PROBLEMDONG Qiang，LIU Chao-hui，MA Yi Instructor：WU Meng-da（National Uni