UberEATS 外卖服务的智能派单系统

UberEATS 外卖服务的智能派单系统

1. Intelligent Dispatch for UberEATS Peng Zhai, Uber Engineering (NYC) QCon Shanghai 2017
6. Agenda QCon Shanghai 2017 • Intros • UberEATS Overview • Dispatch Internals • System Evolution • Challenges • Q&A
7. UberEATS 101
8. UberEATS Deliver the right food for right now
9. UberEATS Quick Facts ● Launched in Toronto in December 2015 ● Available in 120+ cities (and expanding) ● Eclipses Uber’s main ride-hailing business in some markets ● Profitable in 20+ cities ● Hugely enterprise focused
10. Our mission Make eating well effortless at any time, for anyone
11. Temp control Restaurant selection Nutrition info Dish search Smart recommendations Flawless deliveries Make eating well effortless at any time, for anyone Speed Scheduling Operating hours Low cost More cities Dietary restrictions
12. UberEATS A Virtuous Cycle
13. UberEATS Impacts Restaurant Growth “We weren’t prepared for the volume that came in” through UberEats this year, Mr. Gordon, 46, said. “I myself, as an owner, had to work three weeks straight cooking on the food line just to keep up.” https://www.nytimes.com/2017/09/23/technology/ubereats-fooddelivery.html
14. UberEATS Impacts Courier Earning Opportunities
15. Eater Experiences Two ways to order Most eaters order in the UberEATS app Web ordering is also available at (available for Android or iPhone) UberEATS.com
16. Restaurant Experiences iPad or Android Order Page Delivery Page
17. Courier Experiences On-Trip Navigation
18. Courier Experiences On-Trip Navigation - Guided Pick-Up (cont’d)
19. Life of a UberEATS Order Events 1 A customer places an order on the UberEATS app or at UberEATS.com 2 The restaurant receives an order notification on an UberEATS iPad in the restaurant 3 The restaurant adjust prep time (if needed), accepts the order and begins preparing the food 4 When the food is nearly ready, the UberEATS system automatically requests a courier 5 The courier arrives at the restaurant, picks up the food, and delivers to the customer
20. UberEATS Dispatch
21. Dispatch A system that ... Makes Demand-Supply Matching Decisions
22. Dispatch Expectations Eater ● Fast drop-off ● Low delivery fee ● 24/7 Restaurant ● Short wait time ● Low Unfulfillment Courier ● Short wait time ● Smart route planning ● Quick hand-off
23. Our mission Short wait time Fast drop-off Quick hand-off Low unfulfillment Low cost Smart route planning Move anything quickly, reliably and efficiently anywhere, at any time Cities 24/7
24. Dispatch A Case Study
25. Dispatch Main Tasks ● ● Prediction ○ Food Preparation Times (Ready, Cold) ○ Waypoint Times (Parking, Walk to Restaurants, Service Time, Hand-Off) ○ Travel Times (Pick-up to Drop-off) Optimization ○ Dispatch N jobs to M couriers (aka, “Vehicle-Routing Problem”) ○ Satisfy business constraints
26. Dispatch “Piece of cake huh?” “Well…”
27. Dispatch Challenges Prediction Is Hard ● We want the prediction to be accurate to ‘minutes’ ● Ground truth is hard to obtain ● Too many things can impact accuracy: vehicle types, cuisine types, and other factors
28. Dispatch Challenges (cont’d) Optimization Is Hard We want to ● solve an NP-Hard problem with a large problem space within seconds ● improve efficiency without compromising delivery quality
30. Dispatch Key Components
31. Dispatch Data Pipeline
32. Dispatch Data Pipeline https://eng.uber.com/ureplicator/
33. Dispatch Prediction Solution
34. Dispatch Prediction Solution (cont’d)
35. Dispatch Prediction Solution (cont’d) https://eng.uber.com/michelangelo/
36. Dispatch Optimization Solution
37. Dispatch Core Algorithm: An Augmented Vehicle Routing Problem (VRP)
38. Dispatch Optimization Solution
39. Dispatch Optimization Solution ● Resource collection ○ ● Plan Generation ○ ● Post-filter infeasible plans Plan Evaluation ○ ● Pre-filter ineligible supplies Evaluate plans with an objective function Find optimal solution set ○ Algorithm: Simulated annealing, Max Set Packing, Linear Programming ○ Exact vs approximate solvers
40. Dispatch Components
41. Dispatch Intelligence ● Monitoring ○ ● Experiments ○ ● Dashboard, Alerts, Replay Switchback, A/B Simulation https://eng.uber.com/argos/
42. Evolution
43. Dispatch An Example Business Objective: Minimize Estimated Time of Arrival (ETA)
50. Dispatch Evolution What’s the next big thing?
51. Dispatch The Evolution - Continuous Optimization
52. Dispatch The Evolution - Continuous Optimization (cont’d)
53. Dispatch The Evolution - Continuous Optimization (cont’d) 28 Min Savings! Before - Total ETA: 66 minutes After - Total ETA: 38 minutes
54. Challenges
55. Dispatch Challenges ● Extreme weather conditions ● Supply positioning ● Predictive dispatch
56. Credits
57. Credits Teams @ Uber Special thanks to ● Engineering ● Data Science ● Product ● City Ops ● SRE
58. Credits Creatives • Icons made by Freepik from Flaticon is licensed by Creative Commons BY 3.0
59. Q&A ubereats.com