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

Почему алгоритмы маршрутизации?

Алгоритмы очень помогли человечеству автоматизировать огромное количество процессов, возникших во время промышленной революции. Алгоритм - это не что иное, как последовательность инструкций, данных машине о том, как выполнять задачу. В Locus мы решаем NP-сложные задачи оптимизации, а создаваемые нами алгоритмы имеют высочайший математический оттенок.

Что такое NP-твердость?

NP-трудная задача оптимизации размера N имеет пространство решений, размер которого больше любого полинома от N. Давайте рассмотрим производную от известной проблемы коммивояжера - вы должны посетить дома своих друзей, чтобы выразить свои пожелания и подарки на Дивали, но ограничение состоит в том, что в вашем распоряжении есть только день. Еще до того, как вы начнете, вы хотите выяснить, как лучше всего навестить друзей, чтобы вы тратили минимум времени на поездки и могли закончить как можно раньше.

Если у вас есть N друзей, количество способов их посещения является факториальным (N), также обозначаемым как N!. Простая процедура - оценить все N! туры, а затем выберите лучший. Однако загвоздка в том, что N! масштабируется быстрее, чем экспоненциальная функция, поскольку N становится больше. Даже для небольшого N = 20 это приведет к выполнению примерно операций. Если предположить, что компьютер выполняет ² операций в секунду, что довольно оптимистично, время выполнения этого алгоритма составит секунд ≈ 12 дней. Ясно, что это нежизнеспособный вариант.

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

В Locus мы играем в кости

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

Другой интуитивный подход - начать со случайного тура из этих 20 возможных! туры и продолжайте итеративно улучшать, внося небольшие изменения, пока никакие небольшие изменения не улучшат обзор. Поскольку полученное здесь решение лучше всех аналогичных решений, оно называется локальным оптимумом. Ограничением этого подхода является то, что он рассматривает только небольшое подмножество всех возможных конфигураций. Следовательно, полученное решение может сильно уступать лучшему.

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

Игры, в которые мы играем

3D Box Packing: упаковываем груз наиболее оптимальным образом. При вдавливании коробки в груз наш алгоритм бросает смещенный кубик, чтобы определить наилучшую ориентацию для установки этого ящика. Матрица более подходит для конфигурации, которая имеет лучшую эффективность упаковки.

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

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

Монте-Карло в Лас-Вегас

Описанный выше метод относится к области алгоритмов Монте-Карло. Также существуют алгоритмы, которые всегда могут найти лучшее решение, такие знаменитые рандомизированные алгоритмы известны как алгоритмы Лас-Вегаса. К счастью, не существует алгоритмов типа Лас-Вегаса для задач, которые мы решаем. В Locus мы разрабатываем и тренируем умные игральные кости, которые помогут нам добраться до Вегаса!

Locus предлагает предприятиям лучшее программное обеспечение для оптимизации маршрутов для улучшения доставки на последней миле с большей экономической эффективностью. Свяжитесь с нами для получения бесплатной демонстрации.

Первоначально опубликовано на https://blog.locus.sh 2 ноября 2017 г.