I runfinalversion
?
0 likes?257 views
This document describes the development of an app called iRun that recommends running routes between locations with customized distances. It does this by building a graph of roads and paths in Cambridge and Boston, cleaning the data, and using Dijkstra's and Monte Carlo algorithms to find optimal routes matching the desired distances while minimizing things like distance difference, turns, and repetitive routes. The end result is a system that can recommend different running routes between set locations for various target distances.
I runfinalversion
- 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?
- 6. Building a graph of Cambridge and Boston
- 7. Data Clean Up 0: Original Map
- 8. Data Clean Up I: Remove un-runnable area
- 9. Data Clean Up II: Remove isolated islands
- 10. Data Clean Up III: Remove spikes
- 11. Data Clean Up IV: Combine parallel roads
- 12. Data Clean Up IV: remove redundant nodes
- 13. After Data Clean Up ? 103,365 Nodes, 225,766 edges reduced to 17,480 Nodes and 49,354 edges ~ 5-fold reduction 5min->30s for path search
- 14. Path Finding Algorithm: My home My Lab Starting Address: my Home Starting Address: my Lab Desired Distance: 3km
- 15. Path Finding Algorithm: Dijkstra¡¯s Algorithm finding one shortest path My home My Lab Shortest Path Length 1131m
- 16. Score ? Penalize difference in desired distance and actual distance ? Penalize turns / loops / zigzags ? Penalize repetitive route
- 17. Path Finding Algorithm: Monte Carlo Heuristic perturbation of route penalty score = 4.99 path length = 1131m My home My Lab
- 18. Path Finding Algorithm: Monte Carlo accept improvements penalty score = 2.95 path length = 1875m My home My Lab
- 19. Path Finding Algorithm: Monte Carlo only accept deterioration with low probability penalty score = 39.32 path length = 8064m My home My Lab
- 20. Path Finding Algorithm: Monte Carlo best route after 1000 iterations penalty score = 0.495 path length = 2985m My home My Lab
- 21. Path Finding Algorithm: Monte Carlo best route after another 1000 iterations penalty score = 0.251 path length = 3202m My home My Lab
- 22. 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