Last-Mile Delivery Made Practical: An Efficient Route Planning Framework with Theoretical Guarantees

Summary: The paper presents a theoretically guaranteed framework for last-mile route planning, achieving 6rho-approximation for makespan and total latency (rho = kLMD core for one courier). An HST-based spatial index yields rho = O(log n) for kLMD; experiments show 29x–109x makespan and 20x–175x latency gains on large-scale datasets. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 12202
Venue: VLDB
Year: 2020
Pagerank: 5.2415551e-05
Overall Rank: 6,006 | 58.22%
DOI: 10.14778/3368289.3368297

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,171	Butterfly Counting on Uncertain Bipartite Graphs	2022	VLDB	6.3879236e-05
6,631	Demand-Aware Route Planning for Shared Mobility Services	2020	VLDB	4.9856578e-05
6,973	The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries	2020	VLDB	4.878479e-05
7,654	LiteHST: A Tree Embedding based Method for Similarity Search	2023	SIGMOD	4.687476e-05
9,679	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	4.3047774e-05
11,030	VeLP: Vehicle Loading Plan Learning from Human Behavior in Nationwide Logistics System	2024	VLDB	4.1945683e-05
11,122	Swift: A Data-Driven Flight Planning System at Scale	2024	VLDB	4.1945683e-05
11,228	A Hierarchical Grouping Algorithm for the Multi-Vehicle Dial-a-Ride Problem	2023	VLDB	4.1945683e-05
11,335	Faster and Better Solution to Embed Lp Metrics by Tree Metrics	2022	SIGMOD	4.1945683e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
498	Large Scale Real-time Ridesharing with Service Guarantee on Road Networks	2014	VLDB	0.00021678756
2,520	A Unified Approach to Route Planning for Shared Mobility	2018	VLDB	8.6069685e-05
3,235	Online Minimum Matching in Real-Time Spatial Data: Experiments and Analysis	2016	VLDB	7.3355287e-05
11,794	Flexible Online Task Assignment in Real-Time Spatial Data	2017	VLDB	4.1945683e-05
11,814	Spatial Crowdsourcing: Challenges, Techniques, and Applications	2017	VLDB	4.1945683e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
7,444	Efficient Label-Constrained Shortest Path Queries on Road Networks: A Tree Decomposition Approach	2022	VLDB	4.7281454e-05
2,332	Order Dispatch in Price-aware Ridesharing	2018	VLDB	9.0171784e-05
1,555	Efficient Route Planning on Public Transportation Networks: A Labelling Approach	2015	SIGMOD	0.00011395261
6,973	The Simpler The Better: An Indexing Approach for Shared-Route Planning Queries	2020	VLDB	4.878479e-05
1,690	Shortest Path and Distance Queries on Road Networks: Towards Bridging Theory and Practice	2013	SIGMOD	0.00010904736
1,892	Querying Shortest Paths on Time Dependent Road Networks	2019	VLDB	0.00010185573
9,679	Real-time Insertion Operator for Shared Mobility on Time-Dependent Road Networks	2024	VLDB	4.3047774e-05
2,520	A Unified Approach to Route Planning for Shared Mobility	2018	VLDB	8.6069685e-05
6,814	Efficient Algorithms for Optimal Location Queries in Road Networks	2014	SIGMOD	4.9185216e-05
6,631	Demand-Aware Route Planning for Shared Mobility Services	2020	VLDB	4.9856578e-05