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

2020-02-23 265浏览

  • 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