В каждом заказе указан адрес доставки. Необходимо определить оптимальный маршрут
Так это классическая задача обхода графа, известная также как "задача коммивояжора". Тут скорее дело не просто в справочнике, а в представлении этого самого графа. IMHO это все-таки задача не для SQL-я. Саму таблицу вершин графа(т.е. географических пунктов) создать не проблема, а вот таблицу связей между вершинами - другое дело.
А потом еще попытатся работать с такой таблицей на SELECT
А потом еще поддерживать целостность такой таблицы.

ЗЫ
Все вышеизложенное IMHO

IMHO
Любой географический пункт можно описать деревом, каждый уровень которого отражает степень детализации.
Приблизительно так
0 - Корень
1 - Страна (можно было и с галлактик начать)
2 - Город (поселок)
3 - Улица
4 - Дом
5 - Кварира
6 - Номер комнаты в квартире

Что это дает ?
1. Можно ввести данный с таким уровнем детализации, который необходим или имеется в наличии. Т.е. для удаленных(неизвестных) регионов, например, только Страна и Город, для более близких(более известных) и Улицы и Дома и т.д.

2. Если собственно уровень детализации сделать атрибутом вершины, то это позволит гибко отражать географическое/административное деление. Т.е. сам уровень отражает старшинство, а атрибут говорит, что это есть. Тогда можно держать в одной таблицы данные вида

Корень - Страна - Республика - Область - Село - Улица
Корень - Страна - Штат - Город - Улица
Корень - Страна - Город
Корень - Материк - Область - Полярная Станция

Но повторюсь, я вижу б`ольшую сложность в создании таблицы связей, которая сделает из этого дерева ненаправленный граф. И трудность вижу прежде всего в большом количестве связей, а также в том, что связи должны будут иметь атрибут(ы) Вес(а), на основе которых и будут собственно вычисляться оптимальные маршруты.

Для такой база достаточно двух параметров: наименование точки и вес.

Весом должен обладать не географический пункт(из первой таблицы), а конкретный маршрут, связывающий 2 пункта(из таблицы связей)

IMHO одним атрибутом "Вес" все же не обойтись, т.к. маршрут может обладать различными конкретными физическими параметрами, которые нельзя просто аккамулировать из-за различия в их природной сущности.

Например пункты А и В соединены 3-мя дорогами Д1, Д2 и Д3.
Д1 - самая короткая, но имеет на пути мост с ограничением по весу машины в 5т и идет через перевал, который зимой закрыт
Д2 - средняя, но платная
Д3 - самая длинная.
Соответственно, для
Д1 имеем 3 Веса: для длины маршрута, для факта наличия моста и для факта наличия перевала
Д2 имеем 2 Веса: для длины маршрута и для факта оплаты за пользование
Д3 имеем 1 Вес: для длины маршрута

Т.о. можно говорить об обязательном наличии каких-то Весов(длина маршрута, тип покрытия). Плюс Веса, которые будут накоплены в виде знаний, полученных при конкретных действиях, т.е. про "вероятность пробки, состояние дорожного покрытия после снегопада, наличие злых гаишников". Другими словами с каждым маршрутом связано множество Весов(возможно оформленных также в виде дерева), полученных умозрительным и/или опытным путем. Чем больше Весов будет иметь маршрут, тем более оптимально может быть рассчитан маршрут. С другой стороны при большом количестве Весов неизменно встанет вопрос актуальности данных, ибо Вес, полученный чисто опытным путем, нуждается в постоянной проверке, т.е. "наличие злых гаишников" на конкретном маршруте должно периодически подтверждаться(или не подтверждатся).

Т.е. поставленная задача потребует каких-то компромиссных решений, с учетом вопросов
- хранения информации
- удобства ее обработки
- и актуальноти данных
- (наверняка еще что-то)