摘要
公車多班距時刻表設計的隨機最佳化問題
陳政信

本論文探討市區公車單一路線多班距之班距設定問題，同時考量公車營運業者本身的利潤、及乘客的利益，建立一目標函數，以找出最佳發車班距使目標函數最高，並且考慮實際行車過程中的隨機因素︰旅運需求、行車時間、乘客因不耐等候而離開等候線等，以符合實務狀況。本論文乃延續劉方旗(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.

目錄
中文摘要 ………………………………………………………………………i
英文摘要 ……………………………………………………………………iii
致謝 ……………………………………………………………………………v
圖目錄 …………………………………………………………………….viii
表目錄 ……………………………………………………………………….ix

第一章 緒論 ………………………………………………………………1
1.1 研究背景與動機 ………………………………………………………1
1.2 研究成果 ………………………………………………………………3
1.3 本文架構 ………………………………………………………………4

第二章 文獻回顧 …………………………………………………………….5
2.1時刻表排班方法 ……………………………………………………….5
2.1.1 確定性方法 ……………………………………………………………5
2.1.2 系統模擬法 …………………………………………………….10
2.1.2.1 單一路線單一班距隨機系統 …………………………………….12
2.2 隨機最佳化(Simulation optimization) ……………………………17
2.2.1 Nelder-Mead 方法論 ……………………………………………….21
2.2.1.1 最初的Nelder-Mead ………………………………………………21
2.2.1.2 彈性容忍法( Flexible Tolerance Method ) …………………27

第三章 多班距排班系統 ……………………………………………………32
3.1 公車排班之隨機系統 ………………………………………………….32
3.2 公車排班之數學模式 ………………………………………………….34

第四章 排班系統的特殊例子 ………………………………………………37
4.1 特殊例子一︰假設乘客無離線現象 ………………………………….37
4.1.1 單一班距的目標函數值 …………………………………………….38
4.1.1.1 目標函數的特性--忽略 時間內的等候成本 ……………………39
4.1.1.2 目標函數的特性--考慮 時間內的等候成本 ……………………42
4.1.1.3 最佳班距的近似解 ……………………………………………….44
4.1.2 兩個班距的目標函數值 …………………………………………….45
4.1.2.1 最佳班距的近似解 ……………………………………………….50
4.2 特殊例子二︰假設乘客有離線現象 ………………………………….51
4.2.1 單一班距的目標函數值 …………………………………………….52

第五章 隨機最佳化應用在排班問題上 ……………………………………64
5.1回溯最佳化 …………….……………………………………………….64
5.2回溯彈性容忍最佳化演算法 ……………………………………………68
5.3公車多班距排班隨機最佳化 ……………………………………………73
5.3.1 兩階段求解 ………………………………………………………….74
5.3.2 隨機最佳化方法論之修正 ………………………………………….75
5.4 模擬實驗結果 ………………………………………………………….76

第六章 結論與未來發展與建議
6.1 結論 …………………………………………………………………….83
6.2 未來研究方向 ………………………………………………………….83

參考文獻 …………………………………………………………………….85

參考文獻[1] Andradóttir, S. (1998). A Review of Simulation Optimization Techniques. Proceedings of the 1998 Winter Simulation Conference, ed. D. J. Mederios, E. F. Watson, J. S. Carson, and M. S. Manivannan, 151─158.[2] Azadivar, F. (1999). Simulation Optimization Methodologies. Proceedings of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. B. Nembhard, D. T. Sturrock, and G. W. Evans, 93─100.[3] Barton, R. R. and J. S. Ivey (1996). Nelder-Mead Simplex Modification for Simulation Optimization. Management Science 42, No. 7, 954─973.[4] Carson, Y. and A. Maria (1997). Simulation Optimization: Methods and Applications. Proceedings of the 1997 Winter Simulation Conference, ed. S. Andradóttir, K. J. Healy, D. H. Withers, and B. L. Nelson, 118─126.[5] Ceder, A. (1984a). Bus Frequency Determination Using Passenger Count Data. Transportation Research---A, 18A, 439─453.[6] Ceder, A. (1984b). Computer Application for Determining Bus Headways and Timetables. Transportation Research Record 1011, 76─87.[7] Chase, T. (2000). Supplementary Notes on the Golden Section Search Technique. ME 5241, Computer Aided engineering.[8] Chen, H. (1994). Stochastic Root Finding in System Design, Ph.D. Dissertation, School of Industrial Engineering, Purdue University, West Lafayette, Indiana, USA.[9] Chen, H. and B.W. Schmeiser (1994). Stochastic Root Finding: Problem Definition, Examples, and Algorithms. In Proceedings of the Third Industrial Engineering Research Conference, ed. L. Burke and J. Jackman, 605─610. Institute of Industrial Engineers, Norcross, Georgia.[10] Chen, H. and B.W. Schmeiser (2001). Stochastic Root Finding via Retrospective Approximation Algorithms. IIE Transactions 33, 259─275.[11] Dengiz, B. and C. Alabas (2000). Simulation Optimization Using Tabu Search. Proceedings of the 2000 Winter Simulation Conference, ed. J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, 805─810.[12] Fu, M. C. (1994). Optimization via Simulation：A Review. Annals of Operation Research 53, 199─247.[13] Fu, M. C. (2001). Simulation Optimization. Proceedings of the 2001 Winter Simulation Conference, ed. B. A. Peters, J. S. Smith, D. J. Medeiros, and M. W. Rohrer, 53─61.[14] Goldsman, D. and B. L. Nelson (2001). Statistical Selection of the Best System. Proceedings of the 2001 Winter Simulation Conference, ed. B. A. Peters, J. S. Smith, D. J. Medeiros, and M. W. Rohrer, 139─146.[15] Hedlund, H. E. and M. Mollaghasemi (2001). A Genetic Algorithm and an Indifference-Zone Ranking and Selection Framework for Simulation Optimization. Proceedings of the 2001 Winter Simulation Conference, ed. B. A. Peters, J. S. Smith, D. J. Medeiros, and M. W. Rohrer, 417─421.[16] Hedlund, P. and A. Gustavsson (1991). Design and Evaluation of an Efficient Modified Simplex Method. Analytica Chimica Acta, 391, 257─267.[17] Hedlund, P. and A. Gustavsson (1998). Design and Evaluation of an Improved Simplex Method. Analytica Chimica Acta, 371, 9─21.[18] Himmelblau, D. M. (1972). Applied Nonlinear Programming. McGraw-Hill, Inc, New York.[19] Hsu, J. C. (1996). Multiple Comparisons : Theory and Methods. Chapman & Hall, London New York.[20] Humphrey, D. G. and J. R. Wilson (1998). A Revised Simplex Search Procedure for Stochastic Simulation Response-Function Optimization. Proceedings of the 1998 Winter Simulation Conference, ed. D.J. Medeiros, E.F. Watson, J.S. Carson and M.S. Manivannan, 751─759.[21] Hurdle, V. F. (1973). Minimum Cost Schedules for a Public Transportation route. Transportation Science, No. 7, 109─137.[22] Jacobson, S. H. and L. W. Schruben (1989). Techniques for Simulation Response Optimization. Operation Research Letters 8, 1─9.[23] Jin, J. (1998). Simulation-Based Retrospective Optimization of Stochastic Systems. Ph.D. Dissertation, School of Industrial Engineering, Purdue University, West Lafayette, Indiana, USA.[24] Kelley, C. T. (1999). Detection and Remediation of Stagnation in the Nelder-Mead Algorithm Using a Sufficient Decrease Condition. SIAM Journal on Optimization 10, 43─55.[25] Lagarias, J. C., J. A. Reeds, M. H. Wright, and P. E. Wright (1998). Convergence Properties of the Nelder-Mead Simplex Method in Low Dimensions. SIAM Journal on Optimization 9, No. 1 , 112─147.[26] Law, A.M. and W.D. Kelton (2000). Simulation Modeling and Analysis, 3rd ed. McGraw-Hill, Inc, New York.[27] Lewis, R. M. and V. Torczon (1999). Pattern Search Algorithm for Bound Constrained Minimization. SIAM Journal on Optimization 9, No. 4, 1082─ 1099.[28] Lewis, R.M., V. Torczon, and M.W. Trosset (2000). Direct Search Methods: Then and Now. Journal of Computational and Applied Mathematics, 124.[29] Mckinnon, K. I. M. (1998). Convergence of the Nelder-Mead Simplex Method to a Nonstationary Point. SIAM Journal on Optimization 9, No. 1, 148─ 158.[30] Neddermeijer, H. G., G. J. van Oortmarssen, N. Piesma, and R. Dekker (2000). A Framework for Response Surface Methodology for Simulation Optimization. Proceedings of the 2000 Winter Simulation Conference, ed. J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, 129─136.[31] Neddermeijer, H. G., G. J. van Oortmarssen, N. Piesma, R. Dekker, and J. Dik F. Habbema. Adaptive Extensions of the Nelder and Mead Simplex Method for Optimization of Stochastic Simulation Models. Econometric Institute Report EI2000-22/A.[32] Nelder, J. A. and R. Mead (1965). A Simplex Method for Function Minimization. Computer Journal 7 , 308─313.[33] Newell, G. F. (1971). Dispatching Policies for a Transportation Route. Transportation Science, No. 5, 91─105.[34] Paviani, D. A. and D. M. Himmelblau (1969). Constrained Nonlinear Optimization by Heuristic Programming. Operations Research 17, 872─882.[35] Press, W. H., S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery (1997). Numerical Recipes in C, 2nd ed. Cambridge University Press.[36] Salzborn, F. J. (1972). Optimum Bus Scheduling. Transportation Science, No. 6, 137─148.[37] Sanchez, S. M. (1997). It Is Far, Far Better Mean I Find… . Proceedings of the 1997 Winter Simulation Conference, ed. S. Andradó ttir, K. J. Healy, D. H. Withers, and B. L. Nelson, 31─38.[38] Sharma, R. R., R.C. Rai, and A. Mishra (1993). Optimal Bus Services on Express Basis in the Case of Balking and Reneging. European Journal of Operational Research, 66, 113─123.[39] Spall, J. C. (1999). Stochastic Optimization and the Simultaneous Perturbation Method. Proceedings of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. B. Nembhard, D. T. Sturrock, and G. W. Evans, 101─109.[40] Spendley, W., G. R. Hext, and F. R. Himsworth (1962). Sequential Application of Simplex Designs in Optimization and Evolutionary Operation. Technometrics 4, No. 4, 441─461.[41] Swisher, J. R., L. W. Schruben, P. D. Hyden, and S. H. Jacobson (2000). A Survey of Simulation Optimization Techniques and Procedures. Proceedings of the 2000 Winter Simulation Conference, ed. J. A. Joines, R. R. Barton, K. Kang, and P. A. Fishwick, 119─128.[42] Swisher, J. R. and S. H. Jacobson (1999). A Survey of Ranking, Selection, and Multiple Comparison Procedures for Discrete-Event Simulation. Proceedings of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. B. Nembhard, D. T. Sturrock, and G. W. Evans, 492─501.[43] Tapiero, C. S. and D. Zuckerman (1979). Vehicle Dispatching with Competition. Transportation Research 13B, 207─216.[44] Torczon, V. (1991). On the Convergence of the Multidirectional Search Algorithm. SIAM Journal on Optimization 1, No. 1, 123─145.[45] Torczon, V. (1997). On the Convergence of the Pattern Search Algorithms. SIAM Journal on Optimization 7, No. 1, 1─25.[46] Vuchic, V. R. (1976). Transit Operating Manua. Pennsylvania Department of Transportation.[47] Walters, F. (1999). Sequential Simplex Optimization — An Update. Analytical Letters 32(2), 193─212.[48] Walters, F. H., L. R. P. Jr., S. L. Morgan, and S. N. Deming (1991). Sequential Simplex Optimization. CRC Press, Boca Raton, FL, 1991.[49] 韓復華(1976)。客運系統班次排定問題之研究，台灣大學土木工程學研究所碩士論 文。[50] 陳武正與蕭耀涎(1978)。公車車輛調度模擬分析，運輸計劃季刊，第七卷，第四期， 199─234。[51] 周義華與謝金玫(1994)。專家系統應用於公車排班作業之研究，運輸計劃季刊，第二 十三卷，第二期，199─234。[52] 周義華與吳宗憲(1997)。公車路線間相互支援之排班專家系統，運輸計劃季刊，第二 十六卷，第一期，159─202。[53] 劉方旗(1998)。市區公車排班與即時機動調度之研究─以新竹市公車為例， 交通大 學交通運輸研究所碩士論文。[54] 陳明典(2001)。市區公車行車系統模擬軟體之設計，中原大學工業工程研究所碩士論 文。