Алгоритм: планирование рейса
Мне нужно спланировать рейс, соединяющий n точек в море с указанным исходным пунктом и указанным пунктом назначения со следующими ограничениями.
Путешествие должно коснуться всех локаций.
Если есть резервирование от A до B, то нужно коснуться a до B
Время, проведенное в каждом месте, варьируется (зависит от бронирования в этом месте)
У каждой локации есть рабочее окно. Если судно доходит до рабочего окна, оно должно подождать.
Примечание. Алгоритмы «минимального связующего дерева» могут отсутствовать, поскольку время, необходимое для каждого порта, зависит от предыдущего маршрута (из-за рабочего окна)
Есть ли для этого какой-нибудь алгоритм?
Ответы 4
Оптимизация колонии муравьев кажется наиболее известным решением этой проблемы. Обратите внимание, что это Проблема NP, фактически даже NP-полная проблема. Это означает, что «легко» проверить правильность решения, но «трудно» найти его. Единственный способ найти «оптимальное» решение - это попробовать все возможные решения, сравнить результаты и выбрать лучшее. Конечно, это неприемлемо, если вы хотите решить ее в разумные сроки.
Алгоритмы ACO найдут хорошее решение, близкое к оптимальному. Я говорю «близко», потому что, как ни крути, нельзя гарантировать, что всегда найдется лучший. Могут существовать лучшие решения. Однако часто нет необходимости действительно искать наилучшее возможное решение, решение, которое просто «очень хорошее», сделает свое дело, и здесь ACO - это именно то, что вы ищете. Он может найти решение в разумные промежутки времени, и решение обязательно будет хорошим.
В вашем случае вам нужно его немного изменить. Обычно он пытается найти только самый короткий маршрут, учитывая только путь. В вашем случае это должно учитывать ваше рабочее время, бронирования и время, потраченное на место. Но это всего лишь модификации того, «как путешествуют муравьи», основной алгоритм остается прежним и будет работать так же.
Спасибо. Звучит многообещающе. Дай мне разобраться и посмотреть, как дела. Кстати какой псевдокод есть?
Это не проблема NP. Вы ищете решение за минимальное время. Правильный термин - NP-Hard.
Это задача коммивояжера с модификацией, добавляющей ограничение рабочего окна ... что означает, что решение этой проблемы будет еще труднее найти, чем стандартную задачу коммивояжера.
У меня есть несколько подходов, которые позволяют дать приблизительные решения.
- Генетические алгоритмы
- Табу Поиск
- Рандомизированный алгоритм (например, случайное блуждание)
Я не знаю, применимо ли к вашей проблеме, мысленно говорю, что нет, но динамическое программирование может иногда использоваться для решения неразрешимых проблем.
Над этой проблемой много работы. Он носит разные названия
- задача коммивояжера (маршрутизация транспортных средств) с временными окнами и ограничениями приоритета.
- Проблема получения и доставки.
Есть множество исследований по этой проблеме, многие из них в Исследовании операций Журналы. В целом это проблема NP-Hard, поэтому общее точное решение проблемы, описанное вами, нецелесообразно, но могут быть хорошие, точные или приблизительные решения вашей конкретной проблемы. Лучший алгоритм будет зависеть от ваших данных.
- Насколько велик ваш набор данных. Если «n» относительно мало (30–100), то, вероятно, возможно точное решение с математическое программирование.
- Насколько жестки временные окна и ограничения по приоритетности. Если количество возможных мест для посещения в любое временное окно невелико, тогда возможно решение, подобное динамическому программированию.
- Если вы не можете найти особый случай, вы, вероятно, захотите объединить алгоритм эвристического построения с постпроцессором локального поиска. Простая альтернатива - так называемая эвристика ПОНЯТЬ, где вы
- взять существующую эвристику построения,
- randomize - это то, что несколько запусков дадут вам несколько решений,
- запустить рандомизированную версию несколько раз
- выберите лучшее решение.
Заботится ли о рабочей оконной части? Рабочее окно означает, что вес кромки зависит от пути к кромке.