Single-Path Design-Balanced Network Design Problem Results of C problem
Year   2017 2017 2017 2017 2017 2017 2017
Problem Problem Lower Bound/60h Gurobi/UB/60h LB heuristic RINS heuristic RINS+LB Capacity Scaling and MIP Neighborhood Search Capacity Scaling and MIP Neighborhood Search Tuned
c33 20_230_40_V_L 434986 434986 434986 434986 434986 434986 434986
c35 20_230_40_V_T 405089 405089 405089 405089 405089 405089 405089
c36 20_230_40_F_T 691642 691642 691642 691642 691642 691642 691642
c37 20_230_200_V_L 97008 97985 101592 100073 101982 98267 97975
c38 20_230_200_F_L 140338 140338 147719 144933 144517 143682 140845
c39 20_230_200_V_T 100948 100948 101963 102411 102518 101808 101056
c40 20_230_200_F_T 138790 141048 153061 143948 147030 142003 141105
c41 20_230_40_V_L 439205 439205 439205 439205 439205 439205 439205
c42 20_230_40_F_L 616525 616525 616525 616525 616525 616525 616525
c43 20_230_40_V_T 505657 505657 505657 505657 505657 505657 505657
c44 20_230_40_F_T 656324 656324 656324 656324 656324 656324 656324
c45 20_230_200_V_L 77550 78431 81524 80067 79510 79407 78477
c46 20_230_200_F_L 118645 121141 129103 127335 126433 122496 121468
c47 20_230_200_V_T 77340 77340 79593 77928 78215 77485 77340
c48 20_230_200_F_T 110783 114260 119619 116549 116696 114687 113734
c49 30_520_100_V_L 55363 55363 55384 55384 55415 55363 55363
c50 30_520_100_F_L 98469 100700 105557 105123 103346 102005 100745
c51 30_520_100_V_T 54961 54961 54961 54961 54961 54961 54961
c52 30_520_100_F_T 102944 103419 106591 105327 106813 104081 103471
c53 30_520_400_V_L 114516 115960 120279 119137 119284 115900 115900
c54 30_520_400_F_L 151185 155274 162427 160749 160837 157397 154939
c55 30_520_400_V_T 117073 118462 120483 120196 120802 118870 118807
c56 30_520_400_F_T 153937 157709 164153 162842 163979 160578 160178
c57 30_700_100_V_L 49039 49039 49039 49039 49039 49039 49039
c58 30_700_100_F_L 61910 61910 64141 62738 63372 62642 62320
c59 30_700_100_V_T 48719 48719 48719 48719 48719 48721 48719
c60 30_700_100_F_T 58239 58239 58616 58391 58460 58329 58285
c61 30_700_400_V_L 98726 100310 102663 101780 102460 100520 100345
c62 30_700_400_F_L 134772 139226 146169 147604 149579 142734 141031
c63 30_700_400_V_T 96735 98890 101927 100818 100933 99261 98980
c64 30_700_400_F_T 130825 134821 141387 139205 139267 135879 134960
Average 198008 199159 202132 201119 201406 199856 199338
Gaps(%)
Problem Problem Lower Bound/60h Gurobi/UB/60h LB heuristic RINS heuristic RINS+LB Capacity Scaling and MIP Neighborhood Search Capacity Scaling and MIP Neighborhood Search Tuned
c33 20_230_40_V_L - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c35 20_230_40_V_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c36 20_230_40_F_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c37 20_230_200_V_L - 1.01% 4.73% 3.16% 5.13% 1.30% 1.00%
c38 20_230_200_F_L - 0.00% 5.26% 3.27% 2.98% 2.38% 0.36%
c39 20_230_200_V_T - 0.00% 1.01% 1.45% 1.56% 0.85% 0.11%
c40 20_230_200_F_T - 1.63% 10.28% 3.72% 5.94% 2.32% 1.67%
c41 20_230_40_V_L - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c42 20_230_40_F_L - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c43 20_230_40_V_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c44 20_230_40_F_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c45 20_230_200_V_L - 1.14% 5.12% 3.25% 2.53% 2.39% 1.20%
c46 20_230_200_F_L - 2.10% 8.81% 7.32% 6.56% 3.25% 2.38%
c47 20_230_200_V_T - 0.00% 2.91% 0.76% 1.13% 0.19% 0.00%
c48 20_230_200_F_T - 3.14% 7.98% 5.20% 5.34% 3.52% 2.66%
c49 30_520_100_V_L - 0.00% 0.04% 0.04% 0.09% 0.00% 0.00%
c50 30_520_100_F_L - 2.27% 7.20% 6.76% 4.95% 3.59% 2.31%
c51 30_520_100_V_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c52 30_520_100_F_T - 0.46% 3.54% 2.31% 3.76% 1.10% 0.51%
c53 30_520_400_V_L - 1.26% 5.03% 4.04% 4.16% 1.21% 1.21%
c54 30_520_400_F_L - 2.70% 7.44% 6.33% 6.38% 4.11% 2.48%
c55 30_520_400_V_T - 1.19% 2.91% 2.67% 3.19% 1.53% 1.48%
c56 30_520_400_F_T - 2.45% 6.64% 5.78% 6.52% 4.31% 4.05%
c57 30_700_100_V_L - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c58 30_700_100_F_L - 0.00% 3.60% 1.34% 2.36% 1.18% 0.66%
c59 30_700_100_V_T - 0.00% 0.00% 0.00% 0.00% 0.00% 0.00%
c60 30_700_100_F_T - 0.00% 0.65% 0.26% 0.38% 0.15% 0.08%
c61 30_700_400_V_L - 1.60% 3.99% 3.09% 3.78% 1.82% 1.64%
c62 30_700_400_F_L - 3.30% 8.46% 9.52% 10.99% 5.91% 4.64%
c63 30_700_400_V_T - 2.23% 5.37% 4.22% 4.34% 2.61% 2.32%
c64 30_700_400_F_T - 3.05% 8.07% 6.41% 6.45% 3.86% 3.16%
Average Gap   - 0.95% 3.52% 2.61% 2.86% 1.54% 1.09%
Computation Times
Problem Problem Lower Bound/60h Gurobi/UB/60h LB heuristic RINS heuristic RINS+LB Capacity Scaling and MIP Neighborhood Search Capacity Scaling and MIP Neighborhood Search Tuned
c33 20_230_40_V_L 0 0 1 1 2 1 1
c35 20_230_40_V_T 0 0 1 1 2 2 2
c36 20_230_40_F_T 0 0 1 2 3 2 2
c37 20_230_200_V_L 216000 216000 492 600 600 578 705
c38 20_230_200_F_L 210339 210339 600 600 600 465 511
c39 20_230_200_V_T 33633 33633 600 600 600 481 509
c40 20_230_200_F_T 216000 216000 600 600 600 689 807
c41 20_230_40_V_L 0 0 1 28 2 1 1
c42 20_230_40_F_L 2 2 1 4 10 5 5
c43 20_230_40_V_T 1 1 1 2 2 3 2
c44 20_230_40_F_T 1 1 1 1 3 2 2
c45 20_230_200_V_L 216000 216000 341 600 600 562 808
c46 20_230_200_F_L 216000 216000 600 600 600 633 631
c47 20_230_200_V_T 106275 106275 492 600 600 567 626
c48 20_230_200_F_T 216000 216000 341 600 600 749 815
c49 30_520_100_V_L 711 711 600 600 600 325 221
c50 30_520_100_F_L 216000 216000 492 600 600 668 638
c51 30_520_100_V_T 30 30 600 70 116 63 47
c52 30_520_100_F_T 216000 216000 492 600 600 598 610
c53 30_520_400_V_L 216000 216000 425 600 600 756 756
c54 30_520_400_F_L 216000 216000 495 600 600 657 668
c55 30_520_400_V_T 216000 216000 600 600 600 665 597
c56 30_520_400_F_T 216000 216000 577 600 600 661 629
c57 30_700_100_V_L 124 124 600 227 238 167 102
c58 30_700_100_F_L 58915 58915 600 600 600 402 558
c59 30_700_100_V_T 172 172 341 268 367 225 169
c60 30_700_100_F_T 6155 6155 342 600 600 608 471
c61 30_700_400_V_L 216000 216000 497 600 600 695 668
c62 30_700_400_F_L 216000 216000 600 600 600 678 686
c63 30_700_400_V_T 216000 216000 600 600 600 648 673
c64 30_700_400_F_T 216000 216000 600 600 600 662 584
Average Computation Time   117947 117947 404 426 430 426 436
Gurobi/UB/60h N. Katayama by Gurobi Ver7.51,2018.
LB heuristic X. Li, K. Wei, Y. P. Aneja, P. Tian, Y. Cui, Matheuristics for the single-path design-balanced service network design problem, Computers & Operations Research, 77, pp141-153, 2017.
RINS heuristic X. Li, K. Wei, Y. P. Aneja, P. Tian, Y. Cui, Matheuristics for the single-path design-balanced service network design problem, Computers & Operations Research, 77, pp141-153, 2017.
RINS+LB X. Li, K. Wei, Y. P. Aneja, P. Tian, Y. Cui, Matheuristics for the single-path design-balanced service network design problem, Computers & Operations Research, 77, pp141-153, 2017.
min
Greedy 0.100
Greedy 0.700
Greedy BINARY 0.100
Greedy BINARY 0.700
Greedy 最小
Capacity Scaling and MIP Neighborhood Search N. Katayama, Working paper, 2018.
Capacity Scaling and MIP Neighborhood Search Tuned N. Katayama, Working paper, 2018.