Трудно было предсказать тогда, что через пять лет «Таргет» – заказчик огромного масштаба – станет для нас какой-то мелкой обузой, о которой вспоминают последней и от которой хочется отмахнуться, как от назойливой мухи, потому что приоритетным к тому времени будет клиент намного крупнее. Как бы то ни было, «Таргет» был заинтересован, и осенью 2011-го их представители стали появляться в офисе «КейсПика» (см. цв. вкл., рис. 9). Как-то раз мне довелось сделать для них небольшую презентацию про палетизацию и мой алгоритм упаковки коробок. Палетизация на тот момент им была не нужна – они загружали свои фуры вручную, коробку за коробкой, и пока не собирались отказываться от этого. Но в одной из первых презентаций для руководства «Таргета» два слайда были посвящены алгоритму палетизации KP – в качестве примера расширения интеллектуальной собственности и инновационного потенциала компании.
Рис. 7. Слайд из презентации для «Таргета»: алгоритм палетизации KP как пример инновационного потенциала нашей компании
Но тогда, в конце 2011 г., для «Таргета» особенно важна была плотность хранения товаров в ограниченном пространстве склада. Коробки приходили туда постоянно, днем и ночью, иногда с большими перерывами, а иногда – на множестве фур одновременно. Худшее, что могло случиться, – на стеллажах могло не оказаться места для прибывающих коробок.
Нам нужно было оптимизировать плотность хранения для нашей системы, где коробки сильно различались по размеру. Основной проблемой, которая могла возникнуть после того, как одно место хранения многократно занимали и покидали разные коробки, была фрагментация пространства. Этот эффект аналогичен фрагментации компьютерной памяти, знакомой многим пользователям: когда жесткий диск переполнен нужным и ненужным багажом – сотнями загруженных откуда-то видео, книгами, скачанными «на всякий случай» и не прочитанными никогда, тысячами фоток и мелких файлов разных форматов.
В нашем случае длина одного пролета (storage bay) стеллажей, по обоим концам которого располагались стальные опоры, поддерживающие вес самих стеллажей, коробок и проезжающих мимо них ботов, составляла около 2,5 м. Эта стандартная единица длины была разделена на 36 позиций с интервалами в 3 дюйма – или около 7,6 см, – размеченными профилями (hat sections). Коробки разного размера нужно было максимально эффективно разместить внутри этого отрезка в 36 трехдюймовых единиц длины – так, чтобы оставалось как можно меньше пустот. Левый край каждой коробки должен был находиться точно на опоре hat section.
Коробки прибывали и убывали, и на стеллажах постепенно появлялись мелкие промежутки, где нельзя было поместить новые коробки. Допустим, сначала на пустое пространство стеллажа была уложена коробка размером в 6 единиц длины (общей длиной чуть менее 18 дюймов[14]). По обе стороны этой коробки находились соседние, других размеров. Эта коробка ушла на исполнение заказа, образовав пустое пространство в 6 единиц длины. Потом на это место поставили коробку размером в 4 единицы длины – оставив 2 единицы длины пустого пространства. Но 2 единицы длины – слишком мало для того, чтобы поместить туда какую-нибудь другую коробку. Таким образом, 2 единицы длины оставались незаполненными, потерянными в данный момент для системы – этот эффект похож на фрагментацию компьютерной памяти в результате размещения в ней большого числа мелких файлов.
Когда нужно было определить, куда положить очередную коробку, наш софтвер анализировал каждый пустой интервал на стеллажах – между двумя коробками или между коробкой и вертикальной опорой. Интервалы меньше размера коробки отметались сразу, а что касается тех, которые были больше, – неким вероятностным путем высчитывалась их оптимальность для размещения данной коробки. Но этот способ все равно приводил к фрагментации и появлению множества мелких пустых интервалов, где ничего нельзя было поместить.
В освободившееся к завершению проекта KP время я стал думать над фундаментальным решением этой задачи. И решение, практически исключающее усиление фрагментации и увеличение потерянного пространства, скоро нашлось. Придуманный мной алгоритм немного напоминал прием, использованный в алгоритме палетизации – в том месте, где я подбирал коллекции стеков одинаковой высоты. Только вместо высоты стеков здесь фигурировала длина одной ячейки хранения – пролета между вертикальными опорами.
В моем подходе каждый пролет был виртуально разделен на заранее рассчитанные интервалы, заполнявшие его полностью. Например, пролет в 36 трехдюймовых единиц (называемых в этой системе квант длины) можно было разделить на следующие интервалы: 9, 7, 6, 5, 5, 4, в сумме дающие 36. Другой пролет мог состоять из таких интервалов: 8, 8, 6, 6, 4, 4. Таких комбинаций интервалов можно было подобрать великое множество. Но они должны были подчиняться статистической закономерности: общее число интервалов каждой возможной длины должно быть пропорциональным ожидаемому числу коробок такой длины на стеллажах. Например, если ожидаемое число коробок, занимающих на полках чуть меньше 21 дюйма (7 интервалов длины), было в два раза меньше количества занимающих чуть меньше 15 дюймов (5 интервалов длины), то в этом распределении число интервалов длины 7 должно быть в два раза меньше, чем интервалов длины 5.
Создать такое распределение не очень просто, но вполне возможно. Его нужно вычислять один раз для списка товаров на конкретном складе и в дальнейшем только постепенно корректировать. Я написал программу, генерирующую оптимальное разделение всех пролетов в стеллажах системы на отдельные интервалы, так, чтобы их общее количество соответствовало заданной статистике. Разделение каждого пролета на строгие интервалы значительно упрощало поиск места для очередной коробки. Допустим, на хранение поступила коробка в 17 дюймов длиной (6 единиц на стеллаже). Чтобы выбрать оптимальное место для нее, нужно было найти все пустые интервалы в 6 единиц. Поместив коробку в любой из них, мы автоматически предотвращали фрагментацию, так как пустого пространства не создавалось. Поддерживать список таких интервалов в системе не слишком сложно. Из всех имеющихся пустых интервалов в 6 единиц далее нужно выбрать несколько лучших по другим критериям. Например, если в коробке хорошо продаваемый товар и, по ожиданиям, она очень скоро покинет склад, то ее лучше поместить в начало аллеи стеллажей, чтобы бот быстро преодолевал расстояние до нее от входа в аллею. Если же коробка содержала редкий товар и могла недели или даже месяцы пролежать на складе, ее можно было поместить намного дальше от входа в аллею – боту пришлось бы преодолевать большее расстояние, но число таких путешествий было сравнительно невелико.
Нужно было учитывать и другие нюансы. Например, на обычном неавтоматизированном складе одинаковые или похожие продукты хранятся близко друг к другу, чтобы рабочим было легче находить их. Для нашего автоматизированного склада логика была принципиально другой. Каждый вид товара нужно было максимально рассредоточить по всему пространству. Это повышало доступность товара в любой момент времени: нередко отдельные аллеи стеллажей или целые ярусы закрывались на довольно продолжительное время – боты застревали там, и периодически их приходилось выковыривать оттуда вручную. Но и когда все пути были открыты, рассредоточение позволяло быстро находить упаковки товаров, расположенные относительно недалеко от точки выхода – места, где происходил обмен между ботами и MVC, – значительно сокращая путь бота от стеллажей к этому месту.
Я построил весьма сложный симулятор всех стеллажей системы, оптимизировавшей места хранения каждой коробки. Модель имитировала поступление новых коробок разных товаров на хранение (целыми палетами или слоями из палет) и их убытие на палетизацию согласно заказам магазинов. Модель была основана на описанном выше принципе разделения каждого пролета на неравные интервалы: их общая статистика соответствовала ожидаемой статистике отрезков длины, которую должны были занимать хранящиеся на складе товары. В моей модели действительно практически отсутствовала фрагментация пустого пространства, даже после прибытия и убытия миллионов коробок. Пришлось добавить более сложные механизмы, чем красивый принцип вычисленного заранее разделения пространства на неравные интервалы. Когда стеллажи были почти заполнены, статистика оставшихся пустых мест уже сильно отличалась от размеров новых поступающих товаров, и модель больше не могла найти интервалы нужной длины. Разделение пространства приходилось изменять в реальном времени – переформатировать оставшиеся пустые интервалы так, чтобы добавить отрезки именно недостающей длины. Эти и многие другие нюансы были включены в модель. В результате стеллажи в ней удавалось эффективно заполнять более чем на 98 %, в то время как на нашем складе в Ньюбурге рабочий код начинал жаловаться на отсутствие места для новых коробок (из-за потерь на фрагментацию) при заполнении на 85–87 %.
Ларри и я стали лоббировать имплементацию моего алгоритма. Это не было столь же важным, как проект KP, – в последнем случае речь шла о самом выживании компании, так как с прежними ужасными палетами нельзя было двигаться в будущее. Оптимизация плотности хранения требовалась, но пока можно было обойтись без нее. Контракт с «Таргетом» на строительство нашей масштабной (во много раз больше Ньюбурга) автоматизированной системы под Сакраменто, Калифорния, был уже подписан – гора с плеч.
Софтверный отдел упирался: у них была груда критических багов и ляпов в системе, из-за чего инженеров срывали для работы по вечерам и в выходные. Некоторые из багов останавливали систему полностью, так что до оптимизации, позволяющей увеличить плотность хранения примерно на 10 %, руки совершенно не доходили. В итоге мой алгоритм (да и то в урезанном виде) был реализован в рабочем коде только через шесть лет. К тому времени сама система изменилась почти до неузнаваемости и весь рабочий код был переписан, иногда уже по нескольку раз.