I think we'd be better off hacking the map format and then writing our own routing algorithms using the same methods as Navit or one of the other free map/routing implementations.