{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,9]],"date-time":"2026-04-09T02:15:39Z","timestamp":1775700939388,"version":"3.50.1"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"13","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,9]]},"abstract":"<jats:p>\n            Ridesharing services have gained global popularity as a convenient, economic, and sustainable transportation mode in recent years. One fundamental challenge in these services is planning the shared-routes (\n            <jats:italic>i.e.<\/jats:italic>\n            , sequences of origins and destinations) among the passengers for the vehicles, such that the platform's total revenue is maximized. Though many methods can solve this problem, their effectiveness is still far from optimal on either empirical study (\n            <jats:italic>e.g.<\/jats:italic>\n            , over 31% lower total revenue than our approach) or theoretical study (\n            <jats:italic>e.g.<\/jats:italic>\n            , arbitrarily bad or impractical theoretical guarantee). In this paper, we study the shared-route planning queries in ridesharing services and focus on designing efficient algorithms with good approximation guarantees. Particularly, our idea is to iteratively search the most profitable route among the unassigned requests for each vehicle, which is simpler than the existing methods. Unexpectedly, we prove this simple method has an approximation ratio of 0.5 to the optimal result. Moreover, we also design an index called\n            <jats:italic>additive tree<\/jats:italic>\n            to improve the efficiency and apply randomization to improve the approximation guarantee. Finally, experimental results on two real datasets demonstrate that our additive-tree-based approach outperforms the state-of-the-art algorithms by obtaining up to 31.4%--127.4% higher total revenue.\n          <\/jats:p>","DOI":"10.14778\/3424573.3424574","type":"journal-article","created":{"date-parts":[[2020,10,28]],"date-time":"2020-10-28T01:15:32Z","timestamp":1603847732000},"page":"3517-3530","source":"Crossref","is-referenced-by-count":32,"title":["The simpler the better"],"prefix":"10.14778","volume":"13","author":[{"given":"Yuxiang","family":"Zeng","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yongxin","family":"Tong","sequence":"additional","affiliation":[{"name":"Beihang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuguang","family":"Song","sequence":"additional","affiliation":[{"name":"Beihang University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,10,27]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"http:\/\/www.didichuxing.com\/","author":"Chuxing Didi","year":"2020","unstructured":"Didi Chuxing . http:\/\/www.didichuxing.com\/ , 2020 . Didi Chuxing. http:\/\/www.didichuxing.com\/, 2020."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/outreach.didichuxing.com\/research\/opendata\/","author":"GAIA.","year":"2020","unstructured":"GAIA. https:\/\/outreach.didichuxing.com\/research\/opendata\/ , 2020 . GAIA. https:\/\/outreach.didichuxing.com\/research\/opendata\/, 2020."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/www.openmp.org\/","author":"MP.","year":"2020","unstructured":"Open MP. https:\/\/www.openmp.org\/ , 2020 . OpenMP. https:\/\/www.openmp.org\/, 2020."},{"key":"e_1_2_1_4_1","volume-title":"http:\/\/www.openstreetmap.com\/","year":"2020","unstructured":"OpenStreetMap. http:\/\/www.openstreetmap.com\/ , 2020 . OpenStreetMap. http:\/\/www.openstreetmap.com\/, 2020."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996974"},{"key":"e_1_2_1_7_1","first-page":"3","volume-title":"AAAI","author":"Bei X.","year":"2018","unstructured":"X. Bei and S. Zhang . Algorithms for trip-vehicle assignment in ride-sharing . In AAAI , pages 3 -- 9 , 2018 . X. Bei and S. Zhang. Algorithms for trip-vehicle assignment in ride-sharing. In AAAI, pages 3--9, 2018."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350234"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00369-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/578533"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-40235-7_15"},{"key":"e_1_2_1_12_1","first-page":"111","article-title":"A survey of dial-a-ride problems: Literature review and recent developments","author":"Ho S. C.","year":"2018","unstructured":"S. C. Ho , W. Y. Szeto , Y. H. Kuo , J. M. Y. Leung , M. Petering , and T. W. H. Tou . A survey of dial-a-ride problems: Literature review and recent developments . Transportation Research Part B Methodological , 111 , 2018 . S. C. Ho, W. Y. Szeto, Y. H. Kuo, J. M. Y. Leung, M. Petering, and T. W. H. Tou. A survey of dial-a-ride problems: Literature review and recent developments. Transportation Research Part B Methodological, 111, 2018.","journal-title":"Transportation Research Part B Methodological"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733106"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(86)90020-2"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2010.5447845"},{"key":"e_1_2_1_16_1","first-page":"5310","volume-title":"NeurIPS","author":"Lesmana N. S.","year":"2019","unstructured":"N. S. Lesmana , X. Zhang , and X. Bei . Balancing efficiency and fairness in on-demand ridesourcing . In NeurIPS , pages 5310 -- 5320 , 2019 . N. S. Lesmana, X. Zhang, and X. Bei. Balancing efficiency and fairness in on-demand ridesourcing. In NeurIPS, pages 5310--5320, 2019."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2012.36"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313433"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2937031"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00058"},{"key":"e_1_2_1_23_1","article-title":"Dynamic ridesharing in peak travel periods","author":"Luo H.","year":"2019","unstructured":"H. Luo , Z. Bao , F. Choudhury , and S. Culpepper . Dynamic ridesharing in peak travel periods . IEEE Transactions on Knowledge and Data Engineering , 2019 . H. Luo, Z. Bao, F. Choudhury, and S. Culpepper. Dynamic ridesharing in peak travel periods. IEEE Transactions on Knowledge and Data Engineering, 2019.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544843"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2334313"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3341818"},{"key":"e_1_2_1_27_1","volume-title":"Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32--38","author":"Munkres J.","year":"1957","unstructured":"J. Munkres . Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32--38 , 1957 . J. Munkres. Algorithms for the assignment and transportation problems. Journal of the society for industrial and applied mathematics, 5(1):32--38, 1957."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.14778\/3339490.3339493"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3332299"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1403657111"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-006-0038-6"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2876480.2876483"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2760880"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3085504.3085584"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292500.3330724"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91458-9_18"},{"key":"e_1_2_1_37_1","article-title":"Two-sided online micro-task assignment in spatial crowdsourcing","author":"Tong Y.","year":"2019","unstructured":"Y. Tong , Y. Zeng , B. Ding , L. Wang , and L. Chen . Two-sided online micro-task assignment in spatial crowdsourcing . IEEE Transactions on Knowledge and Data Engineering , 2019 . Y. Tong, Y. Zeng, B. Ding, L. Wang, and L. Chen. Two-sided online micro-task assignment in spatial crowdsourcing. IEEE Transactions on Knowledge and Data Engineering, 2019.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00568-7"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00095"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2014.6816646"},{"issue":"1","key":"e_1_2_1_42_1","first-page":"32","article-title":"Recent progress in large-scale ridesharing algorithms","volume":"57","author":"Yi X.","year":"2020","unstructured":"X. Yi , T. Yongxin , and L. Wei . Recent progress in large-scale ridesharing algorithms . Journal of Computer Research and Development , 57 ( 1 ): 32 -- 52 , 2020 . X. Yi, T. Yongxin, and L. Wei. Recent progress in large-scale ridesharing algorithms. Journal of Computer Research and Development, 57(1):32--52, 2020.","journal-title":"Journal of Computer Research and Development"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368297"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00037"},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Y. Zeng Y. Tong Y. Song and L. Chen. The simpler the better: An indexing approach for shared-route planning queries in ridesharing (full paper). http:\/\/home.cse.ust.hk\/%7Eyzengal\/simple.pdf 2020.  Y. Zeng Y. Tong Y. Song and L. Chen. The simpler the better: An indexing approach for shared-route planning queries in ridesharing (full paper). http:\/\/home.cse.ust.hk\/%7Eyzengal\/simple.pdf 2020.","DOI":"10.14778\/3424573.3424574"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00101"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012245"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204030"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00096"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3424573.3424574","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:17:39Z","timestamp":1672219059000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3424573.3424574"}},"subtitle":["an indexing approach for shared-route planning queries"],"short-title":[],"issued":{"date-parts":[[2020,9]]},"references-count":49,"journal-issue":{"issue":"13","published-print":{"date-parts":[[2020,9]]}},"alternative-id":["10.14778\/3424573.3424574"],"URL":"https:\/\/doi.org\/10.14778\/3424573.3424574","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,9]]}}}