市區公車排班與即時機動調度之研究－以新竹客運為例

Abstract

本研究探討有關市區公車排班以及即時機動調度兩個課題，在市區公車 方面，在車隊大小與營運策略以及需求不變的情況下，針對市區內公車之 排班問題，即在一起迄點相同之公車路線，求解全時段單一班距及多時班 之最佳時刻表。在行車隨機系統中車輛容量固定､旅客在等候線等候時有 時間有上限(Reneging)､旅客到達過程服從非均勻波以松過程､旅客下車 服從二項式分配､公車站間旅行時間服從韋伯分配以及旅客上下車時間為 一常數。本研究將目標函數定義為客運公司之利潤，即收入減成本，其中 收入為票價收入，成本為營運成本加上乘客等候成本。模式分為兩種：單 一班距及多班距。針對單一班距，本論文以隨機尋根問題 (Stochastic Root Finding Problem; SRFP) 之相關求解方法(Bounding Retrospective algorithm; Bounding RA) 為基礎並略做修正， 使其應 用於求解排班問題之最佳班距。在多班距最佳班距求解上，則是在各時段 內利用單一班距所發展之隨機最佳化方法求解最佳發車班距。在發展排班 問題之最佳班次之演算法上，根據本研究對目標函數之特性探討發現目標 函數為一不連續的函數，而其不連續點發生在發車頻率變動之時，因此本 研究先找出最佳發車頻率，然後在最佳發車頻率中找最佳發車班距。以新 竹客運之一路線的試調資料為依據，對本研究所發展之隨機最佳化方法做 測試，結果發現在旅客到達過程為均勻時，本研究發展之方法能保證找到 最佳班距，然在旅客到達過程為非均勻以及等候成本過大時，演算法對起 始解敏感，然在給定適當之起始解，皆能找到最佳發車班距。班表規劃出 來之後，在實際派車調度時常發生塞車或突發狀況導致即定之班表無法按 時發車，因此針對實際派車時之突發狀況，本研究發展一公車即時機動調 度系統，系統中主要是藉由GPS衛星定位訊號獲知目前車輛所在位置，並 根據即時道路行駛速度計算出車輛回站時間，當發現車輛無法在預定的時 間回來執行下一個班次時，即啟動機動調度模式，產生調度方案供調度者 參考。在機動調度模式，主要處理當站內皆無任何預備車可用時，機動調 度其它路線之車輛來支援發生擾動的班次。在模式中根據使用者給定之系 統回復時間定義出機動調度路網，根據此一路網，我們將機動調度問題轉 換成一集合分割的問題並發展一以Column generation為基礎的最佳化方 法來產生可行之調度方案。在調度方案的產生上，本研究允許班表延誤的 情形，因此增加延誤節點至機動調度路網之中。針對此一路網，本研究利 用各節點之成本/對偶值､時間距以及延誤成本定義出各節點間之成本後 求解最短路徑，所得之最短路徑即為一可行之調度方式。以實際班表模擬 測試發現本研究所發展之機動調度模式能迅速地產生最佳調度方案，而與 人工調度的情形，本研究所發展之機動調度模式在非尖峰時段能增加80% 的營運效率，在尖峰時段中則是改善了17%。 This thesis is study on urban bus scheduling problem and real time reschedulin-g problem. On urban bus scheduling problem, fixed fleet size and captive dema-nd are considered. Finding optimal single headway model and multiple headway model are discussed in this thesis. In stochastic bus system, passenger rene-ging, non-homogeneus arrvial process , weibull travel time and constant passen-ger upload/depart time are considered.The object function is define as profit of bus company. It equals ticket revenue minus operating cost and passengers t-otal waiting cost. Single headway model and multiple headway mathematics model are proposed. Finding optimal headway is a stochastic optimization problem. F-or single headway model, the algorithm of stochastic optimization base on boun-ding RA.。Same algorithm is also applied to multiple headway model in each tim- e interval..According to object function is not discontinuous and disconnected point is occurred on frequency changed. Two stage optimization is proposed. I-n the first stage, optimal frequency is found. In the second stage, optimal he-adway is found in optimal frequency.Empirical results show that modified bound-ing RA can find optimal headway in homogeneous arrival process. In non-homogen-eous arrival process and higher fare/ waiting cost ratio, algorithm is sensitiv-e with initial solution.Although schedule is setuped, traffic conjection and u- nexpected situation that cause journey can not be dispatched on given time are often happened. For these situation, real time bus dispatching and rescheduli-ng system are developed in this thesis. In system, real time bus location can be achieved by GPS signal and expected return time of bus is calculated by rea-l time travel speed of each road. When perturbation journey occurred, system w-ill active bus rescheduling module automatically and provides optimal dispatch-ing alternatives. Rescheduling module is deal with the situation that there is no reserved bus in bus station. It will dispatch bus belonged to other route t-o run perturbation journey. In module, rescheduling network model is constru-cted by system recovery time given by dispatcher. Based on the network, SPP(Se-t Partition Problem) is formulated. For the SPP, a column generation approach is proposed to generate available duties. Delay alternative is considered in ge-nerating available duties, thus delay nodes of each journey are appended to re-scheduling network. For the argumentation network, node-to-node cost matrix is calculated. Arc cost is define as sum of node cost/dual price, time distance and delay cost. After cost matrix is constructed, algorithm find the shortest path for given origin and destination. Each path is an available duty.Empiric-al result show that the column generation algorithm can generate optimal resch-eduling alternative efficiently. Comparing to manual dispatching, rescheduling module can improve 80% bus usage rate in un-peak period, 17% in peak period.