Задачи коммивояжера. Разновидности

[eugrita]

Классическая задача коммивояжера предполагает замкнутый путь по графу с посещением вершин 1 раз. Такая постановка мне кажется оторванной от жизни. Более актуальны по-моему следующие уточнения
1) отказ от обязательности посещения всех вершин 1 раз кроме возможно нескольких заданных , т.е. тех в которых надо побывать (сделать дела)
2)Ввести временные ограничения ,т.е. интервалы времен посещений
заданных пунктов.(Расчет времен прибытия в элементарном варианте можно делать по длинам путей и заданной скорости движения)
3)В случае нескольких возможных маршрутов удовлетворяющих условиям 1) и 2) ввести дополнительный критерий оптимальности, например минимальное время возврата в исходную точку
Кто может, укажите ссылку на литературу где приведены различные варианты постановок задачи коммивояжера близкие к изложенному

[Sender]

eugrita в сообщении #1386563 писал(а):

1) отказ от обязательности посещения всех вершин 1 раз кроме возможно нескольких заданных , т.е. тех в которых надо побывать (сделать дела)

Все необязательные удаляем из графа - и вуаля.

[Cash]

eugrita в сообщении #1386563 писал(а):

1) отказ от обязательности посещения всех вершин 1 раз кроме возможно нескольких заданных , т.е. тех в которых надо побывать (сделать дела)

Что мешает отказаться от "лишних" вершин?

eugrita в сообщении #1386563 писал(а):

2)Ввести временные ограничения ,т.е. интервалы времен посещений
заданных пунктов.(Расчет времен прибытия в элементарном варианте можно делать по длинам путей и заданной скорости движения)

Ну добавьте к ребру время в конечной точке (граф направленный)

eugrita в сообщении #1386563 писал(а):

3)В случае нескольких возможных маршрутов удовлетворяющих условиям 1) и 2) ввести дополнительный критерий оптимальности, например минимальное время возврата в исходную точку

Это совсем непонятно... Какие несколько? Одно бы найти...

[eugrita]

Sender в сообщении #1386565 писал(а):

eugrita в сообщении #1386563 писал(а):

1) отказ от обязательности посещения всех вершин 1 раз кроме возможно нескольких заданных , т.е. тех в которых надо побывать (сделать дела)

Все необязательные удаляем из графа - и вуаля.

Не так. Граф есть граф. Во время перемещения от одной обязательной к другой обязательной или в исх пункт мы идем по исходному графу возможно разными путями. Задание временных интервалов посещений тем самым может противоречить оптимальности по времени т е всяким shortpath -пути выбираются прежде всего с целью попадания прибытий в заданные временные интервалы!

-- Пн апр 08, 2019 12:22:13 --

Cash в сообщении #1386566 писал(а):

eugrita в сообщении #1386563 писал(а):

1) отказ от обязательности посещения всех вершин 1 раз кроме возможно нескольких заданных , т.е. тех в которых надо побывать (сделать дела)

Что мешает отказаться от "лишних" вершин?

eugrita в сообщении #1386563 писал(а):

2)Ввести временные ограничения ,т.е. интервалы времен посещений
заданных пунктов.(Расчет времен прибытия в элементарном варианте можно делать по длинам путей и заданной скорости движения)

Ну добавьте к ребру время в конечной точке (граф направленный)

eugrita в сообщении #1386563 писал(а):

3)В случае нескольких возможных маршрутов удовлетворяющих условиям 1) и 2) ввести дополнительный критерий оптимальности, например минимальное время возврата в исходную точку

Это совсем непонятно... Какие несколько? Одно бы найти...

3) задача при заданных временных ограничениях может и не иметь решений, но в случае наличия нескольких - критерий может быть -мин время возврата в исходную вершину
Речь идет об построении алгоритма для такой задачи
-- Пн апр 08, 2019 12:34:46 --
А, наконец понял. Если есть исходный граф с подмножеством заданных вершин, то путем применения алгоритма shortpath к каждой паре заданных мы выкидываем лишние вершины заменяя их ребром с найденным кратч путём и получаем полный граф из заданных вершин (ненулевую матрицу смежности кроме диагональных) А если еще не выполнено неравенство треугольника для нее то удалим и большие ребра)
Ну хорошо, задача почти свелась к классической. Но надо учесть временные ограничения
Но все равно посещение каждой обязательной вершины ровно 1 раз не кажется обоснованным. Может оказаться что и путь в следующую и возвраты проходят повторно через посещенную вершину

[Евгений Машеров]

В общем, Вы хотите решать общую задачу теории расписаний, но именовать её "задачей коммивояжёра". Зачем?

[eugrita]

Евгений Машеров в сообщении #1386650 писал(а):

В общем, Вы хотите решать общую задачу теории расписаний, но именовать её "задачей коммивояжёра". Зачем?

Да, получается сформулированная задача принадлежит теории расписаний. К сожалению ей плохо владею. Если затраты времени на путь от $i-$до $j-$ выделенной вершины обозвать временем обслуживания или временем выполнения работ то да. И одновременно это задача управления проектами
Но меня интересовала именно графовая, транспортная интерпретация задачи
т.е некий гибрид из графов и не очень сложного составления расписания. И хорошо бы как все графовые задачи на элементарных примерах, доступных уровню школьного ЕГ
Спасибо за критику. Подумаю сначала об каких-то наглядных несложных примерах задачи, лежащей на стыке 2 мощных теорий а только потом об компьютерных алгоритмах

[Евгений Машеров]

Первая постановка (когда надо обойти несколько заданных вершин, при этом прочие вершины не обязательно проходить все и не воспрещается повторный проход) сводится к паре задач - построение кратчайших маршрутов из каждой в каждую (полиномиальная сложность, скажем, для Флойда-Уоршела кубическая по числу вершин) и для выбранных вершин - обычная ЗК с матрицей, включающей лишь заданные, а в качестве расстояний - длины кратчайших путей, возможно, через "необязательные" вершины.
Остальные постановки - задачи теории расписаний. Которая, вообще говоря, намного сложнее.
Вообще, ценность ЗК не столько в непосредственном применении (хотя практические приложения есть, и не только "объезд городов", скажем, выбор последовательности технологических операций), сколько в том, что при достаточно простой постановке её решение оказывается весьма затруднённым, и это позволяет отрабатывать на ней идеи алгоритмов, которые потом могут быть перенесены на более сложную и более прикладную постановку задачи. Скажем, для таких методов, как симуляция отжига, муравьиная колония, табу-поиск, генетические алгоритмы ЗК - часто используемый "пробный камень".