用Go打造Grab的路径规划和ETA引擎

1. Go Grab Grab bo.hu@grab.com ETA

2. ● Who’s Grab ● ● ETA ● Go in Grab 2

3. Who’s Grab 3

4. APP 4

5. ● Who’s Grab ● ● ETA ● Go in Grab 5

6. ● ● ETA(Estimated Time of Arrival) 6

7. ● ● GrabFood ● 7

8. ● ● ● 8

9. ● ● ● 9

10. ● Who’s Grab ● ● ETA ● Go in Grab 10

11. ETA 11

12. - vs G2 G4 G5 G7 G8 G3 G1 90 % G6 % 90 % G9 12

13. ETA ● ● ● ● ● ETA 13

14. - OSM https://www.openstreetmap.org 14

15. - OSM OSM Launched Apple Map from OSM 2009 2004 Digital Globe 2016 2012 Telenav OpenStreetCam 2018 2017 Facebook Microsoft Bing Map AI 15

16. - ● ○ ○ ● ○ ○ ● GPS GPS ○ ○ ○ 16

17. - ● ○ ○ ● ○ ○ GPS ● ○ ○ ○ 17

18. - Jakarta Before and After 2016 19,825 Kms 2019 55,692 Kms 18

19. ETA ● ● ● ● ● ETA 19

20. - GPS 20

21. - GPS 21

22. - Map Matching (HMM) vs ● ○ vs GPS ● ● ● Hidden Markov Map Matching Through Noise and Sparseness 22

23. - Map Matching (HMM) ● ○ RTree Nearest Search ● ● 23

24. - Map Matching (HMM) ● ○ RTree Nearest Search ● ○ ● ○ 24

25. - ● ○ GPS ● ○ ○ 25

26. - ● ○ -INF ● ○ Encoded Polyline Algorithm Format (Google) ● encoding/gob ○ ○ ○ Golang schema Serialize/Deserialize 26

27. ETA ● ● ● ● ● ETA 27

28. 28

29. - ● ○ QPS ● ○ ○ ○ V1 - (centralized Redis) V2 - (lock free ring buffer) V3 - spark streaming 29

30. - ● V1 - Redis Aggregation ○ Read QPS Spike 30

31. - ● V2 - Redis + Cache + Time Window ○ ○ CPU 31

32. - ● V3 - ○ ○ ○ 32

33. ETA ● ● ● ● ● ETA 33

34. - Dijkstra 34

35. - Contraction Hierarchies (CH) ● Trade off: vs ● “Basic idea: far away from source / target only use "important" roads (think of highways)” 35

36. - Contraction Hierarchies (CH) ● ● Dijkstra 36

37. - ● ○ ○ slice/map priority queue : Dijkstra flatten ● ○ interface: Geo , WGS84 Web Mercator interface runtime conversion 37

38. - != ● ○ ● ○ ● ○ ○ 38

39. ETA ● ● ● ● ● ETA 39

40. ? 40

41. ETA - ETA= T1 + T2 + T3 + T4 T 3 T 4 New ETA CBD 41

42. ETA - ● ○ ○ ○ Data lake Data warehouse Geo-computed features ● 42

43. ETA - Go ● ● ● ● ● ● 43

44. ETA - Grab-X ● ● ● ● 44

45. ● Who’s Grab ● ● ETA ● Go in Grab 45

46. Go in Grab 46

47. Go in Geo ○ ○ ○ ○ ○ ○ ○ golang/geo qedus/osmpbf go-spatial/tegola tidwall/buntdb lukeroth/gdal jonas-p/go-shp llgcode/draw2d 47

48. Go in Grab ● ○ GrabKit ○ Gandalf ○ Golang Camp ○ Drive SEA Go Go Go ○ book ● 48

49. We’re hiring Say NO to 996: https://github.com/formulahendry/955.WLB bo.hu@grab.com Singapore Seattle Ho Chi Minh City Malaysia Beijing Bangalore Jakarta 49 49

50. Thanks ! bo.hu@grab.com 50