Yannan_iRun_082714
?
0 likes?294 views
Yannan Zheng developed an app called iRun to recommend running routes between locations with customized distances. The app builds a graph of roads in Cambridge and Boston and cleans the data to reduce redundant information. It then uses Dijkstra's algorithm and Monte Carlo simulations to find optimal routes that meet the desired distance while minimizing turns, loops, and repetitive segments. The goal is to recommend different routes for runners based on specified distance needs.
Yannan_iRun_082714
- 2. Here is the problem Sometimes, I want to take a run from Lab to Home
- 3. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days
- 4. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days I want to run different routes on different days
- 5. Here is the problem Sometimes, I want to take a run from Lab to Home But I want to run different miles on different days I want to run different routes on different days How to find routes with targeted distances?
- 8. Building a graph of Cambridge and Boston
- 9. Data Clean Up: Original Map
- 10. Data Clean Up: Remove un-runnable area
- 11. Data Clean Up: Remove isolated islands
- 12. Data Clean Up: Remove spikes
- 13. Data Clean Up: Combine parallel roads
- 14. Data Clean Up: Remove redundant nodes
- 15. Original Map
- 16. After Data Clean Up 103,365 nodes, and 225,766 edges 17,480 nodes, and 49,354 edges 5min 30s for path search ~ 5-fold reduction
- 17. Path Finding Algorithm: My home My Lab Starting Address: my Lab Starting Address: my Home Desired Distance: 3km
- 18. Path Finding Algorithm: Dijkstra¡¯s Algorithm finding one shortest path My home My Lab Shortest Path Length 1131m
- 19. Score ? Penalize difference in desired distance and actual distance ? Penalize turns / loops / zigzags ? Penalize repetitive route
- 20. Path Finding Algorithm: Monte Carlo heuristic perturbation of route penalty score = 4.99 path length = 1131m My home My Lab
- 21. Path Finding Algorithm: Monte Carlo accept improvements penalty score = 2.95 path length = 1875m My home My Lab
- 22. Path Finding Algorithm: Monte Carlo only accept deterioration with low probability penalty score = 39.32 path length = 8064m My home My Lab
- 23. Path Finding Algorithm: Monte Carlo best route after 1000 iterations penalty score = 0.495 path length = 2985m My home My Lab
- 24. Path Finding Algorithm: Monte Carlo best route after another 1000 iterations penalty score = 0.251 path length = 3202m My home My Lab
- 25. Summary ? Build a route recommendation system for runners ? Recommend different routes for given running distances ? Customized running score ? Can be easily generalized for other purposes
- 28. Thank You!