{"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":1775850889069,"version":"3.50.1"},"reference-count":47,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2018,7]]},"abstract":"<jats:p>\n            There has been a dramatic growth of shared mobility applications such as ride-sharing, food delivery and crowdsourced parcel delivery. Shared mobility refers to transportation services that are shared among users, where a central issue is\n            <jats:italic>route planning<\/jats:italic>\n            . Given a set of workers and requests, route planning finds for each worker a route,\n            <jats:italic>i.e.<\/jats:italic>\n            , a sequence of locations to pick up and drop off passengers\/parcels that arrive from time to time, with different optimization objectives. Previous studies lack practicability due to their conflicted objectives and inefficiency in inserting a new request into a route, a basic operation called\n            <jats:italic>insertion<\/jats:italic>\n            . In this paper, we present a unified formulation of route planning called URPSM. It has a well-defined parameterized objective function which eliminates the contradicted objectives in previous studies and enables flexible multi-objective route planning for shared mobility. We prove the problem is NP-hard and there is no polynomial-time algorithm with constant competitive ratio for the URPSM problem and its variants. In response, we devise an effective and efficient solution to address the URPSM problem approximately. We design a novel dynamic programming (DP) algorithm to accelerate the insertion operation from cubic or quadric time in previous work to only linear time. On basis of the DP algorithm, we propose a greedy based solution to the URPSM problem. Experimental results on real datasets show that our solution outperforms the state-of-the-arts by 1.2 to 12.8 times in effectiveness, and also runs 2.6 to 20.7 times faster.\n          <\/jats:p>","DOI":"10.14778\/3236187.3236211","type":"journal-article","created":{"date-parts":[[2018,9,10]],"date-time":"2018-09-10T12:12:28Z","timestamp":1536581548000},"page":"1633-1646","source":"Crossref","is-referenced-by-count":155,"title":["A unified approach to route planning for shared mobility"],"prefix":"10.14778","volume":"11","author":[{"given":"Yongxin","family":"Tong","sequence":"first","affiliation":[{"name":"Beihang University, China"}]},{"given":"Yuxiang","family":"Zeng","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"given":"Zimu","family":"Zhou","sequence":"additional","affiliation":[{"name":"ETH Zurich, Zurich, Switzerland"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}]},{"given":"Jieping","family":"Ye","sequence":"additional","affiliation":[{"name":"Didi Research Institute, Didi Chuxing, Beijing, China"}]},{"given":"Ke","family":"Xu","sequence":"additional","affiliation":[{"name":"Beihang University, China"}]}],"member":"320","published-online":{"date-parts":[[2018,7]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"Boundary of Chengdu. https:\/\/www.openstreetmap.org\/node\/244077729.  Boundary of Chengdu. https:\/\/www.openstreetmap.org\/node\/244077729."},{"key":"e_1_2_1_2_1","unstructured":"Default Speed Limits in OpenStreetMap. https:\/\/wiki.openstreetmap.org\/wiki\/OSM_tags_for_routing\/Maxspeed.  Default Speed Limits in OpenStreetMap. https:\/\/wiki.openstreetmap.org\/wiki\/OSM_tags_for_routing\/Maxspeed."},{"key":"e_1_2_1_3_1","unstructured":"Didi Chuxing. http:\/\/www.didichuxing.com\/.  Didi Chuxing. http:\/\/www.didichuxing.com\/."},{"key":"e_1_2_1_4_1","unstructured":"GAIA. https:\/\/outreach.didichuxing.com\/research\/opendata\/.  GAIA. https:\/\/outreach.didichuxing.com\/research\/opendata\/."},{"key":"e_1_2_1_5_1","unstructured":"Geofabrik. https:\/\/download.geofabrik.de\/.  Geofabrik. https:\/\/download.geofabrik.de\/."},{"key":"e_1_2_1_6_1","unstructured":"OpenStreetMap. http:\/\/www.openstreetmap.com\/.  OpenStreetMap. http:\/\/www.openstreetmap.com\/."},{"key":"e_1_2_1_7_1","unstructured":"Osmconvert. https:\/\/wiki.openstreetmap.org\/wiki\/Osmconvert.  Osmconvert. https:\/\/wiki.openstreetmap.org\/wiki\/Osmconvert."},{"key":"e_1_2_1_8_1","unstructured":"TLC Trip Record Data. http:\/\/www.nyc.gov\/html\/tlc\/html\/about\/trip_record_data.shtml.  TLC Trip Record Data. http:\/\/www.nyc.gov\/html\/tlc\/html\/about\/trip_record_data.shtml."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/2008623.2008645"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.05.028"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611675114"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/646514.695679"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2996913.2996974"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3139958.3139991"},{"key":"e_1_2_1_15_1","volume-title":"Online computation and competitive analysis","author":"Borodin A.","year":"2005","unstructured":"A. Borodin and R. El-Yaniv . Online computation and competitive analysis . Cambridge University Press , 2005 . A. Borodin and R. El-Yaniv. Online computation and competitive analysis. Cambridge University Press, 2005."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796446"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00099"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3064008"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2820783.2820850"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_2_1_21_1","first-page":"140","volume-title":"15th International IEEE Conference on Intelligent Transportation Systems","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 15th International IEEE Conference on Intelligent Transportation Systems , pages 140 -- 146 , 2012 . P. M. d'Orey, R. Fernandes, and M. Ferreira. Empirical evaluation of a dynamic and distributed taxi-sharing system. In 15th International IEEE Conference on Intelligent Transportation Systems, pages 140--146, 2012."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(00)00261-9"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721857"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330219"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733106"},{"key":"e_1_2_1_26_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_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/0191-2615(86)90020-2"},{"key":"e_1_2_1_29_1","first-page":"266","volume-title":"IJCAI","volume":"11","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 , volume 11 , pages 266 -- 272 , 2011 . A. Kleiner, B. Nebel, and V. A. Ziparo. A mechanism for dynamic ride sharing based on parallel auctions. In IJCAI, volume 11, pages 266--272, 2011."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544843"},{"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.1057\/jors.1976.95"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData.2015.7363837"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2627223"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TITS.2015.2413453"},{"key":"e_1_2_1_36_1","volume-title":"Centre de recherche sur les transports. The construction of routes and schedules for the transportation of the handicapped. Montr\u00e9al: Universit\u00e9 de Montr\u00e9al","author":"Roy S.","year":"1983","unstructured":"S. Roy and U. de Montr\u00e9al . Centre de recherche sur les transports. The construction of routes and schedules for the transportation of the handicapped. Montr\u00e9al: Universit\u00e9 de Montr\u00e9al , Centre de recherche sur les transports, 1983 . S. Roy and U. de Montr\u00e9al. Centre de recherche sur les transports. The construction of routes and schedules for the transportation of the handicapped. Montr\u00e9al: Universit\u00e9 de Montr\u00e9al, Centre de recherche sur les transports, 1983."},{"key":"e_1_2_1_37_1","first-page":"1809","volume-title":"AAAI","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 , pages 1809 -- 1815 , 2012 . Z. B. Rubinstein, S. F. Smith, and L. Barbulescu. Incremental management of oversubscribed vehicle schedules in dynamic dial-a-ride problems. In AAAI, pages 1809--1815, 2012."},{"key":"e_1_2_1_38_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_39_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1403657111"},{"key":"e_1_2_1_40_1","first-page":"2885","volume-title":"IJCAI","volume":"13","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 , volume 13 , pages 2885 -- 2891 , 2013 . D. O. Santos and E. C. Xavier. Dynamic taxi and ridesharing: A framework and heuristics for the optimization problem. In IJCAI, volume 13, pages 2885--2891, 2013."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.156"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_2_1_43_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_44_1","volume-title":"Advanced dial-a-ride algorithms research project. Technical report","author":"Wilson N. H.","year":"1976","unstructured":"N. H. Wilson , R. W. Weissberg , and J. Hauser . Advanced dial-a-ride algorithms research project. Technical report , 1976 . N. H. Wilson, R. W. Weissberg, and J. Hauser. Advanced dial-a-ride algorithms research project. Technical report, 1976."},{"key":"e_1_2_1_45_1","unstructured":"SUMC. What is shared-use mobility? https:\/\/goo.gl\/3Jw6z7 2018.  SUMC. What is shared-use mobility? https:\/\/goo.gl\/3Jw6z7 2018."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1977.24"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/MDM.2016.37"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2743025"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3236187.3236211","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:44:53Z","timestamp":1672220693000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3236187.3236211"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,7]]},"references-count":47,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2018,7]]}},"alternative-id":["10.14778\/3236187.3236211"],"URL":"https:\/\/doi.org\/10.14778\/3236187.3236211","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2018,7]]}}}