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

陳政信

doi:10.6840/cycu200200610

18.232.59.38，Hello！

Close
Search Quick Search Advanced Search Publication Search	Personal Service Member Login Searching History Use Bonus Card SYMSKAN
Browse Browse by University of Graduate Thesis Browse by Pinyin of Graduate Thesis Browse by Conference Proceedings Topic Browse by Conference Proceedings Publisher Browse by Pinyin of Conference Proceedings Browse by eBook Category Browse by eBook Topic Browse by eBook Publisher
Customer Services Authorize Airiti Recommend a Journal

Search Symbol (Half-width)	Description of Search Symbols
Space	"AND" indicates the intertwining of key terms used in a search
Double Quotation Marks ("") ( " " )	Double quotation marks indicate the beginning and end of a phrase, and the search will only include terms that appear in the same order of those within the quotations. Example: "image process" ： " image process "
?	Indicates a variable letter. Entering two ? will indicate two variable letters, and so on. Example: "Appl?", search results will yield apple, apply… e , appl y … ( (often used to English word searches) )
*	Indicates an unlimited number of variable letters to follow, from 1~n. Example: Enter "appl*", search results will yield apple, apples, apply, applied, application…(often used in English word searches) e , appl es , appl y , appl ied , appl ication … ( (often used to English word searches) )
AND、OR、NOT	Boolean logic combinations of key words is a skill used to expand or refine search parameters. (1) AND (1) AND: Refines search parameters (2) OR (2) OR: Expands search parameters (3) NOT: Excludes irrelevant parameters

DOI stands for Digital Object Identifier （ D igital O bject I dentifier ） ,
and is the unique identifier for objects on the internet. It can be used to create persistent link and to cite articles.

Using DOI as a persistent link

To create a persistent link, add「http://dx.doi.org/」「 http://dx.doi.org/ 」 before a DOI.
For instance, if the DOI of an article is 10.5297/ser.1201.002 , you can link persistently to the article by entering the following link in your browser: http://dx.doi.org/ 10.5297/ser.1201.002 。
The DOI link will always direct you to the most updated article page no matter how the publisher changes the document's position, avoiding errors when engaging in important research.

Cite a document with DOI

When citing references, you should also cite the DOI if the article has one. If your citation guideline does not include DOIs, you may cite the DOI link.

DOIs allow accurate citations, improve academic contents connections, and allow users to gain better experience across different platforms. Currently, there are more than 70 million DOIs registered for academic contents. If you want to understand more about DOI, please visit airiti DOI Registration （ doi.airiti.com ）。

Data Source

College of Engineering > Graduate Institute of Industrial Engineering
Engineering > General Engineering

Bibliography Management Tool

Related Links

Report an Issue

Search for full text in Holdings

There is no full-text available at the moment. Airiti would like to request author's authorization. I would like to provide authorization.

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

Stochastic Optimization for Computing Bus Multiple Headways

陳政信 , Masters　　Advisor：陳慧芬　　

繁體中文 DOI： 10.6840/cycu200200610

模擬實驗；多班距時刻表設定；最佳班距；回溯彈性容忍最佳化法；最佳發車頻率；隨機最佳化； flexible-tolerance retrospective optimization (FTRO) al ； Optimal multiple-headways ； stochastic optimization ； simulation experiments ； optimal frequencies

Abstract │ Reference (139) │ Times Cited (2) │ Altmetrics

Abstract 〈TOP〉

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

本論文探討市區公車單一路線多班距之班距設定問題，同時考量公車營運業者本身的利潤、及乘客的利益，建立一目標函數，以找出最佳發車班距使目標函數最高，並且考慮實際行車過程中的隨機因素︰旅運需求、行車時間、乘客因不耐等候而離開等候線等，以符合實務狀況。本論文乃延續劉方旗(1998)的研究，由單一路線之發車班距的設定延伸至單一路線多班距的設定，使用的最佳化方法論是一種全面性的求解過程，進而針對各個不同時段的尖離峰，找到一組使得目標函數為最高的班距向量。

針對這個時刻表設定問題﹐我們設定公車行車系統的隨機模式及最佳化模式、利用兩個簡單特例來分析目標函數特性及最佳班距的近似解、最後提出隨機最佳化方法論以計算最佳班距值。從目標函數的特性分析中﹐發現多班距下的目標函數是一不連續函數，而不連續點發生在發車頻率改變時。在兩個特例之最佳班距值近似解的推導上﹐第一個特例假設乘客無離線(reneging)情形發生（即乘客不會因為不耐久候而離開等候站），近似解只和乘客到達率或單位等候成本有關，且每一尖離峰時段的班距相互獨立；第二個特子考量了乘客離線現象，針對單一班距，提出了五種不同情形下最佳班距的近似解，其中一種和第一個特例的近似解相同。

在隨機最佳化方法論方面，由於目標函數是不連續的﹐為了避免落入區域最佳解﹐採取兩階段求解﹐第一階段先找出最佳發車頻率（及班次數）﹐第二階段為在此最佳發車頻率下找出最佳派車班距。兩階段皆採用Jin (1998) 所提出之回溯彈性容忍最佳化法，由於第一階段的決策變數(發車頻率)是整數﹐將此方法論修正使得原先實數域的搜尋修正為整數域的搜尋方式。另外由於隨機最佳化方法論搜尋最佳解的品質好壞，會受到起始解的影響，因此我們使用從特例推導出之近似解來作為此隨機最佳化方法的起始解，以提高方法論的效率。

最後，我們進行模擬實驗來驗證方法論的效率與正確性。以我們提出的行車系統隨機模式，利用修正後回溯彈性容忍最佳化法的隨機最佳化的方法論，針對兩個班距兩站及兩個班距多站的模擬模式進行測試，結果發現我們推導的近似解對於較簡單的行車系統，是一個不錯的最佳班距近似解；而當站數增多時行車系統較複雜﹐使得近似解離最佳解較遠﹐因此因此求解效率較差。

關鍵詞︰多班距時刻表設定，最佳班距，隨機最佳化，最佳發車頻率，回溯彈性容忍最佳化法，模擬實驗。

Parallel Abstract 〈TOP〉

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.

Reference ( 139 ) 〈TOP〉

[1] Andradóttir, S. (1998). A Review of Simulation Optimization Techniques.
連結：
Proceedings of the 1998 Winter Simulation Conference, ed. D. J. Mederios,
連結：
[2] Azadivar, F. (1999). Simulation Optimization Methodologies. Proceedings
連結：
of the 1999 Winter Simulation Conference, ed. P. A. Farrington, H. B.
連結：
Simulation Optimization. Management Science 42, No. 7, 954—973.
連結：

Times Cited (2) 〈TOP〉

Altmetrics

〈TOP〉

E-mail ：

When an article is available to download, a notice will be sent to your mailbox address.

E-mail ：