考量隨機需求下公車路線與撥召服務之整合規劃

A Stochastic Programming Model for Integration of Bus Route Design and Dial-a-ride Scheduling

施欣慧(Hsin-Hui Shih)

指導教授 ： 朱致遠

國立臺灣大學/工學院/土木工程學研究所/碩士(2018年)

https://doi.org/10.6342/NTU201800075

摘要

由於偏遠地區之運輸需求在空間上及時間上較為分散，使用單一運具無法有效服務當地之起訖點需求，因此，本研究結合公車路線及撥召服務，設計整合之規劃模式，以滿足偏遠地區隨機旅次需求。公車為一固定路線、班次之服務，撥召服務較為彈性能依旅客需求改變路徑，採公車結合撥召服務的彈性運輸服務模式，將能提高偏遠地區交通運輸效能。本研究提出整合兩階段之隨機規劃數學模式，第一階段之主線公車路線及時刻表問題以集合分割(Set-partitioning)問題建模，第二階段之撥召服務則是以時窗限制下收送貨之配送路線問題(Pick-up and Delivery Problem with Time Window)描述之。為提昇求解效率，本研究採用兩種演算法，分別應用在兩階段，第一階段以鄰域搜尋法求解主線公車路線及時刻表之集合分割問題，之後以貪婪演算法及2-opt改進法發展混合啟發式演算法以求解撥召服務營運方式。最後，以兩案例比較測試結合公車及撥召服務與否對公共運輸服務之影響，結果顯示，有結合撥召服務的整體規劃能在各種情境下服務近乎全部之需求，未結合撥召服務之規劃，雖能產生一條服務較多旅客之公車路線，剩下之需求即使再提供撥召服務也無法滿足，兩案例證明針對偏遠地區之運輸規劃，若以公車結合撥召服務，能提高運輸效能，且能最小化未能被服務之旅次需求數，本研究最後調整撥召服務之參數進行敏感度分析，並驗證求解過程之正確性，以供未來偏遠地區路網規劃及結合運具之依據。

關鍵字

隨機規劃 ； 大眾運輸 ； 撥召服務 ； 整合規劃 ； 集合分割 ； 鄰域搜尋法

並列摘要

This study integrates bus and dial-a-ride (DAR) services to address stochastic demands in the remote areas. Fixed services, such as buses, provide high capacity, but the route and schedule are fixed. Flexible services, such as dial-a-ride, is door-to-door and the route and schedule vary with the demands but have lower capacity. The integration of fixed and flexible services, which are bus and dial-a-ride, enhances the transportation efficiency and decreases the waste of resources. A 2-stage stochastic mathematical model is formulated. Initially, a fixed bus line with schedule is constructed in the first stage as a set-partitioning problem. A DAR problem is designed in the second stage as a pick-up and delivery vehicle routing problem with time window (PDVRPTW). A hybrid algorithm is developed to solve the stochastic programming problem. A route-enumeration tree search algorithm that is based on the neighborhood search is developed to solve the first stage problem (a fixed bus line). For each solution of the first stage problem, a hybrid heuristic algorithm including greedy algorithm and 2-opt improvement is proposed to solve the second stage problem (DAR problem). An illustrative example and a real case in Hengshan Township are presented to validate the proposed methodology. It is shown that the integration of bus and DAR can effectively prevent the isolation of demands. Solving the problem with DAR service could generate integrated services of bus and DAR that serves the majority of the demands under each scenario. By contrast, without considering DAR, the demands that are not served by buses are very difficult to serve by DAR. The sensitivity analysis for DAR parameters is also conducted, including the capacity of vehicles, maximum driving distance, and the number of vehicles.

並列關鍵字

stochastic ； public transit ； dial-a-ride ； integration ； set-partitioning ； local search ； neighborhood search

參考文獻

[23] 蘇昭銘, 王張煒, & 何文基. (2015). 中小型鄉鎮接駁公車之路線設計方法. 運輸計劃季刊, 44(4), 313-332.

[1] An, K., & Lo, H. (2014). Service Reliability-Based Transit Network Design with Stochastic Demand. Transportation Research Record: Journal of the Transportation Research Board, (2467), 101-109.

[2] An, K., & Lo, H. K. (2016). Two-phase stochastic program for transit network design under demand uncertainty. Transportation Research Part B: Methodological, 84, 157-181.

[3] Baaj, M. H., & Mahmassani, H. S. (1991). An AI‐based approach for transit route system planning and design. Journal of advanced transportation, 25(2), 187-209.

[4] Balinski, M. L., & Quandt, R. E. (1964). On an integer program for a delivery problem. Operations Research, 12(2), 300-304.