計程車共乘及旅客配對整合模式暨求解演算法之研究

Integrated Matching Models and Solution Algorithms for Taxipool.

陳信諺(Hsin-yein Chen)

指導教授 ： 顏上堯

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

摘要

近年來台灣都會區交通量的成長迅速，計程車之使用亦日益普遍，如何有效的透過共乘以提高計程車之服務能量，則成為一重要之課題。然而，目前計程車行在計程車共乘的配對上，多採用人工經驗排班方式，不僅費時且難以得到最佳之配對結果，而降低共乘之績效。緣此，吳權哲(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.

並列關鍵字

Meta-heuristics ； Heuristic ； Greedy Algorithm ； Taxipool ； Multiple commodity network flow problem

參考文獻

黃漢瑄 (2006)，「撥召服務最佳化指派作業之研究」，碩士論文，私立淡江大學運輸管理學系運輸科學研究所。

楊淑芳 (2006)，「以巨集啟發式演算法求解即時資訊下之中型車共乘問題」，碩士論文，私立淡江大學運輸管理學系運輸科學研究所。

韓復華、楊智凱、卓裕仁 (1997)，「應用門檻接受法求解車輛路線問題之研究」，運輸計畫季刊，第二十六卷，第二期，第253-280頁。

顏上堯、陳建榮、湯慶輝 (2004)，「含凹形節線成本最小成本轉運問題鄰近搜尋法之研究」，運輸計劃季刊，第三十三卷，第二期，第277-306頁。

邱明琦、陳春益、林佐鼎 (2002)，「海運貨櫃排程模式之研究」，運輸計劃季刊，第三十一卷，第三期，第495-522頁。