隨機旅行時間下計程車共乘及乘客配對整合模式與求解演算法之研究; An Integrated Model and Solution Algorithms for Taxipool and Passenger Matching Problems under Stochastic Travel Times

NCUIR > Engineering College > Graduate Institute of Civil Engineering > Electronic Thesis & Dissertation > Item 987654321/1340

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/1340

Title:	隨機旅行時間下計程車共乘及乘客配對整合模式與求解演算法之研究;An Integrated Model and Solution Algorithms for Taxipool and Passenger Matching Problems under Stochastic Travel Times
Authors:	吳逸祥;Yi-siang Wu
Contributors:	土木工程研究所
Keywords:	啟發解法;多重貨物網路流動問題;計程車共乘;隨機性旅行時間;時空網路;Taxipool;Stochastic travel times;Time-space network;Multiple commodity network flow problem;Heuristic
Date:	2009-07-06
Issue Date:	2009-09-18 17:27:41 (UTC+8)
Publisher:	國立中央大學圖書館
Abstract:	隨著台灣都會區交通量的迅速成長，計程車已成為台灣都會區中一相當普遍之運輸工具，但其乘載率及使用率偏低則成為一極需解決之惱人問題。透過計程車共乘計劃不僅可提高其使用效率，更可改善都市交通擁擠問題。然而，目前實務上計程車的共乘配對，多採用人工經驗的作法，不僅費時且缺乏系統分析，使得共乘的績效降低。過去計程車共乘的研究多以平均旅行時間為依據，進行共乘配對與排程，此作法未考量實際旅行時間的隨機性。在實際營運時若隨機旅行時間造成之擾動過大，將使原規劃的配對與排程結果失去最佳性。因此，本研究針對多起迄對之預約旅次，考量隨機性旅行時間之影響，建構一隨機性計程車共乘配對模式，期能提供一有效的規劃輔助工具，以幫助決策者有效地規劃乘客配對與車輛排程。本研究利用時空網路流動技巧建立一此隨機模式，模式中包含車流與人流網路，以定式車輛與旅客在時空中的流動與配對。本研究並進一步修改隨機模式之旅行時間為平均旅行時間，建立一確定性模式。此兩模式可定式為特殊之整數多重貨物網路流動問題，屬NP-hard問題。當面臨實務的大型問題時，勢將難以在有限時間內利用數學規劃軟體求得最佳解。緣此，本研究發展一啟發式演算法以有效地求解問題。此外，本研究亦發展一模擬評估方法，以評估兩模式的實際營運績效。最後為評估模式與演算法之實用績效，本研究以實際資料以及合理假設產生測試例，進行範例測試並針對不同參數進行敏感度分析，結果顯示本模式與演算法可在實務上可有效的運用。 As the Taiwan urban areas’ traffic volume grew significantly, taxi becomes more popular than before in Taiwan. The low loading factor and use rate become an annoying problem, which should be resolved immediately. The taxipool plan can not only improve its operational performance, but can also relieve the traffic congestion problem. However, most taxi carriers currently use a trial-and-error process, in accordance with the projected taxi travel times, for taxipool matching, which is neither effective nor efficient. In other words, stochastic disturbances arising from variations in taxi travel times in actual operations are neglected. In the worst scenario, where taxi travel times fluctuate wildly during operations, the planned schedule could be disturbed enough to lose its optimality. Therefore, focusing on multiple origin-destination (OD) with advanced-order passenger trips, we constructed a stochastic taxipool matching model that considers the influence of stochastic travel times. The matching model is expected to be an effective tool for the planner to solve passenger matching and fleet scheduling. We employed network flow techniques to construct the stochastic taxipool matching model, including fleet-flow and passenger-flow networks. Then, we modified the stochastic travel times in the stochastic taxipool matching model as an average travel time to develop a deterministic scheduling model. The two models are formulated as special integer multiple commodity network flow problems, which are characterized as NP-hard. Since the problem sizes are expected to be huge in real practice, the models are difficult to be solved in a reasonable time. Therefore, we also developed a heuristic algorithm for efficiently solving passenger matching and fleet scheduling problems. In addition, to evaluate the stochastic and deterministic taxipool matching models, we also developed a simulation-based evaluation method. The performance of the solution method in practice is evaluated by carrying out a case study using real data and suitable assumptions, and then sensitive analysis is performed for different parameters. The test results show the model to be good and that the solution method could be useful in practice.
Appears in Collections:	[Graduate Institute of Civil Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Size	Format

社群 sharing

Loading...