Алгоритм ветвей и границ python

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

Clever-Shadow/python-salesman

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Задача коммивояжера на Python методом ветвей и границ(алгоритм Литтла).

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

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

Для решения задачи коммивояжера методом ветвей и границ необходимо выполнить следующую последовательность действий:
1 — Построение матрицы с исходными данными.
2 — Нахождение минимума по строкам.
3 — Редукция строк.
4 — Нахождение минимума по столбцам.
5 — Редукция столбцов.
6 — Вычисление оценок нулевых клеток.
7 — Редукция матрицы.
8 — Если полный путь еще не найден, переходим к пункту 2, если найден к пункту 9.
9 — Вычисление итоговой длины пути и построение маршрута.

Читайте также:  Star Admin Premium Bootstrap Admin Dashboard Template

Для тестов можно использовать следующее:
Test1
4
0 10 1 1
10 0 1 5
1 1 0 10
1 5 10 0

Test2
4
0 5 11 9
10 0 8 7
7 14 0 8
12 6 15 0

Test3
3
0 5 10
5 0 7
10 7 0

Test4
4
0 10 1 7
10 0 6 1
1 6 0 10
7 1 10 0

Test5
4
0 1 1 7
1 0 7 1
1 7 0 1
7 1 1 0

Test6
4
0 1 1 7
1 0 20 1
1 20 0 1
7 1 1 0

Test7
4
0 1 6 3
1 0 1 9
6 1 0 1
3 9 1 0

Test8
6
0 5 7 6 8 3
1 0 8 4 6 2
3 9 0 6 5 3
7 8 4 0 4 2
2 7 5 6 0 6
5 2 6 4 5 0

Источник

Жадный алгоритм, ветви и границы для расписания мерчендайзеров (кейс Хакатона на оптимизацию)

Это пилотная статья. Будем благодарны за обратную связь. Если тема вызовет интерес, мы возможно примем решение выложить на GitHub наши исходники (python) и входные data-set’ы.

В марте 2021 г. случилось мне поучаствовать в хакатоне с задачей на комбинаторику и оптимизацию. Команду решил собрать свежую, из одиночек, дрейфующих в пуле самого хака. Довольно быстро нашлись front и back, и втроем мы принялись старательно думать, как потратим деньги, когда выиграемJ Так как сам кейс показался нам по началу не сложным. Надо сказать, что в хаках я не так давно, но уже успел поучаствовать и в ЛЦТ(Лидеры Цифровой Трансформации), и в Цифровом Прорыве. В последнем даже удалось занять бронзу в финале. Роль всегда у меня была project+product+ppt (хотя опыт в программировании у меня также имеется). Не редко в хакатонских кейсах проблемы немного надуманы, решения этих проблем немного фееричны и не несут практического смысла, а побеждает профессиональная преза и поставленный питч. Так вот этот мартовский хакатон меня заинтересовал живостью и насущностью бизнес проблем, которые там решались. Опытные хакатонщики, читающие эти строки, поймут. Но полно про хакатоны и про то, какие они бывают, а то собьемся с курса.

В этам хаке преза и даже front мало интересовали кейсодержателей. Это был натуральный бизнес хакатон с абсолютно живыми дата сетами и с натуральной бизнес болью. Кстати на хакатоне ни одна из команд не предоставила решение. Вроде одни ребята «нарисовали» в своей презе оптимизацию в минус 1 агент, но демонстрацию на защите они не представили. Наша команда не стала исключением и заняла скромное третье место (всего до защиты дошло 5 команд). Теперь наконец к условию:

Есть 204 ТТ (торговые точки). Каждую из них нужно посетить минимум раз в неделю, а некоторые больше одного раза. Длительности посещения каждой ТТ известны и не изменяются внутри недели.

Также предоставлена матрица 204х204 с расстояниями между точками (см. Табл.1 ниже ). Матрица не симметричная, т.к. при составлении учитывались знаки ПДД (одностороннее движение и пр.). Видимо она была получена через API Яндекс.Карт по адресам ТТ. Требовалось найти оптимальное расписание для торговых агентов (мерчендайзеров), улучшив показатели текущего AS IS (оно тоже предоставлено). Важные ограничения: каждая ТТ должна быть закреплена за определенным мерчендайзером (торговым агентом). Другими словами, если торговый агент (далее агент) посещает Магнит на улице Ленина в понедельник, то этот же Магнит в другие дни недели должен посещать именно он. Время работы каждого агента не должно превышать 9,5 часов в день с учетом работы в ТТ и перемещению между ними.

Таблица 1. Матрица расстояний между точками

Предоставленное расписании AS IS распределено на 14 агентов. И как вы уже догадались, решение должно было предложить альтернативное расписание, сократив по возможности количество агентов и их время в пути.

Читайте также:  background-color

Спустя какое-то время после хакатона наш back(python) призвал на помощь коллегу с курсов по deep learning. Парни погуглили, поискали готовый алгоритм, почитали про метод отжига, муравьев, генетику и пришли еще раз к выводу, что подходящего метода и примеров кода именно для этой задачи, куда можно было бы взять и вставить матрицу расстояний, как входной параметр на просторах интернета — нет. Если кто знает где есть – поделитесь, будем благодарны.

Позднее, и даже в параллель я сам начал изучать тему Задачи коммивояжера и эвристические методы, зарекомендовавшие себя для ее решения. Но ни хабр, ни youtube, ни Википедия не давали готового ответа именно для этого частного случая. Останавливаться все равно не хотелось. Наоборот, по мере продвижения вперед интерес подогревался. Мотивации добавило то, что классическая задача коммивояжера относится к NP полным задачам. Если решать задачу полным перебором (brutal force), то уже при 66 торговых точках нужно несколько миллиардов лет и компьютер размером с Землю. Согласитесь, мощь трансвычислительных задач завораживает! И действительно, для решения классической задачи TSP (Travelling salesman problem ) существуют различные эвристические методы, такие как Метод Имитации Отжига, Муравьиный алгоритм, Генетический метод и др. Оставалось решить один вопрос: как применить что-то из этой эвристики к сквозному недельному расписанию нескольких торговых агентов с ограничением по времени. Возможно толковый математик, который кожей чувствует физический смысл дифференцирования, логарифмов, пределов, силу числа e и т.д., справился бы с этой задачей. Но я не такой математик. Формулы счастья по-прежнему в интернете не находилось. Я даже изучил основы нейросетей, но когда я начинал проектировать свою нейросеть для решения — вырастала непреодолимая стена.

И все-таки решение родилось! Ну во-первых я обратился за помощью к своему коллеге, Черкасову Евгению @eny01. Он как раз недавно прошел курсы по data science и python, и рвался в бой, чтобы применить все приобретённые навыки. К слову сказать, бОльшую часть алгоритма именно он и разработал. Себе я взял часть, отвечающую за рекурсивный метод ветвей и границ. Но об этом позже. Вдвоем мы разработали следующий план.

  1. Мы декомпозировали задачу до каждого агента. Набираем ТТ сначала для одного агента до предела по очереди для всех дней недели, затем для второго и т.д.;
  2. Процесс набора ТТ происходит с помощью жадного алгоритма (метод ближайшего соседа);
  3. В случае, когда набор подходит к пределу (9,5 часов) — применяем оптимизацию и считаем, что для данного агента в этот день недели оптимальное расписание составлено. Переходим к следующему дню;

Алгоритм набора расписания для каждого агента более подробно можно увидеть на блок-схеме ниже:

Теперь чуть подробнее про основные моменты:

  1. Ближайшие сосед:

Первой точкой расписания дня недели мы берем точку, наиболее объемную по времени посещения и наиболее частую в неделе. Второй и последующими точками становятся ближайшие к уже отобранным точкам. Каждый раз при добавлении новой точки в расписание дня производится оптимизация по подбору наилучшей первой точки для получаемого кратчайшего пути в расписании. Мы попросту перебираем точки, подставляя каждую в качестве первой и перенабираем к ней при помощи того же жадного алгоритма отдельный массив. В итоге выбираем самый лучший вариант по минимальному пути для прохождения точек.

Читайте также:  Html code for playing videos

Важно следить за переполнением не только в том дне, в котором идет набор, но и параллельно приглядывать за остальными днями торгового представителя- последующими и предыдущими. Так как выбирая точку, скажем для четверга, мы можем переполнить ею пятницу или понедельник.

Когда в одном из дней достигается предел рабочего времени (>=9,5 ч.), система сбрасывает точку приведшую к переполнению и пробует добрать следующую ближайшую. Кстати, мы пробовали вставлять сюда вместо оптимизации «первой точки» и ближайшего соседа полный перебор с ветвями и границами. И результат, !внимание!, получался в итоге тот же. Но времени на перебор с ветвями и границами потребовалось гораздо больше. Около 3,5 часов против 5 минут для всех 204 точек. Таким образом полный перебор был абсолютно избыточен и неэффективен при частом применении. Вследствие чего в этом месте было решено от перебора с ветвями и границами отказаться, но добавить его в финальную оптимизацию составленного расписания.

Ну тут все относительно просто. Утвержденное недельное расписание мы прогоняем через полный перебор, используя метод ветвей и границ. Реализация этой функции потребовала применения рекурсии. Причем если сравнивать работу полного перебора через библиотеку itertools (python), то время на перебор 8 точек составило 21 сек, в то время как наша рекурсия с ветвями и границами отрабатывала за 0.4 с. Что не может не радовать! Цель применения ветвей и границ — оптимизация уже готовых расписаний. Привязка ТТ и агентов уже не меняется, но оптимизируется время в пути (решаем классическую задачу коммивояжера).

Описанным выше образом мы производим набор точек для второго агента, затем для третьего и т.д. В результате работы алгоритма нам удалось не только снизить количество агентов с 14 до 13, но и сократить суммарную траекторию перемещения между ТТ вдвое. Ниже представлены результаты, которых нам удалось добиться:

До оптимизации

После оптимизации (с брутфорсом в наборе расписания)

Относительное изменение, %

Число Мерчендайзеров

Суммарная средняя траектория всех ТП, км

Суммарная траектория всех маршрутов всех ТП, км

Средняя длительность рабочего дня для ТП

Общая продолжительность работы всех ТП, час

Время работы алгоритма для всех агентов на всех днях недели составило 8 минут на домашнем ПК.

И в качестве финального аккорда мы позволили себе выкрутить лимит с 9 часов 30 минут до 9 часов 38 минут. И получили сокращение до 12 агентов с небольшой погрешностью. Из 60 дневных расписаний 14 уходят в переработки от 1 до 8 минут (51 минута в сумме).

Ждем ваших комментариев, замечаний и предложений! Ответим на все вопросы. Пишите, как бы вы решали эту задачу. Особенно ценны для нас будут мнения практиков. Как математиков, так и data science’ов. Возможно кто-то предложит существующие библиотеки python для решения задачи. Мы, как я уже сказал, подходящих библиотек не нашли. Всем спасибо, что дочитали до конца!

Источник

Оцените статью