公車路網加班車派遣與路線延駛決策最佳化

Optimization of decision-making in non-scheduled bus dispatching and route extension of a bus network

蕭妤安(Yu-An Xiao)

指導教授 ： 朱致遠

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

https://doi.org/10.6342/NTU202002390

摘要

當固定班次公車，面對非常態性的乘車需求暴增問題時，需要即時控制策略的輔助，因此本研究針對此問題，建立一個數學模式，並站在公車業者的角度，考量車輛調度問題，提前做出能帶來利潤的即時控制策略。
本研究將延駛(繞至新增的需求站點)與加派公車決策納入模式中，透過建立多層乘客與公車的時空路網，將多場站、多路線，以及兩個即時控制策略納入路網中，並同時考量乘客需求、車輛調度、業者利潤，以及台灣政府公車補助細則，接著利用雙層數學模式，搭配啟發式方法，有系統性的求出即時控制策略解。
為提升雙層數學模式的求解效率，本模式建立兩個區域搜尋求解邏輯，在第一區域搜尋邏輯中，求解不同權重下之上層問題(屬多目標混合整數規劃模式)，以取得第二區域搜尋的初始解，並透過第二區域搜尋演算法，在有限的時間內提升求解結果。本論文研究的核心價值在於即時產生可以為業者帶來利潤的即時控制策略解，並同時紓解即時暴增的乘客需求。

關鍵字

公車即時控制策略 ； 多場站車輛調度問題 ； 時空路網 ； 雙層數學模式 ； 多目標混和整數規劃模式 ； 區域搜尋演算法

並列摘要

Scheduled buses need real-time control strategies (RTCSs) to cope with sudden demand increase. The most important novelty of the proposed methodology is that the multi-depot vehicle scheduling problem (MDVSP), the principle of passenger getting on buses, and the subsidy regulation from the government in Taiwan are considered.
This research considers non-scheduled buses and extension bus routes in the model. At first, layers of bus and passenger time-space networks are constructed. Next, multi depots, multi routes, and two types of RTCSs are considered in time-space networks. Bi-level mathematical programming with a heuristic solution method is adopted to find a solution systematically in a limited time.
To improve the efficiency of solving bi-level mathematical programming, this research proposes a solution method that includes two local search (LS) algorithms. In the first LS, the upper-level problem, which is a multi-objective mixed-integer programming (MOMIP) problem, is solved given different weights and a fine initial solution for the second LS can be found. In the second LS, an improved non-inferior RTCSs is found in a limited time. RTCSs that are timely generated by the methodology could bring profits to the bus company and alleviate the problem of passenger demand surge at the same time.

並列關鍵字

Real-Time Control Strategy ； Multi Depots Vehicle Scheduling Problem ； Time-Space Network ； Bi-Level Mathematical Programming ； Multi-Objective Mixed-Integer Programming ； Local Search Algorithm

參考文獻

Berrebi, S. J., Hans, E., Chiabaut, N., Laval, J.A., Leclercq, L. (2018). Comparing bus holding methods with and without real-time. Transportation Research Part C, pp. 197-211.

Zuo, Z., Yin, W., Yang, G., Zhang, Y., Yin, J., Ge, H. (2019, Apr 1). Determination of Bus Crowding Coefficient Based on Passenger Flow Forecasting. Journal of Advanced Transportation, p. 12.

BARTHOLD, J., Donald, D. (2011, October 21). A self-coordinating bus route. Transportation Research Part B, pp. 481-491.

Cai, D. (2013). WIT Transactions on Ecology and The Environment. Retrieved from WIT Press: www.witpress.com

Cortés, C., Jara-Díaz, S., Tirachini, A. (2011, 2 2). Integrating short turning and deadheading in the optimization of transit services. Transportation Research Part A, pp. 419-434.