計程車共乘及旅客配對整合模式暨求解演算法之研究; Integrated Matching Models and Solution Algorithms for Taxipool.

NCU Institutional Repository > 工學院 > 土木工程研究所 > 博碩士論文 > Item 987654321/1280

請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/1280

題名:	計程車共乘及旅客配對整合模式暨求解演算法之研究;Integrated Matching Models and Solution Algorithms for Taxipool.
作者:	陳信諺;Hsin-yein Chen
貢獻者:	土木工程研究所
關鍵詞:	貪婪式演算法;啟發解;計程車共乘;多重貨物網路流動問題;巨集式啟發解法;Meta-heuristics;Heuristic;Greedy Algorithm;Taxipool;Multiple commodity network flow problem
日期:	2008-06-23
上傳時間:	2009-09-18 17:25:42 (UTC+8)
出版者:	國立中央大學圖書館
摘要:	近年來台灣都會區交通量的成長迅速，計程車之使用亦日益普遍，如何有效的透過共乘以提高計程車之服務能量，則成為一重要之課題。然而，目前計程車行在計程車共乘的配對上，多採用人工經驗排班方式，不僅費時且難以得到最佳之配對結果，而降低共乘之績效。緣此，吳權哲(2007)提出一架構，含三個模式，以分段方式求解多起迄需求計程車共乘配對問題，然此種求解方式並未以整體系統最佳化觀點考量，故未能求得一系統化之最佳解。為更有效幫助業者求得一系統化之最佳解，本研究構建一符合現況之多起迄需求計程車共乘配對整合模式，以期幫助業者規劃一良好之共乘配對方式，進而提升營運績效。本研究針對多起迄對之預約式旅次，以共乘配對系統規劃者的角度，發展一系統化之最佳化模式。此模式預期可定式為一整數多重網路流動問題，屬NP-hard問題，當問題規模變大時，可能難以在有限的時間內利用數學規劃軟體求得一最佳解。緣此，本研究針對此模式發展一系列以貪婪式演算法為基礎並結合巨集式啟發解法之混合式(hybrid)求解演算法，以求解計程車共乘配對問題。最後，本研究以臺北市一計程車行之營運資料為範例進行測試與分析，結果甚佳，顯示本研究所建構之模式與求解之演算法，應可為未來計程車進行實務共乘配對之參考。 In recent years, the traffic volume has grown significantly and taxi becomes more popular than before in Taiwan. How to improve the service performance effectively by using taxipool becomes an important issue. However, currently most taxi carriers use a trial-and-error process for taxipool matching, which is neither effective nor efficient. Wu (2007) developed a taxipool matching framework, including three models, and the framework had been solved by using decomposition method, without optimization from a systemic perspective. Therefore, we develop a system optimization multiple OD matching model to help the taxi carriers to solve a better solution from systemic perspective. It is expected that such model is useful tool for the taxi carriers to plan the most suitable passenger matching and fleet scheduling. We construct an integrated model focusing on advanced-order passenger trips from the planner perspective. The model is formulated as integer multiple commodity network flow problems, which is characterized as NP-hard. Since the problem size is expected to be huge, the model is more difficult to solve in a reasonable time. Therefore, we also try to develop a family of hybrid solution algorithms, based on Greedy Algorithm and Meta-heuristics, for solving passenger matching and fleet scheduling problems. Numerical tests based on real operating data from a taxi carrier are performed to evaluate the proposed solution algorithm. The preliminary results are good, showing that the model and the algorithms could be useful for passenger matching and fleet scheduling.
顯示於類別:	[土木工程研究所] 博碩士論文

文件中的檔案:

檔案	大小	格式	瀏覽次數

在NCUIR中所有的資料項目都受到原著作權保護.

社群 sharing

資料載入中.....