А. Ф. Валеева
Применение конструктивных эвристик в задачах раскроя-упаковки*
Рассматриваются задачи одномерной, прямоугольной, параллелепипедной упаковки,
являющиеся NP-трудными проблемами. Для их решения применяются конструктивные
эвристики, основанные на методах решения задачи "0- 1 рюкзак"
и метаэвристиках муравьиной колонии, поиска с запретами. Приведены результаты
численного эксперимента, подтверждающие высокую эффективность предложенных
алгоритмов.
A. F. Valeeva
Applying of the Constructive Heuristic Methods for Cutting-Packing
Problems
The paper is devoted to solving the linear, rectangular and parallelepiped
cutting-packing problems. It is known, these problems referred to the
class of NP-hard problems. The constructive heuristic methods based on
0- 1 Knapsack Problem and Ant Colony Optimization are developed for solving
these problems. The numerical comparison efficiency of algorithms is conducted.
ОГЛАВЛЕНИЕ
Введение
1. Постановки и математические модели основных задач С&Р
1.1. Постановки и математические модели задач одномерной упаковки
1.2. Постановки и математические модели негильотинных задач прямоугольной
упаковки
1.3. Задача негильотинной прямоугольной упаковки в прямоугольные листы
(2DBP)
1.4. Постановка и математическая модель задачи гильотинного прямоугольного
раскро
1.5. Постановка и математическая модель задачи параллелепипедной упаковки
(3D Bin Packing, 3DBP)
2. Конструктивные эвристики, базирующиеся на методе динамического перебора,
для решения задач рас кроя-упаковки
3. Применение метаэвристик для решения задач двухмерной упаковки
3.1. Алгоритм "имитация отжига"
3.2. Метод поиска с запретами
3.3. Метаэвристика АСО
4. Численные эксперименты
Заключение
*Работа поддержана Российским фондом фундаментальных исследований,
проект 03-01-07002