ОПТИМИЗАЦИОННАЯ ЗАДАЧА ПО РАЗМЕЩЕНИЮ КОНТЕЙНЕРА НА СКЛАДЕ

​OPTIMIZATION PROBLEM FOR PLACING A CONTAINER IN A WAREHOUSE

Oleg Dudnik

Student, Department of Operational Work Management, St. Petersburg State University of Railway Transport,

Russia, St. Petersburg

Maria Zhurba

Student, Department of Operational Work Management, St. Petersburg State University of Railway Transport,

Russia, St. Petersburg

АННОТАЦИЯ

В современном мире, который находится в процессе активной глобализации как транснациональные корпорации, так и более мелкие компании часто сталкиваются с проблемами логистики и складирования. Одна из таких проблем — оптимизация размещения контейнеров на складе. Задача размещения заключается в том, что необходимо расположить прибывающие контейнеры на складе таким образом, чтобы их перемещения были минимальны. Как показывает практика, оптимизация этой задачи позволяет сократить складские издержки на 25%.

ABSTRACT

In the modern world, which is undergoing active globalization, both transnational corporations and smaller companies often face logistics and warehousing challenges. One of these challenges is the optimization of container placement in warehouses. The placement task involves arranging incoming containers in a way that minimizes their movements. As practice shows, optimizing this task can reduce warehousing costs by 25%.

Ключевые слова: решение задачи размещения контейнеров на складе, оптимизация, жадный алгоритм, Simple Random, Simple High, Simple Low, Simple High, Simple Random, Proximity, Inversions, Order.

Keywords: solving the problem of placing containers in a warehouse, optimization, greedy algorithm, Simple Random, Simple High, Simple Low, Simple High, Simple Random, Proximity, Inversions, Order.

Постановка задачи

Дан некоторый склад с контейнерами, в котором необходимо оптимально расположить прибывшие контейнеры. Склад имеет  позиций для размещения контейнеров. Контейнеры идентичны и могу ставится друг на друга. На одной позиции могут быть расположены не более  контейнеров. Планирование происходит на некотором горизонте . Для каждого контейнера известен временной интервал , когда контейнер  будет удален со склада. Контейнеры в рамках определенного временного интервала удаляются одновременно. Если время удаления контейнера находится за пределами горизонта планирования, то считаем, что контейнер не будет удален со склада. На складе работает один кран, который заносит, перемещает и удаляет контейнеры. Кран может перемещать/удалять контейнер, который расположен на самом верху. С каждым перемещением контейнера связаны фиксированные затраты. Задача заключается в том, чтобы найти последовательность расстановок каждого контейнера так, чтобы в итоге свести к минимуму их перемещения.

В данной работе будет рассматриваться решение при помощи жадного алгоритма.

1. Жадный алгоритм

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

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

Целевые функции

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

Так же, необходимы тривиальные функции, с которыми можно сравнивать результаты применяемой оптимизации. Такие функции будут иметь приставку «Simple».

Визуализацию всех целевых функций будем приводить на одном примере. Пусть заданы такие параметры: n = 4, ub = 4. Пусть необходимо загрузить контейнеры: {7, 9, 17, 18}.

При этом, начальное положения склада представлено на рисунке 1:

Рисунок 1. Начальное состояние склада

Simple Random

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

Пошаговая визуализация представлена на рисунках 2-6:

Рисунок 2. Шаг 0 в Simple Random

Рисунок 3. Шаг 1 в Simple Random

Рисунок 4. Шаг 2 в Simple Random

Рисунок 5. Шаг 3 в Simple Random

Рисунок 6. Шаг 4 в Simple Random

Simple High

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

Пошаговая визуализация представлена на рисунках 7-11:

Рисунок 7. Шаг 0 в Simple High

Рисунок 8. Шаг 1 в Simple High

Рисунок 9. Шаг 2 в Simple High

Рисунок 10. Шаг 3 в Simple High

Рисунок 11. Шаг 4 в Simple High

Order

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

Пусть есть стопка {3, 4, 2, 1, 7}, где номера контейнеров совпадают с временными интервалами, когда контейнеры должны быть удалены.

Для того чтобы посчитать сколько элементов стоит в неправильном порядке, возьмем разницу между соседними элементами (Differences), получим {1, -2, -1, 6}. Отрицательная разность говорит о том, что элементы расположены правильно, тогда как положительная говорит об обратном. Превратим все числа меньше нуля в ноль, а остальные в единички (UnitStep) и просуммируем (Total), получим число контейнеров, которые стоят неправильно.

Inversions

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

Пример:

Пусть у нас есть все та же стопка контейнеров {3, 4, 2, 1, 7}, у которой номера контейнеров совпадают с временными интервалами удаления этих контейнеров. Сначала должен уйти контейнер с номером 1, но для этого нужно переместить контейнер 7. В итоге получим {3, 4, 2, 7}. Затем уберем контейнер 2, для чего снова переставляем контейнер 7, получаем {3, 4, 7}. Следующим необходимо удалить контейнер 3, но для этого нужно переставить контейнеры 4 и 7. Остается {4, 7} На предпоследнем шаге мы переставляем 7 контейнер и удаляем 4. После чего удаляем единственный оставшейся контейнер 7.

Получается, что всего необходимо 5 перемещений контейнеров (Не учитываем перемещения обратно, т.к. в их учете нет необходимости. Действие по перемещению всегда предполагают возвращение контейнера на исходное место в данном контексте разбора стопки).

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

Это соображение очевидно, т.к. чтобы убрать контейнер , нам нужно переместить все контейнеры с временным интервалом большим , которые стоят правее , но это и есть число инверсий для .

Для того, чтобы получить из произвольного списка перестановку, необходимо воспользоваться простой пере нумеровкой (Ordering).

Proximity

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

Рисунок 12. Зависимость между высотой и временем ухода контейнера

Введем функцию, которая будет определять характеристику высоты контейнера в диапазоне :

где  - уровень, на котором находится -ый контейнер;

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

Аналогичным образом введем функцию с областью значений , которая будет определять как скоро контейнер должен быть убран:

где - горизонт планирования;

- текущий момент времени;

 - период времени, в который должен быть удален -ый контейнер.

Теперь для каждого контейнера введем функцию оценки:

Функция говорит о том, как хорошо расположен контейнер. Функция принимает значение 0 при лучшем расположении контейнера и 1 при худшем.

Очевидным образом введем целевую функцию:

где  – общее число контейнеров.

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

Проведем 20 тестов всех целевых функций и вычислим среднее значение перемещений контейнеров и время работы алгоритма. Пусть у нас будет 50 мест под контейнеры, ограничение на высоту 40, количество контейнеров 250, горизонт планирования – 30 дней.

В таблице 1 видно, что наилучшее значение показывает целевая функция Proximity. Благодаря оптимизации получаем сокращение издержек на ~30% по сравнению со случайным расположением контейнеров, и на ~50% процентов по сравнению с упорядоченным расположением контейнеров, однако, приходится платить за это вычислительным временем.

Таблица 1.

Результаты вычислительного эксперимента

Список литературы:

1. Адитья Бхаргава – Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих – СПБ,: Питер, 2017.
2. gSconto [Электронный ресурс] / Режим доступа: - www.gsconto.com/ru
3. Хайтек [Электронный ресурс] / Режим доступа: -  www.hightech.fm
4. Технологии Wolfram [Электронный ресурс] / Режим доступа: - www.wolfram.com
5. Dragović B., Park N.: A Study of Container Terminal Planning, Faculty of Mechanical Engineering, Belgrade, VOL. 37, No. 4, 2009., pp. 203-209.