ynamic Ridesharing Services o Dynamic ridesharing: services that arrange one-time shared rides on short notice Car-pooling, Food Delivery, Last-mile Logistics seller (Sp) dEx Arrondiss N△O菜鸟 customer aris 7e How to plan a route for the worker is central for DR
Dynamic Ridesharing Services ⚫ Dynamic ridesharing: services that arrange one-time shared rides on short notice. ⚫ Car-pooling, Food Delivery, Last-mile Logistics 6 seller customer How to plan a route for the worker is central for DR
Dynamic Ridesharing Services o The problem of route planning in dynamic ridesharing is very difficult and most existing solutions are heuristic T-share Adaptive Prune Kinetic insertion Greedy DP ICDE 13 [EJOR'111 TVLDB 14 VLDB18 上二r “ sasw mw/h trak- s mee I rEp. he sprial Nsw AM *hwan in 4c山,,P← enter A-m [=2==J Causae ast Ct Insertion Operator: insert a new request into the current route
Dynamic Ridesharing Services ⚫ The problem of route planning in dynamic ridesharing is very difficult and most existing solutions are heuristic 7 T-share Adaptive insertion Kinetic Prune GreedyDP [ICDE’13] [EJOR’11] [VLDB’14] [VLDB’18] Insertion Operator: insert a new request into the current route
Insertion Operator Given: old route→: new request 6。 Insertion: finding the appropriate location to Insert the new request Goal old route new route
Insertion Operator 8 𝑙1 𝑙2 𝑙3 𝑙4 𝑜𝑟 𝑑𝑟 : old route : new route 𝑙1 𝑙2 𝑙3 𝑙4 𝑜𝑟 𝑑𝑟 : old route : new request Insertion: finding the appropriate location to Insert the new request Given: Goal:
Outline ● Background ● Problem statement o Partition-based framework e Segment-based dp algorithm ● Experiments o Conclusion
Outline ⚫ Background ⚫ Problem Statement ⚫ Partition-based Framework ⚫ Segment-based DP Algorithm ⚫ Experiments ⚫ Conclusion 9
Worker ● Worker:W=〈on,Cp ●O,: current location w: capacity o Capacity constraint: the number of passengers he takes at the same time is less than his capacity ● Request:r=(o Pjuy,ur,cγ,cr origin and destination o tr,e release time and deadline ●cr: occupation e Deadline constraint: the request is delivered before the deadline
Worker ⚫ Worker: 𝑤 = 𝑜𝑤, 𝑐𝑤 ⚫ 𝑜𝑤: current location ⚫ 𝑐𝑤: capacity ⚫ Capacity constraint: the number of passengers he takes at the same time is less than his capacity. ⚫ Request: 𝑟 = 𝑜𝑟 , 𝑑𝑟 ,𝑡𝑟 , 𝑒𝑟 , 𝑐𝑟 ⚫ 𝑜𝑟 ,𝑑𝑟 : origin and destination ⚫ 𝑡𝑟 , 𝑒𝑟 : release time and deadline ⚫ 𝑐𝑟 : occupation ⚫ Deadline constraint: the request is delivered before the deadline. 10