Одной из частных задач, с которыми может столкнуться конструктор при проектировании упаковки – это задача предварительно скомпоновать упаковываемые изделия с целью последующего определения габаритов контейнера (ящика), необходимого для упаковки данных изделий. С такими задачами я сталкивался в ООО «СТЦ». Пример одной организации, может быть, и не показателен, но аналогичная задача встречалась мне и в другой организации.
Такого рода компоновка может выполняться вручную с использованием 3D-моделирования (возможны также другие способы с последующим построением результата на двумерном чертеже вручную). И если таких упаковываемых изделий наберется, например, 20, то ручная компоновка становится достаточно трудоемкой.
Вместе с тем, решение похожих задач рассматривается в различных работах и публикациях, и в качестве одного из методов для их решения используются разнообразные вариации генетических алгоритмов, позволяющие не только скомпоновать, но и оптимизировать компоновку.
Из этого возникла идея самостоятельно разработать приложение для компоновки под свою специфику, попробовав использовать при этом генетические алгоритмы. Что из этого получилось – будет рассказано дальше в статье.
Перейдем к более подробному описанию условий задачи.
UPD
В процессе дальнейшего изучения и работы над материалами по тематике статьи были получены новые результаты, которые, по мнению автора, было бы целесообразно включить в текст статьи в качестве дополнений или в форме корректировки ее текста. По этой причине текст статьи был дополнен.
Конец блока UPD
Продолжим далее изложение материалов статьи.
Предполагается, что упаковываемые изделия помещены в коробки, но не исключается в дальнейшем для расширения сферы применения работы рассматривать и прочие изделия в виде прямоугольных параллелепипедов. Коробки с изделиями помещаются в контейнер (фактически в ящик со съемной крышкой). Дополнительная фиксация осуществляется с помощью прокладок из картона и пенопласта. Другим вариантом размещения, с которым я сталкивался, является применение разборных ящиков со съемными дном и крышкой, крепящихся к стенкам ящика с помощью болтов. Коробки с изделиями укладываются на специализированные (нестандартные) поддоны, крепятся к поддонам с помощью лент (другой вариант, который можно использовать – это фиксация коробок стрейч-пленкой). Поддоны с изделиями помещаются внутрь разборных ящиков.
Условия размещения коробок (далее блоков) внутри контейнера (без учета пространства, занимаемого поддоном) задаются рядом математических ограничений, перечисленных ниже.
1. Имеется множество n размещаемых блоков, i = 0, 1, …, n-1. Каждый i-й блок характеризуют три размера по осям x, y и z:
, 
и 
соответственно (размеры задаются в мм). Размеры по осям заданы для ориентации 1 блока (см. рисунок ниже) [1]. Всего, согласно данному рисунку, может быть шесть вариантов ориентации.
2. На любой из блоков может быть наложено дополнительное ограничение в виде ориентации только вверх. При этом допустимы только варианты ориентации 1 и 2 согласно рисунку выше.
3. Каждый упакованный блок характеризуется координатами двух точек (координаты здесь и далее указываются в мм), где точка 1 – точка, самая близкая к началу координат, точка 2 – наиболее удаленная от начала координат:
и 
. Таким образом, решение задачи имеет вид 
.
4. Каждый i-й блок лежит на дне контейнера или на верхней части одного или нескольких блоков. Для формулировки данного условия введены следующие построения.
Каждый i-й блок характеризуется четырьмя точками на нижней грани:
, (j = 1, 2, 3, 4). Точка с индексом j = 1 совпадает с точкой 1 по п. 3, далее нумерация идет по часовой стрелке.
Каждый k-й (k = 0, 1, …, n-1) блок характеризуются координатами двух точек, задающих верхнюю грань, на которую могут опираться другие блоки. Индексы i и k у каждого отдельно взятого блока совпадают. Точка 1 – точка, самая близкая к началу координат, точка 2 – наиболее удаленная от начала координат:
и 
.
Условие наличия опоры для i-го блока проверяется по выполнению выражения (1) либо выражения (2):
5. Контейнер ограничивается размерами W, L и H (задаваемыми в мм) по осям x, y и z соответственно. В статье рассматриваются два варианта. Либо H принимает значение, соизмеримое с W и L (похожая ситуация рассматривается в работе [2, с. 74]) – вариант 1 алгоритма, либо H является теоретически неограниченной высотой, вычисляемой как сумма наибольших размеров блоков, что основывается на публикации [3] – вариант 2 алгоритма.
UPD
Также будут рассмотрены варианты, когда H соизмерима с двумя другими сторонами контейнера и выбирается по тем же принципам, что и размеры этих двух сторон.
6. Ни один блок не выходит за границы заданного объема:
7. Суммарный объем блоков не превышает объема контейнера:
8. Блоки не налагаются друг на друга в объеме.
Здесь хотелось бы отметить, что в различных источниках могут встречаться различные выражения для описания условия проверки пересечения параллелепипедов. На отработке этой проверки моя работа при отладке приложения застопорилась, и только поиск выражений в различных источниках, общение с некоторыми разработчиками приложений-аналогов и написание специализированной программы для отладки помогло прийти к решению. Приложение для отладки сравнивало проверку пересечения методом перебора и методом сравнения по одному из представленных в различных источниках выражений. В качестве исходных данных для проверки использовались случайно сгенерированные пары параллелепипедов, размещаемые по случайным координатам в ограниченном объеме. Результаты размещения параллелепипедов можно было визуализировать в приложении, описанном в моей предыдущей статье [4]. В конечном итоге удалось убедиться на основе большого количества испытаний в работоспособности выражения, взятого в источнике [5] и модифицированного под свою задачу (условия больше и меньше были заменены на больше или равно и меньше или равно). В этом выражении число выполняемых проверок минимально.
Итак, условие отсутствия пересечений двух параллелепипедов задается логической истинностью выражения для координат точек 1 и 2 согласно п. 3:
Предполагаю, что, например, в математическом аппарате для игр с трехмерной графикой есть соответствующие теоретические положения, доказывающие корректность данного выражения.
UPD
Что в дальнейшем и подтвердилось работой [8].
9. Блоки располагаются параллельно стенкам контейнера.
10. Все блоки должны быть упакованы в заданный контейнер.
После описания математических ограничений задачи перейдем теперь к описанию способа подготовки исходных данных для реализации работы алгоритма.
Следует отметить, что, судя по литературе, для сравнения эффективности алгоритмов трехмерной упаковки существуют эталонные наборы тестовых примеров (см., например, [2, с. 115]). Не исключено, что в дальнейшем будет изучено данное направление, но предварительно на данном этапе была предпринята попытка сгенерировать тестовые примеры самостоятельно с возможностью их адаптации под условия конкретных задач в организации.
Для генерации наборов тестовых примеров было написано консольное приложение на C++. Приведем содержание файла исходных настроек для работы приложения (см. рисунок ниже).
Число блоков (коробок) может варьироваться (см. строку 2 на рисунке выше) Предполагается, что с определенной вероятностью коробки могут упаковываться группами с определенным числом коробок в группе (см. строки 4, 2 и 8 на рисунке выше). Блоки могут с определенной вероятностью быть ориентированы вверх (см. строку 28). Может с определенной вероятностью генерироваться коробка со случайным соотношением сторон (строки 10, 30, 32). Длина стороны по случайно выбранной координате (строки 24 и 26) домножается на множители, лежащие в определенном диапазоне (строки 12, 14, 16, 18, 20 и 22).
Теперь, когда мы описали исходные данные для задачи трехмерной компоновки, перейдем к методам ее решения.
При решении задачи изначально предполагалось, что возможно разработать генетический алгоритм, подходящий для данных условий и позволяющий оптимизировать упаковку применительно к минимизации занимаемого объема. Перечислим основные характеристики данного алгоритма.
В качестве целевой функции генетического алгоритма была взята плотность упаковки:
где
– объем i-го упаковываемого блока, 
;
– объем контейнера, .
Особи популяции кодируются двумя хромосомами (по аналогии с работой [2, с. 77-78]). В первой хромосоме целыми числами задаются индексы i блоков в соответствии с порядком их расположения в наборе исходных данных, передаваемом в алгоритм. Первая хромосома последовательностью генов задает порядок заполнения области упаковки блоками. Во второй хромосоме кодируется ориентация блоков, могущая принимать значения от 1 до 6 (или от 1 до 2 в случае, если на блок наложено ограничение ориентации только вверх) в соответствии с рисунком, на котором указаны возможные варианты ориентации блоков.
Для уплотнения упаковки в соответствии с работой [2, с. 79] используется следующая эвристика для формирования начальной популяции: более крупные блоки удобнее размещать первыми, затем упаковывать меньшие блоки. На основе данного подхода перед формированием начальной популяции все блоки упорядочиваются по следующим параметрам:
а) по убыванию объема;
б) по убыванию длины;
в) по убыванию ширины.
Для того, чтобы хромосома с решением всегда воспроизводила способ укладки блоков в контейнере, используется эвристика для декодирования хромосомы. С этой целью была задействована эвристика «нижней ближайшей точки», используемая в работе [2, с. 77] (см. рисунок и описание ниже).
Согласно ей, блок размещается в точке, где удаление от начала координат минимально, а если есть несколько точек с одинаковым расстоянием, то выбирается первая точка по эвристике «левого нижнего угла», которая будет описана ниже. Для первого блока единственной точкой размещения будет начало координат.
На рисунке
– расстояние блока до точки начала координат, а 
– оптимальная точка, рассчитанная по данной эвристике, 
и 
– альтернативные рассчитанные точки для двух других углов блока (все расстояния в мм).
Сущность эвристики «левого нижнего угла» заключается в следующем. После размещения первого блока из списка возможных положений следующего блока удаляется координата только что размещенного блока (для первого это (0,0,0)) и добавляется набор координат углов этого блока. При размещении следующего блока все возможные точки упорядочиваются по возрастанию координат
, 
, 
и выбирается первая из них, удовлетворяющая математическим ограничениям задачи, указанным выше в пп. 1 — 10.
Проверка условий по выражениям (1) и (2) осуществляется пошагово для каждого вновь вставляемого блока только относительно ранее вставленных блоков. Т.е. проверяется, опирается ли вновь вставляемый блок на дно контейнера или на ранее вставленные блоки.
В качестве метода селекции был взят метод рулетки, применяемый, например, в работе [3]. Идея метода колеса рулетки заключается в том, что для каждой особи выделяется некий сектор колеса рулетки, размер которого пропорционален значению целевой функции. Чем больше значение целевой функции, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений целевых функций всех хромосом рассматриваемой популяции. Затем случайным образом выбирается некоторое число. В результате селекции выигрывает та особь, чей сектор содержит данное число [3].
К особи, хромосомы которой не позволяют упаковать блоки в соответствии с заданными ограничениями, применяется метод смертельных штрафов, упоминаемый, например, в [6], и ее целевая функция принимает значение 0.
Хромосомы родительских пар, отобранных в результате селекции, подвергаются последовательному воздействию операторов кроссинговера и мутации.
Первая хромосома подвергается одноточечному кроссинговеру, модифицированному согласно работе [3].
Идея метода одноточечного кроссинговера заключается в том, что выбираются две особи-родителя. Затем случайным образом выбирается место для разрыва между двумя позициями генов в обеих хромосомах – точка скрещивания. В результате скрещивания пары особей-родителей получаются два потомка, хромосомы каждого из которых состоят из части хромосом одного из родителей до точки скрещивания включительно и части хромосомы другого родителя после точки скрещивания. Необходимость модификации оператора кроссинговера основана на том, что при использовании стандартных операторов могли бы получиться приоритетные списки, содержащие по несколько одинаковых блоков, что противоречит условиям задачи. Поэтому во вторую часть первого потомка дописываются недостающие номера блоков (гены) в том порядке, в каком они встречаются во втором родителе. Аналогично получается и второй потомок. В результате работы оператора скрещивания в новой популяции остаются оба потомка [3].
Вторая хромосома подвергается стандартному одноточечному кроссинговеру без использования модификаций.
Оператор мутации для первой хромосомы аналогичен оператору в работе [3]. Случайно выбранный ген перемещается на начальную позицию в хромосоме.
Оператор мутации для второй хромосомы аналогичен оператору в работе [2, с. 79]. В хромосоме меняются местами два случайно выбранных гена.
Перейдем теперь к изложению других особенностей поиска решения, используемого в данной работе.
Поиск наилучшей компоновки основан не только на упаковке блоков в определенной последовательности и с определенной ориентацией, но и на переборе различных сочетаний габаритов контейнера. Для этого предварительно вычисляется так называемая условная длина стороны, задаваемая в мм.
где
– коэффициент, учитывающий приблизительное соотношение объема контейнера, получаемое с помощью генетического алгоритма, и минимально возможный объем, определяемый суммой объемов блоков.
Далее организуется два цикла, один из которых вложен в другой. В этих циклах вычисляются сочетания сторон контейнера, лежащие в определенном диапазоне.
Стороны вычисляются по следующим выражениям (8) и (9).
где
– вспомогательный множитель для 
;
– начальное значение вспомогательного множителя для ;
– конечное значение вспомогательного множителя для .
где
– вспомогательный множитель для 
;
– начальное значение вспомогательного множителя для ;
– конечное значение вспомогательного множителя для .
Вычисление стороны H опционально и зависит от выбранного варианта алгоритма. Для варианта 1 алгоритма (см. выше п. 5) она вычисляется по следующему выражению:
где
– вспомогательный множитель для 
.
Предполагается, что значения вспомогательных множителей, , , , могут быть подобраны экспериментально и исходя из ряда соображений, на основе опыта вычисления алгоритмом целевых функций, значений получившегося объема для заданного соотношения сторон контейнера, конструктивных соображений и др.
Пример кода на С++, иллюстрирующий расчеты, приведен ниже:
Значение переменной int_H_tmp из программного кода далее записывается в переменную, характеризующую сторону H контейнера.
Для каждого сочетания сторон контейнера происходит выполнение генетического алгоритма. Чтобы сократить время на циклы перебора, для варианта 1 алгоритма происходит проверка определенного условия. Для этого предварительно вычисляется значение теоретически достижимой целевой функции по следующему выражению:
Следует отметить, что данное выражение похоже на выражение для вычисления целевой функции алгоритма, однако при вычислении реальной целевой функции после компоновки происходит после корректировки высоты H, которая определяется по максимальной координате
(i = 0, 1, …, n-1) среди всех блоков.
Условие проверки задается следующим выражением:
где
– коэффициент теоретической целевой функции;
– коэффициент сравнения с максимальной целевой функцией;
– максимальное значение целевой функции, достигнутое на итерациях алгоритма.
Коэффициент определяется экспериментально исходя из практически получаемых значений целевых функций для заданного набора данных (т.е. если теоретическая целевая функция меньше какой-то величины, то предполагается, что нет смысла запускать для нее вычисления генетического алгоритма, т.к. упаковка будет неплотной, и в контейнере будет много пустого объема).
Предназначение коэффициента – учитывать, что теоретическая целевая функция может быть меньше реальной, которая вычисляется с учетом изменения переменной путем ее подгонки под реальные габариты компоновки (см. выше). Если теоретическая целевая функция слишком «маленькая», то она не сможет «подрасти» за счет подгонки и превысить . Это означает, что выражение (12) будет принимать значение истины.
Если выражение (12) принимает логическое значение истины, то переходим к следующей итерации цикла, не выполняя операторы генетического алгоритма.
Пример программного кода на С++, иллюстрирующий вычисления выражения (12) представлен ниже:
Для варианта 2 алгоритма (см. также п. 5 выше) для сокращения времени работы алгоритма проверяется другое выражение:
где
– максимальная целевая функция для первоначальной популяции;
– переменная, учитывающая возрастание целевой функции при выполнении генетического алгоритма.
Смысл этого выражения заключается в том, что если слишком «маленькая», то условие выполнится, а генетический алгоритм не сможет увеличить больше максимальной целевой функции, достигнутой на итерациях. Таким образом, если выражение (13) истинно, то необходимо перейти к следующей итерации, пропустив дальнейшие операторы генетического алгоритма.
Перейдем теперь к описанию результатов практической реализации рассмотренного алгоритма. Для реализации алгоритма был разработан прототип приложения в виде консольной программы на С++.
Результаты компоновки упаковки данное приложение передает в программу моделирования упаковки, рассмотренную в моей предыдущей статье [4].
В качестве набора тестовых исходных данных для числа блоков 5, 10, 15 и 20 были для каждого количества блоков сгенерированы 5 наборов данных, в которых случайным образом были указаны ограничения на ориентацию блоков только вверх.
Перед запуском для алгоритма были заданы некоторые его параметры. Численные значения переменных, , , , , , задавались согласно примерам программного кода, приведенным выше. Переменная принималась равной 1,5.
Одним из параметров алгоритма, который также следует настраивать, является размер популяции. В источнике [7, с. 37] упоминается, что оптимальный размер популяции – 20-30 особей, однако в некоторых задачах может потребоваться 50-100 особей.
Для варианта 2 алгоритма я попробовал несколько раз запустить алгоритм с размером популяции в 30 особей для одного и того же сочетания сторон контейнера. Но вследствие использования метода смертельных штрафов и особенностей решаемой задачи подходящая популяция генерировалась не всегда. Ситуация изменилась при размере популяции в 100 особей. Таким образом, можно сделать вывод, что с размером популяции надо экспериментировать, чтобы алгоритм не пропускал подходящие решения.
Аналогичная ситуация была для алгоритма с, соизмеримой с и . Тут пришлось задавать нетипичный размер популяции в 5000 особей, чтобы алгоритм искал решения для всех сочетаний сторон. Размер популяции в 100 особей при нескольких попытках запуска не позволял сгенерировать подходящую популяцию. И тут можно сделать аналогичный вывод, что с размером популяции надо экспериментировать.
Еще одним параметром алгоритма является число его итераций. Из-за применения метода смертельных штрафов и особенностей решаемой задачи наблюдался эффект постепенного уменьшения числа особей с ненулевой целевой функцией. Для варианта 1 алгоритма популяцию с хотя бы одним индивидом с ненулевой целевой функцией не удавалось получить приблизительно к 30-й итерации.
Что же касается того, что вносило ли такое применение генетических алгоритмов вклад в увеличение целевой функции по сравнению со случайно сгенерированной популяцией, то здесь можно ответить, что вносило. Для варианта 1 алгоритма для одного из наборов исходных данных (количество блоков равно 20) были зафиксированы размеры сторон, которые удалось ранее вычислить для максимального значения целевой функции. Далее был запущен алгоритм для данного сочетания сторон. Удалось увидеть, что алгоритм увеличивал значение целевой функции первоначальной популяции на 3% от объема контейнера (при измерении целевой функции в процентах). Для варианта 2 алгоритма для одного из примеров удалось увидеть прирост целевой функции на 10% от объема контейнера.
В конечном итоге, для тестовых примеров оба варианта алгоритма были запущены с настройками, представленными далее на рисунках. На первом рисунке показаны настройки для варианта 1 алгоритма.
На втором рисунке показаны настройки для варианта 2 алгоритма.
В результате запусков приложения для 5 наборов исходных данных для каждого из нескольких вариантов количества блоков были получены целевые функции, усредненные значения которых будут приведены ниже в таблице в конце статьи.
Пример компоновки, полученной для варианта 1 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Для варианта 2 алгоритма пример компоновки для того же набора исходных данных показан на рисунке ниже.
UPD
Таким образом, с помощью рассмотренных двух вариантов алгоритмов оказалось возможным получить решение. Следующим этапом работы над материалом стала попытка отказаться от метода смертельных штрафов и использовать методы генетического алгоритма, решающего задачу о ранце (см. [2], с. 73). Условие останова для такого генетического алгоритма — получение решения, в котором все блоки могут быть упакованы в заданный контейнер. Методы кодирования хромосом, эвристика предварительной сортировки блоков, эвристика декодирования, методы селекции, кроссинговера и мутации остались теми же, их описание можно посмотреть выше. Настройки генетического алгоритма остались теми же (кроме числа особей в популяции и числа итераций), поменялась только вероятность кроссинговера обеих хромосом, принятая равной 0,8. Еще одним отличием новых вариантов алгоритма стал перебор по всем трем сторонам контейнера. Для
из формулы (7), равного 1, были организованы циклы перебора по трем переменным, пример которых представлен ниже в виде кода.
Целевая функция вычислялась по изначально заданным сторонам контейнера, без подгонки к получившимся габаратам компоновки.
Для того же набора исходных данных, характеризующих упаковываемые блоки, был запущен генетический алгоритм с двумя вариантами настроек: число особей, равное 30, число итераций, равное 150 — первый вариант настроек (вариант 3 алгоритма); число особей, равное 2500, число итераций, равное 0 — второй вариант настроек (вариант 4 алгоритма).
Сочетания сторон контейнера, полученные с помощью циклов, приведенных выше, были отсортированы по убыванию возможной целевой функции, а поиск решения в дальнейшем велся по полученному списку с сочетаниями сторон, начиная от возможной целевой функции, равной 0,9.
Пример компоновки, полученной для варианта 3 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Пример компоновки, полученной для варианта 4 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Ориентировочное время поиска решения при запуске первых двух вариантов алгоритма составило ориентировочно 3 минуты, при запуске двух других вариантов алгоритма с перебором по трем сторонам контейнера — 25-50 минут (ориентировочные характеристики компьютера: процессор Intel® Core(TM) i5-9400F CPU 2.90GHz, 8 ГБ ОЗУ). Время для двух последних вариантов генетического алгоритма можно уменьшить за счет сокращения числа особей в популяции и числа итераций генетического алгоритма, но при этом можно пропуситить более оптимальное решение.
Результаты вычисления целевой функции для всех четырех вариантов алгоритма представлены в таблице ниже.
В заключение отметим, в результате работы на языке C++ был разработан прототип приложения, предназначенного для выполнения компоновки упаковываемых изделий. Приложение позволяет автоматизировать компоновку изделий с приблизительно равными значениями сторон.
Также представляется возможным при некоторой модификации алгоритма не только проектировать новые контейнеры (ящики), но и автоматически подбирать наиболее подходящие по габаритам среди имеющихся. Особенно эффективно это может быть для предприятий, где используются ряды типоразмеров ящиков, например, по ОСТ 4Г О.417.205-81 «Ящики дощатые для изделий радиотехники и средств связи. Технические условия».
Задача, включающая оптимизацию размещения не только блоков в контейнерах, но и контейнеров (ящиков) внутри транспортных средств осталась за рамками данной статьи. Представляется, что эта задача потребует значительно более сложной логики и математического аппарата.
Представляется целесообразным в дальнейшем в первую очередь рассмотреть работу алгоритма с набором блоков с другими сочетаниями сторон, а также поэкспериментировать с реальными наборами упаковываемых изделий. Также для приближения алгоритма к реальным конструктивным требованиям представляется целесообразным учесть ограничения на наружные габариты ящиков, суммарную массу упаковываемых изделий, запрет на штабелирование изделий и др. Для развития направления оптимизации упаковки в пределах одного контейнера можно экспериментировать с коэффициентами и множителями алгоритма, размерами популяции, вероятностями мутации и кроссинговера, использовать альтернативные операторы и методы из обширной теории генетических алгоритмов.
Такого рода компоновка может выполняться вручную с использованием 3D-моделирования (возможны также другие способы с последующим построением результата на двумерном чертеже вручную). И если таких упаковываемых изделий наберется, например, 20, то ручная компоновка становится достаточно трудоемкой.
Вместе с тем, решение похожих задач рассматривается в различных работах и публикациях, и в качестве одного из методов для их решения используются разнообразные вариации генетических алгоритмов, позволяющие не только скомпоновать, но и оптимизировать компоновку.
Из этого возникла идея самостоятельно разработать приложение для компоновки под свою специфику, попробовав использовать при этом генетические алгоритмы. Что из этого получилось – будет рассказано дальше в статье.
Перейдем к более подробному описанию условий задачи.
UPD
В процессе дальнейшего изучения и работы над материалами по тематике статьи были получены новые результаты, которые, по мнению автора, было бы целесообразно включить в текст статьи в качестве дополнений или в форме корректировки ее текста. По этой причине текст статьи был дополнен.
Конец блока UPD
Продолжим далее изложение материалов статьи.
Предполагается, что упаковываемые изделия помещены в коробки, но не исключается в дальнейшем для расширения сферы применения работы рассматривать и прочие изделия в виде прямоугольных параллелепипедов. Коробки с изделиями помещаются в контейнер (фактически в ящик со съемной крышкой). Дополнительная фиксация осуществляется с помощью прокладок из картона и пенопласта. Другим вариантом размещения, с которым я сталкивался, является применение разборных ящиков со съемными дном и крышкой, крепящихся к стенкам ящика с помощью болтов. Коробки с изделиями укладываются на специализированные (нестандартные) поддоны, крепятся к поддонам с помощью лент (другой вариант, который можно использовать – это фиксация коробок стрейч-пленкой). Поддоны с изделиями помещаются внутрь разборных ящиков.
Условия размещения коробок (далее блоков) внутри контейнера (без учета пространства, занимаемого поддоном) задаются рядом математических ограничений, перечисленных ниже.
1. Имеется множество n размещаемых блоков, i = 0, 1, …, n-1. Каждый i-й блок характеризуют три размера по осям x, y и z:
, и соответственно (размеры задаются в мм). Размеры по осям заданы для ориентации 1 блока (см. рисунок ниже) [1]. Всего, согласно данному рисунку, может быть шесть вариантов ориентации.
2. На любой из блоков может быть наложено дополнительное ограничение в виде ориентации только вверх. При этом допустимы только варианты ориентации 1 и 2 согласно рисунку выше.
3. Каждый упакованный блок характеризуется координатами двух точек (координаты здесь и далее указываются в мм), где точка 1 – точка, самая близкая к началу координат, точка 2 – наиболее удаленная от начала координат:
и . Таким образом, решение задачи имеет вид .4. Каждый i-й блок лежит на дне контейнера или на верхней части одного или нескольких блоков. Для формулировки данного условия введены следующие построения.
Каждый i-й блок характеризуется четырьмя точками на нижней грани:
, (j = 1, 2, 3, 4). Точка с индексом j = 1 совпадает с точкой 1 по п. 3, далее нумерация идет по часовой стрелке.Каждый k-й (k = 0, 1, …, n-1) блок характеризуются координатами двух точек, задающих верхнюю грань, на которую могут опираться другие блоки. Индексы i и k у каждого отдельно взятого блока совпадают. Точка 1 – точка, самая близкая к началу координат, точка 2 – наиболее удаленная от начала координат:
и .Условие наличия опоры для i-го блока проверяется по выполнению выражения (1) либо выражения (2):
5. Контейнер ограничивается размерами W, L и H (задаваемыми в мм) по осям x, y и z соответственно. В статье рассматриваются два варианта. Либо H принимает значение, соизмеримое с W и L (похожая ситуация рассматривается в работе [2, с. 74]) – вариант 1 алгоритма, либо H является теоретически неограниченной высотой, вычисляемой как сумма наибольших размеров блоков, что основывается на публикации [3] – вариант 2 алгоритма.
UPD
Также будут рассмотрены варианты, когда H соизмерима с двумя другими сторонами контейнера и выбирается по тем же принципам, что и размеры этих двух сторон.
6. Ни один блок не выходит за границы заданного объема:
7. Суммарный объем блоков не превышает объема контейнера:
8. Блоки не налагаются друг на друга в объеме.
Здесь хотелось бы отметить, что в различных источниках могут встречаться различные выражения для описания условия проверки пересечения параллелепипедов. На отработке этой проверки моя работа при отладке приложения застопорилась, и только поиск выражений в различных источниках, общение с некоторыми разработчиками приложений-аналогов и написание специализированной программы для отладки помогло прийти к решению. Приложение для отладки сравнивало проверку пересечения методом перебора и методом сравнения по одному из представленных в различных источниках выражений. В качестве исходных данных для проверки использовались случайно сгенерированные пары параллелепипедов, размещаемые по случайным координатам в ограниченном объеме. Результаты размещения параллелепипедов можно было визуализировать в приложении, описанном в моей предыдущей статье [4]. В конечном итоге удалось убедиться на основе большого количества испытаний в работоспособности выражения, взятого в источнике [5] и модифицированного под свою задачу (условия больше и меньше были заменены на больше или равно и меньше или равно). В этом выражении число выполняемых проверок минимально.
Итак, условие отсутствия пересечений двух параллелепипедов задается логической истинностью выражения для координат точек 1 и 2 согласно п. 3:
Предполагаю, что, например, в математическом аппарате для игр с трехмерной графикой есть соответствующие теоретические положения, доказывающие корректность данного выражения.
UPD
Что в дальнейшем и подтвердилось работой [8].
9. Блоки располагаются параллельно стенкам контейнера.
10. Все блоки должны быть упакованы в заданный контейнер.
После описания математических ограничений задачи перейдем теперь к описанию способа подготовки исходных данных для реализации работы алгоритма.
Следует отметить, что, судя по литературе, для сравнения эффективности алгоритмов трехмерной упаковки существуют эталонные наборы тестовых примеров (см., например, [2, с. 115]). Не исключено, что в дальнейшем будет изучено данное направление, но предварительно на данном этапе была предпринята попытка сгенерировать тестовые примеры самостоятельно с возможностью их адаптации под условия конкретных задач в организации.
Для генерации наборов тестовых примеров было написано консольное приложение на C++. Приведем содержание файла исходных настроек для работы приложения (см. рисунок ниже).
Число блоков (коробок) может варьироваться (см. строку 2 на рисунке выше) Предполагается, что с определенной вероятностью коробки могут упаковываться группами с определенным числом коробок в группе (см. строки 4, 2 и 8 на рисунке выше). Блоки могут с определенной вероятностью быть ориентированы вверх (см. строку 28). Может с определенной вероятностью генерироваться коробка со случайным соотношением сторон (строки 10, 30, 32). Длина стороны по случайно выбранной координате (строки 24 и 26) домножается на множители, лежащие в определенном диапазоне (строки 12, 14, 16, 18, 20 и 22).
Теперь, когда мы описали исходные данные для задачи трехмерной компоновки, перейдем к методам ее решения.
При решении задачи изначально предполагалось, что возможно разработать генетический алгоритм, подходящий для данных условий и позволяющий оптимизировать упаковку применительно к минимизации занимаемого объема. Перечислим основные характеристики данного алгоритма.
В качестве целевой функции генетического алгоритма была взята плотность упаковки:
где
– объем i-го упаковываемого блока, ; – объем контейнера, .Особи популяции кодируются двумя хромосомами (по аналогии с работой [2, с. 77-78]). В первой хромосоме целыми числами задаются индексы i блоков в соответствии с порядком их расположения в наборе исходных данных, передаваемом в алгоритм. Первая хромосома последовательностью генов задает порядок заполнения области упаковки блоками. Во второй хромосоме кодируется ориентация блоков, могущая принимать значения от 1 до 6 (или от 1 до 2 в случае, если на блок наложено ограничение ориентации только вверх) в соответствии с рисунком, на котором указаны возможные варианты ориентации блоков.
Для уплотнения упаковки в соответствии с работой [2, с. 79] используется следующая эвристика для формирования начальной популяции: более крупные блоки удобнее размещать первыми, затем упаковывать меньшие блоки. На основе данного подхода перед формированием начальной популяции все блоки упорядочиваются по следующим параметрам:
а) по убыванию объема;
б) по убыванию длины;
в) по убыванию ширины.
Для того, чтобы хромосома с решением всегда воспроизводила способ укладки блоков в контейнере, используется эвристика для декодирования хромосомы. С этой целью была задействована эвристика «нижней ближайшей точки», используемая в работе [2, с. 77] (см. рисунок и описание ниже).
Согласно ей, блок размещается в точке, где удаление от начала координат минимально, а если есть несколько точек с одинаковым расстоянием, то выбирается первая точка по эвристике «левого нижнего угла», которая будет описана ниже. Для первого блока единственной точкой размещения будет начало координат.
На рисунке
– расстояние блока до точки начала координат, а – оптимальная точка, рассчитанная по данной эвристике, и – альтернативные рассчитанные точки для двух других углов блока (все расстояния в мм).Сущность эвристики «левого нижнего угла» заключается в следующем. После размещения первого блока из списка возможных положений следующего блока удаляется координата только что размещенного блока (для первого это (0,0,0)) и добавляется набор координат углов этого блока. При размещении следующего блока все возможные точки упорядочиваются по возрастанию координат
, , и выбирается первая из них, удовлетворяющая математическим ограничениям задачи, указанным выше в пп. 1 — 10.Проверка условий по выражениям (1) и (2) осуществляется пошагово для каждого вновь вставляемого блока только относительно ранее вставленных блоков. Т.е. проверяется, опирается ли вновь вставляемый блок на дно контейнера или на ранее вставленные блоки.
В качестве метода селекции был взят метод рулетки, применяемый, например, в работе [3]. Идея метода колеса рулетки заключается в том, что для каждой особи выделяется некий сектор колеса рулетки, размер которого пропорционален значению целевой функции. Чем больше значение целевой функции, тем больше сектор на колесе рулетки. Все колесо рулетки соответствует сумме значений целевых функций всех хромосом рассматриваемой популяции. Затем случайным образом выбирается некоторое число. В результате селекции выигрывает та особь, чей сектор содержит данное число [3].
К особи, хромосомы которой не позволяют упаковать блоки в соответствии с заданными ограничениями, применяется метод смертельных штрафов, упоминаемый, например, в [6], и ее целевая функция принимает значение 0.
Хромосомы родительских пар, отобранных в результате селекции, подвергаются последовательному воздействию операторов кроссинговера и мутации.
Первая хромосома подвергается одноточечному кроссинговеру, модифицированному согласно работе [3].
Идея метода одноточечного кроссинговера заключается в том, что выбираются две особи-родителя. Затем случайным образом выбирается место для разрыва между двумя позициями генов в обеих хромосомах – точка скрещивания. В результате скрещивания пары особей-родителей получаются два потомка, хромосомы каждого из которых состоят из части хромосом одного из родителей до точки скрещивания включительно и части хромосомы другого родителя после точки скрещивания. Необходимость модификации оператора кроссинговера основана на том, что при использовании стандартных операторов могли бы получиться приоритетные списки, содержащие по несколько одинаковых блоков, что противоречит условиям задачи. Поэтому во вторую часть первого потомка дописываются недостающие номера блоков (гены) в том порядке, в каком они встречаются во втором родителе. Аналогично получается и второй потомок. В результате работы оператора скрещивания в новой популяции остаются оба потомка [3].
Вторая хромосома подвергается стандартному одноточечному кроссинговеру без использования модификаций.
Оператор мутации для первой хромосомы аналогичен оператору в работе [3]. Случайно выбранный ген перемещается на начальную позицию в хромосоме.
Оператор мутации для второй хромосомы аналогичен оператору в работе [2, с. 79]. В хромосоме меняются местами два случайно выбранных гена.
Перейдем теперь к изложению других особенностей поиска решения, используемого в данной работе.
Поиск наилучшей компоновки основан не только на упаковке блоков в определенной последовательности и с определенной ориентацией, но и на переборе различных сочетаний габаритов контейнера. Для этого предварительно вычисляется так называемая условная длина стороны, задаваемая в мм.
![$l_0=\sqrt[3]{v_0\cdot \sum\limits_{i=0}^{n-1}V_i},\quad (7)$](https://habrastorage.org/getpro/habr/formulas/049/ed3/ad9/049ed3ad90d7519e769dc3b9c80e9319.svg)
где
– коэффициент, учитывающий приблизительное соотношение объема контейнера, получаемое с помощью генетического алгоритма, и минимально возможный объем, определяемый суммой объемов блоков.Далее организуется два цикла, один из которых вложен в другой. В этих циклах вычисляются сочетания сторон контейнера, лежащие в определенном диапазоне.
Стороны вычисляются по следующим выражениям (8) и (9).
где
– вспомогательный множитель для ; – начальное значение вспомогательного множителя для ; – конечное значение вспомогательного множителя для .
где
– вспомогательный множитель для ; – начальное значение вспомогательного множителя для ; – конечное значение вспомогательного множителя для .Вычисление стороны H опционально и зависит от выбранного варианта алгоритма. Для варианта 1 алгоритма (см. выше п. 5) она вычисляется по следующему выражению:
где
– вспомогательный множитель для .Предполагается, что значения вспомогательных множителей
, , , , могут быть подобраны экспериментально и исходя из ряда соображений, на основе опыта вычисления алгоритмом целевых функций, значений получившегося объема для заданного соотношения сторон контейнера, конструктивных соображений и др.Пример кода на С++, иллюстрирующий расчеты, приведен ниже:
//Вычислим условную длину стороны, мм
int_l0 = pow(2*dbl_V_box_sum, 1.0 / 3.0);
//Переберем все возможные сочетания сторон контейнера (ящика)
for (double W0 = 0.4; W0 < 2; W0 += 0.1) //Перебираем множитель по оси Х
{
for (double L0 = 0.6; L0 < 5; L0 += 0.1) //Перебираем множитель по оси Y
{
//Вычислим размеры сторон контейнера, мм
int_W = int_l0 * W0;
int_L = int_l0 * L0;
int_H_tmp = 0.9 * min(int_W, int_L);
}
}
Значение переменной int_H_tmp из программного кода далее записывается в переменную, характеризующую сторону H контейнера.
Для каждого сочетания сторон контейнера происходит выполнение генетического алгоритма. Чтобы сократить время на циклы перебора, для варианта 1 алгоритма происходит проверка определенного условия. Для этого предварительно вычисляется значение теоретически достижимой целевой функции по следующему выражению:
Следует отметить, что данное выражение похоже на выражение для вычисления целевой функции алгоритма, однако при вычислении реальной целевой функции после компоновки происходит после корректировки высоты H, которая определяется по максимальной координате
(i = 0, 1, …, n-1) среди всех блоков.Условие проверки задается следующим выражением:
где
– коэффициент теоретической целевой функции; – коэффициент сравнения с максимальной целевой функцией; – максимальное значение целевой функции, достигнутое на итерациях алгоритма.Коэффициент
определяется экспериментально исходя из практически получаемых значений целевых функций для заданного набора данных (т.е. если теоретическая целевая функция меньше какой-то величины, то предполагается, что нет смысла запускать для нее вычисления генетического алгоритма, т.к. упаковка будет неплотной, и в контейнере будет много пустого объема).Предназначение коэффициента
– учитывать, что теоретическая целевая функция может быть меньше реальной, которая вычисляется с учетом изменения переменной путем ее подгонки под реальные габариты компоновки (см. выше). Если теоретическая целевая функция слишком «маленькая», то она не сможет «подрасти» за счет подгонки и превысить . Это означает, что выражение (12) будет принимать значение истины.Если выражение (12) принимает логическое значение истины, то переходим к следующей итерации цикла, не выполняя операторы генетического алгоритма.
Пример программного кода на С++, иллюстрирующий вычисления выражения (12) представлен ниже:
//Получившийся объем слишком "большой"
if (1/ dbl_F_theor > 2.5|| 1 / dbl_F_theor <1 ||
dbl_F_theor*1.1 < dbl_Objective_function_max_in_iterations)
{
cout << "\nПолучившийся объем ящика слишком \"большой\", либо меньше " <<
"суммарного объема коробок, либо больше объема для максимальной " <<
"найденной целевой функции с учетом поправочных коэффициентов";
continue;
}
Для варианта 2 алгоритма (см. также п. 5 выше) для сокращения времени работы алгоритма проверяется другое выражение:
где
– максимальная целевая функция для первоначальной популяции; – переменная, учитывающая возрастание целевой функции при выполнении генетического алгоритма.Смысл этого выражения заключается в том, что если
слишком «маленькая», то условие выполнится, а генетический алгоритм не сможет увеличить больше максимальной целевой функции, достигнутой на итерациях. Таким образом, если выражение (13) истинно, то необходимо перейти к следующей итерации, пропустив дальнейшие операторы генетического алгоритма.Перейдем теперь к описанию результатов практической реализации рассмотренного алгоритма. Для реализации алгоритма был разработан прототип приложения в виде консольной программы на С++.
Результаты компоновки упаковки данное приложение передает в программу моделирования упаковки, рассмотренную в моей предыдущей статье [4].
В качестве набора тестовых исходных данных для числа блоков 5, 10, 15 и 20 были для каждого количества блоков сгенерированы 5 наборов данных, в которых случайным образом были указаны ограничения на ориентацию блоков только вверх.
Перед запуском для алгоритма были заданы некоторые его параметры. Численные значения переменных
, , , , , , задавались согласно примерам программного кода, приведенным выше. Переменная принималась равной 1,5.Одним из параметров алгоритма, который также следует настраивать, является размер популяции. В источнике [7, с. 37] упоминается, что оптимальный размер популяции – 20-30 особей, однако в некоторых задачах может потребоваться 50-100 особей.
Для варианта 2 алгоритма я попробовал несколько раз запустить алгоритм с размером популяции в 30 особей для одного и того же сочетания сторон контейнера. Но вследствие использования метода смертельных штрафов и особенностей решаемой задачи подходящая популяция генерировалась не всегда. Ситуация изменилась при размере популяции в 100 особей. Таким образом, можно сделать вывод, что с размером популяции надо экспериментировать, чтобы алгоритм не пропускал подходящие решения.
Аналогичная ситуация была для алгоритма с
, соизмеримой с и . Тут пришлось задавать нетипичный размер популяции в 5000 особей, чтобы алгоритм искал решения для всех сочетаний сторон. Размер популяции в 100 особей при нескольких попытках запуска не позволял сгенерировать подходящую популяцию. И тут можно сделать аналогичный вывод, что с размером популяции надо экспериментировать.Еще одним параметром алгоритма является число его итераций. Из-за применения метода смертельных штрафов и особенностей решаемой задачи наблюдался эффект постепенного уменьшения числа особей с ненулевой целевой функцией. Для варианта 1 алгоритма популяцию с хотя бы одним индивидом с ненулевой целевой функцией не удавалось получить приблизительно к 30-й итерации.
Что же касается того, что вносило ли такое применение генетических алгоритмов вклад в увеличение целевой функции по сравнению со случайно сгенерированной популяцией, то здесь можно ответить, что вносило. Для варианта 1 алгоритма для одного из наборов исходных данных (количество блоков равно 20) были зафиксированы размеры сторон, которые удалось ранее вычислить для максимального значения целевой функции. Далее был запущен алгоритм для данного сочетания сторон. Удалось увидеть, что алгоритм увеличивал значение целевой функции первоначальной популяции на 3% от объема контейнера (при измерении целевой функции в процентах). Для варианта 2 алгоритма для одного из примеров удалось увидеть прирост целевой функции на 10% от объема контейнера.
В конечном итоге, для тестовых примеров оба варианта алгоритма были запущены с настройками, представленными далее на рисунках. На первом рисунке показаны настройки для варианта 1 алгоритма.
На втором рисунке показаны настройки для варианта 2 алгоритма.
В результате запусков приложения для 5 наборов исходных данных для каждого из нескольких вариантов количества блоков были получены целевые функции, усредненные значения которых будут приведены ниже в таблице в конце статьи.
Пример компоновки, полученной для варианта 1 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Для варианта 2 алгоритма пример компоновки для того же набора исходных данных показан на рисунке ниже.
UPD
Таким образом, с помощью рассмотренных двух вариантов алгоритмов оказалось возможным получить решение. Следующим этапом работы над материалом стала попытка отказаться от метода смертельных штрафов и использовать методы генетического алгоритма, решающего задачу о ранце (см. [2], с. 73). Условие останова для такого генетического алгоритма — получение решения, в котором все блоки могут быть упакованы в заданный контейнер. Методы кодирования хромосом, эвристика предварительной сортировки блоков, эвристика декодирования, методы селекции, кроссинговера и мутации остались теми же, их описание можно посмотреть выше. Настройки генетического алгоритма остались теми же (кроме числа особей в популяции и числа итераций), поменялась только вероятность кроссинговера обеих хромосом, принятая равной 0,8. Еще одним отличием новых вариантов алгоритма стал перебор по всем трем сторонам контейнера. Для
из формулы (7), равного 1, были организованы циклы перебора по трем переменным, пример которых представлен ниже в виде кода. for (double W0 = 0.3; W0 <= 2.5; W0 += 0.1) //Перебираем множитель по оси Х
for (double L0 = 0.3; L0 <= 5.0; L0 += 0.1) //Перебираем множитель по оси Y
for (double H0 = 0.3; H0 <= 2.5; H0 += 0.1) //Перебираем множитель по оси ZЦелевая функция вычислялась по изначально заданным сторонам контейнера, без подгонки к получившимся габаратам компоновки.
Для того же набора исходных данных, характеризующих упаковываемые блоки, был запущен генетический алгоритм с двумя вариантами настроек: число особей, равное 30, число итераций, равное 150 — первый вариант настроек (вариант 3 алгоритма); число особей, равное 2500, число итераций, равное 0 — второй вариант настроек (вариант 4 алгоритма).
Сочетания сторон контейнера, полученные с помощью циклов, приведенных выше, были отсортированы по убыванию возможной целевой функции, а поиск решения в дальнейшем велся по полученному списку с сочетаниями сторон, начиная от возможной целевой функции, равной 0,9.
Пример компоновки, полученной для варианта 3 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Пример компоновки, полученной для варианта 4 алгоритма (для 20 упаковываемых блоков), показан на рисунке ниже.
Ориентировочное время поиска решения при запуске первых двух вариантов алгоритма составило ориентировочно 3 минуты, при запуске двух других вариантов алгоритма с перебором по трем сторонам контейнера — 25-50 минут (ориентировочные характеристики компьютера: процессор Intel® Core(TM) i5-9400F CPU 2.90GHz, 8 ГБ ОЗУ). Время для двух последних вариантов генетического алгоритма можно уменьшить за счет сокращения числа особей в популяции и числа итераций генетического алгоритма, но при этом можно пропуситить более оптимальное решение.
Результаты вычисления целевой функции для всех четырех вариантов алгоритма представлены в таблице ниже.
В заключение отметим, в результате работы на языке C++ был разработан прототип приложения, предназначенного для выполнения компоновки упаковываемых изделий. Приложение позволяет автоматизировать компоновку изделий с приблизительно равными значениями сторон.
Также представляется возможным при некоторой модификации алгоритма не только проектировать новые контейнеры (ящики), но и автоматически подбирать наиболее подходящие по габаритам среди имеющихся. Особенно эффективно это может быть для предприятий, где используются ряды типоразмеров ящиков, например, по ОСТ 4Г О.417.205-81 «Ящики дощатые для изделий радиотехники и средств связи. Технические условия».
Задача, включающая оптимизацию размещения не только блоков в контейнерах, но и контейнеров (ящиков) внутри транспортных средств осталась за рамками данной статьи. Представляется, что эта задача потребует значительно более сложной логики и математического аппарата.
Представляется целесообразным в дальнейшем в первую очередь рассмотреть работу алгоритма с набором блоков с другими сочетаниями сторон, а также поэкспериментировать с реальными наборами упаковываемых изделий. Также для приближения алгоритма к реальным конструктивным требованиям представляется целесообразным учесть ограничения на наружные габариты ящиков, суммарную массу упаковываемых изделий, запрет на штабелирование изделий и др. Для развития направления оптимизации упаковки в пределах одного контейнера можно экспериментировать с коэффициентами и множителями алгоритма, размерами популяции, вероятностями мутации и кроссинговера, использовать альтернативные операторы и методы из обширной теории генетических алгоритмов.
Библиографический список
- Луцан М.В., Нужнов Е.В. Решение задачи трехмерной упаковки с палетированием контейнеров // Известия ЮФУ. Технические науки .– 2014 .– № 7 (156) .– С. 196-204.
- Луцан М.В. Разработка и исследование методов поддержки и оптимизации информационных процессов в транзитном контейнерном терминале: диссертация… кандидата технических наук: 05.25.05 / Луцан Максим Васильевич; [Место защиты: Юж. федер. ун-т]. — Таганрог, 2014. — 138 с.: ил.
- Тимофеева О.П., Чернышева Т.Ю, Корелин О.Н., Волков А.В. Генетический алгоритм в оптимизации трехмерной упаковки блоков в контейнер // Труды НГТУ им. Р. Е. Алексеева .– 2017 .– №2 (117) .– С. 21-27.
- Моделирование упаковки с использованием API SolidWorks [Электронный ресурс] .– URL: habr.com/ru/company/stc_spb/blog/656439 .– (дата обращения 09.12.2022).
- AABB: Axis-Aligned Bounding Box [Электронный ресурс] .– URL: gamedev.ru/terms/AABB .– (дата обращения 09.12.2022).
- Семенкин Е.С., Сергиенко Р.Б. Коэволюционный генетический алгоритм решения сложных задач условной оптимизации // Сибирский аэрокосмический журнал .– 2009 .– №2 .– С. 17-21.
- Панченко Т.В. Генетические алгоритмы [Текст]: учебно-методическое пособие / под ред. Ю.Ю. Тарасевича .– Астрахань: Издательский дом «Астраханский университет», 2007 .– 87 c.
- Валиахметова, Ю.И. Мультиметодная технология ортогональной упаковки и ее
применение в задачах транспортной логистики / Ю.И. Валиахметова [и др.] //
Информационные технологии. – 2009. – № S12. – С. 1-32.