Метка «задача коммивояжëра»

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

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

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

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

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

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

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

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

Я хочу описать историю одного заносчивого и самовлюбленного студента Академического Университета, коим я, конечно, не являюсь, но хорошо представляю его мысли и переживания. Будем называть этого студента, например, Шурик. На момент поступления Шурика в Академический Университет (АУ), согласно его программистскому резюме, он уже был экспертом в области алгоритмов. Он мастерски владел алгоритмом поиска в глубину, знал несколько методов сортировки массивов, и имел представление о двоичном поиске. Естественно, курс алгоритмов его не интересовал совершенно, да и вообще, мало чему можно научить программиста с пятилетним опытом. Программа теоретической информатики АУ его заинтересовала тем, что в темах по известным ему предметам было слишком много неизвестных ему слов. Но это же Питер, там они и бордюр то странным словом называют, вероятно, и для поиска в глубину красивых слов понавыдумывали. Он тщательно изучил слайды и видеозаписи курсов. Оказалось, что существует какая-то там информатика, которой Шурик не владеет в совершенстве. Шурик собрал книги, носки и пять лет опыта, и отправился в Питер на собеседование. Там он встретили людей, которые могут научить чему-то даже программиста с таким опытом. Это все рушило Шурикову картину мира, в которой знание информатики измерялось количеством написанных классов на C#.
Во время учëбы в магистратуре Шурик занимался исследованиями в области схемной сложности и области экспоненциальных алгоритмов. Это действительно очень интересно и, что не менее важно, полезно для поступления в аспирантуру.
На данный момент Шурик является счастливым аспирантом New York University, использует слово «поребрик», и с глубокой благодарностью вспоминает Академический Университет. А кафедра теоретической информатики АУ и сейчас ведëт набор новых магистрантов.
Сейчас я передаю слово Шурику, который и расскажет об одном своëм исследовании.

Читать полностью »


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