Задача коммивояжера с дополнительным частичным заказом

Question

Я ищу имя для этой проблемы или любые ссылки по алгоритму или исходному коду :

Пример: Вы хотите найти лучший маршрут кПосетите 100 крупнейших городов США (классический TSP), но прежде чем вы сможете посетить какой-либо конкретный город, вы должны посетить столицу штата, в котором он находится.

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

Некоторые поиски в Google поднимают проблему последовательного упорядочения или "SOP"но не так много литературы, и я убежден, что это широко распространенное имя.

Я не думаю, что эти частичные упорядочения могут быть представлены в классическом TSP просто путем выбора ребер для использования в графе.(например, вы не можете сначала поехать из Нью-Йорка в Чикаго, но как только вы посещаете Спрингфилд, вы можете ) или веса, но я могу ошибаться.

Answer 1

Проблема последовательного упорядочения впервые была введена Escudero в 1988 году в статье, озаглавленной « Неточный алгоритм для задачи последовательного упорядочения » (она появилась в Европейском журнале оперативных исследований ), так что это оригинальное название проблемы. Аннотация статьи гласит:

Учитывая направленный G = (N, A) и штрафная матрица С, последовательная Проблема заказа (далее SOP) состоит из нахождения перестановки узлы из множества N, так что это минимизирует функцию на основе C и делает не нарушать приоритет отношения, заданные множеством А. Сильные достаточные условия для невозможность создания экземпляра СОП встроен в процедуру для СОП Предварительная обработка. Обратите внимание, что это один из ключевые шаги в любом алгоритме, который попытки решить СОП. Уронив ограничения, связанные с приоритетом отношения, СОП может быть преобразован в классическое асимметричное путешествие Задача продавца (далее АЦП). Алгоритм получает (надеюсь) Удовлетворительные решения путем изменения оптимальное решение для связанных Проблема Назначения (далее AP), если это не выполнимый последовательный Заказ (далее ФСО). Новый Решение «исправляет» подпрограммы (если любой) отдавая предпочтение патчам с нулевой сниженной стоимостью в ссылках дуги. Нижняя граница на основе AP на оптимальное решение ATSP затягивается используя некоторые из приведенных процедур в 1]. В любом случае локальный поиск для улучшения начального ФСО выполнила; он использует 3- и 4-смену основанные процедуры. вычислительный результаты по широкому кругу случаев сообщается.

Эскудеро и его сотрудники имеют ряд работ на эту тему со ссылками на еще больше. Если вы просматриваете литературу, вам может помочь поиск по ним или этой справке.

SOP - это хорошо изученная ограниченная версия Асимметричной задачи коммивояжера , поэтому большая часть литературы по ATSP может быть связана.

Answer 2

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