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