ISSN 0236-235X (P)
ISSN 2311-2735 (E)

Journal influence

Higher Attestation Commission (VAK) - К1 quartile
Russian Science Citation Index (RSCI)

Bookmark

Next issue

2
Publication date:
16 June 2024

Comparison analysis and task classification according to cargo optimal placement in restricted space

Date of submission article: 09.09.2015
UDC: 004.02
The article was published in issue no. № 4, 2015 [ pp. 58-61 ]
Abstract:The paper is devoted to the problem of objects optimal placement in restricted space. This problem belongs to the class of cutting and packing problems. The paper formulates the common cutting and packing problem. It also describes the approach to such problems classification and criteria, which are the basis of the typology and the main categories of the problems. The scientific researches review shows that similar problems arise in various domains and these problems have various features as a specificity of a problem domain. The authors consider several problems of cargo optimal placement, which have some similarities with the problem of cargo placement on a transport spacecraft. They compare considered problems to the problem of cargo placement on the transport spacecraft according to common characteristics of these problems. Furthermore, each problem under consideration is assigned to one of the classes in terms of the given typology. As a result of a comparison analysis, there is a conclusion that there is no any universal decision method for the optimal placement problem. There are some particular features and restrictions for any real problem, which must be considered. The authors set a task of development of a new method to find the optimal cargo placement. This method must consider any specific features of the problem domain related to spacecrafts.
Аннотация:Работа посвящена проблеме оптимального размещения объектов в ограниченном пространстве. Данная задача относится к классу задач раскроя и упаковки. Дается общая постановка задачи раскроя и упаковки. Описаны подход к классификации задач и критерии, на основе которых строится типология и выделяются основные категории задач. Обзор научных исследований по данной проблеме показывает, что в различных предметных областях возникают похожие задачи, каждая из которых имеет свои особенности, обусловленные спецификой конкретной предметной области. Рассматривается несколько задач по оптимальному расположению грузов, сходных с задачей размещения грузов на борту транспортного грузового корабля. Делается сравнение по основным характеристикам рассмотренных задач с задачей размещения грузов на борту транспортного грузового корабля. Кроме этого, для каждой задачи выявляется класс в рамках рассмотренной типологии, к которому ее можно отнести. В результате сравнительного анализа делается вывод о том, что универсального метода решения задачи оптимального размещения не существует, каждая конкретная практическая задача имеет свои особенности и ограничения, которые необходимо учитывать. Ставится задача разработки нового метода поиска оптимального расположения грузов, учитывающего специфические особенности предметной области, связанной с космическими кораблями.
Authors: Pogorelov A.S. ( pogorelov-alserg@yandex.ru) - Don Branch of the Space Simulator Center (Engineer-Programmer), Novocherkassk, Russia, Andreev D.A. (dimak134@yandex.ru) - Don Branch of the Space Simulator Center (Programmer Engineer), Novocherkassk, Russia, Panfilov A.N. (panfiloff@rambler.ru) - South-Russian State Polytechnical University (Associate Professor), Novocherkassk, Russia, Ph.D
Keywords: spacecraft, center of mass, cutting and packing problem, cargo spacecraft, cargo optimal placement
Page views: 6018
Print version
Full issue in PDF (9.58Mb)
Download the cover in PDF (1.29Мб)

Font size:       Font:

Задача поиска оптимального расположения грузов на борту транспортного грузового корабля (ТГК) исследовалась авторами ранее [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.


Permanent link:
http://swsys.ru/index.php?page=article&id=4069&lang=en
Print version
Full issue in PDF (9.58Mb)
Download the cover in PDF (1.29Мб)
The article was published in issue no. № 4, 2015 [ pp. 58-61 ]

Back to the list of articles