Отцы матана, подскажите решение

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

Комбинация метода Монте-Карло на графах с методом локальной оптимизации, например:
«Алгоритм статистических испытаний для определения параметров структур сетей связи по методу Монте-Карло» ©.

Ещё можно «потыкать» генетические алгоритмы на графах.

Ещё можно «потыкать» генетические алгоритмы на графах.

Я тыкал в свое время. То еще удовольствие, хочу сказать...

Посоветуйте что-нибудь толковое

Как тебе уже сказали, твои условия кривые. Если тебе такую задачку задали, то можешь потроллить препода и сделать один маршрут.

Может быть стоит добавить условие, что время в пути между любыми узлами должно быть минимальным?

Набор узлов и рёбер составляет собой маршрут.

Каких? Подозреваю, что последовательно соединённых, но всё же не ясно, например, может/должен ли он быть циклическим.

Как уже сказали выше — гамильтонов цикл.

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

* от любого до любого узла можно добраться с двумя (или меньше) пересадками

Думаю, это невыполнимо для произвольного графа. Пример - бинарное дерево.

Граф не взвешенный? Время маршрута не учитывается? Странная постановка.

Не, один точно не получится, там куча веток в районы. Ну и про «списывать» это шуточка была.

Невыполнимо. Если с двумя решение не найдётся, то подниму до трёх.

Хорошее замечание! Циклических не хотелось бы, лучше туда-обратно. Но тогда непонятно, что делать с дорогами с односторонним движением.

Измерить и учитывать можно расстояние, но на время оно влияет слабо. Проще не учитывать.

Циклических не хотелось бы, лучше туда-обратно

Но ведь это просто цикл по одним и тем же узлам. У тебя же нет маршрутов в один конец.

Второе условие заменить на адекватное «не использовать одно ребро больше m раз».

Если не поменять, то всё, как уже сказали выше, сведётся к гамильтоновым циклам либо на весь граф, либо внутри отдельных его областей с транзитными маршрутами между ними (привет московским автобусам).