Have you already tried OsmAnd on your phone?

some hints for that:

  1. You can dowlnoad very fresh OSM data from the main server and create Osmand maps via OsmandMapCreator.

  2. Always try the latest development version of Osmand via www.osmand.net … there are even nightly versions.

  3. You can try two or three online routers with Osmand, but also it has an own offline router. Try the last one and report!