北京航空航天大学：动态拼车服务中的高效插入操作（PPT讲稿）An Efficient Insertion Operator in Dynamic Ridesharing Services

An Efficient Insertion Operator in Dynamic Ridesharing Services YiXu, Yongxin Tong, Yexuan Shi, Qian Tao, Ke Xu Wei Li Key Laboratory of Software Development Environment, School of Computer Science and Engineering, Beihang University, China O)北京航空航天大学 BEIHANG UNIVERSITY

An Efficient Insertion Operator in Dynamic Ridesharing Services Yi Xu, Yongxin Tong, Yexuan Shi, Qian Tao, Ke Xu, Wei Li Key Laboratory of Software Development Environment, School of Computer Science and Engineering, Beihang University, China

Outline o Background o Problem statement o Partition-based framework e Segment-based dp algorithm ● Experiments o Conclusion

Outline 2 ⚫ Background ⚫ Problem Statement ⚫ Partition-based Framework ⚫ Segment-based DP Algorithm ⚫ Experiments ⚫ Conclusion

ynamic Ridesharing Services o Dynamic ridesharing: services that arrange one-time shared rides on short notice

Dynamic Ridesharing Services ⚫ Dynamic ridesharing: services that arrange one-time shared rides on short notice 3

ynamic Ridesharing Services o Dynamic ridesharing: services that arrange one-time shared rides on short notice Car-pooling DIDi destination of B U BER lyn VI destination of A origin of A ans 7 Arrondiss origin of B

Dynamic Ridesharing Services ⚫ Dynamic ridesharing: services that arrange one-time shared rides on short notice. ⚫ Car-pooling, 4 origin of A destination of A origin of B destination of B

ynamic Ridesharing Services o Dynamic ridesharing: services that arrange one-time shared rides on short notice Car-pooling, Food Delivery restaurant seamless 口碑 Arrondiss 美团 residence Arrondiss

Dynamic Ridesharing Services ⚫ Dynamic ridesharing: services that arrange one-time shared rides on short notice. ⚫ Car-pooling, Food Delivery, 5 restaurant residence

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