用Go打造Grab的路径规划和ETA引擎
2020-02-23 263浏览
- 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