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