透過您的圖書館登入
IP:3.214.184.69
  • 學位論文

公車多班距時刻表設計的隨機最佳化問題

Stochastic Optimization for Computing Bus Multiple Headways

指導教授 : 陳慧芬
若您是本文的作者,可授權文章由華藝線上圖書館中協助推廣。

摘要


摘要 公車多班距時刻表設計的隨機最佳化問題 陳政信 本論文探討市區公車單一路線多班距之班距設定問題,同時考量公車營運業者本身的利潤、及乘客的利益,建立一目標函數,以找出最佳發車班距使目標函數最高,並且考慮實際行車過程中的隨機因素︰旅運需求、行車時間、乘客因不耐等候而離開等候線等,以符合實務狀況。本論文乃延續劉方旗(1998)的研究,由單一路線之發車班距的設定延伸至單一路線多班距的設定,使用的最佳化方法論是一種全面性的求解過程,進而針對各個不同時段的尖離峰,找到一組使得目標函數為最高的班距向量。 針對這個時刻表設定問題﹐我們設定公車行車系統的隨機模式及最佳化模式、利用兩個簡單特例來分析目標函數特性及最佳班距的近似解、最後提出隨機最佳化方法論以計算最佳班距值。從目標函數的特性分析中﹐發現多班距下的目標函數是一不連續函數,而不連續點發生在發車頻率改變時。在兩個特例之最佳班距值近似解的推導上﹐第一個特例假設乘客無離線(reneging)情形發生(即乘客不會因為不耐久候而離開等候站),近似解只和乘客到達率或單位等候成本有關,且每一尖離峰時段的班距相互獨立;第二個特子考量了乘客離線現象,針對單一班距,提出了五種不同情形下最佳班距的近似解,其中一種和第一個特例的近似解相同。 在隨機最佳化方法論方面,由於目標函數是不連續的﹐為了避免落入區域最佳解﹐採取兩階段求解﹐第一階段先找出最佳發車頻率(及班次數)﹐第二階段為在此最佳發車頻率下找出最佳派車班距。兩階段皆採用Jin (1998) 所提出之回溯彈性容忍最佳化法,由於第一階段的決策變數(發車頻率)是整數﹐將此方法論修正使得原先實數域的搜尋修正為整數域的搜尋方式。另外由於隨機最佳化方法論搜尋最佳解的品質好壞,會受到起始解的影響,因此我們使用從特例推導出之近似解來作為此隨機最佳化方法的起始解,以提高方法論的效率。 最後,我們進行模擬實驗來驗證方法論的效率與正確性。以我們提出的行車系統隨機模式,利用修正後回溯彈性容忍最佳化法的隨機最佳化的方法論,針對兩個班距兩站及兩個班距多站的模擬模式進行測試,結果發現我們推導的近似解對於較簡單的行車系統,是一個不錯的最佳班距近似解;而當站數增多時行車系統較複雜﹐使得近似解離最佳解較遠﹐因此因此求解效率較差。 關鍵詞︰多班距時刻表設定,最佳班距,隨機最佳化,最佳發車頻率,回溯彈性容忍最佳化法,模擬實驗。

並列摘要


ABSTRACT Stochastic Optimization for Computing Bus Multiple Headways by Cheng-Hsin Chen We consider the problem of finding the optimal multiple-headways for a single bus line that consists of a sequence of bus stops, where passengers can go aboard and alight. The stochastic model consists of random customer arrivals, random number of alighting passengers at each stop, and random bus travel time. The objective function is based on the operation income and customer service. This is a stochastic optimization problem. The stochastic system might be too complicate to compute the objective function values but we can estimate the function values through simulation experiments. This thesis extends the work of Liou (1998), which consider a single headway, rather than multiple headways, for a bus line. For this multiple-headway stochastic optimization problem, we define the stochastic model of the bus line and the objective function, study the behaviors of the objective function and propose approximate solutions using two special cases, and then propose general stochastic-optimization methods for computing headways. We found that the objective function is discontinuous where the discontinuity occurs when the bus frequency (number of buses dispatched per day) changes. The approximate solutions are constructed based on two special cases. The first special case doesn’t consider the situation of passenger reneging and the second does. For the first special case, the approximate solution only depends on the unit customer waiting cost and passenger arrival rate. For the second case, we propose approximate solutions for five situations; one of them is the same as the one for the first case. We propose a general stochastic optimization method---flexible-tolerance retrospective optimization (FTRO) algorithm---to compute the optimal headways. Our algorithm is revised from the algorithm proposed by Jin (1998). Since the objective function is discontinuous, our algorithm first computes the optimal frequencies and then computes the optimal headways associated with these frequencies. The purpose is to avoid local optimums. FTRO is used in both searches. For the first search, the decision variable (frequency) is an integer and hence the original FTRO proposed by Jin (1998) is revised so that the search domain is limited to integers only. Furthermore, to increase the efficiency of FTRO, the approximate solutions derived based on the two special cases are used as initial solutions. Simulation experiments are run to evaluate the efficiency and accuracy of FTRO. There are two experiments: the first use examples with two headways and two bus stops; the second uses an example with 58 bus stops. Simulation results show that the approximate solutions are good initial solutions in the first experiment. However, when the number of bus stops increases, the approximate solution may be far from the optimal solution and hence the algorithm efficiency decreases. Keywords: Optimal multiple-headways, stochastic optimization, flexible-tolerance retrospective optimization (FTRO) algorithm, optimal frequencies, Simulation experiments.

參考文獻


[54] 陳明典(2001)。市區公車行車系統模擬軟體之設計,中原大學工業工程研究所碩士論
E.F. Watson, J.S. Carson and M.S. Manivannan, 751—759.
[51] 周義華與謝金玫(1994)。專家系統應用於公車排班作業之研究,運輸計劃季刊,第二
[52] 周義華與吳宗憲(1997)。公車路線間相互支援之排班專家系統,運輸計劃季刊,第二
Proceedings of the 1998 Winter Simulation Conference, ed. D.J. Medeiros,

被引用紀錄


陳俊維(2011)。以逐點流體基礎近似方法求解大眾運輸系統最佳時變發車頻率〔碩士論文,國立臺北科技大學〕。華藝線上圖書館。https://doi.org/10.6841%2fNTUT.2011.00660
柯志明(2004)。具排班功能之公車系統模擬產生器的設計〔碩士論文,中原大學〕。華藝線上圖書館。https://doi.org/10.6840%2fcycu200400611

延伸閱讀