Рубрика «задача коммивояжёра» - 2

Как я изобретал метод имитации отжига
Доброго времени!

Сподвигло меня на написание этой работы прочтение «Введение в оптимизацию. Имитация отжига». Так уж сложилось, что как раз недавно я столкнулся с задачей коммивояжера и для ее решения придумал алгоритм, суть которого, как оказалось, очень близка к идее алгоритма имитации отжига, описываемого в указанной статье. Более того, там даже есть «отсылка» к моей идее, а еще похожие обсуждения велись в комментариях, потому я решил, что сообществу будет интересно посмотреть на реализацию.
Читать полностью »

image
Пример XLS-таблицы, которая используется до внедрения системы – и отлично подходит в качестве источника первичных данных.

Есть такой классный тип математических задач — маршрутизация торговых представителей. Хорошо известный каждому, изучавшему дискретную математику.

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

Фактически, задача сводится к двум:

  • Обобщенной задаче коммивояжера (TSP).
  • И построению оптимального расписания-плана.

При этом в задачах также учитываются доступные ресурсы (например, наличие машин, их вместимость, проходимость дорог и так далее), параметры точек (время ее работы точки, частота посещения, перечень задач, которые требуется решать в данной точке и так далее), изменения, например, внезапный переезд одного ларька на другой конец города. Ну и финальный штрих — довольно часто эта задача решается супервайзером с высшим гуманитарным образованием. Читать полностью »

В предыдущей публикации был рассмотрен алгоритм решения задачи коммивояжёра на плоскости рекурсивным полным перебором. Результат получился любопытным, но итоговый маршрут содержал очевидные неоптимальные участки. В предлагаемой заметке рассмотрен улучшенный алгоритм, который я назвал «рекурсивным жадным алгоритмом». Признаюсь сразу, итоговый маршрут в сравнении с рекурсивным полным перебором получается лучше, в среднем, на 8%.
Читать полностью »

Сформулируем задачу.
Дано N узлов, расположенных на плоскости. Задан входной узел (Вх) и выходной узел (Вых). Необходимо обнаружить кратчайший путь, охватывающий все узлы, начинающийся во входном узле, заканчивающийся в выходном узле и проходящий через каждый узел только один раз.

Есть мнения, что задача коммивояжёра может формулироваться ещё двумя способами:
1. Необходимо обнаружить кратчайший гамильтонов цикл.
2. Необходимо обнаружить кратчайший путь, начинающийся в заданном узле.

Однако обе эти формулировки при ближайшем рассмотрении оказываются частными случаями первоначальной формулировки.
Формулировка 1 подразумевает, что входным узлом может быть любой узел, а выходным — один из ближайших к нему. Что требует полного перебора всех ближайших узлов к произвольно выбранному узлу.
Формулировка 2 подразумевает, что входной узел задан, а выходным узлом может быть любой. Что требует полного перебора всех выходных узлов с последующим выбором кратчайшего пути из всех кратчайших.
Поэтому мы остановимся на первоначальной формулировке, и будем решать задачу в общем виде.
Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js