Кэшируй пары город/город и расстояние между ними в (redis)/(любой другой базе ключ/значение)
перед отправкой запроса проверяй - нет ли ответа в кеше.
Раз в полгода/месяц очищай кеш на случай появления новых дорог/новых участков на карте.
Другой вариант - собственный сервис геокодирования/прокладки маршрутов -
project-osrm.org
написан на С и никаких ограничений :-)
Profit!