{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,7]],"date-time":"2026-08-07T07:59:15Z","timestamp":1786089555329,"version":"3.56.0"},"reference-count":60,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>\n            Last-mile delivery (LMD) refers to the movement of goods from transportation origins to the final destinations. It has widespread applications such as urban logistics, e-commerce, etc. One fundamental problem in last-mile delivery is route planning, which schedules multiple couriers' routes,\n            <jats:italic>i.e.<\/jats:italic>\n            , sequences of origins and destinations of the requests under certain optimization objectives. Prior studies usually designed heuristic solutions to two strongly NP-hard optimization objectives: minimizing the makespan (\n            <jats:italic>i.e.<\/jats:italic>\n            , maximum travel time) of couriers and total latency (\n            <jats:italic>i.e.<\/jats:italic>\n            , waiting time) of requesters. There is no algorithm with theoretical guarantees for either optimization objective in practical cases. In this paper, we propose a theoretically guaranteed solution framework for both objectives. It achieves both approximation ratios of 6\u03c1, where \u03c1 is the approximation ratio of a core operation, called\n            <jats:italic>k<\/jats:italic>\n            LMD, which plans for one courier a route consisting of\n            <jats:italic>k<\/jats:italic>\n            requests. Leveraging a spatial index called hierarchically separated tree, we further design an efficient approximation algorithm for\n            <jats:italic>k<\/jats:italic>\n            LMD with \u03c1 =\n            <jats:italic>O<\/jats:italic>\n            (log\n            <jats:italic>n<\/jats:italic>\n            ), where\n            <jats:italic>n<\/jats:italic>\n            is the number of requests. Experimental results show that our approach outperforms state-of-the-art methods by averagely 48.4%-96.0% and 49.7%-96.1% for both objectives. Especially in large-scale real datasets, our algorithm has 29.3x-108.9x shorter makespan and 20.2x-175.1x lower total latency than the state-of-the-art algorithms.\n          <\/jats:p>","DOI":"10.14778\/3368289.3368297","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"320-333","source":"Crossref","is-referenced-by-count":69,"title":["Last-mile delivery made practical"],"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":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yongxin","family":"Tong","sequence":"additional","affiliation":[{"name":"Beihang University, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology, Hong Kong SAR, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/www.alibabagroup.com\/","author":"Alibaba Group","year":"2019","unstructured":"Alibaba Group . https:\/\/www.alibabagroup.com\/ , 2019 . Alibaba Group. https:\/\/www.alibabagroup.com\/, 2019."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/www.amazon.com\/","year":"2019","unstructured":"Amazon. https:\/\/www.amazon.com\/ , 2019 . Amazon. https:\/\/www.amazon.com\/, 2019."},{"key":"e_1_2_1_3_1","volume-title":"https:\/\/www.cainiao.com\/","year":"2019","unstructured":"Cainiao. https:\/\/www.cainiao.com\/ , 2019 . Cainiao. https:\/\/www.cainiao.com\/, 2019."},{"key":"e_1_2_1_4_1","volume-title":"https:\/\/tianchi.aliyun.com\/competition\/entrance\/231-581\/introduction","year":"2019","unstructured":"Cainiao dataset published in Tianchi. https:\/\/tianchi.aliyun.com\/competition\/entrance\/231-581\/introduction , 2019 . Cainiao dataset published in Tianchi. https:\/\/tianchi.aliyun.com\/competition\/entrance\/231-581\/introduction, 2019."},{"key":"e_1_2_1_5_1","volume-title":"http:\/\/www.fedex.com\/","year":"2019","unstructured":"FedEx. http:\/\/www.fedex.com\/ , 2019 . FedEx. http:\/\/www.fedex.com\/, 2019."},{"key":"e_1_2_1_6_1","volume-title":"http:\/\/home.cse.ust.hk\/~yzengal\/fesi.pdf","year":"2019","unstructured":"Full paper. http:\/\/home.cse.ust.hk\/~yzengal\/fesi.pdf , 2019 . Full paper. http:\/\/home.cse.ust.hk\/~yzengal\/fesi.pdf, 2019."},{"key":"e_1_2_1_7_1","volume-title":"https:\/\/en.wikipedia.org\/wiki\/Labour_Law_of_the_People's_Republic_of_China","year":"2019","unstructured":"Labour Law of the People's Republic of China. https:\/\/en.wikipedia.org\/wiki\/Labour_Law_of_the_People's_Republic_of_China , 2019 . Labour Law of the People's Republic of China. https:\/\/en.wikipedia.org\/wiki\/Labour_Law_of_the_People's_Republic_of_China, 2019."},{"key":"e_1_2_1_8_1","volume-title":"http:\/\/www.meituan.com\/","year":"2019","unstructured":"Meituan. http:\/\/www.meituan.com\/ , 2019 . Meituan. http:\/\/www.meituan.com\/, 2019."},{"key":"e_1_2_1_9_1","volume-title":"https:\/\/www.crunchbase.com\/organization\/olist","year":"2019","unstructured":"Olist. https:\/\/www.crunchbase.com\/organization\/olist , 2019 . Olist. https:\/\/www.crunchbase.com\/organization\/olist, 2019."},{"key":"e_1_2_1_10_1","volume-title":"https:\/\/www.kaggle.com\/olistbr\/brazilian-ecommerce","year":"2019","unstructured":"Olist dataset published in Kaggle. https:\/\/www.kaggle.com\/olistbr\/brazilian-ecommerce , 2019 . Olist dataset published in Kaggle. https:\/\/www.kaggle.com\/olistbr\/brazilian-ecommerce, 2019."},{"key":"e_1_2_1_11_1","volume-title":"http:\/\/www.seamless.com\/","year":"2019","unstructured":"Seamless. http:\/\/www.seamless.com\/ , 2019 . Seamless. http:\/\/www.seamless.com\/, 2019."},{"key":"e_1_2_1_12_1","volume-title":"https:\/\/en.wikipedia.org\/wiki\/Strong_NP-completeness","year":"2019","unstructured":"Strong NP-completeness. https:\/\/en.wikipedia.org\/wiki\/Strong_NP-completeness , 2019 . Strong NP-completeness. https:\/\/en.wikipedia.org\/wiki\/Strong_NP-completeness, 2019."},{"key":"e_1_2_1_13_1","volume-title":"the development of trip planning engine for the vehicle routing problem in Cainiao (Chinese). https:\/\/yq.aliyun.com\/articles\/697250","year":"2019","unstructured":"The road to the world champion : the development of trip planning engine for the vehicle routing problem in Cainiao (Chinese). https:\/\/yq.aliyun.com\/articles\/697250 , 2019 . The road to the world champion: the development of trip planning engine for the vehicle routing problem in Cainiao (Chinese). https:\/\/yq.aliyun.com\/articles\/697250, 2019."},{"key":"e_1_2_1_14_1","volume-title":"https:\/\/en.wikipedia.org\/wiki\/United_States_labor_law","author":"United States labor law.","year":"2019","unstructured":"United States labor law. https:\/\/en.wikipedia.org\/wiki\/United_States_labor_law , 2019 . United States labor law. https:\/\/en.wikipedia.org\/wiki\/United_States_labor_law, 2019."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_16_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_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796446"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/UIC-ATC-ScalCom.2014.112"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00099"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00131"},{"key":"e_1_2_1_21_1","first-page":"379","volume-title":"WWW","author":"Das A.","year":"2018","unstructured":"A. Das , S. Gollapudi , A. Kim , D. Panigrahi , and C. Swamy . Minimizing latency in online ride and delivery services . In WWW , pages 379 -- 388 , 2018 . A. Das, S. Gollapudi, A. Kim, D. Panigrahi, and C. Swamy. Minimizing latency in online ride and delivery services. In WWW, pages 379--388, 2018."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1030.0052"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1031171.1031208"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.2018.0837"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3291933"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1721837.1721857"},{"key":"e_1_2_1_28_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_29_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733106"},{"key":"e_1_2_1_30_1","first-page":"773","volume-title":"WWW","author":"Ji S.","year":"2019","unstructured":"S. Ji , Y. Zheng , Z. Wang , and T. Li . Alleviating users' pain of waiting: Effective task grouping for online-to-offline food delivery services . In WWW , pages 773 -- 783 , 2019 . S. Ji, Y. Zheng, Z. Wang, and T. Li. Alleviating users' pain of waiting: Effective task grouping for online-to-offline food delivery services. In WWW, pages 773--783, 2019."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11535331_16"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.85"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/GLOCOM.2018.8647947"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-22363-6_7"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10707-019-00359-w"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2018.2861864"},{"key":"e_1_2_1_37_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 , 2013 . S. Ma, Y. Zheng, and O. Wolfson. T-share: A large-scale dynamic taxi ridesharing service. In ICDE, pages 410--421, 2013."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2334313"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.1050.0135"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-91458-9_18"},{"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\/3137765.3137827"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994523"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2016.7498228"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3137628.3137643"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3236187.3236211"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3292390.3292395"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00568-7"},{"key":"e_1_2_1_49_1","volume-title":"Approximation algorithms","author":"Vazirani V. V.","year":"2001","unstructured":"V. V. Vazirani . Approximation algorithms . Springer , 2001 . V. V. Vazirani. Approximation algorithms. Springer, 2001."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2008.925849"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-018-0521-x"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00056"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00133"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971947"},{"key":"e_1_2_1_55_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_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3239552"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00095"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00037"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012245"},{"key":"e_1_2_1_60_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\/3368289.3368297","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:44:19Z","timestamp":1672220659000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368297"}},"subtitle":["an efficient route planning framework with theoretical guarantees"],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":60,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368297"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368297","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}