Библиотека тестовых задач
Дискретные
задачи размещения
Библиотека тестовых задач
Библиотека тестовых задач
Задача раскроя и упаковки
Тестовые
примеры.
Упаковка
прямоугольников
в контейнеры
с запрещенными областями
Тестовые примеры сгенерированны случайным образом так, чтобы для каждого примера было известно его оптимальное решение. Сгенерированы два класса примеров (CLASS_PREPLACED, CLASS_IMPURITIES). В примерах первого класса ни один предмет не может пересекаться с запрещенными областями. Таким образом, каждая запрещенная область может рассматриваться как заранее размещенный предмет. Во втором классе каждой запрещенной области соответствует предмет таких же размеров, обладающий свойством, позволяющим ему пересекаться с запрещенными областями. Для каждого примера известно его оптимальное решение. Все примеры в обоих классах поделены на группы по количеству контейнеров в оптимальном решении (3, 7, 10, 15) и по количеству запрещенных областей (10, 40, либо 70 процентов от количества предметов в данном примере). Размерность примеров составляет 20, 60, 100, 140, либо 200 предметов. При генерации примеров размеры контейнеров выбирались из диапазона от 100 до 300 и затем случайным образом разрезались с помощью гильотинных разрезов на заданное количество предметов и запрещенных областей безотходным способом. Размеры дополнительных контейнеров брались равными 300х300.
Формат файлов с тестовыми примерами
TXT файл примера организован следующим образом. Описание каждого контейнера начинается с ключевого слова new_bin. Сразу за ним записывается номер контейнера. Два числа на следующей строке указывают ширину и высоту контейнера. Если контейнер содержит запрещенные области, то для каждой запрещенной области с новой строки указываются ее ширина, высота и координаты X и Y ее левого нижнего угла в пределах контейнера. Описание контейнеров заканчивается ключевым словом end_bins. Прямоугольные предметы описываются между строками со словами begin_items и end_items. Описание каждого предмета начинается с новой строки. Для всех предметов указан его номер, ширина, высота и значение бинарного параметра di.
Численные эксперименты
Рассматриваются четыре варианта поставленной задачи:
ориентированная задача (O) – повороты предметов не допускаются;
неориентированная задача (R) – допускаются повороты предметов на 90°;
гильотинная задача раскроя прямоугольных листов (G) – каждый предмет может быть вырезан из листа (контейнера) при помощи рекурсивных разрезов от края до края;
негильотинная задача (F) – допускаются произвольные разрезы листов.
В следующих таблицах представлены результаты разработанные модифицированным алгоритмом имитации отжига. Указаны значения оценки незанятой площади первых m – 1 контейнеров, где m – это число используемых контейнеров. Данная оценка вычисляется следующим образом:
Dm – 1 характеризует степень загрузки первых m – 1 контейнеров. В случаях когда данная оценка достигает значения 0%, решение является оптимальным, т.к. первые m – 1 контейнеров загружены полностью и дальнейшее улучшение упаковки невозможно.
Таблица1: Class_Preplaced
n
IMP_10
IMP_40
IMP_70
O|G
R|G
O|F
R|F
O|G
R|G
O|F
R|F
O|G
R|G
O|F
R|F
20
8,503
8,766
4,554
2,398
3,317
2,608
0
2,989
1,835
4,655
2,325
3,949
60
8,347
6,586
5,522
4,458
8,189
6,177
7,06
5,764
7,195
5,914
7,07
5,301
100
5,954
4,614
4,421
3,338
7,367
6,899
6,766
4,993
6,116
5,882
7,53
5,171
140
5,577
5,337
4,571
3,986
7,762
6,407
6,156
5,355
8,85
7,812
7,729
5,538
200
5,357
5,282
4,321
3,126
7,792
5,984
6,129
5,41
6,239
6,046
5,422
4,463
Среднее
6,748
6,117
4,678
3,461
6,885
5,615
5,222
4,902
6,047
6,062
6,015
4,884
20
0
6,305
0
4,978
3,197
3,197
0
4,064
4,416
5,902
0
1,96
60
6,656
4,135
5,558
3,147
7,409
6,163
5,878
5,008
5,876
5,441
5,309
3,966
100
5,639
5,894
4,707
3,517
6,407
5,529
5,011
3,959
7,423
5,923
7,807
6,495
140
6,253
5,232
4,242
4,036
7,261
6,759
6,024
5,089
7,473
6,801
6,283
4,27
200
6,35
5,7
4,332
3,005
7,306
6,424
6,124
5,233
7,173
5,287
4,867
3,782
Среднее
4,98
5,453
3,768
3,737
6,316
5,614
4,607
4,671
6,472
5,871
4,853
4,095
20
0
0
0
0
4,671
6,422
0
1,358
1,606
4,774
0
0
60
6,536
4,314
4,535
3,697
7,612
5,93
5,932
4,822
5,061
4,817
4,809
4,377
100
6,083
4,548
5,232
3,824
7,456
6,065
6,071
5,172
6,575
5,624
4,779
3,838
140
5,418
4,289
4,8
3,959
8,231
6,874
5,903
4,894
7,256
6,127
5,543
4,726
200
5,079
4,762
4,215
3,427
6,24
5,936
5,745
4,88
6,866
6,674
5,695
5,019
Среднее
4,623
3,583
3,756
2,981
6,842
6,245
4,73
4,225
5,531
5,603
4,165
3,592
20
0
0
0
0
0
0
0
0
8,173
8,183
0
0
60
6,862
4,539
4,719
3,973
5,497
5,012
4,156
3,903
7,789
5,81
4,596
4,31
100
6,299
4,728
5,416
4,027
6,275
3,982
5,988
4,507
7,228
6,139
5,695
4,352
140
6,038
4,214
5,377
3,991
6,327
4,83
4,883
4,471
5,104
4,922
5,19
4,475
200
4,886
4,232
4,316
3,32
6,181
5,044
5,929
4,038
6,021
4,855
5,308
4,057
Среднее
4,817
3,543
3,966
3,062
4,856
3,774
4,191
3,384
6,863
5,982
4,158
3,439
Таблица2: Class_Impurities
n
IMP_10
IMP_40
IMP_70
O|G
R|G
O|F
R|F
O|G
R|G
O|F
R|F
O|G
R|G
O|F
R|F
20
0
4,55
0
3,224
0
0
0
0
0
0
0
0
60
9,097
7,992
6,697
6,333
12,35
9,584
9,689
9,088
10,14
9,618
9,502
8,971
100
8,3
8,576
6,119
5,899
10,637
8,72
10,11
8,348
9,94
8,684
8,434
8,414
140
9,217
8,782
5,545
5,664
11,173
11,291
11,55
9,187
11,218
9,693
9,562
8,375
200
8,991
9,552
7,712
7,117
12,027
11,505
11,063
9,282
10,834
8,353
8,853
7,394
Среднее
7,121
7,89
5,215
5,647
9,237
8,22
8,482
7,181
8,426
7,27
7,27
6,631
20
0
3,206
0
3,206
0
0
0
0
0
0
0
0
60
7,879
5,245
7,349
5,501
6,644
7,496
8,443
7,163
6,522
7,401
7,58
7,171
100
6,425
4,4
5,507
4,701
9,982
8,292
8,994
6,831
8,3
7,356
7,678
6,557
140
8,428
6,17
5,031
4,353
9,95
9,787
9,461
7,454
8,305
7,913
7,461
6,763
200
8,663
7,187
6,784
3,86
10,533
9,854
9,199
7,849
7,969
6,459
6,85
5,832
Среднее
6,279
5,242
4,934
4,324
7,422
7,086
7,219
5,859
6,219
5,826
5,914
5,265
20
0
0
0
0
0
0
0
0
0
0
0
0
60
7,681
6,344
5,993
5,103
8,803
8,324
8,893
7,663
6,918
5,115
5,011
4,824
100
8,269
6,566
6,088
5,002
9,917
8,682
8,814
7,061
8,451
6,642
7,242
6,386
140
6,383
6,276
4,906
4,665
9,703
8,051
8,472
6,832
8,323
6,644
7,47
6,089
200
8,715
7,248
5,958
4,761
9,3
7,748
7,486
5,652
8,158
6,167
7,124
6,489
Среднее
6,21
5,287
4,589
3,906
7,545
6,561
6,733
5,442
6,37
4,914
5,369
4,758
20
0
0
0
0
0
0
0
0
0
0
0
0
60
7,469
6,715
5,954
6,093
8,923
8,529
7,838
9,283
7,973
6,562
5,321
7,377
100
6,452
6,56
7,395
4,875
8,291
8,233
8,057
6,276
7,032
7,779
7,646
5,941
140
5,987
5,104
5,824
4,273
8,051
7,689
7,512
6,106
8,785
7,477
7,246
6,687
200
7,165
5,373
5,691
4,328
9,85
9,362
9,207
7,337
8,393
7,386
8,072
6,671
Среднее
5,415
4,75
4,973
3,914
7,023
6,763
6,523
5,8
6,437
5,841
5,657
5,335
