Asset-balanced network design		Results for C Instances
Lowe Bound / Upper Bound
Year		2017	2017	2009	2009	2010	2011	2012	2013	2015	2015	2016	2018	2018	2018
Problem	Problem	Optimal/ Lower Bound/ Giurobi7/ 60h	Upper Bound/ Giurobi7/ 60h	Tabu Search	Parallel Tabu Search	Guided Local Search	MIP Tabu Search	Tabu Assisted Guided Local Search Approache	Three-Stage Metaheuristic	Capacity Scaling and Restricted Branch-and-Bound Matheuristic	Capacity Scaling and Local Branch Matheuristic	Cutting-Plane Matheuristic	Hybrid Algorithm	Capacity Scaling and MIP Neighborhood Search	Capacity Scaling and MIP Neighborhood Search Tuned
c37	20/230/200/V/L	97274	97274	102919	101345	101267	98421	98760	97274	97597	97274	98699	97274	97274	97274
c38	20/230/200/F/L	139395	139395	150764	148384	143017	141744	142213	139395	139831	139395	141744	139395	139395	139395
c39	20/230/200/V/T	100221	100221	103371	103371	103428	101244	102137	100720	100530	100221	103103	100478	100558	100478
c40	20/230/200/F/T	138962	138962	149942	144766	143446	141130	141802	138962	139253	138994	142638	138994	139414	138962
c45	20/300/200/V/L	77436	77436	82533	80269	80183	78576	78787	77584	77584	77502	79953	77463	77584	77502
c46	20/300/200/F/L	119259	119259	128757	126258	126097	121106	121773	119987	119324	119259	120979	119259	119554	119554
c47	20/300/200/V/T	76208	76208	78571	78444	77839	76545	77066	76450	76208	76208	76545	76208	76208	76208
c48	20/300/200/F/T	111333	111333	116338	116338	116712	113412	114465	111776	111462	111462	113412	111475	112177	112177
c49	30/520/100/V/L	54683	54683	55981	55786	55437	55159	55422	54783	54733	54683	55733	54683	54683	54683
c50	30/520/100/F/L	97323	98084	104533	101612	100999	101129	100290	100098	99193	98171	104235	98595	99734	98381
c51	30/520/100/V/T	53023	53023	54493	54092	53644	53224	53744	53035	53246	53023	53224	53030	53029	53029
c52	30/520/100/F/T	100110	101111	105167	104702	106096	104426	103996	101412	102043	101131	106251	101576	101360	101130
c53	30/520/400/V/L	114547	114547	119735	118071	119344	115477	116196	115528	114688	114565	115220	114891	114870	114688
c54	30/520/400/F/L	151457	152678	162360	160979	163182	153943	154941	153409	152893	152776	153737	154336	153017	153017
c55	30/520/400/V/T	116509	116509	120421	120421	122877	116959	118336	117226	116671	116616	117056	117141	116681	116681
c56	30/520/400/F/T	153785	154804	161978	161987	166488	155863	157940	155906	155121	154820	155942	157655	155766	154985
c57	30/700/100/V/L	48693	48693	49429	49429	49465	49139	49221	48807	48708	48693	49268	48693	48693	48693
c58	30/700/100/F/L	61263	61263	63889	63292	62936	62000	62055	61408	61528	61298	62267	61433	61948	61667
c59	30/700/100/V/T	46750	46750	48202	47487	47518	46865	47518	46812	47137	46750	46928	46750	47062	47033
c60	30/700/100/F/T	56131	56131	58204	57187	58559	56599	57571	56237	56609	56169	57701	56207	56235	56180
c61	30/700/400/V/L	98979	99263	103932	103932	104534	99588	101610	100589	99333	99314	99458	101316	99796	99351
c62	30/700/400/F/L	134908	137510	157043	148114	152580	139088	142563	141037	137889	137724	139607	145185	138026	137990
c63	30/700/400/V/T	96763	97200	103085	103085	103581	97901	98657	97875	97426	97278	97737	99133	97353	97350
c64	30/700/400/F/T	130934	132266	141917	138609	142575	132999	135778	133686	132487	132487	132855	134122	132370	132201
Average		98998	99358	105149	103665	104242	100522	101368	100000	99646	99409	101012	100221	99699	99525
Gaps(%)
c37	20/230/200/V/L		0.00%	5.80%	4.19%	4.10%	1.18%	1.53%	0.00%	0.33%	0.00%	1.46%	0.00%	0.00%	0.00%
c38	20/230/200/F/L		0.00%	8.16%	6.45%	2.60%	1.69%	2.02%	0.00%	0.31%	0.00%	1.69%	0.00%	0.00%	0.00%
c39	20/230/200/V/T		0.00%	3.14%	3.14%	3.20%	1.02%	1.91%	0.50%	0.31%	0.00%	2.88%	0.26%	0.34%	0.26%
c40	20/230/200/F/T		0.00%	7.90%	4.18%	3.23%	1.56%	2.04%	0.00%	0.21%	0.02%	2.65%	0.02%	0.33%	0.00%
c45	20/300/200/V/L		0.00%	6.58%	3.66%	3.55%	1.47%	1.74%	0.19%	0.19%	0.09%	3.25%	0.03%	0.19%	0.09%
c46	20/300/200/F/L		0.00%	7.96%	5.87%	5.73%	1.55%	2.11%	0.61%	0.05%	0.00%	1.44%	0.00%	0.25%	0.25%
c47	20/300/200/V/T		0.00%	3.10%	2.93%	2.14%	0.44%	1.13%	0.32%	0.00%	0.00%	0.44%	0.00%	0.00%	0.00%
c48	20/300/200/F/T		0.00%	4.50%	4.50%	4.83%	1.87%	2.81%	0.40%	0.12%	0.12%	1.87%	0.13%	0.76%	0.76%
c49	30/520/100/V/L		0.00%	2.37%	2.02%	1.38%	0.87%	1.35%	0.18%	0.09%	0.00%	1.92%	0.00%	0.00%	0.00%
c50	30/520/100/F/L		0.78%	7.41%	4.41%	3.78%	3.91%	3.05%	2.85%	1.92%	0.87%	7.10%	1.31%	2.48%	1.09%
c51	30/520/100/V/T		0.00%	2.77%	2.02%	1.17%	0.38%	1.36%	0.02%	0.42%	0.00%	0.38%	0.01%	0.01%	0.01%
c52	30/520/100/F/T		1.00%	5.05%	4.59%	5.98%	4.31%	3.88%	1.30%	1.93%	1.02%	6.13%	1.46%	1.25%	1.02%
c53	30/520/400/V/L		0.00%	4.53%	3.08%	4.19%	0.81%	1.44%	0.86%	0.12%	0.02%	0.59%	0.30%	0.28%	0.12%
c54	30/520/400/F/L		0.81%	7.20%	6.29%	7.74%	1.64%	2.30%	1.29%	0.95%	0.87%	1.51%	1.90%	1.03%	1.03%
c55	30/520/400/V/T		0.00%	3.36%	3.36%	5.47%	0.39%	1.57%	0.62%	0.14%	0.09%	0.47%	0.54%	0.15%	0.15%
c56	30/520/400/F/T		0.66%	5.33%	5.33%	8.26%	1.35%	2.70%	1.38%	0.87%	0.67%	1.40%	2.52%	1.29%	0.78%
c57	30/700/100/V/L		0.00%	1.51%	1.51%	1.59%	0.92%	1.08%	0.23%	0.03%	0.00%	1.18%	0.00%	0.00%	0.00%
c58	30/700/100/F/L		0.00%	4.29%	3.31%	2.73%	1.20%	1.29%	0.24%	0.43%	0.06%	1.64%	0.28%	1.12%	0.66%
c59	30/700/100/V/T		0.00%	3.11%	1.58%	1.64%	0.25%	1.64%	0.13%	0.83%	0.00%	0.38%	0.00%	0.67%	0.61%
c60	30/700/100/F/T		0.00%	3.69%	1.88%	4.33%	0.83%	2.57%	0.19%	0.85%	0.07%	2.80%	0.14%	0.19%	0.09%
c61	30/700/400/V/L		0.29%	5.00%	5.00%	5.61%	0.62%	2.66%	1.63%	0.36%	0.34%	0.48%	2.36%	0.83%	0.38%
c62	30/700/400/F/L		1.93%	16.41%	9.79%	13.10%	3.10%	5.67%	4.54%	2.21%	2.09%	3.48%	7.62%	2.31%	2.28%
c63	30/700/400/V/T		0.45%	6.53%	6.53%	7.05%	1.18%	1.96%	1.15%	0.69%	0.53%	1.01%	2.45%	0.61%	0.61%
c64	30/700/400/F/T		1.02%	8.39%	5.86%	8.89%	1.58%	3.70%	2.10%	1.19%	1.19%	1.47%	2.43%	1.10%	0.97%
Average			0.29%	5.59%	4.23%	4.68%	1.42%	2.23%	0.86%	0.61%	0.33%	1.98%	0.99%	0.63%	0.46%
Computation Time (seconds)
c37	20/230/200/V/L	10646	10646	3600	3600	3600	3600	2400	5460	92	5580	635	7200	440	298
c38	20/230/200/F/L	17476	17476	3600	3600	3600	3600	2400	5520	219	8837	1026	7200	328	324
c39	20/230/200/V/T	911	911	3600	3600	3600	3600	2400	4680	46	4223	544	7200	309	308
c40	20/230/200/F/T	54646	54646	3600	3600	3600	3600	2400	5040	556	9578	634	7200	259	256
c45	20/300/200/V/L	22796	22796	3600	3600	3600	3600	2400	9720	79	8596	432	7200	172	170
c46	20/300/200/F/L	158348	158348	3600	3600	3600	3600	2400	6600	421	9056	1027	7200	386	319
c47	20/300/200/V/T	362	362	3600	3600	3600	3600	2400	5400	37	1977	283	7200	211	160
c48	20/300/200/F/T	111034	111034	3600	3600	3600	3600	2400	8460	606	7863	958	7200	129	128
c49	30/520/100/V/L	189	189	3600	3600	3600	3600	2400	5100	15	1607	225	7200	150	92
c50	30/520/100/F/L	216000	216000	3600	3600	3600	3600	2400	7080	413	10337	1630	7200	218	210
c51	30/520/100/V/T	993	993	3600	3600	3600	3600	2400	6180	10	5333	82	7200	239	168
c52	30/520/100/F/T	216000	216000	3600	3600	3600	3600	2400	9900	422	21799	870	7200	359	346
c53	30/520/400/V/L	45514	45514	3600	3600	3600	3600	2400	13260	194	9284	6830	7200	291	280
c54	30/520/400/F/L	216000	216000	3600	3600	3600	3600	2400	8760	806	5214	10529	7200	402	362
c55	30/520/400/V/T	44903	44903	3600	3600	3600	3600	2400	12600	82	12286	5413	7200	271	267
c56	30/520/400/F/T	216001	216001	3600	3600	3600	3600	2400	8160	1293	11929	10696	7200	353	354
c57	30/700/100/V/L	74	74	3600	3600	3600	3600	2400	4440	8	381	101	7200	67	61
c58	30/700/100/F/L	45377	45377	3600	3600	3600	3600	2400	9180	69	9823	631	7200	92	83
c59	30/700/100/V/T	1784	1784	3600	3600	3600	3600	2400	8100	17	8587	125	7200	72	72
c60	30/700/100/F/T	6447	6447	3600	3600	3600	3600	2400	9120	51	8212	309	7200	399	331
c61	30/700/400/V/L	216000	216000	3600	3600	3600	3600	2400	8160	498	11661	7893	7200	301	288
c62	30/700/400/F/L	216000	216000	3600	3600	3600	3600	2400	4800	1318	7746	15723	7200	419	422
c63	30/700/400/V/T	216000	216000	3600	3600	3600	3600	2400	13320	1825	14481	8405	7200	385	367
c64	30/700/400/F/T	216000	216000	3600	3600	3600	3600	2400	7800	3504	12901	10953	7200	401	406
Average Computation Time		93729	93729	3600	3600	3600	3600	2400	7785	524	8637	3581	7200	277	253
Gaps of R problem
			Upper Bound/ Giurobi7/ 60h	Tabu Search	Parallel Tabu Search	Guided Local Search	MIP Tabu Search	Tabu Assisted Guided Local Search Approache	Three-Stage Metaheuristic	Capacity Scaling and Restricted Branch-and-Bound Matheuristic	Capacity Scaling and Local Branch Matheuristic	Cutting-Plane Matheuristic	Hybrid Algorithm	Capacity Scaling and MIP Neighborhood Search	Capacity Scaling and MIP Neighborhood Search Tuned
Gaps			0.02%	5.98%	4.43%		1.77%		0.64%	0.78%	0.03%	2.63%
Computation Time			-	3600.0	3600.0		3600.0		5711.1	251.3	5074.2	1004.1
Optimal/Lower Bound/Giurobi751/30h				N. Katayama, Working paper, 2018.
Upper Bound/Giurobi7.51/30h				N. Katayama, Working paper, 2018.
Tabu Search				M.B. Pedersen, T.G. Crainic, and O.B.G.Madsen. Models and tabu search metaheuristics for service network design with asset-balance requirements. Transportation Science, Vol. 43, pp. 158–177, 2009.
Parallel Tabu Search				M.B. Pedersen, T.G. Crainic, and O.B.G.Madsen. Models and tabu search metaheuristics for service network design with asset-balance requirements. Transportation Science, Vol. 43, pp. 158–177, 2009.
Guided Local Search				R. Bai, G. Kendall, R. Qu, J.A.D. Atkin, Tabu assisted guided local search approaches for freight service network design, Information Sciences, 189(15), 266–281, 2012.
Tabu Guided Local Search				R. Bai, G. Kendall, R. Qu, J.A.D. Atkin, Tabu assisted guided local search approaches for freight service network design, Information Sciences, 189(15), 266–281, 2012.
MIP Tabu Search				M. Chouman and T. G. Crainic. MIP-based tabu search for service network design with design-balanced requirements. Technical Report CIRRELT-2011-68, Centrede recherche sur les transports,Universit'e de Montr'eal, 2011.
Three-Stage Metaheuristic				V.D. Minh,T.G. Crainic,M. Toulouse, A three-stage metaheuristic for the capacitated multi-commodity fixed-cost network design with design-balance constraints, J. Heuristics, 19, 757–795, 2013.
Capacity Scaling and Restricted Branch-and-Bound Matheuristic				N. Katayama, A combined matheuristics for service network design problem", The International Federation of Logistics and SCM Systems, Vol.8, pp11-20, 2015.
Capacity Scaling and Local Branch Matheuristic 20-2000				N. Katayama, A combined matheuristics for service network design problem", The International Federation of Logistics and SCM Systems, Vol.8, pp11-20, 2015.
Cutting-Plane Matheuristic				M. Choumann and T.G. Crainic,  Cutting-plane matheuristic for service network design with design-balanced requirements, Transportation Science, Vol.49, pp99-113, 2016.
Hybrid Algorithm				R. Bai,J.R. Woodward, N. Subramanian, J. Cartlidge, Optimisation of transportation service network using κ-node large neighbourhood search, Computers and Operations Research, 89,193–205, 2018.
Capacity Scaling and MIP Neighborhood				N. Katayama, Working paper, 2018.
Capacity Scaling and MIP Neighborhood Search Tuned				N. Katayama, Working paper, 2018.