随着城市现代化进程的不断加速，城市人口不断增加，人们在生活中经常会遇到早晚高峰时期堵车、打车难等问题。随着GPS、Wi-Fi、RFID以及Bluetooth等无线智能设备的普及，移动轨迹数据被各行业的信息系统不断的收集，因此利用这些数据通过城市的大数据分析与挖掘解决城市中所面临的一些困难与挑战。如今，城市交通管理方面的一些决策对市民的出行起着非常重要的作用，本文着重研究车辆共享移动线路推荐问题。该问题的目的就是对于在不同位置发出乘车请求的用户，将满足一些限制条件的多个乘客作为一个请求组合分配给行驶的车辆，使得车辆的收益最大化。求解该问题对于解决城市打车难、车辆座位利用率低、减小环境污染以及缓解交通都有非常广泛的实践意义。

   本文设计了两个算法解决问题，分别为精确算法以及基于模拟退火的近似算法。在精确算法中，通过三个阶段解决该问题，分别为组合与剪枝、相容性剪枝，计算与推荐。第一阶段主要计算出所有的请求组合情况并通过车辆的容量的限制对请求的组合进行剪枝，车辆的容量限制就是在同一个请求组合的乘客总数不能超过车辆的当前的座位数量。第二阶段通过判断每个请求组合中用户的路径序列是否满足相容性条件，所谓的相容性条件就是在同一个组合中的用户的请求路径序列可以连接为同一条路径序列，为此本文设计了Match算法和Compatibility算法。第三阶段我们通过定义的评价函数计算每个请求组合的利润，并将利润最大的组合推荐给司机，为此我们设计了Scanning算法。另外，通过对模拟退火算法步骤的分析，本文提出了一种近似的解法SA Group Search算法。该方法中最为关键的是在迭代的过程中产生新的可行解，为此设计Produce算法通过增加请求以及对限制条件的判断等方法为每一次迭代产生新的可行解。

   通过对比在两个真实道路网络数据以及一个人工道路网络数据集上的实验表明，本文提出的两个方法都能很好的解决车辆共享移动线路推荐问题，并且对提高座位利用率，增加司机的收入有的明显的效果，同时通过对共享车辆前后车辆的行驶距离的比较表明该问题对环境保护起着间接的作用。对于在大量的用户请求的情况下，本文提出的近似算法能够起到很好的效果。

With the accelerating of urban modernization and the growing of urban population. People often ener traffic jams during rush hours and difficulty in taking a taxi in the morning and evening of our daily life. However, with the popularity of wireless intelligent devices such as GPS, Wi-Fi, RFID and Bluetooth, mobile trajectory data are collected by the information system of industry continuously. Thus the big data collection and analysis are of great help to cities facing troubles and challenges. The decisions that the urban traffic management has made are of importance to the public transportation. This thesis focuses on the recommendation of the mobile route planning on vehicle sharing. And the purpose is to maximize the driver’s profits by combining passengers from different locations and at the same time according with specified conditions as one request group. Solving this besetting problem is of practical significance for the alleviation of taxi-hailing difficulty, low utilization of car seats, environmental pollution and traffic jam.

In this thesis, two methods are designed to solve this problem, which are exact algorithm and the approximate algorithm based on simulated annealing. In the exact algorithm, Three stage are included to solve this problem which are combination and pruning, compatibility and pruning, calculation and recommendation The first stage calculates all the combination of passenger’s requests and pruning the request groups based on the capacity of vehicle. The capacity of the vehicle means that the sum of the passenger in a request group should be less than the capacity of the vehicle. The second stage judges whether a request group satisfies the condition of compatibility. The compatibility means that all the path sequence in a request group can link to one common path. Thus, the Match algorithm and Compatibility algorithm are designed. The third stage calculates the profit of each request group based on the profit function and recommends the max profit group to the driver. So the Scanning algorithm comes into use. In addition, a method named SA Group Search is proposed through analyzing the procedures of simulated annealing algorithm. The key of this method is to solve how to produce a new feasible solution. Therefore, we design the Produce algorithm to produce a new feasible solution according to the constraints.

Experimental results on two real and one synthetic data sets shows that two methods proposed in this thesis can solve the problem of the recommendation of mobile route planning on carpooling. And it has great effect on improving the utilization rate of vehicle seats and increasing the driver’s income. Also, by comparing the distance between two shared vehicles, the environmental pollution is mitigated.  In the case of a large number of user requests, approximate algorithm proves to be effective.

[1] Zheng Y, Liu Y, Yuan J, et al. Urban computing with taxicabs[C]// UBICOMP 2011: Ubiquitous Computing, International Conference, UBICOMP 2011, Beijing, China, September 17-21, 2011, Proceedings. DBLP, 2011:89-98.
[2] Baldacci R, Maniezzo V, Mingozzi A. An Exact method for the car pooling problem based on lagrangean column generation[J]. Operations Research, 2004, 52(3):422-439.
[3] Calvo R W, De Luigi F, Haastrup P, et al. A distributed geographic information system for the daily car pooling problem[J]. Computers & Operations Research, 2004, 31(13):2263-2278.
[4] Wang H, Winter S. Utilizing Taxi Empty Cruise Time to Solve the Short Distance Trip Problem[J]. Its World Congress, 2010.
[5] Gan H Z, Ye X, Wang Q. Investigating the effect of travel time variability on drivers' route choice decisions in Shanghai, China[J]. Transportation Planning & Technology, 2010, 33(8):657-669.
[6] Li Q, Zeng Z, Yang B, et al. Hierarchical route planning based on taxi GPS-trajectories[C]// International Conference on Geoinformatics. IEEE Xplore, 2009:1-5.
[7] Cheng S F, Qu X. A service choice model for optimizing taxi service delivery[C]// International IEEE Conference on Intelligent Transportation Systems. IEEE Xplore, 2009:1-6.
[8] Evans M R, Oliver D, Shekhar S, et al. Fast and exact network trajectory similarity computation: a case-study on bicycle corridor planning[C]// ACM SIGKDD International Workshop on Urban Computing. New York, USA, June 22-27. ACM, 2013:9.
[9] Liao Z. Real-time taxi dispatching using global positioning systems[J]. Communications of the Acm, 2003, 46(5):págs. 81-83.
[10] Lee D H, Wang H, Cheu R L, et al. A Taxi Dispatch System Based on Current Demands and Real-Time Traffic Conditions[J]. Transportation Research Record Journal of the Transportation Research Board, 2004, 1882(1).
[11] Seow K T, Dang N H, Lee D H. A collaborative multiagent taxi-dispatch system[J]. IEEE Transactions on Automation Science & Engineering, 2010, 7(3):607-616.
[12] Li Z, Ding B, Wu F, et al. Attraction and avoidance detection from movements[J]. Proceedings of the Vldb Endowment, 2013, 7(3):157-168.
[13] Huang X, Luo J, Wang X. Finding frequent sub-trajectories with time constraints[C]// ACM SIGKDD International Workshop on Urban Computing. Chicago, IL, USA, August 11-14. ACM, 2013:13.
[14] Kim Y, Han J, Yuan C. TOPTRAC: Topical Trajectory Pattern Mining.[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Hilton, Sydney, August, 10-13. ACM, 2015:587-596.
[15] Jindal T, Giridhar P, Tang L A, et al. Spatiotemporal periodical pattern mining in traffic data[C]// ACM SIGKDD International Workshop on Urban Computing. Chicago, IL, USA, August 11-14. ACM, 2013:11.
[16] Chen Z, Shen H T, Zhou X. Discovering popular routes from trajectories[C]// IEEE, International Conference on Data Engineering. IEEE Computer Society, 2011:900-911.
[17] Liu W, Zheng Y, Chawla S, et al. Discovering spatio-temporal causal interactions in traffic data streams[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. Manchester Grand Hyatt, San Diego, CA, August 21-24. ACM, 2011:1010-1018.
[18] Xue A Y, Zhang R, Zheng Y, et al. Destination prediction by sub-trajectory synthesis and privacy protection against such prediction[C]// IEEE, International Conference on Data Engineering. IEEE, 2013:254-265.
[19] Li X, Pan G, Wu Z, et al. Prediction of urban human mobility using large-scale taxi traces and its applications[J]. Frontiers of Computer Science, 2012, 6(1):111-121.
[20] Li Q, Zheng Y, Xie X, et al. Mining user similarity based on location history[C]// ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Acm-Gis 2008, Irvine, California, Usa, November 5-7, 2008, Proceedings. DBLP, 2008:34.
[21] Ge Y, Xiong H, Tuzhilin A, et al. An energy-efficient mobile recommender system[J]. Soft Computing, 2010, 18(1):35-49.
[22] Applegate D L, Bixby R E, Chvatal V, et al. The traveling salesman problem: a computational study[M]. Princeton university press, 2011.
[23] Denardo E V, Fox B L. Shortest-route methods: 1. Reaching, pruning, and buckets[J]. Operations Research, 1979, 27(1): 161-186.
[24] Dell'Amico M, Fischetti M, Toth P. Heuristic Algorithms for the Multiple Depot Vehicle Scheduling Problem[J]. Management Science, 1993, 39(1):115-125.
[25] Huang J, Huangfu X, Sun H, et al. Backward Path Growth for Efficient Mobile Sequential Recommendation[J]. IEEE Transactions on Knowledge & Data Engineering, 2013, 27(1):46-60.
[26] Wang Y, Zheng Y, Xue Y. Travel time estimation of a path using sparse trajectories[C]// ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, August24-27. ACM, 2014:25-34.
[27] Yuan J, Zheng Y, Zhang C, et al. T-drive: driving directions based on taxi trajectories[C]// ACM Sigspatial International Symposium on Advances in Geographic Information Systems, Acm-Gis 2010, San Jose, Ca, Usa, November 3-5, 2010, Proceedings. DBLP, 2010:99-108.
[28] Yuan J, Zheng Y, Zhang L, et al. Where to find my next passenger[C]// UBICOMP 2011: Ubiquitous Computing, International Conference, UBICOMP 2011, Beijing, China, September 17-21, 2011, Proceedings. DBLP, 2011:109-118.
[29] Yuan N J, Zheng Y, Zhang L, et al. T-Finder: A Recommender System for Finding Passengers and Vacant Taxis[J]. Knowledge & Data Engineering IEEE Transactions on, 2013, 25(10):2390-2403.
[30] Wang H, Li G, Hu H, et al. R3: A real-time route recommendation system[J]. Proceedings of the Vldb Endowment, 2014, 7(13):1549-1552.
[31] Yuan J, Zheng Y, Zhang L, et al. Where to find my next passenger[C]// UBICOMP 2011: Ubiquitous Computing, International Conference, UBICOMP 2011, Beijing, China, September 17-21, 2011, Proceedings. DBLP, 2011:109-118.
[32] Yamamoto K, Uesugi K, Watanabe T. Adaptive Routing of Cruising Taxis by Mutual Exchange of Pathways[C]// Knowledge-Based Intelligent Information and Engineering Systems, International Conference, Kes 2008, Zagreb, Croatia, September 3-5, 2008, Proceedings. DBLP, 2008:559-566.
[33] Reviews E M. The multiple traveling salesman problem: an overview of formulations and solution procedures[J]. Omega, 2006, 34(3):209–219.
[34] Zheng X, Liang X, Xu K. Where to wait for a taxi?[C]// ACM SIGKDD International Workshop on Urban Computing. Beijing, China, August 12-16, 2012ACM, 2012:149-156.
[35] Ma S, Zheng Y, Wolfson O. T-share: A large-scale dynamic taxi ridesharing service[C]// IEEE International Conference on Data Engineering. IEEE Computer Society, 2013:410-421.
[36] Huang Y, Jin R, Bastani F, et al. Large Scale Real-time Ridesharing with Service Guarantee on Road Networks[J]. Proceedings of the Vldb Endowment, 2013, 7(14).
[37] Santos D O, Xavier E C. Taxi and Ride Sharing: A Dynamic Dial-a-Ride Problem with Money as an Incentive[J]. Expert Systems with Applications, 2015, 42(19):6728-6737.
[38] Cao B, Alarabi L, Mokbel M F, et al. SHAREK: A Scalable Dynamic Ride Sharing System[C]// IEEE International Conference on Mobile Data Management. IEEE Computer Society, 2015:4-13.
[39] Ma S, Wolfson O. Analysis and evaluation of the slugging form of ridesharing[C]// 2013:64-73.
[40] Cordeau J F, Laporte G. The dial-a-ride problem: models and algorithms[J]. Annals of Operations Research, 2007, 153(1):29-46.
[41] Dijkstra E W. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1(1):269-271.
[42] 魏延, 谢开贵. 模拟退火算法[J]. 红河学院学报, 1999(4):7-11.
[43] Kirkpatrick S, Jr C D G, Vecchi M P. Optimization by Simulated Annealing[J]. Readings in Computer Vision, 1983, 220(4598):606-615.