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

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

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