Библиотека тестовых задач
Дискретные
задачи размещения
Библиотека тестовых задач
Библиотека тестовых задач
Задача раскроя и упаковки
Тестовые
примеры.
Упаковка кругов и
прямоугольников
Тестовые примеры сгенерированны случайным образом так, чтобы для каждого примера была известна некоторая верхняя оценка его оптимального решения. Генерация примеров осуществлялась следующим образом. Допустим, необходимо получить тестовый пример упаковки n предметов, nc из которых круги, а nr — прямоугольники, в полосу ширины W. Тогда прямоугольная область размером W´UB, где UB — заданная верхняя оценка оптимальной длины полосы, нарезается на nc квадратов и nr прямоугольников безотходным способом. Затем каждый квадрат заменяется на круг диаметром, равным стороне квадрата. Если nc= 0, то для такого примера существует решение, когда все прямоугольники упакованы в полосу длины UB безотходным способом, т. е. такое решение является оптимальным. В случае, когда nc > 0, UB является лишь верхней оценкой оптимальной длины полосы. Всего было сгенерировано 24 примера с количеством предметов от 8 до 196.
В следующей таблице указаны параметры всех примеров, включая верхнюю UB и нижнюю LB оценки, а также результаты, полученные алгоритмом вероятностного поиска с запретами.
Все примеры Test-CR.zip 5 Kb
Исходные данные содержатся в текстовых файлах CR1P1 - CR8P3. В каждом файле число после слова STRIP указывает на заданную ширину полосы. Каждому предмету соответствует одна строка после слова ITEMS. Если строка содержит два вещественных числа, то это длина и ширина прямоугольника, если строка содержит одно вещественное число, то это радиус круга.
Пример
Параметры примера
TABU SEARCH
Отклонение (%)
Время
W
n
nc
nr
LB
UB
Среднее
Лучшее
от LB
от UB
(сек.)
10
7
3
4
8,99
10
10
10
11,28
0
0
10
8
4
4
8,96
10
10
10
11,61
0
2
10
7
4
3
8,69
10
10
10
15,09
0
0
20
17
7
10
17,83
20
20
20
12,15
0
326
20
17
8
9
17,32
20
19,91
19,9
14,91
-0,5
417
20
17
6
11
17,69
20
20
20
13,04
0
346
40
25
10
15
13,46
15
15,27
15,27
13,42
1,77
738
40
25
6
19
13,83
15
16,17
15,81
14,34
5,42
596
40
25
14
11
13,18
15
15
15
13,8
0
920
60
29
10
19
27,61
30
30,97
30,49
10,43
1,64
597
60
29
14
15
26,21
30
30,43
30
14,45
0
671
60
29
6
23
28,45
30
31
31
8,94
3,33
558
60
49
20
29
53,14
60
63,04
61,61
15,93
2,68
904
60
49
16
33
53,96
60
63,21
62,4
15,64
4
810
60
49
12
37
56,99
60
63,58
63
10,54
5
996
60
73
39
34
78,3
90
93,15
91,93
17,42
2,15
1360
60
73
35
38
78,76
90
92,93
90,61
15,05
0,68
1027
60
73
31
42
78,98
90
93,98
92,34
16,92
2,6
1235
80
97
45
52
104,37
120
125,72
122,97
17,82
2,48
1220
80
97
41
56
106,87
120
126,03
125,75
17,68
4,8
1190
80
97
37
60
107,31
120
125,89
125,46
16,92
4,55
1065
160
196
80
116
212,23
240
255,71
251,92
18,7
4,97
1202
160
196
96
100
209,77
240
248,6
246,91
17,71
2,88
1612
160
196
110
86
202,65
240
239,44
235,77
16,34
-1,76
1508