Summary of results of the DA + tabu search algorithm

Inst. LB=k Distance (average, best, worst) / number of solutions / gap with LBd(k)
k k+1 k+2 k+3 k+4 k+5 k+6 k+7 k+8 k+9 k+10 k+11 k+12
1.1 6 1069 1015 1005 1001 999 999 998
1060 1008 1002 998 993 996 998
1090 1029 1012 1005 1002 1002 998
5,59 1,83 1,44 1,14 0,78 0,52 0,09
49 50 50 49 30 7 1
1.2 6 988 958 950 950 951
978 953 947 947 951
1003 966 958 953 951
4,01 1,97 1,23 1,02 0,83
50 50 50 25 1
1.3 6 972 936 920 911 908 907
965 929 914 907 907 906
988 947 929 920 911 909
5,00 3,24 2,40 1,67 1,36 1,00
50 50 50 50 36 15
2.1 6 1001 985 980 978 978
996 981 977 975 977
1008 990 984 981 980
2,69 1,51 0,99 0,60 0,44
50 50 50 42 13
2.2 6 975 950 947 947
966 945 944 944
986 960 951 949
3,94 1,98 1,67 1,32
50 50 48 16
2.3 6 919 906 904 904 903
914 903 901 902 901
925 910 907 905 907
3,06 2,04 1,81 1,62 1,28
50 50 41 18 11
3.1 6 811 796 792 791 791
806 792 789 786 788
817 802 795 794 793
3,38 2,61 2,40 1,85 1,55
50 50 48 34 10
3.2 5 746 729 722 718 718
738 724 719 715 715
752 735 726 721 721
5,50 4,16 3,76 3,04 2,34
50 50 50 44 26
3.3 5 701 698 696 697
697 694 692 696
707 702 699 699
2,73 2,21 1,59 1,34
50 47 34 5
4.1 5 694 686 684 684
689 683 682 683
704 690 687 686
4,31 3,31 2,43 1,90
50 50 46 5
4.2 5 681 678 678 678
676 675 676 677
687 680 679 679
2,77 2,01 1,63 0,94
50 47 21 2
4.3 5 698 692 693
691 689 690
701 697 696
3,45 2,25 1,77
50 49 15
5.1 11 1790 1768 1758 1753 1749 1747 1745 1745
1777 1757 1750 1743 1741 1738 1738 1741
1804 1783 1769 1764 1759 1758 1754 1752
4,44 3,42 3,04 2,77 2,50 2,26 2,03 1,88
50 50 50 45 37 30 20 13
5.2 11 1886 1817 1792 1779 1771 1764 1760 1758 1757
1886 1799 1782 1768 1758 1752 1749 1751 1747
1886 1834 1810 1792 1780 1773 1769 1767 1765
9,38 5,88 4,67 4,02 3,58 3,13 2,81 2,58 2,33
1 50 50 48 49 44 37 26 14
5.3 10 1685 1645 1628 1622 1618 1616 1614 1616
1663 1634 1618 1612 1609 1611 1611 1612
1698 1656 1637 1631 1626 1622 1620 1619
7,25 4,89 3,89 3,40 2,96 2,60 2,15 1,90
50 50 50 48 33 33 23 4
6.1 11 1681 1651 1639 1633 1630 1629 1632 1634
1670 1638 1627 1621 1620 1626 1628 1634
1706 1662 1651 1641 1637 1635 1636 1634
6,03 4,11 3,22 2,64 2,18 1,79 1,59 1,29
50 50 49 42 30 16 4 2
6.2 11 1664 1649 1645 1643 1643 1643 1645
1653 1642 1636 1637 1639 1637 1641
1675 1659 1652 1650 1646 1649 1648
4,28 3,23 2,86 2,56 2,31 2,03 1,86
50 50 42 28 14 9 3
6.3 11 1810 1784 1766 1757 1753 1752 1751 1749 1753
1799 1773 1755 1748 1743 1748 1745 1746 1753
1821 1793 1777 1767 1760 1757 1756 1754 1753
6,68 5,12 4,04 3,43 3,02 2,77 2,47 2,14 2,13
47 50 50 48 38 27 21 10 3
7.1 10 1398 1370 1359 1355 1353 1353 1354
1388 1360 1348 1348 1348 1347 1351
1412 1383 1370 1362 1361 1358 1357
7,26 5,06 4,19 3,70 3,37 3,02 2,77
50 50 50 49 27 17 3
7.2 10 1328 1281 1266 1260 1258 1257 1257
1314 1272 1257 1254 1250 1254 1254
1337 1296 1274 1267 1262 1262 1261
9,95 6,25 4,87 4,20 3,70 3,29 2,95
15 50 49 44 24 15 2
7.3 10 1322 1292 1283 1277 1274 1274 1274 1272
1313 1281 1274 1270 1266 1267 1271 1271
1341 1303 1292 1287 1282 1280 1279 1273
8,91 6,52 5,68 5,13 4,73 4,58 4,37 3,90
49 50 50 47 40 19 11 2
8.1 10 1402 1341 1326 1319 1315 1314 1312 1315 1316
1390 1328 1316 1312 1305 1308 1308 1312 1315
1415 1349 1335 1326 1322 1318 1317 1318 1318
12,22 7,20 5,85 5,10 4,47 4,04 3,60 3,42 3,10
9 50 50 50 41 24 9 6 2
8.2 10 1333 1287 1273 1267 1264 1264 1264 1265 1264
1318 1278 1260 1257 1258 1257 1260 1262 1260
1354 1294 1281 1277 1272 1270 1269 1268 1267
11,06 7,06 5,72 4,99 4,45 4,16 3,83 3,41 2,89
25 50 50 46 32 18 10 3 2
8.3 9 1163 1150 1146 1146 1147
1151 1139 1138 1140 1146
1186 1159 1156 1152 1147
7,71 6,15 5,37 4,89 4,39
50 49 29 7 2
9.1 8 1931 1912 1901 1895 1899
1928 1904 1896 1892 1894
1945 1925 1911 1905 1901
2,02 1,57 1,23 0,92 0,97
50 50 50 46 3
9.2 8 1960 1923 1914 1909 1907 1910
1945 1916 1909 1903 1902 1906
1982 1936 1928 1915 1913 1911
3,38 2,27 2,13 1,92 1,60 1,43
50 50 50 44 11 6
9.3 8 1845 1793 1783 1777 1777 1782
1826 1787 1777 1769 1774 1782
1861 1808 1793 1783 1781 1782
3,68 1,89 1,63 1,14 0,83 0,71
50 50 50 44 9 1
10.1 8 1961 1935 1925 1921
1952 1924 1913 1915
1978 1943 1932 1926
2,36 1,80 1,40 0,88
50 50 46 39
10.2 8 1878 1837 1818 1811 1807 1810
1864 1826 1805 1797 1801 1809
1920 1847 1832 1819 1815 1813
4,65 3,33 2,50 1,99 1,41 1,20
50 50 50 39 37 6
10.3 8 1885 1868 1871
1865 1859 1869
1904 1880 1874
2,06 0,81 0,45
50 50 16
11.1 7 1603 1581 1577 1577
1595 1578 1573 1575
1615 1586 1582 1580
2,18 1,09 0,91 0,55
50 50 46 11
11.2 7 1657 1629 1616 1614 1614 1617
1649 1621 1608 1608 1609 1613
1667 1641 1626 1622 1621 1620
3,41 2,54 1,98 1,88 1,77 1,74
50 50 50 29 11 4
11.3 7 1572 1489 1469 1472
1542 1477 1465 1471
1637 1504 1479 1475
7,43 2,79 1,38 1,14
50 50 50 6
12.1 7 1538 1449 1451
1493 1442 1449
1634 1461 1457
9,03 2,43 1,94
49 50 10
12.2 7 1553 1540 1536 1538
1541 1530 1529 1536
1562 1549 1544 1541
3,87 2,91 2,33 1,93
50 48 34 7
12.3 7 1348 1329 1325 1326
1336 1320 1321 1322
1372 1339 1332 1329
3,92 2,51 1,77 1,28
50 50 38 8
13.1 14 3380 3323 3300 3288 3281 3277 3281 3285
3334 3291 3272 3264 3260 3266 3274 3278
3446 3346 3317 3309 3305 3291 3293 3293
5,90 4,26 3,51 2,97 2,60 2,27 2,16 1,98
25 50 48 44 26 13 11 2
13.2 16 4106 4037 3988 3954 3933 3919 3911 3907 3904
4106 4008 3963 3933 3912 3902 3889 3893 3893
4106 4061 4017 3973 3951 3939 3925 3921 3914
5,56 4,46 3,58 2,90 2,49 2,19 1,96 1,82 1,69
1 50 50 50 50 46 39 31 25
13.3 14 3507 3466 3457 3453 3455 3459 3461
3483 3443 3439 3444 3441 3450 3461
3539 3485 3479 3476 3470 3464 3461
4,21 2,91 2,47 2,14 1,92 1,76 1,53
50 49 36 22 13 3 1
14.1 14 3393 3339 3323 3322 3326 3322
3366 3302 3301 3309 3312 3315
3416 3371 3349 3338 3338 3330
6,73 4,83 4,12 3,76 3,55 3,07
50 50 46 24 12 5
14.2 14 3610 3587 3576 3571 3568 3567 3570
3583 3560 3565 3555 3553 3551 3566
3643 3602 3594 3587 3581 3573 3573
4,49 3,74 3,33 3,03 2,73 2,49 2,29
50 50 43 34 26 10 6
14.3 14 3259 3231 3219 3213 3211 3210 3208
3235 3210 3198 3199 3193 3199 3199
3286 3251 3238 3231 3223 3218 3224
5,56 4,51 3,93 3,51 3,23 2,93 2,59
50 49 44 32 24 14 7
15.1 13 3008 2896 2859 2835 2821 2812 2811 2811
2967 2870 2838 2819 2805 2802 2798 2800
3049 2917 2883 2859 2834 2821 2824 2819
9,81 6,08 4,89 3,99 3,35 2,85 2,66 2,44
17 50 50 48 44 33 26 7
15.2 13 2822 2790 2771 2763 2761 2761 2777 2770
2796 2764 2754 2752 2747 2754 2777 2770
2858 2823 2793 2779 2777 2771 2777 2770
6,11 4,86 4,08 3,53 3,16 2,86 3,13 2,46
50 50 49 38 19 7 1 1
15.3 13 2725 2698 2686 2682 2681 2681
2705 2678 2670 2670 2673 2678
2747 2713 2699 2690 2688 2685
5,87 4,70 4,01 3,54 3,11 2,70
50 50 42 27 20 2
16.1 13 2735 2716 2706 2704 2702 2706
2719 2695 2690 2686 2692 2706
2760 2728 2722 2714 2707 2706
5,85 4,72 3,93 3,37 2,67 2,19
50 50 43 27 7 1
16.2 12 2722 2641 2616 2604 2602 2600 2605
2722 2620 2599 2594 2590 2594 2601
2722 2658 2636 2619 2610 2612 2609
10,09 6,60 5,21 4,28 3,69 3,08 2,72
1 50 50 43 31 14 3
16.3 13 2671 2633 2618 2614 2613 2611 2603 2613
2638 2605 2603 2597 2599 2601 2603 2613
2688 2656 2636 2627 2623 2622 2603 2613
6,72 5,08 4,31 3,85 3,49 3,00 2,21 2,06
50 50 44 36 23 11 1 1