Над этой задачей пришлось очень серьезно поломать голову, и я подошел к ней следующим образом. Итак, необходимо проверить все возможные комбинации групп товаров (те или иные группы могут присутствовать либо отсутствовать в этих комбинациях). Попробуем подобрать такую комбинацию групп, чтобы их суммарный объем был чуть меньше, чем максимальный объем, который реально упаковать в одну палету. Этот максимальный объем невозможно предсказать с точностью. Для одной комбинации товаров палета будет упакована под завязку с 85 кубическими футами коробок, для другой места не останется уже после 75 кубических футов. Это едва ли можно оценить исходя из предварительной общей статистики (большие у нас коробки или маленькие, квадратные или продолговатые): слишком много факторов влияет на процент остающегося между коробками пустого пространства.
Я придумал итерационный алгоритм, позволяющий искать оптимальные комбинации в условиях такой неопределенности. Допустим, у нас есть 10 групп товаров. Их всевозможные комбинации можно представить в виде двоичного числа с 10 разрядами (битами): всего таких комбинаций будет 1024. Если в определенном разряде стоит 1, то группа товаров, соответствующая этому разряду, присутствует в данной комбинации, если 0 – то отсутствует в ней. Например, число 21 в двоичном коде представляется как 10101, то есть биты в разрядах 1, 3, 5 (начиная с младшего) равны единице. Это соответствует комбинации из групп товаров под номерами 1, 3, 5. Нужно вычислить общий объем товаров во всех этих комбинациях и отбросить те, чей объем превышает максимальный ожидаемый объем палеты. Оставшиеся комбинации нужно отсортировать по объему, от большего к меньшему. Далее нужно взять первую комбинацию в отсортированном списке и попробовать построить палету из этих групп товаров. Например, комбинация состоит из групп товаров под номерами 1, 5, 7, 9 (в двоичном виде она представляется как 101010001, а в десятичном соответствует числу 337), и ее объем составляет 99 % от ожидаемого максимума. Допустим, не все коробки из этой комбинации поместились в палету. Тогда отбрасываем полученный результат и пробуем следующую комбинацию – например, из групп 2, 4, 7, с общим объемом 98 % от максимума. Теперь нам удалось упаковать все коробки. Отлично! Значит, больше не надо заботиться о группах 2, 4, 7 – все они поместились в первую палету, – и на следующей итерации мы повторяем ту же процедуру с оставшимися семью группами – 1, 3, 5, 6, 8, 9, 10. Этот алгоритм позволял одновременно минимизировать число палет заказа и делать каждую из них максимально «чистой»: каждая товарная группа имелась только в одной палете (кроме групп, полностью составляющих одну или более палет и имеющих остаток в одной из палет с другими группами).
В реальности задача могла быть еще сложнее. Не все группы товаров хорошо сочетаются друг с другом. Некоторые товары могут находиться далеко друг от друга на полках магазина, другие – например, жидкие средства для стирки и детское питание – нежелательно помещать в одной палете. В таких случаях условия задачи нужно скорректировать. Комбинации должны быть отсортированы не просто по объему коробок, а по составному показателю, учитывающему, насколько группы товаров в комбинации совместимы друг с другом. Например, такую совместимость (affinity) между любыми двумя группами можно представить в виде матрицы Aij с элементами, принимающими значение от 0 (если пара плохо совместима) до 1 (если хорошо). Тогда объем комбинаций можно, например, умножать на среднее значение совместимостей входящих в нее групп. Или на минимальное значение этих совместимостей – единственно верного варианта здесь нет. После этого комбинации нужно сортировать уже по этой метрике и начинать пробовать упаковку с той, что имеет максимальное значение.
Я сделал бóльшую часть прототипов этих алгоритмов летом и осенью 2014 г., до тех пор, пока почти полностью не сосредоточился на проекте штучного отбора с «Таргетом». Но возвращаться к палетизации как к основному направлению работы мне уже не очень-то хотелось. Вместе с Ларри и тогдашним вице-президентом софтверного отдела Брюсом Ф. мы пришли к следующему варианту: взамен Дэвида мы найдем квалифицированного программиста, и тот, консультируясь со мной, начнет переписывать мой алгоритм с самого начала, с учетом моих недавних корректировок. Помимо этого, нужно будет переписать код с C++ на C# – весь софтвер у нас теперь был основан на «си-шарпе». Новый инженер будет формально числиться в отделе планирования и управления (Planning and Control, или кратко – PnC) – так называлась группа программистов, пишущих софт для координации движения ботов, оптимизации распределения коробок по стеллажам хранения и других подобных задач. Предполагалось, конечно, что я буду участвовать в отборе кандидатов и мое одобрение будет необходимым при найме.
Но вскоре, в конце сентября, я узнал, что человека на эту позицию уже нашли, не спросив моего мнения. Группой PnC руководил Мэтт Эрл – как и я, выходец из лаборатории «Си-энд-Эс», ставшей CTO Group в «Симботике» (Мэтт пришел туда почти на год позже меня). Мэтт, PhD Корнеллского университета, уже занимался прежде задачами координации движения мобильных роботов – как в складской сфере, так и для воздушных дронов. Один из руководителей его диссертации в Корнелле основал компанию «Кива Системс», купленную «Амазоном» в 2012 г. и превращенную в «Амазон Роботикс».
Мэтт пользовался немалым уважением в «Симботике». Он руководил важнейшим направлением, много работал и сам писал рабочий код – в отличие, например, от меня. Но к тому времени у него проявилась очень проблематичная черта. Он считал себя всезнайкой и старался все грести под себя, огораживая свою «полянку», и если кто-то, по его мнению, пытался залезть на нее, реагировал крайне негативно, порой почти истерически. Я с ним пересекался достаточно редко, но иногда пробовал обсуждать проблемы распределения задач для наших ботов и их маршрутизации, нынешнее решение которых мне казалось далеко не оптимальным. Мэтт весьма неохотно шел на это, считая, что ему виднее.
И вот теперь Мэтт нанял для переписывания софта палетизации некоего Омара К. Я заранее написал Мэтту о минимальных требованиях к кандидату на эту позицию. Главными были знакомство с Матлабом (языком, на котором был написан мой прототип алгоритма) и хорошее представление о комбинаторной оптимизации. Моя первая встреча с Омаром показала, что у него были практически нулевые знания по обоим вопросам. Когда я стал объяснять ему принципы алгоритма KP, он тут же «поплыл». Построение стеков, а также их двумерная упаковка в плоский слой были слишком сложной для него задачей. После первых двух-трех наших встреч решение о его найме выглядело крайне неудачным.
Я поделился своими опасениями с Ларри и написал Мэтту, что введение Омара в курс дела требует намного больше усилий и времени, чем я ожидал, – но не стал сразу бить тревогу. Я был сосредоточен на новом интересном проекте штучного отбора (breakpack) с «Таргетом». Проблема палетизации, в отличие от 2011 г., на тот момент не была первоочередной. Тогда мы не предполагали, что уже в следующем, 2015 г. она снова станет критически важной.
Время шло. Каждые пару месяцев я встречался с Омаром, чтобы посмотреть, как продвигается новый рабочий код палетизации. Продвигался он из рук вон плохо. Омар едва научился упаковывать слои из одинаковых коробок. Композитные слои со сложной двумерной упаковкой из стеков были для него недостижимой высотой – он до сих пор с трудом понимал, как должен работать алгоритм построения таких слоев. Некомпетентность Омара грозила провалить весь проект.
В дальнейшем подтвердилось, что это не было только моим мнением. Над непроходимым тугодумством Омара хихикали другие девелоперы из группы PnC. «Он настолько туп, что от общения с ним у меня каждый раз голова болит», – высказался один из них. Как и в случае с Гилом К. («Винсом Масукой» из восьмой главы), для меня оставалось загадкой, как такие бестолковые персонажи оказывались на должностях, требующих высоких компетенций. Тем не менее это случалось регулярно, и на собеседованиях с кандидатами не всегда удавалось распознать их неготовность к работе, на которую они нанимались.
Незадолго до ухода Ларри, в мае 2015-го, я понял: терпеть все это уже нельзя. Я подробно рассказал Ларри о плачевном состоянии проекта. Он воспринял это со всей серьезностью и довел до сведения остального начальства. Как выяснилось, руководство софтверного отдела пребывало в блаженном неведении и считало, что проект нового кода палетизации продвигается успешно и без особых проблем.
По совету Ларри в июне 2015 г. я представил план оздоровления проекта, и теперь на него назначили не одного Омара, а целую команду из недавно пришедших молодых разработчиков. Скорость заметно возросла. Менеджером команды стал Кайл Т., относительно недавно получивший PhD и первоначально нанятый в команду управления ботами. Теперь, к осени 2015-го, палетизация вновь стала актуальной и требовала концентрации сил. Мы подписали контракт с «Кока-Колой» о строительстве системы в Нью-Брансуике, штат Нью-Джерси. По плану общая площадь наших стеллажей на этом складе была небольшой, но система должна была включать четыре ячейки палетизации и работать очень интенсивно (по числу коробок в час). Кроме того, наконец-то было принято решение о строительстве системы в Бетлехеме, хотя и меньшего размера, чем предполагалось первоначально. К тому же «Волмарт» был уже близок к подписанию контракта на первый проект с «Симботиком». Следующий год обещал стать очень горячим в строительстве новых систем.
К началу 2016-го склад «Кока-Колы» в Нью-Брансуике начал обретать форму. Были возведены стеллажи, по ним протянули километры кабелей, по некоторым ярусам начали ездить – в тестовом режиме – наши боты. Было установлено оборудование для депалетизации и палетизации. За несколько лет после нашей первой системы в Ньюбурге мы полностью переделали соответствующие ячейки. В 2015 г. «Симботик» купил базирующуюся в Монреале канадскую компанию «Эксиум», предложившую свою разработку для систем депалетизации и палетизации. Обе концепции были интересными.