臺灣博碩士論文加值系統

傳統共乘網站通常只找出發地或目的地相近的所有對象，由使用者自行挑選理想的共乘組合，就整體的共乘配對而言，可能因而錯失許多共乘的機會，降低使用者參與共乘的意願。我們在先前的研究中提出浮動計價方案，讓共乘者依路程分攤費用，並以回饋金額為目標，為個別駕駛尋找最佳乘客組合。本論文考慮動態環境下，從已配對但未確認的共乘組合中，為新進乘客尋找最適合加入者，除了提昇駕駛所得的回饋金額，還必須使乘客應分攤的費用最低。我們設計以區段概念為基礎的索引方法，利用區段內的搭乘人數，事先計算現有共乘組合的配對資訊；新進乘客可透過此索引迅速查出最佳的共乘組合，而加入後，相關區段的索引資訊便會立即更新。從實驗得知，我們所提方法可比傳統作法平均減少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.

目錄
摘要..............................................................................................................................................................I
ABSTRACT....................................................................................................................................................II
誌謝............................................................................................................................................................III
目錄............................................................................................................................................................IV
附表目錄.....................................................................................................................................................V
附圖目錄....................................................................................................................................................VI
第一章 簡介...........................................................................................................................................1
第二章 相關研究...................................................................................................................................9
2.1 聰明共乘網.........................................................................................................................................9
2.2 共乘網站分類與比較........................................................................................................................13
第三章 方法架構及問題定義................................................................................................................18
3.1 方法架構...........................................................................................................................................18
3.2 問題定義與原理................................................................................................................................21
第四章 更新共乘組合...........................................................................................................................26
4.1 反轉表索引之建立及查詢................................................................................................................26
4.2 區段式索引之建立及查詢................................................................................................................32
4.3 壓縮區段式索引之建立及查詢........................................................................................................36
4.4 區段式索引之更新............................................................................................................................42
第五章 實驗結果與分析.......................................................................................................................46
5.1 實驗資料...........................................................................................................................................46
5.2 時間分析...........................................................................................................................................47
5.3 資料量分析.......................................................................................................................................55
第六章 結論.........................................................................................................................................61
附錄...........................................................................................................................................................62
參考文獻...................................................................................................................................................68






附表目錄
表一、臨界性質......................................................................................................11
表二、乘客群組的資料表......................................................................................12
表三、各駕駛路線記錄表......................................................................................27
表四、駕駛路線反轉表..........................................................................................28
表五、各乘客路線記錄表......................................................................................30
表六、統計駕駛C1路線的已搭乘人數.................................................................31
表七、各對應方格間可能的情況..........................................................................40
表八、各資料下CSIM對SIM的壓縮率...................................................................59
表九、方格壓縮率..................................................................................................60
表十、區段壓縮率..................................................................................................60





附圖目錄
圖一、浮動分攤計價的例子....................................................................................3
圖二、乘客路線........................................................................................................5
圖三、各駕駛的行駛路線........................................................................................5
圖四、最佳共乘組合................................................................................................6
圖五、Smart Carpool System架構圖........................................................................9
圖六、共乘網站的分類..........................................................................................14
圖七、系統架構圖..................................................................................................19
圖八、挑選最佳共乘組合的流程..........................................................................21
圖九、插入的作法..................................................................................................23
圖十、取代的作法..................................................................................................25
圖十一、不同終點的取代對象與預算貼補金額..................................................34
圖十二、相同起點的預算資訊整合至同一區段..................................................35
圖十三、整合於各區段的預算資訊......................................................................36
圖十四、觀察兩區段之間的相差金額及相差對象..............................................41
圖十五、壓縮後的區段索引表格及壓縮資訊......................................................41
圖十六、加入新乘客的影響範圍..........................................................................43
圖十七、SIM更新後的預算資訊............................................................................44
圖十八、CSIM更新後的預算資訊..........................................................................45
圖十九、駕駛數量10的查詢時間........................................................................48
圖二十、駕駛數量15的查詢時間........................................................................49
圖二十一、駕駛數量20的查詢時間....................................................................49
圖二十二、駕駛數量25的查詢時間....................................................................50
圖二十三、駕駛數量30的查詢時間....................................................................50
圖二十四、駕駛數量10的建立時間....................................................................51
圖二十五、駕駛數量15的建立時間....................................................................51
圖二十六、駕駛數量20的建立時間....................................................................52
圖二十七、駕駛數量25的建立時間....................................................................52
圖二十八、駕駛數量30的建立時間....................................................................53
圖二十九、駕駛數量10的更新時間....................................................................53
圖三十、駕駛數量15的更新時間........................................................................54
圖三十一、駕駛數量20的更新時間....................................................................54
圖三十二、駕駛數量25的更新時間....................................................................55
圖三十三、駕駛數量30的更新時間....................................................................55
圖三十四、駕駛數量10的資料量比較................................................................56
圖三十五、駕駛數量15的資料量比較................................................................57
圖三十六、駕駛數量20的資料量比較................................................................57
圖三十七、駕駛數量25的資料量比較................................................................58
圖三十八、駕駛數量30的資料量比較................................................................58

參考文獻
[1]吳沛儒, “任務型共乘接駁計程車之規劃與設計,” 私立交通工程與管理學系碩士班碩士論文, 2004.
[2]陳信彥, “計程車共乘及旅客配對整合模式暨求解演算法之研究,” 國立中央大學土木工程學研究所碩士論文, 2008.
[3]黃運琳, “電動車輛之動態模擬與振動模態分析,” 中華民國第十四屆車輛工程學術研討會論文集, Paper No.A06, 2009.
[4]T. Brinkhoff, “A Framework for Generating Network-based Moving Objects,” GeoInformatica, 6(2):pp.153-180, 2002.
[5]H.H. Chen, Y.H. Wu, C.W. Cho, and C.Y. Chang, “Passenger Search Problem and Solutions for Ride Sharing,” National Computer Symposium, 2009.
[6]J. Dobrosielski, T. Gray, A. Nhan, and M. Stolen, “Carpool.UMD : Community Carpooling,” Conference on Human Factors in Computing Systems, pp.2055-2060, 2007.
[7]R. Geisberger, D. Luxen, S. Neubauer, P. Sanders, and L. Völker, “Fast Detour Computation for Ride Sharing,” Computing Research Repository, abs/0907.5269, 2009.
[8]G. Gidófalvi, T.B. Pedersen, T. Risch, and E. Zeitler, “Highly Scalable Trip Grouping for Large-scale Collective Transportation Systems,” International Conference on Extending Database Technology, pp. 678-689, 2008.
[9]J. Morse, J. Palay, Y. Luon, and S. Nainwal, “CarLoop :Leveraging Common Ground to Develop Long-term Carpools,” Computer Human Interaction, pp.2073-2078, 2007.
[10]I. Timko, M. Böhlen, and J. Gamper, “Sequenced Spatio-Temporal Aggregation in Road Networks,” International Conference on Extending Database Technology, pp.048-059, 2009.
[11]X. Xing, T. Warden, T. Nicolai, and O. Herzog, “SMIZE: A Spontaneous Ride-Sharing System for Individual Urban Transit,” Multiagent System Technologies, pp.165-176, 2009.
[12]Avego Shared Transport, “AEVGO,” http://www.avego.com/.
[13]Bureau of Environmental Protection Tainan County, “Tainan Carpool Website,” http://60.244.114.20/modules.php?name=Nuke_Map.
[14]Carpool, “Carpool,” http://www.carpool.com.tw.
[15]Carpool Connect, “Carpool.Connect,” http://www.carpoolconnect.com/.
[16]Carpool King, “Carpool King,” http://www.carpoolking.com/.
[17]Carpool Zone, “Smart Commute: Choose Your Way!,” http://www.smartcommute.ca/.
[18]CARRIVA, “CARRIVA,” http://www.carriva.org/ceemes/.
[19]Carticipate, “Carticipate,” http://www.carticipate.com/.
[20]Ecolane, “Ecolane DRT,” http://www.ecolane.com/.
[21]GoLoco, “GoLoco,” http://www.goloco.org/.
[22]Google, “Google Maps,” http://maps.google.com/.
[23]Green Cove , “Tecovoiturage,” http://covoiturage-campus.com/index.php/.
[24]JAYRIDE, “JayRide,” http://www.jayride.co.nz/.
[25]Kijiji, “Kijiji,” http://taipei.kijiji.com.tw/.
[26]Ministry of Transportation and Communications R.O.C., “Traffic statistics the number of registered vehicles in major countries,” http://www.motc.gov.tw/motchypage/compare/e3010.xls/.
[27]Ministry of Transportation and Communications R.O.C., “Statistical indicators of important traffic in 2008,” http://www.motc.gov.tw/mocwebGIP/wSite/public/Attachment/f1235700150319.doc/.
[28]Ministry of Transportation and Communications R.O.C., “Uses the vehicle of behavior in the investigation report,” http://www.motc.gov.tw/motchypage/survey/20091102154105_2.doc/.
[29]Piggyback, “Piggyback,” http://www.piggybackmobile.com/.
[30]Ride Now dynamic ridesharing system, “Ride Now,” http://www.ridenow.org/.
[31]United Nations Envirnment Programme, “UNEP 2009 Annual Report,” http://www.unep.org/PDF/UNEP_AR_2009_FINAL.pdf/.
[32]Yahoo!, “Yahoo! Maps,” http://tw.maps.yahoo.com/.