Где взять расстояние между городами, если количество сочетаний более 100 000?

Всем привет!

Есть 500+ городов (Россия и СНГ), нужно посчитать расстояние между городами. Нужно составить сочетание каждый с каждым. Чтобы более наглядно.

1. Москва
2. Санкт-Петербург
3. Екатеринбург

1. Москва - Санкт-Петербург (оно же Санкт-Петербург - Москва)
2. Москва - Екатеринбург (оно же Екатеринбург - Москва)
3. Санкт-Петербург - Екатеринбург (оно же Екатеринбург - Санкт-Петербург)

Если я не ошибаюсь, то в комбинаторике это формула сочетания без повторений, что приблизительно равняется 100 000 сочетаниям.

При лимитах в Google Maps Distance Matrix в 2500 запросов в сутки, мне придется собирать эти данные 40 дней, что, естественно, очень долго.

Напрашивается единственный жизнеспособный вариант: можно собрать координаты городов (500 запросов), и высчитывать между ними расстояние по формуле. По сути, не важно как высчитывать (GC, или Rhumb Line), как собственно ясно, по дорогам мы прокладываем или напрямую по воздуху.

Вопрос: есть ли какие-то способы посчитать дистанцию быстрее и проще (API без лимитов), чем предложенный мною вариант?