| 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. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|