客運車輛機動調度演算法之研究

Abstract

在公車營運上，業者對於排班與調度最大的問題，是如何利用有限的資源對其做合理的調度，以提高服務品質、確保營運績效。在實務營運上，有很多因素會使得原定班次受到擾動，例如人員請假、車輛維修、旅客需求變動等，調度員則必須立即將可用車輛做適當的調度。 因應班次受擾動的調整，不只影響部分的班表，還可能會牽動其他班次及其他車輛的班表，進而造成整個班表的擾動，不當的調整將會影響業者營運績效及服務水準，故當有事件發生時，如何有效地調度可用車輛來解決擾動班次，降低營運損失，實乃當前業者所普遍關切之課題。 本研究的目的在改進傳統實務的作法，考慮車輛數及其他資源之限制，發展一客運車輛機動調度系統，當發現車輛無法在預定的時間回來執行下一個任務時，即啟動機動調度模式，依照當時可用之車輛產生調度方案供調度者參考。 在調度模式中，本研究將機動調度問題轉換成一集合分割的問題，並發展一以變數產生法（Column Generation）為基礎的演算法來產生可行的調度方案。在調度方案的產生上，本研究利用各節點之成本、對偶值、時間間距、延誤成本、路線變動成本求解最短路徑，所得之最短路徑即為一可行之調度方式。 為測試系統的實用性，本研究模擬各種班表情境，作實例測試與修正，並針對所有可調參數做敏感度分析。實務上客運業者可以針對其調度方案與考量之不同，設定較合適之可調參數值，以求系統能符合業者的需求。

In order to improve the quality of service and insure the performance of operations, the most important thing in bus dispatching is how to maintain established schedule. In reality, the bus company must readjust the schedule under abnormal circumstances such as traffic jam and mechanical failures. Readjusting the schedule may inference the whole schedule. Inappropriate adjustment will affect the performance of operation and the quality of service, so how to dispatch bus effectively becomes an important task. The purpose of this study is to adapt a bus dispatching algorithm to improve traditional methods. A column generation approach is proposed to generate available duties. For the vehicle scheduling network, node-to-node cost matrix is calculated. Arc cost is defined as sum of node cost, dual price, time distance, delay cost, and route changed cost. We develop a Multi-Labels Correcting Method to solve the shortest path problem with resource constraints. Each path is an available duty. In order to evaluate the practicability of the algorithm, we test how the real-time bus dispatching algorithm apply in the real world. Second, we establish different situations of schedule. Apply the solution algorithm to solve the problem. Finally, we perform sensitivity analyses by adjusting parameters on the model.