區域公交的多車場車輛調度優化

徐瑜婷，宋 瑞，鄭 鋰

（北京交通大學交通運輸學院，北京 100044）

區域公交的多車場車輛調度優化

徐瑜婷，宋 瑞，鄭 鋰

（北京交通大學交通運輸學院，北京 100044）

在運營企業費用最少的基本模型基礎上，以乘客等待費用最少為目標函數討論多車場車輛調度問題，并建立相應模型。基于逆差函數算法對模型求解，設計兩種方法進行求解:一種是人工插入空駛車程，求解過程中加入乘客等待時間的限制;另一種是通過由逆差函數為基礎設計的PT-Manager仿真軟件進行算法優化，對實際案例進行參數標定以及求解。結果表明:該模型逆差函數算法求解過程簡單、結果直觀，PT-Manager仿真軟件能夠幫助公交調度人員進行車輛調度及優化，對現有的車輛調度以及多車場的發展有一定的指導意義。

多車場調度;逆差函數;車輛調度;PT-Manager

0 引言

解決現代城市交通擁堵問題的最主要方法之一是大力發展城市公共交通，而運營調度規劃是公共交通的主要難點之一。而公共交通規劃的運營調度分為客流需求預測、時刻表的編制、行車計劃、人員的配置等4個方面，由此可見，公交車輛調度是公交規劃及運營管理中非常重要的環節。

公交車輛調度主要分為多車場車輛調度（Multiple Deport Vehicle Scheduling Problem，簡稱MDVSP）和單車場車輛調度。其中，單車場的車輛只能在固定的車場間運行，多車場調度車輛可以在多個車場間被調用，并允許車輛分布于多個車場。單車場車輛調度具有簡單、便于管理的優點，多車場車輛調度則更有利于運輸資源的合理和優化調度，更符合社會可持續發展的要求。多車場車輛調度以一個區域內的車場整體為研究對象，公交運營組織和調度的區域大可包含整個城市的公交運營線路，小可只包含2～3條單線模式的運營線路，具體的每一個區域大小的確定主要是以整個區域的運營效率為最高這個標準來確定的。研究表明，通過對區域內公交車輛的統一管理，可以大大提高車輛利用率，降低運營成本［1］。我國現有的車輛調度多為單車場調度問題，車場對車輛的規劃管理以每個車場為目標，為提高公交運營效率減少道路擁堵程度，筆者以區域公交車輛調度為研究對象，探討適合我國實際情況的區域公交調度。

國內外研究學者對多車場調度問題進行了大量研究，Ceder，等［2-3］以公交網絡中兩輛公交車相遇的次數最大及乘客等待時間最少為目標，對公交區域同步換乘進行了研究。在此基礎上，A.Haghani，等［4］引入站點換乘權重與線路換乘吸引度，以乘客總換乘等待時間最少為目標建立了公交區域調度模型。此后，D.Huisman，等［5］提出了用插入最小空駛車程的逆差函數的方法來分析車輛的調度問題。鄒迎［6］在對北京公交區域運營組織與調度系統初步探討中，提出了多線路車場調度問題。石琴，等［7］提出了基于換乘優化的公交區域調度模型。此外，張欣偉，等［8］研究了在提供公共交通信息條件下公交換乘時間最短的調度問題，并提出了線性規劃模型。

車輛調度求解算法以智能算法居多。采用遺傳算法、禁忌搜索算法、蟻群算法等智能搜索算法解決車輛調度問題，能覆蓋大區域的車輛調度問題，通常能計算3個及以上車場數量的區域車輛調度問題，最終的最優解通過計算機大規模計算得出，質量較高且更符合實際情況。但就中國實際情況考慮，基于逆差函數算法的仿真軟件能得出簡單易懂的階躍函數，能計算出各車場各個時刻的車輛數。在插入空駛車程，即當運營中插入擾動情況時，智能算法經過復雜冗長計算才能得出結果，而逆差函數只需調度人員對圖形進行插入，操作簡單，出錯率低。

筆者旨在建立以企業花費最少、以乘客在各車場的等待時間最短以及等待費用最少的目標函數。在算法的運用中，首先運用遺傳算法、禁忌搜素、模擬退火等智能算法［9］得到初始解，然后采用逆差函數插入空駛車程減少車隊規模進行解的優化調整。這一過程中逆差函數算法搜索收斂性以及求解的優質性劣于直接采用智能算法得出最優解，但是以模擬仿真為基礎的逆差函數便于實際仿真，能對實際情況優化仿真，算法得出的結果易于處理，每插入空駛車程，都能對結果進行動態輸出，簡單易懂，易于操作和理解。

1 問題描述與建模

1.1 問題描述

公交時刻表提供了各公交班次信息，包括出發時間和到達時間等，如圖1。圖中，班次i的出發時間為Si，到達時間為ei，班次i結束時刻到班次j開始時刻之間的運行時間為ti，j。目標車輛在完成班次i后可繼續進行班次j的必要條件為:ei+ti，j≤sj。如果車輛執行上述的班次，則連接兩者之間的班次常常稱為空駛班次，此時的班次為不載乘客班次。安排空駛班次的目的是減少整個車隊的規模。反之，如果班次j的到達時刻加上i至j班次間的運行時間小于班次i的出發時刻，則可以用班次j的車輛繼續完成班次i。

圖1 插入空駛車程示意Fig.1 Insert deadheading trips diagram

每輛車可以連續完成一系列的班次，形成車次鏈（圖2）。定義車輛從該車場駛出的第1班次為出場班次，與之相對應，當車輛執行完相應的調度任務，回歸車場所完成的最后一次運輸稱為入場班次。一輛車的車次鏈包含出場班次、入場班次和一系列的空駛車次以及常規班次。而這些班次的對應費用稱為出場費用、入場費用，以及空駛費用。

圖2 車次鏈形成Fig.2 Train chain diagram

在已知行車時刻表的基礎上，可用逆差函數求解多車場車輛調度問題。逆差函數是一個階躍函數，用以表示的是每個車場當前的車輛數，當車輛從車場出發執行一個班次時，階躍函數的函數值增加1，當車輛回到車場時，其函數值減少1。把所有車場的函數值相加，得到總的階躍函數，即為該研究對象區域所需要的車隊規模的大小。在每個車場的階躍函數的構建過程中，需要對應線路的時刻表數據，以橫軸表示時刻表的時間，縱軸表示車輛數量。某線路某時刻由車場出發的總班次數與總到達班次數之差見式（1）:

式中:k為車場編號，k=1，2，3，…，K（K表示研究區域內的車場總數）;t代表研究時刻;S代表研究時段內對應時刻表中所有班次的集合;d（k，t，S）表示從開始時刻到t時刻的車場k出發總班次數與總到達班次數之差;s（k，t，S）表示所有班次集合S中從開始時刻到t時刻之間的車場k到達的車輛總和;e（k，t，S）表示t時內研究的所有的班次集合S中從開始時刻到t時刻之間的車場k內到達的車輛總和。

設D（k，S）為研究時段t內車場k的總班次之差d（k，t，S）的最大值，如式（2）:

多個車場的逆差函數值之和就是總的車輛數，設全局逆差函數（即t時內的所有車場逆差函數之和）為g（t，S）。g（t，S）在t時內的最大值用G（t，s）表示。插入空駛班次的條件為:當研究區域達到最大值G（S）的時刻為t*，在t*之前執行一個空駛班次DH1。如果這趟空駛班次在時刻由車場u發出，在時刻到達車場v，那么必須滿足條件。當完成空駛車次的插入后，時刻表對應的車次時間變為S1=S+DH1。如果在sv1時刻，車場v達到其容量極值區間，則存在t*之前或是恰在t*達到極值區間的情況有［10］:

只有式（5）的情況是唯一可能減少需用車輛數量的情況。所以在車場v到達極值區間的時刻之前可在車場u，v之間插入第一個空駛車程，形成第一個空駛班次DH1。

在插入空駛班次DH1以后，為避免車場u在到達極值區間的時候車輛數量不夠的情況發生，也為了減少車隊規模，在車場u極值區間之前插入新的空駛班次以消除車場u的需用車輛數的變化。設定執行這次空駛的班次為DH2，自車場q出發到達車場u，這里的車場q可以是車場v，也可以是其他車場，發車的到達區間為［，］，其中，。

1.2 模型建立

區域公交車輛調度模型的目標函數多是企業花費費用最少。實際上，除了考慮企業的運營效益外，還要考慮乘客的滿意度。筆者加入乘客等待時間費用來體現對乘客滿意度的考慮。

模型具體形式如下:

式中:cq∈［x，y］，q∈w;x，y為任意值，且滿足x＞y;av，p表示路徑p是否包含點v∈B，若包含，則av，p=1，反之av，p=0;yp表示與每條路徑相關聯的0-1變量，若有車次通過p，則yp=1，反之yp=0;cp表示包含弧的費用;Ωk表示車站場k出發，經歷集合B中一些節點后返回相同車場的路徑集合;cq表示車場k的乘客q單位等待費用;q表示在車場k等車的乘客;W表示各個車場等車乘客總體集合;dk表示車場k的車輛數容量;?q表示車場k的乘客等待的權重。

式（7）為目標函數，其中，cpyp表示企業的花費費用，cqyp?q表示乘客的等待費用。約束條件中，式（8）保證每個班次j∈B只能由某一車場的1輛車完成;式（9）表示車場車輛數不超過車場的容量;式（10）限制車輛在路徑上運行與否，取值只能是“0”或“1”;式（11）限制所有乘客在各車場的等待權重之和為1。

2 求解算法

2.1 求解過程基本介紹

逆差函數算法是通過PT-Manager軟件來實現的。首先采用文獻［10］中的方法實行鄰域搜索得出初始解，然后用逆差函數算法對初始解進行優化，采用仿真軟件進行仿真分析，在模型約束中加入乘客等待時間的容忍度進行算法計算得出最終解。

2.2 逆差函數算法

逆差函數算法是采用圖形方法求解每個車場實時的車輛情況。通過插入空駛車程來減少整個研究區域的車隊規模，得到車隊規模下限。

用逆差函數求解多車場問題步驟如下:

1）根據固定行車計劃下確定的時刻表，得出任意車次的出發車場u、到達車場v以及兩車場之間的運行時間t，分別得出任意車場k的逆差函數圖d（k，t，S）。

2）比較各車場的逆差函數圖，選擇容量極值區間最長的車場a為研究對象。

3）選擇最先有車到達即最先到達最大值的車場b，若該時刻車場b到達車場a的空駛時間大于車場a下一班次的發車時間，則插入空駛車程1，反之依次查看各車場是否能插入空駛車程到車場a。

4）重復上述第2）步直到a車場無法再插入空駛車程減少車隊規模為止。

5）若剩余各車場由于插入空駛車程到a，使得自車場的車隊規模增加，則選擇從別的車場間插入空駛車程保證該車場車隊規模不變，依次調整直到除了a車場以外其余車場車隊規模不變。

6）依次檢驗所有車場是否能插入空駛車程，直到所有車場檢查完成后，轉到第7）步，否則轉到第3）步。

7）算法結束，得到插入空駛車程的解。

2.3 PT-Manager仿真軟件求解

在PT-Manager仿真軟件上執行上述逆差函數算法。PT-Manager仿真軟件是由Altdoit Software Solutions公司開發運行的仿真軟件，針對逆差函數求解多車場車輛調度問題進行仿真。通過直接輸入相關時刻表、車次信息得出各車場逆差函數d（k，t，S）以及全局逆差函數g（t，S），進一步通過空駛信息輸入，得出空駛車次。具體步驟為:

1）根據時刻表輸入每個車次的運行信息，包含車次名稱、出發車場、到達車場、出發到達時間等。

2）確認輸入所有車次信息后，運行程序，得出各個車場的逆差函數圖形。

3）選擇空駛車程的輸入。有兩種方式可供選擇，第1種方式是直接得出各車場間的空駛時間及空駛里程，輸入到軟件的空駛矩陣中，自動生成空駛車次，轉到第3）步;第2種方式是依據各車場的逆差函數手動輸入每一空駛車程車次名稱，出發車場、到達車場、兩車場間空駛時間，不斷調整，保證每個乘客在每個車場等待時間不超過模型建立中約束條件（11）以及乘客能容忍的在車場之間的等待時間的要求，直到不能再減少車隊規模時，轉到第5）步。

4）得到空駛矩陣進行運行，輸入乘客能容忍的最長等待時間，運行得出空駛車次。

5）依據得出的空駛車次進一步修改時刻表，優化時刻表，減少整個研究范圍的車隊規模。

6）輸出插入的空駛車程和時刻表變化的情況，得出插入空駛車程前后的時刻表，比較優化結果。

7）由實際情況得出各車場乘客等待權重，計算插入空駛車程前后的目標函數值，比較分析空駛車程插入的合理與否。

3 案例分析

選取北京市公交線路l1，l2，l3，l4，分別代表 320路、309路、運通105路和103路，進行多車場車輛調度的實例分析。這4條線包含3個車場A、B和C，公交線和車場布置如圖3。

圖3 區域車場間的位置信息及其線路信息Fig.3 Position and road information about multiple depot diagram

3.1 參數設置及數據輸入

設定線路的單位運行費用c320=3，c65=6，c運通105=4;在仿真軟件中，取各車場乘客的等待權重αq值相同，分別為αA=αB=αC=1/3;以及取值αA=0.25，αB=0.3，αC=0.45，同時cq=5，求解過程如圖4。圖4（a）代表A車場插入空駛車程前車場逆差函數;當1.2節模型中目標函數的y取值為10 min時，運行得出的空駛車次見圖4（b）。

圖4 A車場插入空駛車場前后逆差函數Fig.4 A depot’s DF before/after insert deadheading diagram

3.2 優化結果分析

經過求解得到插入空駛車程如表1。

表1 研究區域插入空駛車程的車次Table 1 Timetable after insert deadheading trips

在插入的空駛車程和時刻表變化的情況，得出插入空駛車程前后的時刻表，如表2。將參數值代入目標函數（7）中，取3車場等待權重相同得出，插入空駛車程前目標函數值為96.00;插入空駛車程后目標函數為 59.33。而取值 αA=0.25，αB=0.3，αC=0.45，得出插入前后的目標函數值分別為104.32及76.48。

表2 研究區域各車場優化前后車隊規模Table 2 Vehicle quantity before and after inserting deadheading trips

從不同車場的取值權重可以看出，雖然目標函數值變大，但是對于每個車場來說，對乘客的重要程度有一定改變，更符合實際情況，能充分考慮每個車場的乘客等待滿意程度。由于乘客的等待費用的不同可能會導致不同車場的乘客要求不同，而造成不同車場權重的不同。

從相同取值權重的車場插入空駛車程前后可以看出，在原有的時刻表（固定行車計劃）的基礎上，得出的各個車場逆差函數，在PT-Manager仿真軟件中，分別輸入各車次的運行狀態，加入乘客的等待時間的函數后，求出插入的空駛車程，發現車隊規模由原來的18輛減少為11輛，同時目標函數降低38.2%。把上述插入空駛車程的結果帶回時刻表，可對時刻表進行調整優化。

4 結語

以運營企業成本費用和乘客等待費用之和最小為目標函數，建立了多車場車輛調度模型。利用人工和PT-Manager仿真軟件求解，詳細給出了求解步驟。結合北京實際運營進行算例分析，采用PTManager仿真軟件求解，考慮不同車場乘客等待權重不同即乘客的滿意程度不同，結果得到研究區域整體的車隊規模減少了7輛，降低企業的運營成本，同時乘客在每個車場的等待時間不超過10 min，提高乘客滿意度，使得各車場之間車輛銜接更合理，證明了模型合理性。

（References）:

［1］ 劉志剛，申金升，楊威.基于禁忌搜索的公交區域調度配車模型研究［J］.交通運輸工程與信息學報，2007，5（4）:63-67.

Liu Zhigang，Shen Jinsheng，Yang Wei.Study on multiple bus vehicle dispatching based on Taboo research［J］.Transportation Engineering and Information Technology，2007，5（4）:63-67.

［2］ Ceder A.Methods for creating bus timetables［J］.Transportation Rearch:Part A，1986，21（1）:59-83.

［3］ Ceder A，Golany B，Tal O.Creating bus time tables with maximal synchronization［J］.Transportation Research:Part A，2001，35（10）:913-928.

［4］ Haghani A，Banihashemi M，Chiang K H.A comparative analysis of bus transit vehicle scheduling models［J］.Transportation Research:Part B，2003，37（4）:301-322.

［5］ Huisman D，Freling R，Albert P M，et al.A robust solution approach to the dynamic vehicle scheduling problem［J］.Transportation Science，2004，38（4）:447-458.

［6］ 鄒迎.公交區域調度行車計劃編制方法研究［J］.交通運輸系統工程與信息，2007，7（3）:78-82.

Zou Ying.Study on bus regional scheduling travel plan organizing method［J］.Journal of Transportation Systems Engineering and Information Technology，2007，7（3）:78-82.

［7］ 石琴，覃運梅，黃志鵬.公交區域調度的最大同步換乘模型［J］.中國公路學報，2007，20（6）:90-94.

Shi Qin，Qin Yunmei，Huang Zhipeng.Maximal synchronous transfer model of bus regional dispatching［J］.China Journal of Highway and Transport，2007，20（6）:90-94.

［8］ 張欣偉，張貴蘭.城市公交線網規劃體系研究［J］.交通企業管理，2008，12（5）:62-64

Zhang Xinwei，Zhang Guilan.Study on urban bus routes planning system［J］.Transportation Enterprise Management，2008，12（5）:62-64.

［9］ Zhang Qiao，Xu Xu，Liang Yanchun.An improved artificial immune algorithm with a dynamic threshold［J］.Journal of Bionic Engineering，2006，3（2）:92-97.

［10］賽德爾，關偉.公共交通規劃與運營理論、建模及應用［M］.北京:清華大學出版社，2010.

Ceder A，Guan Wei.Public Transport Planning and Operation of the Theory，Modeling and Application［M］.Beijing:Tsinghua University Press，2010.

Optimization of Vehicles Dispatching Model for Multiple Depots in Regional Traffic

Xu Yuting，Song Rui，Zheng Li
（School of Traffic＆ Transportation，Beijing Jiaotong University，Beijing 100044，China）

On the base of the fundamental model whose objective was to minimize the company’s costs，multiple depot dispatching problem was discussed and then the corresponding model was established，in which minimizing passengers’waiting expense was considered in the objective function.Then deficit function was used to solve the objective function，which can be solved in two different ways:firstly，manual work was used to insert the deadheading trips to restrict the passengers’waiting time;secondly，PT-manager simulation software which was built on the base of deficit function was introduced to simulate and analyze.In order to make a statistic explore the actual data was introduced.The results proved that the using deficit function to solve the proposed model is simple and accurate.PT-manager simulation software could provide guide and optimization for bus dispatching staff，which also could provide referential significance to the current bus dispatching and the development of multiple depot dispatching.

multiple depot dispatching;deficit function;vehicle dispatching;PT-Manager

U280

A

1674-0696（2013）02-0258-05

10.3969/j.issn.1674-0696.2013.02.19

2012-05-31;

2012-09-21

中央高校基本科研業務費專項基金項目（2009YJS044）

徐瑜婷（1988—），女，重慶忠縣人，碩士研究生，主要從事城市交通規劃與管理方面的研究。E-mail:11121015@bjtu.edu.cn。