- 學位論文
動態環境下最佳共乘組合之快速更新
Fast Update of the Best Carpool Groups in Dynamic Environment
摘要
傳統共乘網站通常只找出發地或目的地相近的所有對象，由使用者自行挑選理想的共乘組合，就整體的共乘配對而言，可能因而錯失許多共乘的機會，降低使用者參與共乘的意願。我們在先前的研究中提出浮動計價方案，讓共乘者依路程分攤費用，並以回饋金額為目標，為個別駕駛尋找最佳乘客組合。本論文考慮動態環境下，從已配對但未確認的共乘組合中，為新進乘客尋找最適合加入者，除了提昇駕駛所得的回饋金額，還必須使乘客應分攤的費用最低。我們設計以區段概念為基礎的索引方法，利用區段內的搭乘人數，事先計算現有共乘組合的配對資訊；新進乘客可透過此索引迅速查出最佳的共乘組合，而加入後，相關區段的索引資訊便會立即更新。從實驗得知，我們所提方法可比傳統作法平均減少84%的查詢時間，並達到平均22.52%的壓縮率，有效降低現有共乘組合需處理的資料量。
並列摘要
Traditional carpool websites only find the users who have similar starting points or destinations for a ridesharing search. The users need to choose by themselves the best among all candidates. As a result, there might be losses of many ridesharing opportunities and the users would not be willing to join the ridesharing system anymore. The previous work has proposed a floating share scheme in which the ridesharing partners can share the payment according to their routes’ distances, and a method of finding the best passenger group for a driver. In this thesis, given the set of ridesharing groups, we further consider the problem of finding the best group for a new passenger. In addition to the increase of the driver’s saving, the returned group must also lead to the lowest expense for the new passenger. We design a segment-based indexing method to keep and compress the current set of ridesharing groups. A new passenger can find the best group via the index, which can then be quickly updated. In the experiments, our method achieves 84% speedup in query processing time and 22.52% compression ratio on average to reduce the data for processing.