Efficiency Optimization in Dynamic City Express Services
The research focuses on enhancing the efficiency of large-scale dynamic city express services by addressing the drawbacks of current systems. It introduces the Dynamic City Express Problem (DCEP) and proposes a solution involving candidate courier generation and request assignment techniques. By employing strategies like Smallest Incurred Distance First (SIDF) and a two-level priority queue structure, the study aims to improve the effectiveness and speed of service delivery in urban environments.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Effective and Efficient: Large-scale Dynamic City Express Siyuan Zhang , Lu Qin , Yu Zheng*, Hong Cheng The Chinese University of Hong Kong, China Centre for QCIS, FEIT, University of Technology, Sydney, Australia *Microsoft Research, Beijing, China
Current city express services works as follows: 1r 3r 2c 3c 2r 0r 4r (10:05 a.m.) 6r (10:00 a.m.) 1c 7r 5r (10:15 a.m.) R Transit station Truck Region 1 1c 5r Courier (10:00 a.m.) Pickup request (deadline) 0r Delivery 1c 0r 1c Original route of 1c 5r 1c New route of 0r
Background Drawbacks of current systems: Boundary requests are ignored. 1r 3r 2c 3c 2r 0r 4r (10:05 a.m.) 6r (10:00 a.m.) 1c 7r 5r (10:15 a.m.) Process each pickup request individually and immediately We study the dynamic city express problem (DCEP) and aim to design a better central dispatch system
DCEP Problem and Our Solution The Dynamic City Express Problem (DCEP): l(r1): location; d(r1): deadline (10:00 a.m.) NP-complete (10:05 a.m.) (10:15 a.m.) 2. Pickup request as many as possible 3. Come back on time 1. Must deliver Effectiveness: using Smallest Incurred Distance First (SIDF) for assignment. Efficiency: using two-level priority queue structure to speed up.
Step 1: Candidate Courier Generation c1 c3 c1 c2 ts0 c4 c3 c4 (10:00 a.m.) c2 r1 c5 c5 Build network voronoi index: dist from all road intersections to their tsi are precomputed. lower bound: dist(l(c2),l(r1))=d02-dist(l(ts0), l(c2))-dist(l(r1),l(ts2)) Candidate Voronoi regions: ts0, ts1, ts2 cost[dist(l(tsj),l(r1))-radius(tsj)]<d(r1)-tcur radius(tsj) is service range of tsi Candidate couriers: c2, c4, c5 cost[dist(l(c2),l(r1))]<d(r1)-tcur
Step 2: Assign a batch of requests using Smallest Incurred Distance First (SIDF) algorithm The basic algorithm assigns requests according to arrival time 4r c2 3r r7 10 c1 10 r6 5r 10 20 10 r0 r1 r2 Basic route: r5 <r5,c1,r1,r2,20,true> r0 r6 SIDF route: r7 r2 <r7,c1,r1,r2,0,true> r1 <r6,c1,r0,r1,10,true> Our solution first collects requests every tr minutes
Efficiency improvement: Two- level priority queue Initialization: initialize and 2nd iteration No exact distance calculations Satisfy r7 <r7,c1,r1,r2,0,true> <r6,c2,r3,r4,22.1,false> <r6,c2,r3,r4,22.1,false> <r7,c2,r3,r4,39.5,false> <r7,c1,r1,r2,0,false> <r7,c1,r0,r1,5.5,false> <r6,c1,r0,r1,5.6,false> <r5,c1,r1,r2,14.1,false> <r7,c2,r3,r4,39.5,false> <r7,c1,r0,r1,5.5,false> <r6,c1,r0,r1,5.6,false> <r5,c1,r1,r2,14.1,false> 3rd iteration Get dist(r0,r6) and dist(r6,r1) 1st iteration <r6,c1,r0,r1,10,true> <r6,c1,r0,r1,5.6,false> Get dist(r1,r7) and dist(r7,r2) <r7,c1,r1,r2,0,true> <r6,c2,r3,r4,22.1,false> <r7,c1,r1,r2,0,false> <r7,c2,r3,r4,39.5,false> <r5,c1,r1,r2,14.1,false> <r6,c1,r0,r1,10,true> <r5,c1,r1,r2,14.1,false> <r6,c2,r3,r4,22.1,false> 4th iteration <r7,c1,r0,r1,5.5,false> <r6,c1,r0,r1,5.6,false> <r5,c1,r1,r2,14.1,false> <r5,c1,r1,r2,14.1,false> <r7,c1,r0,r1,5.5,false> <r7,c1,r1,r2,0,true> <r6,c1,r0,r1,5.6,false> <r7,c2,r3,r4,39.5,false> Satisfy r6 <r6,c1,r0,r1,10,true> <r6,c2,r3,r4,22.1,false> <r5,c1,r1,r2,14.1,false> <r7,c2,r3,r4,39.5,false>
PERFORMANCE STUDIES We perform simulations on the road network of Beijing Measurements: Satisfaction Ratio(SR): Average incurred distance(AID): Average process time per request Algorithm: Nearest Basic SIDF* (our solution with efficiency improvement)
Effectiveness n: courier number tr: batch time
Efficiency SIDF* is much more efficiency than SIDF!
Scalability N: number of nodes on the road network. The largest road network consists of 81,000 nodes and 104,000 edges.
