{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T03:06:06Z","timestamp":1787022366953,"version":"build-2736575974"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2020,3]]},"abstract":"<jats:p>The dramatic development of shared mobility in food delivery, ridesharing, and crowdsourced parcel delivery has drawn great concerns. Specifically, shared mobility refers to transferring or delivering more than one passenger\/package together when their traveling routes have common sub-routes or can be shared. A core problem for shared mobility is to plan a route for each driver to fulfill the requests arriving dynamically with given objectives. Previous studies greedily and incrementally insert each newly coming request to the most suitable worker with a minimum travel cost increase, which only considers the current situation and thus not optimal. In this paper, we propose a demand-aware route planning (DARP) for shared mobility services. Based on prediction, DARP tends to make optimal route planning with more information about requests in the future. We prove that the DARP problem is NP-hard, and further show that there is no polynomial-time deterministic algorithm with a constant competitive ratio for the DARP problem unless P=NP. Hence, we devise an approximation algorithm to realize the insertion operation for our goal. With the insertion algorithm, we devise a prediction based solution for the DARP problem. Extensive experiment results on real datasets validate the effectiveness and efficiency of our technique.<\/jats:p>","DOI":"10.14778\/3384345.3384348","type":"journal-article","created":{"date-parts":[[2020,3,26]],"date-time":"2020-03-26T10:21:06Z","timestamp":1585218066000},"page":"979-991","source":"Crossref","is-referenced-by-count":51,"title":["Demand-aware route planning for shared mobility services"],"prefix":"10.14778","volume":"13","author":[{"given":"Jiachuan","family":"Wang","sequence":"first","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peng","family":"Cheng","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Libin","family":"Zheng","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chao","family":"Feng","sequence":"additional","affiliation":[{"name":"AI Labs, DiDi Chuxing, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China and The University of New South Wales, Australia"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zheng","family":"Wang","sequence":"additional","affiliation":[{"name":"AI Labs, DiDi Chuxing, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,3,26]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"[online] didi chuxing. http:\/\/www.didichuxing.com\/.  [online] didi chuxing. http:\/\/www.didichuxing.com\/."},{"key":"e_1_2_1_2_1","unstructured":"[online] geofabrik. https:\/\/download.geofabrik.de\/.  [online] geofabrik. https:\/\/download.geofabrik.de\/."},{"key":"e_1_2_1_3_1","unstructured":"[online] meituan. https:\/\/www.meituan.com\/.  [online] meituan. https:\/\/www.meituan.com\/."},{"key":"e_1_2_1_4_1","unstructured":"[online] tlc trip record data. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page\/.  [online] tlc trip record data. https:\/\/www1.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page\/."},{"key":"e_1_2_1_5_1","unstructured":"[online] uber. https:\/\/www.uber.com\/.  [online] uber. https:\/\/www.uber.com\/."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.05.028"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_2_1_8_1","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1007\/3-540-46541-3_53","volume-title":"STACS","author":"Ascheuer N.","year":"2000","unstructured":"N. Ascheuer , S. O. Krumke , and J. Rambau . Online dial-a-ride problems: Minimizing the completion time . In STACS , volume 1770 of Lecture Notes in Computer Science , pages 639 -- 650 . Springer , 2000 . N. Ascheuer, S. O. Krumke, and J. Rambau. Online dial-a-ride problems: Minimizing the completion time. In STACS, volume 1770 of Lecture Notes in Computer Science, pages 639--650. Springer, 2000."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996974"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139991"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796446"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064008"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SAHCN.2018.8397114"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820850"},{"key":"e_1_2_1_15_1","volume-title":"International transactions in operational research, 8(2):155--166","author":"Colorni A.","year":"2001","unstructured":"A. Colorni and G. Righini . Modeling and optimizing dynamic dial-a-ride problems . International transactions in operational research, 8(2):155--166 , 2001 . A. Colorni and G. Righini. Modeling and optimizing dynamic dial-a-ride problems. International transactions in operational research, 8(2):155--166, 2001."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2005.02.038"},{"key":"e_1_2_1_17_1","volume-title":"Statistics for spatio-temporal data","author":"Cressie N.","year":"2015","unstructured":"N. Cressie and C. K. Wikle . Statistics for spatio-temporal data . John Wiley & Sons , 2015 . N. Cressie and C. K. Wikle. Statistics for spatio-temporal data. John Wiley & Sons, 2015."},{"key":"e_1_2_1_18_1","first-page":"140","volume-title":"ITSC","author":"Orey P. M.","year":"2012","unstructured":"P. M. d' Orey , R. Fernandes , and M. Ferreira . Empirical evaluation of a dynamic and distributed taxi-sharing system . In ITSC , pages 140 -- 146 . IEEE, 2012 . P. M. d'Orey, R. Fernandes, and M. Ferreira. Empirical evaluation of a dynamic and distributed taxi-sharing system. In ITSC, pages 140--146. IEEE, 2012."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00261-9"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721857"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2015.7218644"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330219"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733106"},{"key":"e_1_2_1_24_1","volume-title":"ORSA\/TIMS National Meeting","author":"Hung H.","year":"1982","unstructured":"H. Hung , R. Chapman , W. Hall , and E. Neigut . A heuristic algorithm for routing and scheduling dial-a-ride vehicles . In ORSA\/TIMS National Meeting , 1982 . H. Hung, R. Chapman, W. Hall, and E. Neigut. A heuristic algorithm for routing and scheduling dial-a-ride vehicles. In ORSA\/TIMS National Meeting, 1982."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(86)90020-2"},{"key":"e_1_2_1_27_1","first-page":"266","volume-title":"IJCAI","author":"Kleiner A.","year":"2011","unstructured":"A. Kleiner , B. Nebel , and V. A. Ziparo . A mechanism for dynamic ride sharing based on parallel auctions . In IJCAI , pages 266 -- 272 . IJCAI\/AAAI, 2011 . A. Kleiner, B. Nebel, and V. A. Ziparo. A mechanism for dynamic ride sharing based on parallel auctions. In IJCAI, pages 266--272. IJCAI\/AAAI, 2011."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3065386"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820837"},{"key":"e_1_2_1_30_1","first-page":"410","volume-title":"ICDE","author":"Ma S.","year":"2013","unstructured":"S. Ma , Y. Zheng , and O. Wolfson . T-share: A large-scale dynamic taxi ridesharing service . In ICDE , pages 410 -- 421 . IEEE, 2013 . S. Ma, Y. Zheng, and O. Wolfson. T-share: A large-scale dynamic taxi ridesharing service. In ICDE, pages 410--421. IEEE, 2013."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2334313"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2627223"},{"key":"e_1_2_1_33_1","first-page":"1","volume-title":"1st international physical internet conference","author":"Roug J.-F.","year":"2014","unstructured":"J.-F. Roug ` es and B. Montreuil. Crowdsourcing delivery: New interconnected business models to reinvent delivery . In 1st international physical internet conference , pages 1 -- 19 , 2014 . J.-F. Roug`es and B. Montreuil. Crowdsourcing delivery: New interconnected business models to reinvent delivery. In 1st international physical internet conference, pages 1--19, 2014."},{"key":"e_1_2_1_34_1","volume-title":"Incremental management of oversubscribed vehicle schedules in dynamic dial-a-ride problems","author":"Rubinstein Z. B.","year":"2012","unstructured":"Z. B. Rubinstein , S. F. Smith , and L. Barbulescu . Incremental management of oversubscribed vehicle schedules in dynamic dial-a-ride problems . In AAAI. AAAI Press , 2012 . Z. B. Rubinstein, S. F. Smith, and L. Barbulescu. Incremental management of oversubscribed vehicle schedules in dynamic dial-a-ride problems. In AAAI. AAAI Press, 2012."},{"key":"e_1_2_1_35_1","first-page":"2885","volume-title":"IJCAI","author":"Santos D. O.","year":"2013","unstructured":"D. O. Santos and E. C. Xavier . Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem . In IJCAI , pages 2885 -- 2891 . IJCAI\/AAAI, 2013 . D. O. Santos and E. C. Xavier. Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem. In IJCAI, pages 2885--2891. IJCAI\/AAAI, 2013."},{"key":"e_1_2_1_36_1","volume-title":"Shared mobility: current practices and guiding principles. Technical report","author":"Shaheen S.","year":"2016","unstructured":"S. Shaheen , A. Cohen , and I. Zohdy . Shared mobility: current practices and guiding principles. Technical report , 2016 . S. Shaheen, A. Cohen, and I. Zohdy. Shared mobility: current practices and guiding principles. Technical report, 2016."},{"key":"e_1_2_1_37_1","unstructured":"SUMC. [online] what is shared-use mobility? https:\/\/goo.gl\/3Jw6z7 2018.  SUMC. [online] what is shared-use mobility? https:\/\/goo.gl\/3Jw6z7 2018."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.156"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137643"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_2_1_41_1","volume-title":"Advanced dial-a-ride algorithms. Technical report","author":"Wilson N. H.","year":"1975","unstructured":"N. H. Wilson , R. Weissberg , B. Higonnet , and J. Hauser . Advanced dial-a-ride algorithms. Technical report , 1975 . N. H. Wilson, R. Weissberg, B. Higonnet, and J. Hauser. Advanced dial-a-ride algorithms. Technical report, 1975."},{"key":"e_1_2_1_42_1","volume-title":"Advanced dial-a-ride algorithms research project. Technical report","author":"Wilson N. H. M.","year":"1976","unstructured":"N. H. M. Wilson , R. W. Weissberg , and J. Hauser . Advanced dial-a-ride algorithms research project. Technical report , 1976 . N. H. M. Wilson, R. W. Weissberg, and J. Hauser. Advanced dial-a-ride algorithms research project. Technical report, 1976."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00095"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2016.37"},{"key":"e_1_2_1_45_1","first-page":"2258","volume-title":"WWW","author":"Yuen C. F.","year":"2019","unstructured":"C. F. Yuen , A. P. Singh , S. Goyal , S. Ranu , and A. Bagchi . Beyond shortest paths: Route recommendations for ride-sharing . In WWW , pages 2258 -- 2269 . ACM, 2019 . C. F. Yuen, A. P. Singh, S. Goyal, S. Ranu, and A. Bagchi. Beyond shortest paths: Route recommendations for ride-sharing. In WWW, pages 2258--2269. ACM, 2019."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368297"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00037"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3298239.3298479"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2997016"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204030"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3384345.3384348","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T04:52:12Z","timestamp":1672203132000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3384345.3384348"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3]]},"references-count":49,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,3]]}},"alternative-id":["10.14778\/3384345.3384348"],"URL":"https:\/\/doi.org\/10.14778\/3384345.3384348","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2020,3]]}}}