с гуглмапс качайте и склеивайте
благо утилит навалом
Sasplanet например уже готовая прога для навигации.
Заранее в кэш предпологаемый маршрут закачайте..