臺灣博碩士論文加值系統

計程車在大都市的交通運輸中，已扮演了一個不可或缺的角色，其衍伸出的問題引起各方學者的興趣與關注。對於乘客而言，如何迅速地尋找到計程車。相對地，計程車要如何避免漫無目的地找尋乘客，在繁雜交通中已成為一大挑戰。
本研究之目的在於提出一套適用計程車與共乘乘客的推薦機制。當計程車提出詢問時，能依據不同的時間地點，推薦計程車一條路徑。對於乘客發出推薦請求時，則是推薦乘客附近區域，讓乘客與計程車能快速地找到對方。除此之外，針對需要共乘服務的乘客，也能搜尋適當的乘客搭配共乘。
我們根據10,357台計程車在110天中記錄下的GPS軌跡資料，在不同時段下，以R-Tree的方式分析出熱門的行走路線與載客地點；並利用非合作式賽局理論(non-cooperative game theory)，在多輛計程車需要推薦路徑時，有彼此競爭且獲利互相影響的關係下，從中求出多輛計程車選擇推薦路線的納許均衡(Nash Equilibrium)，以獲得雙贏的結果。當計程車已有載客的情況下，且乘客有共乘需求時，則會不斷地篩選候選乘客，並從中挑選出最適合的對象搭配共乘。
在我們的推薦機制下，藉由分析計程車與乘客的歷史資訊，找出不同時段的熱門載客路徑與地點，並給予相對應的推薦，能有效地縮短計程車跟乘客的等待時間。藉由共乘機制，在乘客容許的等待時間下，讓乘客到達目的地又能減少車資；同時計程車也可以藉由共乘機制，延長載客的距離、提高計程車司機的收入。

The taxicab becomes one of the most important public transportations in many big cities. Customers always suffer from waiting a long time for taxis. Similarly, the taxi drivers spend much time on cruising on the road for finding passengers. Therefore, we present a recommendation mechanism for both taxis and passengers. When taxis and passengers have requests for recommendation, the server provides them with paths and locations.
The first aim of our model is to respectively recommend taxis and passengers for picking up passengers quickly and finding taxis easily. The second purpose is providing taxi-sharing service for passengers who want to save the payment. In our method, we analyze the historical Global Positioning System (GPS) trajectories generated by 10,357 taxis during 110 days and present the service region with time-dependent R-Tree. We formulate the problem of choosing the paths among the taxis in the same region by using non-cooperative game theory, and find out the solution of this game which is known as Nash equilibrium. When a taxi is occupied and the on-board passengers who want taxi-sharing service, the taxi checks the proper passengers for sharing periodically.
In order to verify the proposed recommendation mechanism, the simulation of SUMO, MOVE, and TraCI are adopted to fit our model. The results show that our method can find taxis and passengers efficiently. In addition, applying our method can reduce the payment of passengers and increase the taxi revenue by taxi-sharing.

中文摘要 i
ABSTRACT ii
Acknowledgement iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES ix
Chapter 1 Introduction 1
1.1 Motivation 3
1.2 Objectives 4
1.3 Thesis Overview 4
Chapter 2 Related Works 5
2.1 Existing Systems 5
2.1.1 Taxi Recommender System 5
2.1.2 Taxi Ridesharing System 6
2.2 Related Methods 7
2.2.1 R-Tree 7
2.2.2 Game Theory 8
2.3 Recent Traffic Simulators 10
2.3.1 SUMO 10
2.3.2 MObility model generator for Vehicular networks (MOVE) 10
2.3.3 TraCI 11
Chapter 3 System Structure 13
3.1 Overview 13
3.2 Parameters Definitions 15
3.3 Cognition Phase 17
3.3.1 Taxi Trajectories 17
3.3.2 Movement Logs 18
3.4 Inference Phase 18
3.5 Recommendation Phase 21
3.5.1 Recommendation for One Taxi 21
3.5.2 Non-cooperative Game Model for Taxi Recommendation 23
3.5.3 Passenger Recommendation 27
3.5.4 Recommendation for Taxi-sharing 28
3.5.5 Pricing Scheme 33
Chapter 4 Simulation and Result 35
4.1 Simulation Settings 35
4.1.1 Dataset 35
4.2 Parameters 36
4.2.1 Evaluation Factor 36
4.2.2 Comparing the traditional algorithms with our work 38
4.3 Performance Evaluation 38
4.3.1 The observation of ‘Average Waiting Time of Taxis and Passengers’ 39
4.3.2 The observation of ‘Average Increased Revenue of Taxis’ 42
4.3.3 The observation of ‘Average Payment Saved of Passengers’ 43
4.3.4 The observation of ‘Average Service Time of Passengers’ 44
4.3.5 The observation of ‘Required Average Number of Taxis’ 46
Chapter 5 Conclusions and Future Work 47
REFERENCE 48

[1]K. D. and R. C., SUMO (Simulation of Urban MObility), German Aerospace Centre, 2007. http://sumo.sourceforge.net/
[2]Pedro M. d’Orey, Ricardo Fernandes and Michel Ferreira. Empirical Evaluation of Dynamic and Distribution Taxi-Sharing System. In IEEE International Conference on Intelligent Transportation Systems (ITSC), 2012.
[3]Antonin Guttman. R-trees a dynamic index structure for spatial searching. In Proceedings of the 1984 ACM SIGMOD international conference on Management of data - SIGMOD '84, page 47, 1984
[4]Morgenstern, Oskar and John von Neumann (1947) The Theory of Games and Economic Behavior Princeton University Press
[5]Roger B. Myerson (1991). Game Theory: Analysis of Conflict, Harvard University Press, p. 1. Chapter-preview links, pp. vii-xi.
[6]MOVE (MObility model generator for VEhicular networks): Rapid Generation of Realistic Simulation for VANET., 2007.
http://lens1.csie.ncku.edu.tw/MOVE/index.htm
[7]Shuo Ma, Yu Zheng, and Ouri Wolfson. T-Share: A Large-Scale Dynamic Taxi Ridesharing Service. In IEEE International Conference on Data Engineering, 2013.
[8]Dusit Niyato and Ekram Hossain. Competitive Spectrum Sharing in Cognitive Radio Networks: A Dynamic Game Approach. In IEEE Transaction on Wireless Communication, 2008.
[9]Quality Carpool Service ,http://www.qcar.org.tw/
[10]Aumann, Robert J. (1987), game theory, The New Palgrave: A Dictionary of Economics 2, pp. 460–82.
[11]TraCI (Traffic Control Interface)
http://sourceforge.net/apps/mediawiki/sumo/?title=TraCI
[12]Taipei City Public Transportation Office, Taxi Pricing System
http://www.pto.taipei.gov.tw/ct.asp?xItem=1199267＆ctNode=12602＆mp=117041
http://english.dot.taipei.gov.tw/ct.asp?xItem=53996843＆ctNode=65636＆mp=117002
[13]Jing Yuan, Yu Zheng, Chengyang Zhang, Wenlei Xie, Xing Xie, Guangzhong Sun, and Yan Huang. T-drive: driving directions based on taxi trajectories. In Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems, GIS '10, pages 99-108, New York, NY, USA, 2010. ACM.
[14]Jing Yuan, Yu Zheng, Xing Xie, and Guangzhong Sun. Driving with knowledge from the physical world. In The 17th ACM SIGKDD international conference on Knowledge Discovery and Data mining, KDD'11, New York, NY, USA, 2011. ACM.
[15]Nicholas Jing Yuan, Yu Zheng, Liuhang Zhang, and Xing Xie. T-Finder: A Recommender System for Finding Passengers and Vacant Taxis. In IEEE Transactions on Knowledge and Data Engineering ,2013