Имеется (точнее, проектируется) автоматизированный склад (Regional Distibution Center) с картонными коробками на полках. Коробки - прямоугольные, но сильно отличаются по размеру, у каждой может быть своя длина, ширина, высота. Длина, например, может варьироваться где-то от 12 до 80 см. Одновременно на складе может храниться несколько сотен тысяч таких коробок, в будущем - более миллиона. Наименований товаров - тоже потенциально больше миллиона. Характерный срок хранения их варьируется на несколько порядков: некоторые товары проходят через систему по нескольку сотен коробок в день, некоторые - могут лежать на полке полгода.
Склад представляет собой трёхмерную структуру: примерно 20 этажей (вертикальных уровней, один этаж в среднем около полуметра), на каждом этаже несколько сотен параллельных рядов с полками, каждый ряд ещё разделён на пролёты между вертикальными опорами, длина пролёта примерно 3 метра. По рядам на рельсах двигаются мобильные роботы которые могут положить коробку на полку, или взять коробку с полки. Роботы едут к началу рядов и принимают приходящие коробки с вертикального конвейера и затем развозят их по полкам или наоборот, погружают исходящие коробки на вертикальный конвейер.
Задача такая: создать алгоритм динамически оптимального размещения этих коробок по складу. В среднем нужно разместить 2-3 таких коробки в секунду, и столько же (в среднем) отправить "на вынос", т.е. на shipping. Для каждой такой коробки алгоритм должен предложить несколько потенциальных мест для её хранения, в разных частях склада. Из этих нескольких кандидатов другой софтверный модуль, управляющий "роем" мобильных роботов, выбирает один, наиболее подходящий с точки зрения организации траффика. Ну то есть чтобы эти роботы успевали его подхватить с вертикального конвейера и не создавали при этом пробок (за этот модуль - транспортного потока - ответственен не я, а другой человек, Ph.D. из Корнеля, который до того занимался управлением "стаи" автономных летательных аппаратов, типа военных дронов).
Оптимизация должна быть сразу по многим параметрам. Главный критерий - плотность размещения, т.е. чтобы оставалось как можно меньше пустых мест куда ничего нельзя всунуть. Второй - максимальная дисперия, или доступность данного товара. Т.е. скажем, упаковки с Sony Playstation III должны иметься на многих уровнях и в разных рядах, потому что в каждый конкретный момент какой-то уровень или ряд может быть закрыт (скажем, там застрял сломавшийся робот). Третье - оптимизация со сроком хранения, т.е. коробка должна покинуть склад заблаговременно, до того как у неё истёк срок годности. Четвёртое - минимизация расстояния и времени движения мобильных роботов (если товар быстро слетает с полок, он должен храниться ближе к выходу ряда, а если его продажи малы и он может лежать много месяцев - его можно разместить в конце ряда, в тупике. Ну и ещё множество более тонких критериев и правил, например, что стиральный порошок не должен храниться рядом с детским питанием и, тем более, над ним.
Если алгоритм размещения сделать чисто случайным - фактически размазывать всё равномерно по пространству, в конце концов будет типичная проблема фрагментации: огромное количество мелких пустых закутков, куда ничего нельзя всунуть (напоминает проблему фрагментации компьютерной памяти). Сейчас одна наша построенная действующая система примерно так и делает: то есть, якобы она использует какие-то сложные алгоритмы, но на самом деле получается именно размазывание соплей по пространству. Следующее поколение, которое мы делаем, должно быть намного лучше. Большую часть года склад не слишком заполнен, поэтому даже размазывание по пространству, хоть и неоптимально, в принципе допустимо. Но 2-3 недели в году, перед рождественскими праздниками, он может быть забит под завязку - тогда борьба будет идти за каждый пустой уголок на полке. В этом смысле в пике загруженности требования к алгоритму очень жёсткие.
Заказчик системы - одна из крупнейших торговых сетей, в магазинах которой бывали, наверное, 80% американцев, поэтому ставки весьма высоки "не проебать проект".
Сейчас у меня задействовано в этой части проектa человек пять (потом будет больше), в том числе один интересный персонаж. Математик, работавший до этого "квантом" в каком-то хедж-фонде в Нью Йорке. Он, кстати, пару лет назад имел там свои "15 минут славы", когда они с напарником установили рекорд на скорость обьезда всех станций нью-йорксого метро. Это такой вариант "traveling salesman problem" в реальном времени. Вот здесь, в газетах про него (Матт Ферриси) писали:
http://www.nydailynews.com/new-york/math-whizzes-shoot-set-record-traversing-subway-system-article-1.422797
http://www.wallstreetandtech.com/trading-technology/212902786
и даже в Вики - оказывается на это счёт есть соответствующий рекорд Гинесса.
Парень не глупый но, с другой стороны, этакий типичный математик-ботан. Его приходится пинать - не в том смысле что ничего не делает, а что слишком часто получается мямление на тему "а если с этой стороны на проблему посмотреть... а если с другой...". Нужно постоянно напоминать что мы здесь не теоремы доказываем, а решаем практическую актуальную задачу. В результате пока красивый, быстрый и простой алгоритм, оптимизирующий плотность размещения, сделал я сам, с него мы, наверное, и начнём - а дальше развивать и усложнять под многокритериальную задачу. В общем, весьма интересно, хоть я сам код уже не пишу.