гуглите "графы поиск пути". Дороги будут ребрами графа, вершины графа - населенные пункты. Для ребер параметры - длина, для населенных пунктов - все остальное (название, координаты. погода).
В качестве СУБД подойдет что-то типа
neo4j. И еще по поводу выбора СУБД и подходов к решению
почитайте.