Всем привет!
Сразу скажу, что задача сложная и я надеюсь хоть на какую-то помощь и совет. Любые мысли и идеи приветствуются и предлагаю их обсуждать. Позже постараюсь с примерами картинок оформить.
Чем отличается задача от традиционного коммивояжёра:
1)У перехода две стоимости - время и расстояние
2)Переход от точки к точки допустимо совершать только в определённое время и от перехода зависит время перехода (грубо говоря мы переходим из A в B и допустим в 13:00 это стоит 1 час времени, а в 15:00 - 2 часа времени, стоимость в расстоянии не меняется). Соответственно у нас есть время отправления и прибытия из точки в точку. По каждому необходимо пройтись ОДИН раз. Если где-то осталась непройденное направление, то допускается пройтись ещё один раз по направлению (учитывая времена).
3)В каждой точке коммивояжёр должен отдохнуть определённое время(зависит от точки и только после этого он может ехать дальше)
4)При набеге определённой стоимости в часах, либо в километрах коммивояжёр обязан оказаться в определённом городе (поспать допустим). Можно прийти заранее, но позже нельзя. 
5)Город начала и время отправления можно выбрать самостоятельно - в приоритете города, в которых коммивояжёр может поспать (4).

Соответственно жду подсказок, вопросов и обсуждения 

Какие есть мысли на данный момент, возможно они кого-то натолкнут на более интересные:
1)Город следует выбирать по принципу различия входов и выходов - допусти приехать можно 8 способами, а уехать 9 способами (опять же предположение)
2)Следующее направление движение следует выбирать на основе стоимостных функций. Одна стоимостная функция зависит от приближения времени сна т.е. она увеличивается при приближении данного времени и если данное направление приводит в город, в котором можно отдохнуть. Вторая функция зависит от среднего количества неиспользованных направлений движения т.е. она увеличивается в направлении где много неотработанных направлений. Это нужно для того чтобы не использовать возможность повторного проезда по направлению (она нежелательна).

Пока больше мыслей нет..

GooG2e, На первый взгляд - задача для полного перебора. Условия достаточно сложны для интуитивного поиска инвариантов, в то же время достаточно жесткие условия, которые эффективно сокращают возможные "ходы".

Ну мы вот сейчас ходим и в ТЗ проверяем условия, по которым можно что-то отрезать при волновом поиске.

Жаль, что Вы не ответили на мой вопрос на Винграде:
В данном случае это важно.

да необходимо пройтись именно по каждому направлению, а не узлу. Грубо говоря есть расписание автобусов и нужно на всех автобусах хоть раз прокатиться. На одном атвобусе нельзя кататься больше двух раз

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

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

Пока есть вариант с поиском в глубину, чтобы при нахождении одного варианта мы могли начать отбрасывать другие, если они хуже по определённому критерию.

Сегодня возник ещё один вариант - строить дерево вширь, но на каждом этапе искать вариант с минимльной стоимостью и все элементы, которые имеют стоимость в n раз больше отсекать. При необходимости n можно повышать т.е. в цикле увеличивать значение, если при прошлом обходе не получился ответ.