Получение расстояния между городами

Привет!

Появилась задача, суть:

Дана начальная и конечная точка (город, А и город Б). Нужно вычислить расстояние между двумя городами, расстояние именно не географической прямой, а по дорогам. Есть API Яндекс Карт, Google и других, но там ограничения по запросам, что в проде является fatal.

Применение: на основе расстояния высчитывается ставка рубль\километр для перевозки.

Какое бы вы решение применили?