{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T19:54:49Z","timestamp":1775850889082,"version":"3.50.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2014,10]]},"abstract":"<jats:p>Urban traffic gridlock is a familiar scene. At the same time, the mean occupancy rate of personal vehicle trips in the United States is only 1.6 persons per vehicle mile. Ridesharing has the potential to solve many environmental, congestion, pollution, and energy problems. In this paper, we introduce the problem of large scale real-time ridesharing with service guarantee on road networks. Trip requests are dynamically matched to vehicles while trip waiting and service time constraints are satisfied. We first propose two scheduling algorithms: a branch-and-bound algorithm and an integer programing algorithm. However, these algorithms do not adapt well to the dynamic nature of the ridesharing problem. Thus, we propose kinetic tree algorithms which are better suited to efficient scheduling of dynamic requests and adjust routes on-the-fly. We perform experiments on a large Shanghai taxi dataset. Results show that the kinetic tree algorithms outperform other algorithms significantly.<\/jats:p>","DOI":"10.14778\/2733085.2733106","type":"journal-article","created":{"date-parts":[[2015,5,12]],"date-time":"2015-05-12T15:37:52Z","timestamp":1431445072000},"page":"2017-2028","source":"Crossref","is-referenced-by-count":145,"title":["Large scale real-time ridesharing with service guarantee on road networks"],"prefix":"10.14778","volume":"7","author":[{"given":"Yan","family":"Huang","sequence":"first","affiliation":[{"name":"University of North Texas"}]},{"given":"Favyen","family":"Bastani","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Ruoming","family":"Jin","sequence":"additional","affiliation":[{"name":"Kent State University"}]},{"given":"Xiaoyang Sean","family":"Wang","sequence":"additional","affiliation":[{"name":"Shanghai Key Laboratory of Data Science, Fudan University"}]}],"member":"320","published-online":{"date-parts":[[2014,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873665"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559907"},{"issue":"2","key":"e_1_2_1_4_1","first-page":"156","article-title":"Modeling and optimizing dynamic dial-a-ride problems","volume":"8","author":"Colorni A.","year":"2001","unstructured":"A. Colorni and G. Righini . Modeling and optimizing dynamic dial-a-ride problems . International Transaction in Operation Research , 8 ( 2 ): 156 -- 166 , 2001 . A. Colorni and G. Righini. Modeling and optimizing dynamic dial-a-ride problems. International Transaction in Operation Research, 8(2):156--166, 2001.","journal-title":"International Transaction in Operation Research"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1060.0283"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02094-0_7"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(91)90083-2"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ITSC.2002.1041302"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00261-9"},{"key":"e_1_2_1_10_1","volume-title":"Department of Transportation","author":"Ghoseiri K.","year":"2011","unstructured":"K. Ghoseiri , A. Haghani , and M. Hamedi . Real-time rideshare matching problem. Final Report of UMD-2009-05, U.S . Department of Transportation , 2011 . K. Ghoseiri, A. Haghani, and M. Hamedi. Real-time rideshare matching problem. Final Report of UMD-2009-05, U.S. Department of Transportation, 2011."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1353343.1353425"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-010-0185-7"},{"key":"e_1_2_1_13_1","volume-title":"Large scale real-time ridesharing with service guarantee on road networks. CoRR, abs\/1302.6666","author":"Huang Y.","year":"2013","unstructured":"Y. Huang , R. Jin , F. Bastani , and X. S. Wang . Large scale real-time ridesharing with service guarantee on road networks. CoRR, abs\/1302.6666 , 2013 . Y. Huang, R. Jin, F. Bastani, and X. S. Wang. Large scale real-time ridesharing with service guarantee on road networks. CoRR, abs\/1302.6666, 2013."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/956676.956677"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316756"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(85)90257-7"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544843"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007638"},{"key":"e_1_2_1_19_1","first-page":"43","volume-title":"Very Large Databases (VLDB)","author":"Mouratidis K.","year":"2006","unstructured":"K. Mouratidis , M. L. Yiu , D. Papadias , and N. Mamoulis . Continuous nearest neighbor monitoring in road networks . In Very Large Databases (VLDB) , pages 43 -- 54 , 2006 . K. Mouratidis, M. L. Yiu, D. Papadias, and N. Mamoulis. Continuous nearest neighbor monitoring in road networks. In Very Large Databases (VLDB), pages 43--54, 2006."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.17.3.351"},{"key":"e_1_2_1_21_1","first-page":"790","volume-title":"Very Large Databases (VLDB)","author":"Tao Y.","year":"2003","unstructured":"Y. Tao , D. Papadias , and J. Sun . The tpr*-tree: an optimized spatio-temporal access method for predictive queries . In Very Large Databases (VLDB) , pages 790 -- 801 , 2003 . Y. Tao, D. Papadias, and J. Sun. The tpr*-tree: an optimized spatio-temporal access method for predictive queries. In Very Large Databases (VLDB), pages 790--801, 2003."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2463695"},{"key":"e_1_2_1_23_1","unstructured":"TICKENGO. Tickengo. http:\/\/tickengo.com.  TICKENGO. Tickengo. http:\/\/tickengo.com."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2733085.2733106","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:17:58Z","timestamp":1672226278000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2733085.2733106"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,10]]},"references-count":23,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2014,10]]}},"alternative-id":["10.14778\/2733085.2733106"],"URL":"https:\/\/doi.org\/10.14778\/2733085.2733106","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2014,10]]}}}