隨機性擾動下規劃問題求解演算法之研究

A Solution Approach for Planning Problems under Stochastic Disturbances

湯慶輝(Ching-Hui Tang)

指導教授 ： 顏上堯

國立中央大學/工學院/土木工程學系/博士(2006年)

摘要

過去學者在處理規劃問題時，大多以預測之平均值構建數學模式求算最佳解。然而在運輸系統的實務營運中，隨時可能遭遇許多隨機性因素的干擾，例如旅次需求、車輛旅行時間、班機到離延誤等。此等隨機性因素對規劃的最佳化結果可能產生相當的影響，甚至可能使其在實際營運時失去最佳性。另外，以往研究多將靜態時期規劃與即時性擾動規劃兩者分開單獨處理，且在面對隨機性擾動時，多著重於處理即時性擾動規劃。因此，本研究針對隨機問題之特性，發展一整合規劃與即時階段之求解架構，將規劃與即時兩不同階段之規劃問題在隨機擾動下做一整合性之分析。期能於未來實務應用上，提供有效的工具，以處理隨機環境中的規劃問題。
為測試所發展的求解架構之可行性，本研究以機門指派與長途客運排程問題為應用對象。本研究可分成三個部分：第一個部分在機門指派問題方面，考量班機隨機到離延誤之特性，整合靜態機門指派與即時性機門指派，求得一較符合班機隨機延誤下之機門指派結果。第二部份則以長途客運排程問題為對象，考量車輛旅行時間之隨機特性，除在規劃階段發展一隨機性旅行時間長途客運排程模式外，並進一步考量因車輛旅行時間延誤之即時調整問題，建立一套整體性之求解架構，求得一較符合車輛旅行時間隨機擾動下之排程結果。第三部份同樣利用本研究發展之求解架構，同時考量市場旅客需求之隨機性、變動的市場佔有率與車輛旅行時間之隨機特性，發展一多隨機因素之長途客運排程模式，同時亦考量即時階段之調整問題，以幫助業者有效規劃車隊排程與班次表。此三部份皆使用實際營運資料加上適當的假設，利用C程式語言，配合CPLEX數學規劃軟體進行求解。最後，根據此三部份的研究結果，提出結論與建議。

關鍵字

隨機性擾動 ； 機門指派 ； 班機隨機到離延誤 ； 隨機車輛旅行時間 ； 隨機需求 ； 變動市場佔有率 ； 長途客運排程

並列摘要

There are many stochastic factors that will affect the performance of the planning results in a passenger transportation system, such as passenger demands, vehicular travel times and flight delays. Past traditional deterministic models have been established based on the average values of factors such as input to obtain optimal solutions. However, such stochastic factors during the operational stage could have a significant influence on the planning results. An optimal plan might therefore lose its optimality when applied in real world operations where stochastic disturbances occur. In addition, most stochastic disturbance planning problems have been handled in two separate stages, the planning and the real-time stages. Most past research on these types of problems has focused on improving real-time adjustments to stochastic disturbances. In this research however we try to develop an integrated framework that combines both the planning and the simulated real-time stages together. The framework is expected to be useful for solving for better planning solutions to stochastic disturbance problems.
To evaluate how the proposed framework performs in practice, we perform applications to both gate assignment and inter-city bus scheduling problems. The dissertation includes three essays. In the first, we consider the stochastic characteristics of flight delays in actual operations; we integrate both the planning and the simulated real-time stages together to solve for gate assignment plans flexible enough to meet stochastic disturbances. In the second essay, we consider the bus scheduling planning problem with stochastic bus travel times. We develop an integrated framework that can systematically analyze planned bus scheduling and simulated real-time schedule adjustment problems in order to help the inter-city bus carriers plan suitable bus routes/schedules. The third essay considers the stochastic passenger demands, the variable market shares and the stochastic bus travel times of real world operations to develop a multi-stochastic bus scheduling model. Simulated real-time schedule adjustment is also incorporated into the framework. The result is to produce a better bus route/schedule plan. We performed these applications using real operational data, with reasonable simplifications. We used the C computer language to write the necessary programs, coupled with the CPLEX mathematical programming solver, to solve the problems. Finally, conclusions and suggestions are given.

並列關鍵字

Stochastic disturbances ； Stochastic bus travel times ； Variable market shares ； Stochastic passenger demands ； Stochastic flight delays ； Inter-city bus scheduling ； Gate assignment

參考文獻

Babic, O., Teodorovic, D., and Tosic, V., 1984. Aircraft stand assignment to minimize walking, Journal of Transportation Engineering 110, 55-66.

Bertsimas, D. and Sim, M., 2004. The price of robustness, Operation Research 52, 35-53.

Bihr, R.A., 1990. A conceptual solution to the aircraft gate assignment problem using 0,1 linear programming, Computers and Industrial Engineering 19, 280-284.

Bolat, A., 1999. Assigning arriving flights at an airport to the available gates, Journal of the Operational Research Society 50, 23-34.

Bolat, A., 2000. Procedures for providing robust gate assignments for arriving aircrafts, European Journal of Operational Research 120, 63-80.