週期共乘之索引及配對技術

Indexing and Matching Techniques for Periodic Ridesharing

周宛儒(Yan-Ju Chou)

指導教授 ： 吳宜鴻

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

https://doi.org/10.6840/cycu201200956

摘要

近年來，由於交通便利和私人轎車的普及，工作場合或學校和自身的住宅可能距離愈來愈遠，通勤便成了一種日常需求，本研究基於此需求提出了週期共乘的索引及配對方法，讓長期擁有共同路線的使用者，得以定期地實行共乘，並節省雙方的旅費。我們設計時間區間的索引結構，用來記錄週期性共乘的資訊，並利用該索引達到快速篩選搭乘時間符合的候選共乘對象，而不必逐一檢視每一筆使用者的週期資訊；暫存一段時間內所記錄的候選對象後，我們利用對稱式架構輔以反覆配對的方法替駕駛與乘客配對，以提高加入共乘的乘客人數為目標，反覆選擇駕駛及乘客，每次只選一名最佳的對象。實驗結果顯示我們的方法在答案品質及執行時間之間取得不錯的平衡。

關鍵字

週期共乘 ； 配對 ； 索引 ； 時間區間

並列摘要

Recent years, due to the convenient transportation and the popularization of private cars, the distance between company and residence has become farther. More and more people commute in daily life. Therefore, this study proposed the indexing and matching techniques for periodic ridesharing so that the long-term commuters on the same route can share rides periodically and save the traveling expenses. We designed an index structure on time intervals to record the information about periodic ridesharing. Based on the index, without checking every record, the candidates whose time intervals are qualified could be quickly found. With the candidates recorded in a time period, we employed a symmetric framework aided by the iterative matching approach to find the matches among drivers and passengers. To maximize the number of participant passengers, our approach alternately chose drivers and passengers, and each time only one of the best choices was made. Experiment results show that our approach achieved a good balance between the quality of answer and the execution time.

並列關鍵字

matching ； indexing ； time interval ； periodic ridesharing

參考文獻

[2] Joshua Morse, Joshua Palay, Yarun Luon and Satyendra Nainwal, “CarLoop: Leveraging Common Ground to Develop Long-term Carpools,” Computer Human Interaction, pp. 2073-2078, 2007.

[3] Jun Zhang, Nikos Mamoulis, Dimitris Papadias and Yufei Tao, “All-Nearest-Neighbors Queries in Spatial Databases,” International Conference on Scientific and Statistical Database Management, pp. 297-306, 2004.

[4] Leong Hou U, Nikos Mamoulis and Man Lung Yiu, “Computation and Monitoring of Exclusive Closest Pairs,” IEEE Transactions on Knowledge and Data Engineering, pp. 1641 - 1654, 2008.

[5] Manel Sghaier, Hayfa Zgaya, Slim Hammadi and Christian Tahon, “A Distributed Optimized Approach based on the Multi Agent Concept for the Implementation of a Real Time Carpooling Service with an Optimization Aspect on Siblings,” International Journal of Engineering, 2011.

[6] Norbert Beckmann, Hans-Peter Kriegel, Ralf Schneider and Bernhard Seeger, “The R*-Tree: An Efficient and Robust Access Method for Points and Rectangles,” Special Interest Group on Management of Data, pp. 322-331, 1990.