合理計費機制之汽車共乘系統及乘客搜尋技術

Ride Sharing System and Passenger Search Techniques for a Fair Payment Scheme

陳泓翰(Hong-Han Chen)

指導教授 ： 吳宜鴻

中原大學/工學院/資訊工程研究所/碩士(2010年)

https://doi.org/10.6840/CYCU.2010.00595

摘要

共乘最大的功用在於能幫使用者找到與自己有相同路線需求的其他使用者，以達到節省交通費用及節能的目的。傳統的人工配對方式無法應付大量的使用者及路線，提供自動化的方式有其必要。目前線上共乘系統大多要求使用者以文字輸入路線上的地點、以及其他資訊如抵達時間和駕駛習慣，使用者只能利用關鍵詞查詢來找出完全相符的答案，然而，文字難以清楚描述路線資訊，因此使用者往往得不到滿意的答案；此外，使用者需花費許多時間確認答案，容易讓使用者感到不便並對共乘系統產生倦怠感。有鑑於此，本論文提出一個自動化的使用者共乘配對系統，使用谷歌地圖作為使用者輸入位置資訊的介面，能有效解決傳統使用文字所會遇到的問題；我們也定義了此系統所衍生的乘客搜尋問題，並將計費方案納入考量，提出一個可以找出「駕駛省最多錢且乘客負擔最少錢」的方法，最後，我們實作一套雛型系統以整合所提方法與使用者確認共乘伙伴的程序。實驗結果顯示，我們提出的搜尋方法能有效找出近似的最佳解，而比對過程中，我們利用所發現的一個特性也大幅減少需要檢查的候選對象。

關鍵字

自動化系統 ； 最佳解 ； 谷歌地圖 ； 合用共乘 ； 乘客搜尋 ； 共乘網

並列摘要

Carpool has the greatest function of helping users find the others who can share a ride on the same route for saving traffic costs and energy. Because the traditional way that finds the matches manually cannot handle the large amount of users and routes, an automatic way is needed. Currently, most of the online carpool systems require users to input textual descriptions about the terminals on the routes and other information such as arrival time and drivers’ habits. Users can only use keyword queries to find exact matches on those descriptions. However, it is hard to describe the routes in text, and thus users usually get no satisfactory answers. In addition, users have to spend a lot of time on the mutual confirmation for a match. As a result, they may feel inconvenient and tired of carpool. Therefore, in the thesis we propose an automatic carpool system using Google map as the input interface for user routes’ positions. It can overcome the difficulties on traditional text-based systems. We also define the passenger search problem created by our system. Moreover, we take the carfare into account and design a method that can make driver’s saving the most and passengers’ expense the least. Finally, we implement a prototype system to integrate the proposed method and the procedures for mutual confirmation. The experiment results show that our method can find near optimal answers. Furthermore, during the search, a property we found is also applied to greatly reduce the number of candidates for examination.

並列關鍵字

Passenger Search ； Ride Sharing ； Automatic System ； Google Map ； Carpool ； Optimal Solution

參考文獻

[1] 林瑜芳、顏上堯, “小汽車共乘公平性配對模式暨求解演算法之研究,” 國立中央大學土木工程學研究所碩士論文, 2008.

[2] 陳信彥、顏上堯, “計程車共乘及旅客配對整合模式暨求解演算法之研究,” 國立中央大學土木工程學研究所碩士論文, 2008.

[10] D. Coppersmith, T.J. Nowicki, G.A. Paleologo, C. Tresser, and C.W. Wu, “The Optimality of the On-line Greedy Algorithm in Carpool and Chairman Assignment Problems,” IBM Research Report, 2005.

[13] R. Fagin and J.H. Williams, “A Fair Carpool Scheduling Algorithm,” IBM Journal of Research and Development, 27(2): 133-139, 1983.

[14] G. Gidófalvi, T.B. Pedersen, T. Risch, and E. Zeitler, “Highly Scalable Trip Grouping for Large-scale Collective Transportation Systems,” EDBT, pp. 678-689, 2008.