Вы можете использовать openstreetmap с pgrouting в postgis, если вам важны только приблизительные оценки. Если вы просто делаете город с городом, то вам действительно не нужно беспокоиться о геокодировании, так как города давно известны.
Если ваш сервис ограничен Англией, я бы сохранил большую таблицу БД с комбинациями для попарного расстояния 5000 лучших городов. Вычислите его один раз в автономном режиме, используя pgrouting, а затем вызовите его, когда поступит запрос. Это сделает приложение намного быстрее для большинства ваших пользователей.
Все основные игроки карты имеют API-интерфейсы маршрутизации (Yahoo, Bing, MapQuest, Nokia).
Вы также можете посмотреть на deCarta для того же вида услуг. Они долгое время были движком LBS позади Yahoo и Google.
[обновить], если вы просто делаете это для приблизительной оценки, вам действительно нужно выполнить маршрутизацию или вы можете просто сделать расстояние по прямой. Прямая линия гораздо проще решить. Вам просто нужны последние значения для центров городов без данных по уличной сети или для расчета маршрутов.