在通勤尖峰時段或是旅客眾多的觀光景點，妥善使用共乘服務可以避免塞車、汙染或是能源浪費的問題，並且提升乘客的便利性。過去研究大多著重在只有起點、終點的需求上，但是現在有越來越多使用者有拜訪多個興趣點的行程。在多興趣點的查詢條件下，往往會搭配在各個位置預計停留的時間。在考慮到使用者等待與停留時間之後，如果可以針對這些時間去做妥善的安排、調度車輛，可以使得乘客在時間上，達到更佳的搭乘體驗。因此在論文中，我們介紹在使用者等待與停留時間限制下的共乘問題。它同時考量了乘客預計拜訪的多個興趣點，滿足使用者預設的最大等待時間與在各個興趣點的停留時間，為系統找出增加移動時間最少的行程安排。為了同時滿足乘客與車輛的限制，我們先提出了Enhanced Ridesharing Algorithm(ERA)，利用我們所設計的過濾方法，先將不符合使用者條件的車輛刪除，藉此減少計算量，提升運算速率。接著我們再提出Approximate Ridesharing Algorithm(ARA)，利用啟發式搜尋的概念，快速找到一組符合使用者條件並且準確率高的近似答案。我們設計了一系列的實驗，利用兩個真實資料集Oldenburg與California來驗證我們提出的方法。

During peak commuting times or tourist attractions with many passengers, proper use of ridesharing services can avoid traffic congestion, pollution, or a waste of energy, and improve passenger convenience. In the past, most of the research focused on the needs of only the starting location and the destination, but now more and more users have itineraries that visit multiple points of interest. Under the query conditions of multiple points of interest, the estimated staying time at each location is often added. After considering the user's waiting and staying time, if the vehicle can be properly arranged and scheduled for these times, passengers can achieve a better riding experience in terms of time. Therefore, in the paper, we introduce the ridesharing problem with the constraints of waiting and staying time. It also considers multiple points of interest that passengers expect to visit, meets the user's maximum waiting time and staying time at each point of interest, and finds the trip schedule for the system that increases the least travel time cost. To meet the restrictions of both passengers and vehicles, we first proposed the Enhanced Ridesharing Algorithm (ERA). Using the filtering method we designed, we first deleted vehicles that did not meet the user's conditions, thereby reducing the amount of calculation and increasing the calculation efficiency. Then we propose the Approximate Ridesharing Algorithm (ARA), using the concept of heuristic search to quickly find a set of approximate answers that meet the user's conditions and have high accuracy. We designed a series of experiments, using two real datasets Oldenburg and California to verify our proposed method.

[1] S. Ma, Y. Zheng, and O. Wolfson, “T-share: A large-scale dynamic taxi ridesharing service,” in 2013 IEEE 29th International Conference on Data Engineering (ICDE), pp. 410–421, 2013.
[2] S. Ma, Y. Zheng, and O. Wolfson, “Real-time city-scale
taxi ridesharing,” Knowledge and Data Engineering, IEEE Transactions on, vol. 27, pp. 1782–1795, Jul. 2015.
[3] Y. Huang, F. Bastani, R. Jin, and X. S. Wang, “Large scale real-time ridesharing with service guarantee on road networks,” Proc. VLDB Endow., vol. 7, p. 2017–2028,Oct.2014.
[4] Y. Xu, Y. Tong, Y. Shi, Q. Tao, K. Xu, and W. Li, “An efficient insertion operator in dynamic ridesharing services,” in 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1022–1033, 2019.
[5] B. Cao, L. Alarabi, M. F. Mokbel, and A. Basalamah, “Sharek: A scalable dynamic ride sharing system,” in 2015 16th IEEE International Conference on Mobile Data Management, vol. 1, pp. 4–13, 2015.
[6] M. Asghari, D. Deng, C. Shahabi, U. Demiryurek, and Y. Li, “Price-aware real-time ridesharing at scale: an auction-based approach,” in Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, pp. 1–10, Oct. 2016.
[7] L. Chen, Q. Zhong, X. Xiao, Y. Gao, P. Jin, and C. S. Jensen, “Price-and-time-aware dynamic ridesharing,” in 2018 IEEE 34th International Conference on Data Engineering (ICDE), pp. 1061–1072, 2018.
[8] E. D’Andrea, B. Lazzerini, and F. Marcelloni, “A System for Multi-Passenger Urban Ridesharing Recommendations with Ordered Multiple Stops,” The Computer Journal, vol. 63, pp. 657–687, Feb. 2019.
[9] M. T. Mahin and T. Hashem, “Activity-aware ridesharing group trip planning queries for flexible pois,” ACM Trans. Spatial Algorithms Syst., vol. 5, Sep. 2019.
[10] N. Ta, G. Li, T. Zhao, J. Feng, H. Ma, and Z. Gong, “An efficient ridesharing framework for maximizing shared route,” IEEE Transactions on Knowledge and Data Engineering, vol. 30, no. 2, pp. 219–233, 2018.
[11] A. Colorni and G. Righini, “Modeling and optimizing dynamic dial-a-ride problems,” International Transactions in Operational Research, vol. 8, pp. 155–166, Mar. 2001.
[12] P. Healy and R. Moll, “A new extension of local search applied to the Dial-A-Ride Problem,” European Journal of Operational Research, vol. 83, pp. 83–104, May. 1995.
[13] E. Feuerstein and L. Stougie, “On-line single-server dial-a-ride problems,” Theoretical Computer Science, vol. 268, pp. 91–105, Oct. 2001.
[14] J. Cordeau and G. Laporte, “A tabu search heuristic for the static multi-vehicle dial-a-ride problem,” Transportation Research Part B: Methodological, vol. 37, no. 6, pp. 579–594, 2003.
[15] A. Attanasio, J. Cordeau, G. Ghiani, and G. Laporte, “Parallel tabu search heuristics for the dynamic multi-vehicle dial-a-ride problem,” Parallel Computing, vol. 30, pp. 377–387, Mar. 2004.
[16] A. Mourad, J. Puchinger, and C. Chu, “A survey of models and algorithms for optimizing shared mobility,” Transportation Research Part B: Methodological, vol. 123, pp. 323–346, 2019.
[17] D. Gavalas, C. Konstantopoulos, and G. Pantziou, “Chapter 13 design and management of vehicle-sharing systems: a survey of algorithmic approaches,” in Smart Cities and Homes (M. S. Obaidat and P. Nicopolitidis, eds.), pp. 261–289, Boston: Morgan Kaufmann, 2016.
[18] M. Furuhata, M. Dessouky, F. Ordóñez, M. Brunet, X. Wang, and S. Koenig, “Ridesharing: The state-of-the-art and future directions,” Transportation Research Part B: Methodological, vol. 57, p. 28–46, Nov. 2013.
[19] R. S. Thangaraj, K. Mukherjee, G. Raravi, A. Metrewar, N. Annamaneni, and K. Chattopadhyay,“Xhare-a-ride: A search optimized dynamic ride sharing system with approximation guarantee,” in 2017 IEEE 33rd International Conference on Data Engineering (ICDE), pp. 1117–1128, 2017.
[20] Y. Xu, J. Qi, R. BorovicaGajic, and L. Kulik, “Geoprune: Efficiently finding shareable vehicles based on geometric properties,” ArXiv, Jul. 2019.
[21] J. AlonsoMora, S. Samaranayake, A. Wallar, E. Frazzoli, and D. Rus, “On-demand high-capacity ride-sharing via dynamic trip-vehicle assignment,” Proceedings of the National Academy of Sciences, vol. 114, no. 3, pp. 462–467, 2017.
[22] Y. Wang, R. Kutadinata, and S. Winter, “Activity-based ridesharing: Increasing flexibility by time geography,” in Proceedings of the 24th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems, SIGSPACIAL ＇16, (New York, NY, USA), 2016.
[23] X. Fu, J. Huang, H. Lu, J. Xu, and Y. Li, “Top-k taxi recommendation in realtime social-aware ridesharing services,” in Advances in Spatial and Temporal Databases, pp. 221–241, Jul. 2017.
[24] P. Cheng, H. Xin, and L. Chen, “Utility-aware ridesharing on road networks,” in Proceedings of the 2017 ACM International Conference on Management of Data, pp. 1197–1210, May. 2017.
[25] J. Fan, J. Xu, C. Hou, B. Cao, T. Dong, and S. Cheng, “Uroad: An efficient algorithm for large-scale dynamic ridesharing service,” in 2018 IEEE International Conference on Web Services (ICWS), pp. 9–16, 2018.
[26] L. Zheng, L. Chen, and J. Ye, “Order dispatch in price-aware ridesharing,” Proc. VLDB Endow., vol. 11, p. 853–865, Apr. 2018.
[27] L. Zheng, P. Cheng, and L. Chen, “Auction-based order dispatch and pricing in ridesharing,” in 2019 IEEE 35th International Conference on Data Engineering (ICDE), pp. 1034–1045, 2019.
[28] S. Yeung, E. Miller, and S. Madria, “A flexible real-time ridesharing system considering current road conditions,” in 2016 17th IEEE International Conference on Mobile Data Management (MDM), vol. 1, pp. 186–191, 2016.
[29] H. Luo, Z. Bao, F. Choudhury, and S. Culpepper, “Dynamic ridesharing in peak travel periods,” IEEE Transactions on Knowledge and Data Engineering, pp. 1–1, 2019.
[30] E. D’Andrea, D. Di Lorenzo, B. Lazzerini, F. Marcelloni, and F. Schoen, “Path clustering based on a novel dissimilarity function for ridesharing recommenders,” in 2016 IEEE International Conference on Smart Computing (SMARTCOMP), pp. 1–8, 2016.
[31] Y. Hou, X. Li, and C. Qiao, “Tictac: From transfer-incapable carpooling to transfer-allowed carpooling,” in 2012 IEEE Global Communications Conference (GLOBECOM), pp. 268–273, 2012.
[32] B. Coltin and M. Veloso, “Ridesharing with passenger transfers,” in 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems, pp. 3278–3283, 2014.
[33] M. Zhu, X. Liu, M. Qiu, R. Shen, W. Shu, and M. Wu, “Transfer problem in a cloud-based public vehicle system with sustainable discomfort,” Mobile Networks and Applications, vol. 21, Jan. 2016.
[34] T. Brinkhoff, “A framework for generating network-based moving objects,” GeoInformatica, vol. 6, Jun. 2000.
[35] F. Li, D. Cheng, M. Hadjieleftheriou, G. Kollios, and S. Teng, “On trip planning queries in spatial databases,” in Proceedings of the 9th International Conference on Advances in Spatial and Temporal Databases, SSTD＇05, (Berlin, Heidelberg), p. 273–290, 2005.