{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T14:47:41Z","timestamp":1760453261870},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"7","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,3]]},"abstract":"<jats:p>\n            One of the most important challenges in shared mobility services (\n            <jats:italic>e.g.<\/jats:italic>\n            , ride-sharing and parcel delivery) is planning routes for workers by considering real road conditions. To tackle this challenge, the \"insertion operator\", which computes the optimal route for the worker to serve (\n            <jats:italic>i.e.<\/jats:italic>\n            , insert) the newly appeared delivery request, has been acted as the fundamental operation in existing solutions. However, existing works implicitly assume a static road network, hence are hard to fulfill the real-world scenario, where travel time between two locations is not constant at different times of a day. By contrast, we focus on the insertion operator over time-dependent road networks that capture the periodic pattern of road conditions. We also show that the time complexity of existing solutions would degrade into cubic time and hence such solutions can no longer satisfy the real-time requirement under this real-world setting. To satisfy the need for real-time computation, we propose a data summary to model the time-dependent travel time functions between pairs of vertices in the route. Based on the data summary, we design an efficient solution that can enumerate the best insertion position in linear time while satisfying complex spatiotemporal constraints. Finally, extensive experiments are conducted on real datasets from several applications of shared mobility. The results show that our solution is up to 44.5X faster than the state-of-the-art solution.\n          <\/jats:p>","DOI":"10.14778\/3654621.3654633","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:21:08Z","timestamp":1717107668000},"page":"1669-1682","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Real-Time Insertion Operator for Shared Mobility on Time-Dependent Road Networks"],"prefix":"10.14778","volume":"17","author":[{"given":"Zengyang","family":"Gong","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology"}]},{"given":"Yuxiang","family":"Zeng","sequence":"additional","affiliation":[{"name":"School of Computer Science and Engineering, Beihang University"}]},{"given":"Lei","family":"Chen","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology (Guangzhou), Hong Kong University of Science and Technology"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. Cainiao. https:\/\/global.cainiao.com\/"},{"key":"e_1_2_1_2_1","unstructured":"2023. DiDi Chuxing. https:\/\/www.didiglobal.com\/"},{"key":"e_1_2_1_3_1","unstructured":"2023. Google Map. https:\/\/www.google.com\/maps\/"},{"key":"e_1_2_1_4_1","unstructured":"2023. Meituan. https:\/\/www.meituan.com"},{"key":"e_1_2_1_5_1","unstructured":"2023. Openstreetmap. http:\/\/www.openstreetmap.com\/"},{"key":"e_1_2_1_6_1","unstructured":"2023. Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks. https:\/\/github.com\/gzyhkust\/Insertion-Operator\/blob\/main\/fullpaper.pdf"},{"key":"e_1_2_1_7_1","unstructured":"2023. What is Shared Mobility? https:\/\/sharedusemobilitycenter.org\/what-is-shared-mobility\/"},{"key":"e_1_2_1_8_1","volume-title":"An On-Line Truthful and Individually Rational Pricing Mechanism for Ride-Sharing (SIGSPATIAL '17)","author":"Asghari Mohammad","unstructured":"Mohammad Asghari and Cyrus Shahabi. 2017. An On-Line Truthful and Individually Rational Pricing Mechanism for Ride-Sharing (SIGSPATIAL '17). Association for Computing Machinery, New York, NY, USA, Article 7, 10 pages."},{"key":"e_1_2_1_9_1","volume-title":"2021 IEEE 37th International Conference on Data Engineering (ICDE). 325--335","author":"Chen Di","year":"2021","unstructured":"Di Chen, Ye Yuan, Wenjin Du, Yurong Cheng, and Guoren Wang. 2021. Online Route Planning over Time-Dependent Road Networks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). 325--335."},{"key":"e_1_2_1_10_1","volume-title":"37th IEEE International Conference on Data Engineering, ICDE 2021","author":"Chen Di","year":"2021","unstructured":"Di Chen, Ye Yuan, Wenjin Du, Yurong Cheng, and Guoren Wang. 2021. Online Route Planning over Time-Dependent Road Networks. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19--22, 2021. IEEE, 325--335."},{"key":"e_1_2_1_11_1","volume-title":"Price-and-Time-Aware Dynamic Ridesharing. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE Computer Society","author":"Chen Lu","unstructured":"Lu Chen, Qilu Zhong, Xiaokui Xiao, Yunjun Gao, Pengfei Jin, and Christian S. Jensen. 2018. Price-and-Time-Aware Dynamic Ridesharing. In 2018 IEEE 34th International Conference on Data Engineering (ICDE). IEEE Computer Society, Los Alamitos, CA, USA, 1061--1072."},{"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.1145\/2820783.2820850"},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the 29th International Conference on Advances in Geographic Information Systems","author":"Camila","unstructured":"Camila F. Costa and Mario A. Nascimento. 2021. Last Mile Delivery Considering Time-Dependent Locations. In Proceedings of the 29th International Conference on Advances in Geographic Information Systems (Beijing, China) (SIGSPATIAL '21). Association for Computing Machinery, New York, NY, USA, 121--132."},{"key":"e_1_2_1_15_1","article-title":"PARP: A Parallel Traffic Condition Driven Route Planning Model on Dynamic Road Networks","volume":"12","author":"Dai Tianlun","year":"2021","unstructured":"Tianlun Dai, Bohan Li, Ziqiang Yu, Xiangrong Tong, Meng Chen, and Gang Chen. 2021. PARP: A Parallel Traffic Condition Driven Route Planning Model on Dynamic Road Networks. ACM Trans. Intell. Syst. Technol. 12, 6, Article 73 (dec 2021), 24 pages.","journal-title":"ACM Trans. Intell. Syst. Technol."},{"key":"e_1_2_1_16_1","first-page":"1","article-title":"On-Line Single-Server Dial-a-Ride Problems","volume":"268","author":"Feuerstein Esteban","year":"2001","unstructured":"Esteban Feuerstein and Leen Stougie. 2001. On-Line Single-Server Dial-a-Ride Problems. Theor. Comput. Sci. 268, 1 (oct 2001), 91--105.","journal-title":"Theor. Comput. Sci."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2330163.2330219"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2733085.2733106"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.08.021"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.bdr.2021.100246"},{"key":"e_1_2_1_21_1","first-page":"1251","article-title":"Top-k Vehicle Matching in Social Ridesharing: A Price-Aware Approach","volume":"33","author":"Li Yafei","year":"2021","unstructured":"Yafei Li, Ji Wan, Rui Chen, Jianliang Xu, Xiaoyi Fu, Hongyan Gu, Pei Lv, and Mingliang Xu. 2021. Top-k Vehicle Matching in Social Ridesharing: A Price-Aware Approach. IEEE Transactions on Knowledge and Data Engineering 33, 3 (2021), 1251--1263.","journal-title":"IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_22_1","volume-title":"Mobility-Aware Dynamic Taxi Ridesharing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 961--972","author":"Liu Zhidan","year":"2020","unstructured":"Zhidan Liu, Zengyang Gong, Jiangzhou Li, and Kaishun Wu. 2020. Mobility-Aware Dynamic Taxi Ridesharing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 961--972."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2019.2961341"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3511808.3557132"},{"key":"e_1_2_1_25_1","volume-title":"2013 IEEE 29th International Conference on Data Engineering (ICDE). 410--421","author":"Ma Shuo","year":"2013","unstructured":"Shuo Ma, Yu Zheng, and Ouri Wolfson. 2013. T-share: A large-scale dynamic taxi ridesharing service. In 2013 IEEE 29th International Conference on Data Engineering (ICDE). 410--421."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2014.2334313"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TBDATA.2016.2627223"},{"key":"e_1_2_1_28_1","volume-title":"Reinforcement Learning for Ridesharing: A Survey. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC). 2447--2454","author":"Qin Zhiwei Tony","year":"2021","unstructured":"Zhiwei Tony Qin, Hongtu Zhu, and Jieping Ye. 2021. Reinforcement Learning for Ridesharing: A Survey. In 2021 IEEE International Intelligent Transportation Systems Conference (ITSC). 2447--2454."},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence","author":"Douglas","unstructured":"Douglas O. Santos and Eduardo C. Xavier. 2013. Dynamic Taxi and Ridesharing: A Framework and Heuristics for the Optimization Problem. In Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence (Beijing, China) (IJCAI '13). AAAI Press, 2885--2891."},{"key":"e_1_2_1_30_1","volume-title":"Shared Mobility: Current Practices and Guiding Principles Brief.","author":"Shaheen Susan","year":"2016","unstructured":"Susan Shaheen, Adam Cohen, Ismail Zohdy, and Beaudry Kock. 2016. Shared Mobility: Current Practices and Guiding Principles Brief. (2016)."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18","volume":"119","author":"Siahkamari Ali","year":"2020","unstructured":"Ali Siahkamari, Aditya Gangrade, Brian Kulis, and Venkatesh Saligrama. 2020. Piecewise Linear Regression via a Difference of Convex Functions. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13--18 July 2020, Virtual Event (Proceedings of Machine Learning Research), Vol. 119. PMLR, 8895--8904."},{"key":"e_1_2_1_32_1","volume-title":"Database Systems for Advanced Applications","author":"Tao Qian","unstructured":"Qian Tao, Yuxiang Zeng, Zimu Zhou, Yongxin Tong, Lei Chen, and Ke Xu. 2018. Multi-Worker-Aware Task Planning in Real-Time Spatial Crowdsourcing. In Database Systems for Advanced Applications, Jian Pei, Yannis Manolopoulos, Shazia Sadiq, and Jianxin Li (Eds.). Springer International Publishing, Cham, 301--317."},{"key":"e_1_2_1_33_1","volume-title":"Xhare-a-Ride: A Search Optimized Dynamic Ride Sharing System with Approximation Guarantee. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 1117--1128","author":"Thangaraj Raja Subramaniam","year":"2017","unstructured":"Raja Subramaniam Thangaraj, Koyel Mukherjee, Gurulingesh Raravi, Asmita Metrewar, Narendra Annamaneni, and Koushik Chattopadhyay. 2017. Xhare-a-Ride: A Search Optimized Dynamic Ride Sharing System with Approximation Guarantee. In 2017 IEEE 33rd International Conference on Data Engineering (ICDE). 1117--1128."},{"key":"e_1_2_1_34_1","article-title":"Unified Route Planning for Shared Mobility","volume":"47","author":"Tong Yongxin","year":"2022","unstructured":"Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, and Ke Xu. 2022. Unified Route Planning for Shared Mobility: An Insertion-Based Framework. ACM Trans. Database Syst. 47, 1, Article 2 (may 2022), 48 pages.","journal-title":"An Insertion-Based Framework. ACM Trans. Database Syst."},{"key":"e_1_2_1_35_1","first-page":"11","article-title":"A Unified Approach to Route Planning for Shared Mobility","volume":"11","author":"Tong Yongxin","year":"2018","unstructured":"Yongxin Tong, Yuxiang Zeng, Zimu Zhou, Lei Chen, Jieping Ye, and Ke Xu. 2018. A Unified Approach to Route Planning for Shared Mobility. Proc. VLDB Endow. 11, 11 (jul 2018), 1633--1646.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.14778\/3565838.3565849"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.14778\/3342263.3342265"},{"key":"e_1_2_1_38_1","volume-title":"2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE Computer Society","author":"Wang Yishu","year":"2021","unstructured":"Yishu Wang, Ye Yuan, Hao Wang, Xiangmin Zhou, Congcong Mu, and Guoren Wang. 2021. Constrained Route Planning over Large Multi-Modal Time-Dependent Networks. In 2021 IEEE 37th International Conference on Data Engineering (ICDE). IEEE Computer Society, Los Alamitos, CA, USA, 313--324."},{"key":"e_1_2_1_39_1","volume-title":"An Efficient Insertion Operator in Dynamic Ridesharing Services. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1022--1033","author":"Xu Yi","year":"2019","unstructured":"Yi Xu, Yongxin Tong, Yexuan Shi, Qian Tao, Ke Xu, and Wei Li. 2019. An Efficient Insertion Operator in Dynamic Ridesharing Services. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1022--1033."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2020.3027200"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209978.3210213"},{"key":"e_1_2_1_42_1","volume-title":"Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery; Data Mining","author":"Ye Jieping","year":"2019","unstructured":"Jieping Ye. 2019. Transportation: A Data Driven Approach. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery; Data Mining (Anchorage, AK, USA) (KDD '19). Association for Computing Machinery, New York, NY, USA, 3183."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.14778\/3368289.3368297"},{"key":"e_1_2_1_44_1","volume-title":"37th IEEE International Conference on Data Engineering, ICDE 2021","author":"Zeng Yuxiang","year":"2021","unstructured":"Yuxiang Zeng, Yongxin Tong, and Lei Chen. 2021. HST+: An Efficient Index for Embedding Arbitrary Metric Spaces. In 37th IEEE International Conference on Data Engineering, ICDE 2021, Chania, Greece, April 19--22, 2021. IEEE, 648--659."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.14778\/3424573.3424574"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/3476249.3476267"},{"key":"e_1_2_1_47_1","volume-title":"Online Trichromatic Pickup and Delivery Scheduling in Spatial Crowdsourcing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 973--984","author":"Zheng Bolong","year":"2020","unstructured":"Bolong Zheng, Chenze Huang, Christian S. Jensen, Lu Chen, Nguyen Quoc Viet Hung, Guanfeng Liu, Guohui Li, and Kai Zheng. 2020. Online Trichromatic Pickup and Delivery Scheduling in Spatial Crowdsourcing. In 2020 IEEE 36th International Conference on Data Engineering (ICDE). 973--984."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.14778\/3204028.3204030"},{"key":"e_1_2_1_49_1","volume-title":"Auction-Based Order Dispatch and Pricing in Ridesharing. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1034--1045","author":"Zheng Libin","year":"2019","unstructured":"Libin Zheng, Peng Cheng, and Lei Chen. 2019. Auction-Based Order Dispatch and Pricing in Ridesharing. In 2019 IEEE 35th International Conference on Data Engineering (ICDE). 1034--1045."},{"key":"e_1_2_1_50_1","volume-title":"2023 IEEE 39th International Conference on Data Engineering (ICDE). 3126--3139","author":"Zhu Guanzhou","year":"2023","unstructured":"Guanzhou Zhu, Dong Zhao, Yizong Wang, Haotian Wang, Desheng Zhang, and Huadong Ma. 2023. COME: Learning to Coordinate Crowdsourcing and Regular Couriers for Offline Delivery During Online Mega Sale Days. In 2023 IEEE 39th International Conference on Data Engineering (ICDE). 3126--3139."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3654621.3654633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T22:24:27Z","timestamp":1717107867000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3654621.3654633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3]]},"references-count":50,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2024,3]]}},"alternative-id":["10.14778\/3654621.3654633"],"URL":"https:\/\/doi.org\/10.14778\/3654621.3654633","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,3]]},"assertion":[{"value":"2024-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}