On my way: Optimizing driving routes for navigation applications

Conventionally, the route recommendations given by GPS navigation applications have been considered as the optimal route search problem only between two locations - origin and destination [1]. Sometimes people want to visit several intermediate locations prior to reaching their final destination. For example, travelers may want to visit a diner and a gas station before arriving at their vacation destination. Although there is likely to be many choices that are available along the route to the destination, only one place from each type should be chosen. Furthermore, in new emerging application domains, such as physical-world crowdsourcing [2], people may want to opportunistically visit some places in order to complete personal or work related tasks. Our work explores a design space where we try to reduce the amount of requests made to third-party map and route data providers. We explore the simple idea of using the Euclidean distance as a rough estimate for the optimal route between destinations with multiple waypoints. Our preliminary results indicate that with over 80% of test cases, this simple Euclidean distance estimator approach gives at least one optimal routing alternative.