Задача поиска оптимального расположения грузов на борту транспортного грузового корабля (ТГК) исследовалась авторами ранее [1]. В рассматриваемом случае в задаче размещения грузов есть определенные особенности:

–      форма грузов может быть произвольной;

–      множество контейнеров, в которые укладывается груз, конечно;

–      форма грузового отсека сложная и состоит из трех основных частей: нижней полусферы, цилиндрической проставки и верхней полусферы;

–      имеется ограничение по центру масс корабля (после загрузки грузового отсека отклонение центра масс корабля от нормы не должно превышать установленного значения).

Данная задача относится к классу задач раскроя и упаковки, постановка которой в обобщенном виде представлена в работе [2]. Рассмотрим общую постановку задачи упаковки.

Имеются два множества элементов: контейнеров и упаковываемых предметов.

Контейнеры и предметы – это одно-, двух-, трех- или N-мерные геометрические объекты. Соответственно, речь идет об одно-, двух-, трех- или N-мерной задаче упаковки.

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

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

Общую задачу упаковки можно условно разделить на пять подзадач:

–      выбор контейнеров;

–      выбор упаковываемых предметов;

–      группировка выбранных предметов на подмножества;

–      нахождение соответствия между подмножествами предметов и множеством контейнеров;

–      размещение предметов в каждом из выбранных контейнеров с соблюдением геометрических ограничений.

В работе [2] также описывается новый подход к классификации задач раскроя и упаковки. На основе пяти критериев строится типология и выделяются основные категории задач. Это дает возможность систематизации научных исследований по проблеме раскроя и упаковки. Кроме этого, разработанная типология имеет большую практическую значимость: классифицируя конкретную задачу, можно отнести ее к какой-либо категории, что позволяет более подробно изучить ее особенности, связанные с данной категорией, а изучив методы решения задач, относящихся к одной категории, можно выбрать наиболее подходящие аспекты и адаптировать их для решения конкретной поставленной задачи.

Выделяют пять критериев классификации задач раскроя и упаковки [2].

1. Размерность задачи. Задача может быть од- но-, двух-, трех- или N-мерной.

2. Оптимизируемое свойство. Выделяются два случая:

–      объем контейнеров фиксированный; требуется максимизировать суммарный объем размещаемых предметов, то есть разместить в контейнерах максимум предметов;

–      объем размещаемых предметов фиксированный; требуется минимизировать пространство, куда размещаются предметы, то есть разместить все имеющиеся предметы в минимально возможном объеме внутри контейнеров.

3. Вид размещаемых предметов. Выделяют следующие предметы:

–      однородные (предметы одной формы и размеров);

–      слабооднородные (все предметы можно сгруппировать в относительно небольшое число классов, содержащих однородные предметы);

–      неоднородные (среди всего множества предметов есть лишь небольшое число однородных предметов, почти все предметы различны по форме и размерам).

4. Множество контейнеров. Различают задачи с одним контейнером для упаковки и задачи с несколькими контейнерами.

5. Форма размещаемых предметов, которая может быть правильной (прямоугольники, шары, параллелепипеды, цилиндры и т.д.) и неправильной.

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

Описываемую в работе [1] задачу поиска оптимального расположения грузов на борту транспортного грузового корабля можно отнести к промежуточному классу MHLOPP (Multiple hete­rogeneous large object placement problem – задача размещения во множестве неоднородных контейнеров).

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

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

В работах [3, 4] рассматривается действующая программная система packer3d, предназначенная для расчета оптимальной укладки грузов в транспортные средства. В этой системе грузы, как и объем, в который они помещаются, имеют форму параллелепипеда с заданными размерами. Требуется рассчитать точное положение ящиков в заданном объеме таким образом, чтобы его заполнение грузом было допустимым и наиболее эффективным по объему, то есть суммарный объем поместившихся ящиков должен быть максимальным из всех возможных. Кроме этого, алгоритм, описываемый в работе, позволяет учитывать такие дополнительные ограничения, как грузоподъемность, максимальное давление на верхнюю грань ящика, сбалансированность давления на оси транспортного средства [3].

По классификации из работы [2] данную задачу можно отнести к промежуточному классу SLOPP (Single large object placement problem – задача размещения в одном контейнере).

Алгоритм packer3d основан на сведении трехмерной задачи упаковки к двухмерной и включает в себя следующие части:

–      алгоритм комбинирования предметов;

–      алгоритм трехмерной задачи (сведение к двухмерной);

–      выбор области укладки для трехмерного алгоритма;

–      алгоритм двухмерной укладки.

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

В работах [5, 6] рассматривается математическая четырехмерная модель размещения груза в трюмах судна. Эта модель, как и система packer3d, оперирует с грузами и контейнерами (в данном случае трюмами), описываемыми в форме параллелепипеда. Кроме этого, модель способна работать с более чем одним контейнером (трюмом), а также учитывать такие ограничения, как совокупность зон трюмов, запретных для размещения грузов (строительные конструкции, служебные помещения, стационарное оборудование, дороги и т.д.), зазор между соседними грузовыми объектами [6].

По классификации из работы [2] данную задачу можно отнести к промежуточному классу MILOPP (Multiple identical large object placement problem – задача размещения во множестве однородных контейнеров).

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

В работе [7] предлагаются математическая модель и метод решения 3D-задачи оптимальной упаковки цилиндров и параллелепипедов в параболический контейнер с круговыми стеллажами с учетом минимально допустимых расстояний и ограничений поведения механической системы (динамическое равновесие, моменты инерции, устойчивость). При этом задача состоит в том, чтобы разместить множество элементов на полках внутри отсеков контейнера с учетом минимально допустимых расстояний и ограничений поведения системы так, чтобы расстояние между центром тяжести множества загруженных элементов и заданным центром тяжести контейнера достигало своего минимального значения.

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

По классификации из работы [2] данную задачу можно отнести к промежуточному классу MHLOPP (Multiple heterogeneous large object placement problem – задача размещения во множестве неоднородных контейнеров).

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

В работе [9] рассматривается задача упаковки грузов в заданном объеме на примере их упаковки в самолет с известным центром тяжести. Для обеспечения нормального маневра самолета грузы необходимо уложить в имеющийся в самолете контейнер так, чтобы отклонение от известного центра тяжести самолета было минимальным.

По классификации из работы [2] данную задачу можно отнести к промежуточному классу SLOPP (Single large object placement problem – задача размещения в одном контейнере).

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

В работе [10] рассматривается подход к оптимизации положения центра масс набора блоков. Этот подход является общим и не привязан к какой-либо конкретной предметной области. Особенность его в том, что оптимизация положения центра масс осуществляется для набора уже упакованных грузов, то есть исходным для алгоритма является результат оптимального размещения грузов по какому-либо другому методу упаковки, не учитывающему центр масс. Однако существенным недостатком данного подхода является необходимость низкой плотности первоначальной упаковки грузов, когда объем контейнера превышает суммарный объем всех блоков и остается достаточно места для перемещения.

По классификации из работы [2] данную задачу можно отнести к промежуточному классу SLOPP (Single large object placement problem – задача размещения в одном контейнере).

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

В таблице представлено сравнение по основным характеристикам рассмотренных задач с задачей размещения грузов на борту транспортного грузового корабля. Символ «+» означает совпадение характеристик, символ «–» – отличие задач друг от друга в отношении данной характеристики, символ «±» – частичное совпадение характеристик.

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

Литература

1.     Погорелов А.С., Панфилов А.Н., Андреев Д.А. Задача оптимального размещения грузов на борту транспортного грузового корабля // Инженерный вестн. Дона. 2015. № 3; URL: http://www.ivdon.ru/ru/magazine/archive/n3y2015/3140 (дата обращения: 08.09.2015).

2.     Wäscher G., Haußner H., Schumann H. An improved typology of cutting and packing problems. European Journ. of Operational Research, 2007, no. 183, pp. 1109–1130. 3.     Псиола В.В. О приближенном решении 3-мерной задачи об упаковке на основе эвристик // Интеллектуальные системы. Теория и приложения. 2007. № 1–4. С. 83–100. 4.     Псиола В.В. Оценка качества алгоритма Packer3D (Теория и практика). М.: Изд-во МГУ, 2009. 35 c.

5.     Нырков А.П., Соколов С.С. Эффективное математическое и алгоритмическое обеспечение оперативного размещения груза на транспорте // Наука в жизни современного человека: матер. Междунар. симпоз. 2013. URL: www.sworld.com.ua (дата обращения: 08.09.2015).

6.     Соколов С.С. Математическая модель рационального размещения груза в трюмах судна // Вестн. гос. ун-та морского и речного флота им. адмирала С.О. Макарова. 2010. № 3. С. 89–92. 7.     Коваленко А.А., Панкратов А.В., Романова Т.Е. Размещение объектов в контейнере параболической формы с круговыми стеллажами с учетом ограничений поведения // Журн. выч. и приклад. матем. 2013. № 2. С. 23–32.

8.     Chernov N. Phi-Functions for 2D Objects Formed by Line Segments and Circular Arcs. Advances in Operations Research. 2012. URL: http://dx.doi.org/10.1155/2012/346358 (дата обращения: 08.09.2015).

9.     Остапенко В.В., Соболенко Л.А., Прохорович И.В. Метод обратно-выпуклого программирования и оптимальная упаковка грузов // Системные исслед. и информ. технол. 2004. № 2. С. 95–103. 10.  Карпов К.Э., Яновский В.В. Offline-алгоритм оптимизации центра масс упакованных блоков // Изв. СПб ГЭИ ЛЭТИ. 2007. № 9. С. 10–16.