8.7. Задача оптимальной раскладки грузов па поддоне

Рассмотрим применения ГА для нахождения оптимальной раскладки коробок одинаковых размеров на поддоне (паллете). Данная задача часто возникает в логистике, где осуществляется либо хранение, либо транспортировка грузов, упакованных в коробки и укладываемых на стандартные поддоны. При этом коробки могут быть произвольного размера, так как в различных странах используются различные стандарты, но на поддон укладываются лишь коробки одинакового размера.

По существующим нормам коробки могут на 5мм выступать за пределы поддона (рис. 8.36, а).

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

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

Оптимальным решением данной задачи следует считать решение, удовлетворяющее следующим условиям:

1)   коэффициент заполнения поддона коробками максимально высокий;

2)   варианты раскладок, найденные системой, должны обеспечивать возможность качественного штабелирования.

В качестве входной информации система учитывает:

•    размеры коробки;

•    размеры поддона;

•    размер популяции;

•    коэффициент новых особей по поколениям;

•    вероятность мутации;

•    размер выступа коробок за пределы границы поддона.

Выходными данными должно являться описание и отображение оптимального решения. Основным критерием оптимизации является коэффициент заполнения площади поддона (рис. 8.37):

где Sbox — площадь коробки; Щох — количество коробок на одном уровне поддона; Spai — площадь поддона.

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

Каждая особь имеет некоторые свойства:

•    тело — описание особи. В нашем случае описание представлено в виде линейной бинарной строки, где О-му значению бита соответствует горизонтальное расположение коробки, 1-му — вертикальное. Такое описание особи (раскладки) дает легкое применение операторов генетики и ускоряет работу программы в целом, что в конечном итоге приводит к лучшим результатам. Для преобразования такой линейной цепочки применяется специальный алгоритм укладки. Каждая следующая коробка укладывается на первое попавшееся место на поддоне по приоритету слева-направо, сверху-вниз. Так, раскладка, приведенная на рисунке 8.37, соответствует особи: 00001 1 1 100000000 111100000000111100000000 0;

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

ента заполнения условных линий поддона S со своим коэффициентом важности ks (рис. 8.38):

Коэффициент заполнения условных линий поддона S рассчитывается по формуле:

где Рх — ширина поддона;

I — общее число линий, di — незаполненность по линии.

Для работы программы необходимо задать некоторые входные пара™ метры, среди которых будут: размеры коробок {Вх, By), размеры поддона (Рх,Ру), а также некоторые коэф™ фициенты. Первое поколение особей (раскладок) генерируется по случайному закону. В качестве уело™

ВИЙ окончания процесса эволюции популяции может использоваться либо окончание времени эволюции t > Т, либо выполнение равенства

= О, что означает, что получены все генотипы в хромосомном набо™ ре популяции.

После того, как получена попу™ ляция, содержащая лучшие особи, следует использовать несколько лучших особей для формирования раскладки коробок на нескольких уровнях шта™ беля. Так можно, например, все четные уровни заполнять согласно лучшей особи, а все начетные — согласно второй по качеству особи популяции (рис. 8.39).

Программа, реализующая генетический алгоритм, написана на языке программирования Borland C++ с использованием объектного подхода, т. е. все необходимые основные данные и процедуры реализованы как свой™ ства и методы соответствующих классов. Такой подход позволяет просто и наглядно представить необходимые данные и описать методы работы

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

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

Методы объекта BOX (коробка) позволяют создавать описание коробки (К), после чего К в состоянии сама отвечать на основные вопросы, возникающие при укладке коробок и подсчете коэффициентов, такие как: Не занимает ли коробка места с координатами х, у и определенной ориентацией? Не расположена ли коробка на уровне у? и т. п. При этом К «умеет» отображать себя на экране в заданных координатах (метод show(x, у)).

Методы объекта PERSON (особь) позволяют создать раскладку с некоторым описанием, т. е. проверить, как укладывается данное описание на поддон и вычислить соответственно коэффициент заполнения поддона К, количество переложенных коробок, подсчитать коэффициент заполнения поддона по уровням и, соответственно, найти функцию пригодности S для данного варианта укладки.

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

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

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

1.   МАХ РОР — количество особей в популяции.

2.   К NEW — количество новых особей (число скрещиваний).

3.   K MUT — коэффициент мутации (часть изменяющейся длины особи).

4.   LIFE — время «жизни» особи (максимальное число поколений, которое она может существовать).

5.   K NEAR — коэффициент близости особей.

6.   ks — коэффициент влияния на функцию жизнеспособности.

Значения этих параметров, обеспечивающие эффективное функционирование системы, были получены экспериментально и соответственно равны: K_NEW = 2; KJVfUT = 2; LIFE = 7; KJNEAR = 10; ks = 0,9.

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

1.   Размеры коробки не кратны друг другу (ширина не кратна длине).

2.   Размеры коробки кратны друг другу (ширина кратна длине).

3.   Размеры коробки кратны друг другу (ширина кратна длине) и они кратны какому-либо из размеров поддона.

Анализ полученных результатов показал, что ПГА ведет себя лучше (дает большие значения коэффициента заполнения поддона) в 1-м, самом общем, случае и незначительно хуже — во 2-м и 3-м случаях (по всей видимости это объясняется тем, что эвристический метод реализует именно поиск кратных сочетаний размеров для оптимизации).

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

В результате можно сделать следующие выводы:

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

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