A COMPLETE SURVEILLANCE ALGORITHM FOR THE PROBLEM OF ONE-DIMENSIONAL PACKING OF OBJECTS WITH A CHANGE IN WEIGHT

АЛГОРИТМ ПОЛНОГО ПЕРЕБОРА ДЛЯ ЗАДАЧИ ОДНОМЕРНОЙ УПАКОВКИ ОБЪЕКТОВ С ИЗМЕНЕНИЕМ ВЕСА

Научная статья

Дворянкин А.М.¹, Жан Макс Хабиб Тапе^2, *

^{1, 2} Волгоградский государственный технический университет, Волгоград, Россия

* Корреспондирующий автор (jeanmax.habib[at]mail.ru)

Аннотация

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

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

Ключевые слова: одномерная упаковка, сила, нагруженные отрезки, алгоритм, упаковка, отклонение от целевого центра тяжести.

A COMPLETE SURVEILLANCE ALGORITHM FOR THE PROBLEM OF ONE-DIMENSIONAL PACKING OF OBJECTS WITH A CHANGE IN WEIGHT

Research article

Dvoryankin A.M.¹, Jean Max Habib Tape^2, *

^{1, 2} Volgograd State Technical University, Volgograd, Russia

* Corresponding author (jeanmax.habib[at]mail.ru)

Abstract

The purpose of the work is to find the optimal placement of one-dimensional objects (segments with a given weight) with a minimum deviation of the center of gravity from a given one and a minimum deviation of the center of gravity of objects, provided that the weight of one given object is zeroed. The paper proposes a formalized formulation of the problem and a search algorithm based on a complete enumeration of the set of all possible solutions. Obviously, this algorithm will find a global solution to the problem, and will serve as a basis for comparing the effectiveness of future approximate algorithms.

A formula is given that determines the possible deviation for the given segments. Examples of the algorithm are given. Based on the results of the work, it is possible to plan the optimal placement of the cargo on the vehicle.

Keywords: one-dimensional packing, force, loaded segments, algorithm, packing, deviation from the target center of gravity.

Введение

Имеются различные постановки и алгоритмы решения задач одномерной оптимальной упаковки (размещения): «задачи о ранце» [1], упаковка одномерных контейнеров [2], представление перестановками решений одномерной задачи упаковки [3], оптимальная загрузка летательного аппарата [4], [5]. Задача одномерной упаковки является задачей комбинаторной оптимизации и относится к классу NP-полных [6].

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

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

Задача упаковки

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

Эта задача возникает при проектировании компоновки самолёта, размещения груза на транспортном средстве, для которого положение центра тяжести является важным.

Модель

Будем использовать обозначения отрезков, понятие соединения отрезков и формулы вычисления центра тяжести соединения отрезков в соответствии с работой [7]. Обозначим A= (a, p, b) - горизонтальный отрезок, где 𝑎 - расстояние от левого края отрезка до точки приложения вертикальной силы p (вес отрезка) , b - расстояние от точки приложения силы до правого края отрезка. Полагаем a > 0, p ≥ 0, b > 0 Обозначим d = a + b длину отрезка. Для обозначения различных отрезков будем использовать нижние индексы в виде букв или цифр: A_y = (a_y, p_y, b_y) или A_i = (a_i, p_i, b_i). Компоненты отрезка A будем также обозначать как a = a(A), p = p(A), b = b(A). Через Соединение отрезков A_x и A_y будем обозначать как A_xy = A_xA_y. При этом A_xy = (a_xy, p_xy, b_xy), где компоненты соединения вычисляются по формулам [7]:

a_xy = a(A_xy) = [p_xa_x + p_y(a_x + b_x + a_y)], p_xy = p(A_xy) = p_x + p_y, b_xy = b(A_xy) = d_x +d_y - a_xy.

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

 Предполагаем, что задано множество отрезков R = {A_i = (a_i, p_i, b_i)}. где

i = 1,2,...,n. Среди этих отрезков выделен один: . Назовем его "груз". Этот груз будет удаляться (сбрасываться), т.е.  через некоторое время будет равно 0. Задано число C – целевой центр тяжести соединения отрезков из множества R. Пусть J_n - множество перестановок чисел 1,2,...,n. Любой перестановке I = (i₁,i₂,...,i_n) ÎJ_n можно сопоставить соединение отрезков:

AI = Ai₁Ai₂... Ai_n. Введем обозначения:

• ЦТ1(AI) - центр тяжести соединения отрезков на перестановке I при условии p_k ≠ 0;
• ЦТ2(AI) - центр тяжести соединения отрезков на перестановке I при условии p_k = 0;
• delta1(AI) = |ЦТ1(AI) С| - отклонение от целевого центра тяжести при

p_k ≠ 0;

• delta2(AI) = |ЦТ2(AI) С| - отклонение от целевого центра тяжести при

p_k = 0;

• delta(AI) = max(delta1(AI), delta2(AI)) – максимальное отклонение центра тяжести соединения отрезков на перестановке I от целевого положения с учётом обнуления веса отрезка с номером k.
• (<перестановка>,<ЦТ1 при P_k <>0>,<delta1=|ЦТ1-С|>,<ЦТ2при P_k=0>,<delta2=|ЦТ2-С|>,<Delta=max(delta1,delta2)>)

Формулировка задачи: найти перестановку T = (t₁,t₂,...,t_n) ÎJ_n , на которой достигается минимальное значение величины delta(AI). 

Алгоритм

Для решения сформулированной задачи предлагается алгоритм полного перебора всех перестановок с ограничением. Т.к. сложность алгоритма O(n!), то практическое его использование рекомендуется для n <= 10.

Обоснование рекомендации. Причина рекомендации - рост n!, который представлен в таблице.

 

Таблица 1 – Рост n!

n	5	8	10	13	15	30
n!	129	40320	3.6*106	6.2*109	1.3*1012	2.7*1032

 

Предполагаем, что n – число отрезков для упаковки. При n=5 расчет всех вариантов можно сделать вручную. При n=8 для расчета может потребоваться программируемый калькулятор. При n=10 потребуется вычислительная техника более высокой производительности. При n=13 суперкомпьютер. При n=15 не справится современные компьютеры. Количество вариантов при n=30 превышает количество атомов на земле.

Считаем, что для сравнительного анализа эффективности будущих приближенных алгоритмов решения этой задачи n=10 будет достаточно.

Шаг 0. Определить значение n – количество отрезков. Инициализация необходимых массивов и ввод исходных данных: множество отрезков R, C - целевой центр тяжести для соединения отрезков, k – номер отрезка, вес которого будет обнуляться. Присвоить переменной w большое значение.

Шаг 1. Генерация очередной перестановки I.

Шаг 2. На перестановке I вычислить центры тяжести соединения отрезков ЦТ1(AI) и ЦТ2(AI), вычислить отклонения delta1(AI), delta2(AI) и delta(AI).

Шаг 3. Выполнить сравнение величин w и delta(AI).

Шаг 4. Если delta(AI) < w, то перейти на шаг 5. Иначе на шаг 6.

Шаг 5. w := delta(AI), запомнить перестановку I (T := I).

Шаг 6. Если I – НЕ последняя перестановка, то перейти на шаг 1.

Шаг 7. Конец.

Результат работы алгоритма - оптимальная перестановка T .

В таблице 2 представлен пример исходных данных при n = 5 ,С=30, k=2, где k – номер отрезка с обнулением веса.

 

Таблица 2 – Исходные данные

	7	8	12
	5	5	8
	4	1	2
	2	6	15
	6	10	11

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

Таблица 3 – Результат работы алгоритма

Количество отрезков	Пример входных данных	Результат работы алгоритма	Время выполнения задач
N = 5	C= 30 ; A p b 7 8 12 5 5 8 4 1 2 2 6 15 6 10 11	При k =2; p2= 0 ; номер Оптимальной перестановки: 111 Оптимальная перестановка: (5 3 2 1 4 ) ЦТ1 = 30.233     delta1 = 0.233 ЦТ2 = 30.68       delta2 = 0.68 решение задачи находится в массиве с заданным отрезком с нулевым весом Целевой ЦТ = 30 Delta=max(delta1,delta2) = 0.68 Оптимальный центр тяжести ЦТ2 = 30.68 Отклонение от целевого тяжести ЦТ(delta2) = 0.68	1.30 Секунда

 

Тестирование программы

на тестовых примерах была проведена связь между количеством сегментов N и временем выполнения программы V

сначала для T1 при p_k ≠ 0 и V2 для p_k = 0;

 тогда V = V1 + V2 со временем V для всего.

примечание V1 ≈ T2

тогда V ≈ 2V1 ≈ 2V2

 из всех наших результатов мы замечаем, что

время выполнения программы сильно зависит от количества сегментов N.

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

а) рассматривать все возможные случаи;

б) найти те, которые удовлетворяют условию данной задачи;

в) ищется глобальный оптимум.

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

Заключение

Сформулирована задача оптимальной упаковки (размещения) отрезков, нагруженных сосредоточенной силой, с условием изменения веса одного выделенного отрезка. Критерием оптимальной упаковки является минимальное отклонение центра тяжести от заданного значения. Алгоритм даёт точное решение. Временная сложность алгоритма составляет O (n!). Алгоритм полного перебора будет полезен при сравнении эффективности будущих приближенных алгоритмов. На основе этих теорем построен алгоритм полного перебора для задачи одномерной упаковки объектов с изменением веса. 

Конфликт интересов Не указан.

Conflict of Interest None declared.

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

1. Беллман Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус.– М.: Наука, 1965.— 460 с.
2. Mongeau M. Optimization of aircraft container loading / M. Mongeau, C. Be` s // IEEE Transactions on Aerospace and Electronic Systems 39, 2003. 1, 140–150.
3. Залюбовский В. В. О представлении перестановками допустимых решений одномерной задачи упаковки в контейнеры / В. В. Залюбовский // Труды XIII Байкальской международной школы-семинара «Методы оптимизации». Том 1: Иркутск, ИСЭМ СО АН РАН. – 2005. с.461-467.
4. Wim Vancroonenburg. Automatic air cargo selection and weight balancing: A mixed integer programming approach / Wim Vancroonenburg, Jannes Verstichel, Karel Tavernier et al. // Transportation Research Part E: Logistics and Transportation Review, Volume 65, May 2014, Pages 70-83. DOI: 1016/j.tre.2013.12.013 .
5. Kaluzny Bohdan L. Optimal aircraft load balancing / Kaluzny, Bohdan L.; Shaw, R. H. A. David. // International Transactions in Operational Research, Volume 16, Number 6, November 2009, pp. 767-787(21). DOI: 10.1111/j.1475-3995.2009.00723.x
6. Гэри М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. –М.: Мир, 1982. – 416 с.
7. Дворянкин А.М. Задача размещения нагруженных отрезков./ А.М. Дворянкин, М.Б. Кульцова, И.Г. Жукова // Известия ВолгГТУ. Сер. Актуальные проблемы управления, вычислительной техники и информатики в технических системах. – Волгоград, 2017. – № 8 (203). – C. 29-34.

 Список литературы на английском языке / References in English

1. Bellman R. Prikladnye zadachi dinamicheskogo programmirovanija [Applied dynamic programming] / R. Bellman, S. Dreyfus. Moscow, Science Publ., 1965. 460 p. [in Russian]
2. Mongeau M. Optimization of aircraft container loading / M. Mongeau, C. Be` s // IEEE Transactions on Aerospace and Electronic Systems 39, 2003. 1, 140–150.
3. Zaljubovskij V. V. O predstavlenii perestanovkami dopustimyh reshenij odnomernoj zadachi upakovki v kontejnery [On the representation by permutations of admissible solutions of the one-dimensional problem of packing into containers] / Zaljubovskij V. V. // Proceedings of the XIII Baikal International School-Seminar "Optimization Methods". Volume 1: Irkutsk, ISEM SB RAS. - 2005. p.461- 467. [in Russian]
4. Wim Vancroonenburg. Automatic air cargo selection and weight balancing: A mixed integer programming approach / Wim Vancroonenburg, Jannes Verstichel, Karel Tavernier et al. // Transportation Research Part E: Logistics and Transportation Review, Volume 65, May 2014, Pages 70-83. DOI: 1016/j.tre.2013.12.013 .
5. Kaluzny Bohdan L. Optimal aircraft load balancing / Kaluzny, Bohdan L.; Shaw, R. H. A. David. // International Transactions in Operational Research, Volume 16, Number 6, November 2009, pp. 767-787(21). DOI:  10.1111/j.1475-3995.2009.00723.x
6. Garey M. Vychislitel'nye mashiny i trudnoreshaemye zadachi [Computers and inaccessible tasks] / M. Garey, D. Johnson. Moscow, Mir Publ., 1982. 416 p. [in Russian]
7. Dvoryankin A. M. Zadacha razmeshhenija nagruzhennyh otrezkov [The problem of locating segments loaded by force] / A. M. Dvoryankin, M. B. Kultsova, I. G. Zhukova // Izvestiya Volgogradskogo gosudarstvennogo tekhnicheskogo universiteta. Seriya «Aktualnye problemy upravleniya, vychislitelnoy tekhniki i informatiki v tekhnicheskikh sistemakh» [Poceedings of the Volgograd State Technical University. Series "Actual Problems of Control, Computer Technology and Computer Science in Technical Systems"], 2017, no. 8 (203), pp. 29–34. [in Russian]