臺灣博碩士論文加值系統

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

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.

目錄
摘要.....I
Abstract.....II
誌謝.....III
目錄.....IV
圖目錄.....V
表目錄.....VI
第一章 緒論.....1
第二章 研究背景.....6
2.1共乘系統.....6
2.2相關研究.....8
第三章 索引方法.....12
3.1 區間樹結構.....12
3.2 建立區間樹.....15
3.3 查詢區間樹.....20
第四章 配對方法.....26
4.1循序配對.....26
4.2反覆配對.....28
4.3範例.....35
第五章 實驗.....40
5.1索引方法之效能評估.....40
5.2配對方法之效能評估.....44
第六章 結論與未來展望.....53
參考文獻.....54

圖目錄
圖一、對稱式配對架構圖.....4
圖二、索引結構.....13
圖三、區間樹.....14
圖四、區間樹建構流程圖.....15
圖五、區間樹T1.....17
圖六、新增一筆資料.....17
圖七、加入一筆新共乘區間於D1.....18
圖八、資料節點D1之分裂.....19
圖九、區間樹T1新增P6並分裂後.....20
圖十、top-k搜尋之流程圖.....21
圖十一、區間樹T2.....23
圖十二、C1與查詢區間重疊天數之上限.....23
圖十三、區間佇列以及候選佇列.....24
圖十四、候選佇列數量已達門檻值.....25
圖十五、循序配對法，三位駕駛和六名乘客的例子.....28
圖十六、駕駛及乘客共乘資訊的權重矩陣.....29
圖十七、駕駛供應總數.....30
圖十八、配對流程.....32
圖十九、反覆配對的方法步驟.....33
圖二十、更新資訊的方法步驟.....35
圖二十一、選擇駕駛D3後之駕駛及乘客配對資訊.....36
圖二十二、駕駛座位表(a)更新前、(b)步驟一二更新後、(c)步驟三四更新後.....37
圖二十三、選擇乘客P3後之駕駛及乘客配對資訊.....38
圖二十四、只剩一名駕駛.....39
圖二十五、不同使用者週期長度建樹的效能分析.....41
圖二十六、不同節點大小之建樹時間.....42
圖二十七、當k=10時，不同數量使用者查詢的效能分析.....43
圖二十八、當k=10時，不同查詢長度的效能分析.....44
圖二十九、配對乘客(a)區間樹駕駛資料100筆 (b)區間樹駕駛資料900.....47
圖三十、配對駕駛(a)區間樹乘客資料100筆(b)區間樹乘客資料900筆.....48
圖三十一、反覆配對之不同k值以配對乘客為控制變數.....50
圖三十二、平均k值以配對乘客為控制變數之不同方法比較.....50
圖三十三、反覆配對之不同k值以配對駕駛為控制變數.....51
圖三十四、平均k值以配對駕駛為控制變數之不同方法比較.....51
圖三十五、不同週期長度(a)以乘客為控制變數(b)以駕駛為控制變數.....52

表目錄
表一、共乘系統之比較.....7
表二、駕駛座位表.....31
表三、配對乘客與候選駕駛平均數量.....46
表四、配對駕駛與候選乘客平均數量.....46
表五、配對乘客與候選駕駛平均數量.....49
表六、配對駕駛與候選乘客平均數量.....49

參考文獻
[1]Ece Kamar and Eric Horvitz, “Collaboration and Shared Plans in the Open World: Studies of Ridesharing,” International Joint Conference on Artificial Intelligence, pp. 187-195, 2009.
[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.
[7]Roberto Wolfler Calvo, Fabio de Luigi, Palle Haastrup and Vittorio Maniezzo, “A Distributed Geographic Information System for the Daily Car Pooling Problem,” Computers and Operations Research, pp. 2263-2278, 2004.
[8]Shangyao Yan, Chun Ying Chen and Yu Fang Lin, “A Model With a Heuristic Algorithm for Solving the Long-Term Many-to-Many Car Pooling Problem,” IEEE Transactions on Intelligent Transportation Systems, pp. 1362-1373, 2011.
[9]Xin Xing, Tobias Warden, Tom Nicolai and Otthein Herzog, “SMIZE: A Spontaneous Ride-Sharing System for Individual Urban Transit,” Conference on Multi-Agent System Technologies, pp. 165-176, 2009.
[10]吳沛儒, “任務型共乘接駁計程車之規劃與設計,” 逢甲大學交通工程與管理學系碩士班碩士論文, 2004.
[11]吳素華, “計程車共乘接駁機制之規劃設計,” 逢甲大學運輸科技與管理學系碩士班碩士論文, 2008.
[12]陳德紹, “動態規劃應用於計程車共乘派遣演算法研發,” 逢甲大學運輸科技與管理學系碩士班碩士論文, 2009.
[13]AVEGO, http://www.avego.com/
[14]Carticipate, http://www.carticipate.com/
[15]Carriva, http://www.carriva.org/MFC/app
[16]Carpool King, http://www.carpoolking.com/tw/zh-tw/
[17]Carpool Zone, https://www.carpoolzone.smartcommute.ca/en/my/index.php
[18]Google map, http://maps.google.com.tw/
[19]Goloco, http://www.goloco.org/greetings/guest
[20]JAYRIDE, http://www.jayride.co.nz/
[21]Kijiji, http://taipei.kijiji.com.tw/
[22]Ocoseats, http://www.coseats.com/
[23]Ride Now, http://www.ridenow.org/
[24]Zimride, http://www.zimride.com/
[25]http://en.wikipedia.org/wiki/Traffic_congestion
[26]桃北北宜基共乘網, http://carpool.tpc.gov.tw/carpool/
[27]交通部全球資訊網, http://210.69.99.7/mocwebGIP/wSite/mp?mp=1