Table A2 MILP and heuristic performance...

Table A2

MILP and heuristic performance

n	I		MILP (solved with Gurobi)							Heuristic
n	I	Time	UB	LB	GAP (%)	# Un	Un penalty	Utilization	Route	Time	Objective	# Un	Un penalty	Utilization	Route
3	1	5.7	5.09	5.09	0.0	0	0	2	3.09	2.7	5.09	0	0	2	3.09
3	2	3.5	3.04	3.04	0.0	0	0	1	2.04	2.9	3.04	0	0	1	2.04
3	3	73.3	8.15	8.15	0.0	0	0	2	6.15	2.2	9.74	0	0	2	7.74
3	4	17.3	6.79	6.79	0.0	0	0	2	4.79	2.2	6.79	0	0	2	4.79
3	5	1.8	3.61	3.61	0.0	0	0	1	2.61	2.8	3.61	0	0	1	2.61
3	6	8.8	4.96	4.96	0.0	0	0	1	3.96	2.5	4.96	0	0	1	3.96
3	7	9.8	4.23	4.23	0.0	0	0	1	3.23	2.6	4.23	0	0	1	3.23
3	8	5.8	4.86	4.86	0.0	0	0	2	2.86	2.6	4.86	0	0	2	2.86
3	9	6.7	5.13	5.13	0.0	0	0	1	4.13	2.7	5.13	0	0	1	4.13
3	10	101.9	6.02	6.02	0.0	0	0	1	5.02	3.0	6.02	0	0	1	5.02
4	1	36.9	5.28	5.28	0.0	0	0	1	4.28	4.8	5.28	0	0	1	4.28
4	2	159.4	6.11	6.11	0.0	0	0	2	4.11	7.3	6.11	0	0	2	4.11
4	3	380.2	7.22	7.22	0.0	0	0	2	5.22	4.3	7.22	0	0	2	5.22
4	4	10262.5	7.49	7.49	0.0	0	0	2	5.49	5.2	7.49	0	0	2	5.49
4	5	119.7	4.70	4.70	0.0	0	0	1	3.70	4.6	5.14	0	0	1	4.14
4	6	601.5	8.20	8.20	0.0	0	0	2	6.20	12.4	8.20	0	0	2	6.20
4	7	444.4	5.49	5.49	0.0	0	0	2	3.49	3.9	5.49	0	0	2	3.49
4	8	26.9	4.77	4.77	0.0	0	0	2	2.77	12.7	4.77	0	0	2	2.77
4	9	2328.9	5.11	5.11	0.0	0	0	1	4.11	5.6	5.11	0	0	1	4.11
4	10	189.1	5.05	5.05	0.0	0	0	2	3.05	8.1	5.05	0	0	2	3.05
5	1	2754.9	7.68	7.68	0.0	0	0	2	5.68	18.0	7.68	0	0	2	5.68
5	2	30089.9	6.97	6.97	0.0	0	0	2	4.97	7.0	6.97	0	0	2	4.97
5	3	26645.5	4.69	4.69	0.0	0	0	1	3.69	10.6	4.69	0	0	1	3.69
5	4	13904.0	7.07	7.07	0.0	0	0	2	5.07	8.2	7.07	0	0	2	5.07
5	5	1848.5	7.37	7.37	0.0	0	0	2	5.37	8.0	7.37	0	0	2	5.37
5	6	3002.4	6.59	6.59	0.0	0	0	2	4.59	5.9	6.59	0	0	2	4.59
5	7	9464.2	8.64	8.64	0.0	0	0	2	6.64	6.8	8.64	0	0	2	6.64
5	8	3252.4	7.71	7.71	0.0	0	0	2	5.71	5.4	9.00	0	0	2	7.00
5	9	1685.5	6.25	6.25	0.0	0	0	2	4.25	6.0	6.25	0	0	2	4.25
5	10	129.0	3.84	3.84	0.0	0	0	1	2.84	9.7	4.07	0	0	1	3.07
6	1	*	5.66	5.66	0.0	0	0	1	4.66	20.0	5.67	0	0	1	4.67
6	2	*	8.57	8.57	0.0	0	0	2	6.57	14.9	8.57	0	0	2	6.57
6	3	*	8.79	8.79	0.0	0	0	2	6.79	6.6	8.79	0	0	2	6.79
6	4	*	9.11	9.11	0.0	0	0	2	7.11	23.5	406.51	1	400	2	4.51
6	5	*	8.08	8.08	0.0	0	0	2	6.08	13.4	8.08	0	0	2	6.08
6	6	*	7.85	7.85	0.0	0	0	2	5.85	14.3	9.15	0	0	2	7.15
6	7	*	7.87	7.87	0.0	0	0	2	5.87	6.7	8.44	0	0	2	6.44
6	8	*	6.53	6.53	0.0	0	0	2	4.53	13.6	7.22	0	0	2	5.22
6	9	*	7.02	7.02	0.0	0	0	2	5.02	13.8	8.02	0	0	2	6.02
6	10	*	5.59	5.59	0.0	0	0	1	4.59	16.8	5.92	0	0	1	4.92
7	1	*	9.25	9.25	0.0	0	0	2	7.25	15.1	9.25	0	0	2	7.25
7	2	*	8.90	8.90	0.0	0	0	2	6.90	21.8	8.90	0	0	2	6.90
7	3	*	10.90	10.90	0.0	0	0	2	8.90	14.5	10.90	0	0	2	8.90
7	4	*	10.12	10.12	0.0	0	0	2	8.12	23.4	10.20	0	0	2	8.20
7	5	*	8.93	8.93	0.0	0	0	2	6.93	14.7	9.21	0	0	2	7.21
7	6	*	7.44	7.44	0.0	0	0	2	5.44	19.3	8.51	0	0	2	6.51
7	7	*	8.77	8.77	0.0	0	0	2	6.77	16.0	9.56	0	0	2	7.56
7	8	*	6.88	6.88	0.0	0	0	2	4.88	20.0	6.88	0	0	2	4.88
7	9	*	8.87	8.87	0.0	0	0	2	6.87	19.4	8.87	0	0	2	6.87
7	10	*	7.65	7.65	0.0	0	0	2	5.65	20.0	7.65	0	0	2	5.65
8	1	*	9.32	9.32	0.0	0	0	2	7.32	28.8	9.75	0	0	2	7.75
8	2	*	109.14	109.14	0.0	1	100	2	7.14	83.2	109.14	1	100	2	7.14
8	3	*	9.49	9.49	0.0	0	0	2	7.49	32.1	10.56	0	0	2	8.56
8	4	*	9.04	9.04	0.0	0	0	2	7.04	39.1	9.04	0	0	2	7.04
8	5	*	8.86	8.86	0.0	0	0	2	6.86	28.5	8.86	0	0	2	6.86
8	6	*	9.09	9.09	0.0	0	0	2	7.09	42.6	209.58	1	200	2	7.58
8	7	*	8.59	8.59	0.0	0	0	2	6.59	33.1	10.16	0	0	2	8.16
8	8	*	7.34	7.34	0.0	0	0	1	6.34	37.5	7.34	0	0	2	5.34
8	9	*	6.43	6.43	0.0	0	0	2	4.4	35.3	7.31	0	0	1	6.31
8	10	*	10.07	10.07	0.0	0	0	2	8.1	48.5	411.10	0	0	401	10.10
9	1	*	7.31	7.31	0.0	0	0	2	5.3	59.4	7.39	0	0	2	5.39
9	2	21,600.0	412.25	7.66	98.1	0	0	402	TBD	68.4	506.89	4	500	2	4.89
9	3	*	10.28	10.28	0.0	0	0	2	8.3	44.0	10.32	0	0	2	8.32
9	4	*	7.88	7.88	0.0	0	0	2	5.9	64.2	7.82	0	0	2	5.82
9	5	*	9.42	9.42	0.0	0	0	2	7.4	54.5	109.15	1	100	2	7.15
9	6	*	10.82	10.82	0.0	0	0	2	8.82	44.5	10.94	0	0	2	8.94
9	7	*	5.47	5.47	0.0	0	0	2	3.47	53.7	5.69	0	0	2	3.69
9	8	*	7.90	7.90	0.0	0	0	2	5.90	49.9	10.24	0	0	2	8.24
9	9	*	11.29	11.29	0.0	0	0	2	9.29	73.4	11.29	0	0	2	9.29
9	10	*	11.10	11.10	0.0	0	0	2	9.10	43.9	11.08	0	0	2	9.08
10	1	*	8.75	8.75	0.0	0	0	2	6.75	72.8	109.22	1	100	2	7.22
10	2	*	10.52	10.52	0.0	0	0	2	8.52	99.0	10.91	0	0	2	8.91
10	3	*	12.84	12.84	0.0	0	0	2	10.84	80.9	12.84	0	0	2	10.84
10	4	*	10.37	10.37	0.0	0	0	2	8.37	84.1	11.72	0	0	2	9.72
10	5	*	11.54	11.54	0.0	0	0	2	9.54	62.4	11.68	0	0	2	9.68
10	6	*	6.76	6.76	0.0	0	0	2	4.76	108.0	6.76	0	0	2	4.76
10	7	21,600.0	408.75	3.63	99.1	0	0	401	7.75	92.6	409.97	0	0	401	8.97
10	8	*	9.23	9.23	0.0	0	0	2	7.23	66.3	9.24	0	0	2	7.24
10	9	*	7.72	7.72	0.0	0	0	2	5.72	76.4	10.24	0	0	2	8.24
10	10	*	10.11	10.11	0.0	0	0	2	8.11	97.5	10.53	0	0	2	8.53
20	1	21,600.0	–	2.23	–	–	–	–	–	1032.9	419.56	0	0	402	17.56
20	2	21,600.0	–	1.82	–	–	–	–	–	646.2	26,014.37	1	25,600	402	12.37
20	3	21,600.0	–	2.43	–	–	–	–	–	868.2	417.18	0	0	402	15.18
20	4	21,600.0	–	2.01	–	–	–	–	–	771.9	416.38	0	0	402	14.38
20	5	21,600.0		1.24	–	–	–	–	–	876.2	419.68	0	0	402	17.68
20	6	21,600.0	–	2.09	–	–	–	–	–	832.1	416.69	0	0	402	14.69
20	7	21,600.0	–	1.48	–	–	–	–	–	874.6	414.25	0	0	402	12.25
20	8	21,600.0	–	1.84	–	–	–	–	–	875.5	415.29	0	0	402	13.29
20	9	21,600.0	–	2.30	–	–	–	–	–	452.8	415.86	0	0	402	13.86
20	10	21,600.0	–	2.31	–	–	–	–	–	663.5	415.26	0	0	402	13.26
30	1	21,600.0	–	0.94	–	–	–	–	–	2614.7	419.64	0	0	402	17.64
30	2	21,600.0	–	0.25	–	–	–	–	–	2963.3	520.18	1	100	402	18.18
30	3	21,600.0	–	1.18	–	–	–	–	–	2935.5	719.16	2	300	402	17.16
30	4	21,600.0	–	1.95	–	–	–	–	–	3099.1	519.52	1	100	402	17.52
30	5	21,600.0	–	0.94	–	–	–	–	–	1930.6	816.81	1	400	402	14.81
30	6	21,600.0	–	0.46	–	–	–	–	–	2125.9	821.17	2	400	402	19.17
30	7	21,600.0	–	0.00	–	–	–	–	–	3282.1	419.93	0	0	402	17.93
30	8	21,600.0	–	1.60	–	–	–	–	–	1933.9	719.08	2	300	402	17.08
30	9	21,600.0	–	0.51	–	–	–	–	–	3198.8	519.53	1	100	402	17.53
30	10	21,600.0	–	1.18	–	–	–	–	–	1452.8	618.99	1	200	402	16.99

n	I		MILP (solved with Gurobi)							Heuristic
n	I	Time	UB	LB	GAP (%)	# Un	Un penalty	Utilization	Route	Time	Objective	# Un	Un penalty	Utilization	Route
3	1	5.7	5.09	5.09	0.0	0	0	2	3.09	2.7	5.09	0	0	2	3.09
3	2	3.5	3.04	3.04	0.0	0	0	1	2.04	2.9	3.04	0	0	1	2.04
3	3	73.3	8.15	8.15	0.0	0	0	2	6.15	2.2	9.74	0	0	2	7.74
3	4	17.3	6.79	6.79	0.0	0	0	2	4.79	2.2	6.79	0	0	2	4.79
3	5	1.8	3.61	3.61	0.0	0	0	1	2.61	2.8	3.61	0	0	1	2.61
3	6	8.8	4.96	4.96	0.0	0	0	1	3.96	2.5	4.96	0	0	1	3.96
3	7	9.8	4.23	4.23	0.0	0	0	1	3.23	2.6	4.23	0	0	1	3.23
3	8	5.8	4.86	4.86	0.0	0	0	2	2.86	2.6	4.86	0	0	2	2.86
3	9	6.7	5.13	5.13	0.0	0	0	1	4.13	2.7	5.13	0	0	1	4.13
3	10	101.9	6.02	6.02	0.0	0	0	1	5.02	3.0	6.02	0	0	1	5.02
4	1	36.9	5.28	5.28	0.0	0	0	1	4.28	4.8	5.28	0	0	1	4.28
4	2	159.4	6.11	6.11	0.0	0	0	2	4.11	7.3	6.11	0	0	2	4.11
4	3	380.2	7.22	7.22	0.0	0	0	2	5.22	4.3	7.22	0	0	2	5.22
4	4	10262.5	7.49	7.49	0.0	0	0	2	5.49	5.2	7.49	0	0	2	5.49
4	5	119.7	4.70	4.70	0.0	0	0	1	3.70	4.6	5.14	0	0	1	4.14
4	6	601.5	8.20	8.20	0.0	0	0	2	6.20	12.4	8.20	0	0	2	6.20
4	7	444.4	5.49	5.49	0.0	0	0	2	3.49	3.9	5.49	0	0	2	3.49
4	8	26.9	4.77	4.77	0.0	0	0	2	2.77	12.7	4.77	0	0	2	2.77
4	9	2328.9	5.11	5.11	0.0	0	0	1	4.11	5.6	5.11	0	0	1	4.11
4	10	189.1	5.05	5.05	0.0	0	0	2	3.05	8.1	5.05	0	0	2	3.05
5	1	2754.9	7.68	7.68	0.0	0	0	2	5.68	18.0	7.68	0	0	2	5.68
5	2	30089.9	6.97	6.97	0.0	0	0	2	4.97	7.0	6.97	0	0	2	4.97
5	3	26645.5	4.69	4.69	0.0	0	0	1	3.69	10.6	4.69	0	0	1	3.69
5	4	13904.0	7.07	7.07	0.0	0	0	2	5.07	8.2	7.07	0	0	2	5.07
5	5	1848.5	7.37	7.37	0.0	0	0	2	5.37	8.0	7.37	0	0	2	5.37
5	6	3002.4	6.59	6.59	0.0	0	0	2	4.59	5.9	6.59	0	0	2	4.59
5	7	9464.2	8.64	8.64	0.0	0	0	2	6.64	6.8	8.64	0	0	2	6.64
5	8	3252.4	7.71	7.71	0.0	0	0	2	5.71	5.4	9.00	0	0	2	7.00
5	9	1685.5	6.25	6.25	0.0	0	0	2	4.25	6.0	6.25	0	0	2	4.25
5	10	129.0	3.84	3.84	0.0	0	0	1	2.84	9.7	4.07	0	0	1	3.07
6	1	*	5.66	5.66	0.0	0	0	1	4.66	20.0	5.67	0	0	1	4.67
6	2	*	8.57	8.57	0.0	0	0	2	6.57	14.9	8.57	0	0	2	6.57
6	3	*	8.79	8.79	0.0	0	0	2	6.79	6.6	8.79	0	0	2	6.79
6	4	*	9.11	9.11	0.0	0	0	2	7.11	23.5	406.51	1	400	2	4.51
6	5	*	8.08	8.08	0.0	0	0	2	6.08	13.4	8.08	0	0	2	6.08
6	6	*	7.85	7.85	0.0	0	0	2	5.85	14.3	9.15	0	0	2	7.15
6	7	*	7.87	7.87	0.0	0	0	2	5.87	6.7	8.44	0	0	2	6.44
6	8	*	6.53	6.53	0.0	0	0	2	4.53	13.6	7.22	0	0	2	5.22
6	9	*	7.02	7.02	0.0	0	0	2	5.02	13.8	8.02	0	0	2	6.02
6	10	*	5.59	5.59	0.0	0	0	1	4.59	16.8	5.92	0	0	1	4.92
7	1	*	9.25	9.25	0.0	0	0	2	7.25	15.1	9.25	0	0	2	7.25
7	2	*	8.90	8.90	0.0	0	0	2	6.90	21.8	8.90	0	0	2	6.90
7	3	*	10.90	10.90	0.0	0	0	2	8.90	14.5	10.90	0	0	2	8.90
7	4	*	10.12	10.12	0.0	0	0	2	8.12	23.4	10.20	0	0	2	8.20
7	5	*	8.93	8.93	0.0	0	0	2	6.93	14.7	9.21	0	0	2	7.21
7	6	*	7.44	7.44	0.0	0	0	2	5.44	19.3	8.51	0	0	2	6.51
7	7	*	8.77	8.77	0.0	0	0	2	6.77	16.0	9.56	0	0	2	7.56
7	8	*	6.88	6.88	0.0	0	0	2	4.88	20.0	6.88	0	0	2	4.88
7	9	*	8.87	8.87	0.0	0	0	2	6.87	19.4	8.87	0	0	2	6.87
7	10	*	7.65	7.65	0.0	0	0	2	5.65	20.0	7.65	0	0	2	5.65
8	1	*	9.32	9.32	0.0	0	0	2	7.32	28.8	9.75	0	0	2	7.75
8	2	*	109.14	109.14	0.0	1	100	2	7.14	83.2	109.14	1	100	2	7.14
8	3	*	9.49	9.49	0.0	0	0	2	7.49	32.1	10.56	0	0	2	8.56
8	4	*	9.04	9.04	0.0	0	0	2	7.04	39.1	9.04	0	0	2	7.04
8	5	*	8.86	8.86	0.0	0	0	2	6.86	28.5	8.86	0	0	2	6.86
8	6	*	9.09	9.09	0.0	0	0	2	7.09	42.6	209.58	1	200	2	7.58
8	7	*	8.59	8.59	0.0	0	0	2	6.59	33.1	10.16	0	0	2	8.16
8	8	*	7.34	7.34	0.0	0	0	1	6.34	37.5	7.34	0	0	2	5.34
8	9	*	6.43	6.43	0.0	0	0	2	4.4	35.3	7.31	0	0	1	6.31
8	10	*	10.07	10.07	0.0	0	0	2	8.1	48.5	411.10	0	0	401	10.10
9	1	*	7.31	7.31	0.0	0	0	2	5.3	59.4	7.39	0	0	2	5.39
9	2	21,600.0	412.25	7.66	98.1	0	0	402	TBD	68.4	506.89	4	500	2	4.89
9	3	*	10.28	10.28	0.0	0	0	2	8.3	44.0	10.32	0	0	2	8.32
9	4	*	7.88	7.88	0.0	0	0	2	5.9	64.2	7.82	0	0	2	5.82
9	5	*	9.42	9.42	0.0	0	0	2	7.4	54.5	109.15	1	100	2	7.15
9	6	*	10.82	10.82	0.0	0	0	2	8.82	44.5	10.94	0	0	2	8.94
9	7	*	5.47	5.47	0.0	0	0	2	3.47	53.7	5.69	0	0	2	3.69
9	8	*	7.90	7.90	0.0	0	0	2	5.90	49.9	10.24	0	0	2	8.24
9	9	*	11.29	11.29	0.0	0	0	2	9.29	73.4	11.29	0	0	2	9.29
9	10	*	11.10	11.10	0.0	0	0	2	9.10	43.9	11.08	0	0	2	9.08
10	1	*	8.75	8.75	0.0	0	0	2	6.75	72.8	109.22	1	100	2	7.22
10	2	*	10.52	10.52	0.0	0	0	2	8.52	99.0	10.91	0	0	2	8.91
10	3	*	12.84	12.84	0.0	0	0	2	10.84	80.9	12.84	0	0	2	10.84
10	4	*	10.37	10.37	0.0	0	0	2	8.37	84.1	11.72	0	0	2	9.72
10	5	*	11.54	11.54	0.0	0	0	2	9.54	62.4	11.68	0	0	2	9.68
10	6	*	6.76	6.76	0.0	0	0	2	4.76	108.0	6.76	0	0	2	4.76
10	7	21,600.0	408.75	3.63	99.1	0	0	401	7.75	92.6	409.97	0	0	401	8.97
10	8	*	9.23	9.23	0.0	0	0	2	7.23	66.3	9.24	0	0	2	7.24
10	9	*	7.72	7.72	0.0	0	0	2	5.72	76.4	10.24	0	0	2	8.24
10	10	*	10.11	10.11	0.0	0	0	2	8.11	97.5	10.53	0	0	2	8.53
20	1	21,600.0	–	2.23	–	–	–	–	–	1032.9	419.56	0	0	402	17.56
20	2	21,600.0	–	1.82	–	–	–	–	–	646.2	26,014.37	1	25,600	402	12.37
20	3	21,600.0	–	2.43	–	–	–	–	–	868.2	417.18	0	0	402	15.18
20	4	21,600.0	–	2.01	–	–	–	–	–	771.9	416.38	0	0	402	14.38
20	5	21,600.0		1.24	–	–	–	–	–	876.2	419.68	0	0	402	17.68
20	6	21,600.0	–	2.09	–	–	–	–	–	832.1	416.69	0	0	402	14.69
20	7	21,600.0	–	1.48	–	–	–	–	–	874.6	414.25	0	0	402	12.25
20	8	21,600.0	–	1.84	–	–	–	–	–	875.5	415.29	0	0	402	13.29
20	9	21,600.0	–	2.30	–	–	–	–	–	452.8	415.86	0	0	402	13.86
20	10	21,600.0	–	2.31	–	–	–	–	–	663.5	415.26	0	0	402	13.26
30	1	21,600.0	–	0.94	–	–	–	–	–	2614.7	419.64	0	0	402	17.64
30	2	21,600.0	–	0.25	–	–	–	–	–	2963.3	520.18	1	100	402	18.18
30	3	21,600.0	–	1.18	–	–	–	–	–	2935.5	719.16	2	300	402	17.16
30	4	21,600.0	–	1.95	–	–	–	–	–	3099.1	519.52	1	100	402	17.52
30	5	21,600.0	–	0.94	–	–	–	–	–	1930.6	816.81	1	400	402	14.81
30	6	21,600.0	–	0.46	–	–	–	–	–	2125.9	821.17	2	400	402	19.17
30	7	21,600.0	–	0.00	–	–	–	–	–	3282.1	419.93	0	0	402	17.93
30	8	21,600.0	–	1.60	–	–	–	–	–	1933.9	719.08	2	300	402	17.08
30	9	21,600.0	–	0.51	–	–	–	–	–	3198.8	519.53	1	100	402	17.53
30	10	21,600.0	–	1.18	–	–	–	–	–	1452.8	618.99	1	200	402	16.99

Note(s): * Alternative MILP solution method used

− Gurobi was not able to find values

Source(s): Table by authors

[ViewLarge]

Sharing Unavailable