Branch and Cut for Vehicle Routing

Vehicle Routing Data Sets

This page contains data sets for the Capacitated Vehicle Routing Problem gathered from various sources identified below. By clicking on the links, you can also get charts listing the charactersitics of the various instances, as well as an optimal solution where one is known. There are some gaps in the charts---we are working on filling them out completely and verifying all the data. Please let us know if you find any mistakes or know of more recent results.

Download the entire library (tar file) (zip file)

Description of file format

Augerat, et al. Set A

Augerat, et al. Set B

Augerat, et al. Set P

Christofides and Eilon

Fisher

Gillet and Johnson

Christofides, Mingozzi, and Toth

Converted TSPLIB Problems

The best solutions and gaps listed here are from the following papers that report computational results:

P. Augerat, J.M. Belenguer, E. Benavent, A. Corberán, D. Naddef, G. Rinaldi, Computational Results with a Branch and Cut Code for the Capacitated Vehicle Routing Problem, Research Report 949-M, Universite Joseph Fourier, Grenoble, France.
U. Blasum and W. Hochstattler, Application of the Branch and Cut Method to the Vehicle Routing Problem, Zentrum fur Angewandte Informatik Koln Technical Report zpr2000-386 (2000).
R. Fukasawa, M. Poggi de Aragao, M. Reis, and E. Uchoa, Robust Branch-and-Cut-and-Price for the Vehicle Routing Problem, Relatorios de Pesquisa em Engenharia de Producao RPEP Vol. 3 No. 8 (2003).
J. Lysgaard, A.N. Letchford, and R.W. Eglese, A New Branch-and-cut Algorithm for Capacitated Vehicle Routing Problems, submitted to Mathematical Programming (2003).
T.K. Ralphs, L. Kopman, W.R. Pulleyblank, and L.E. Trotter Jr., On the Capacitated Vehicle Routing Problem, Mathematical Programming Series B 94 (2003), 343.
K. Wenger, Personal Communication (2003).

Augerat, et al. Set A (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Upper Bound	Optimal Solution
A-n32-k5.vrp	General	Euc 2D	31	5	100	0.82	784	A-n32-k5.opt
A-n33-k5.vrp	General	Euc 2D	32	5	100	0.89	661	A-n33-k5.opt
A-n33-k6.vrp	General	Euc 2D	32	6	100	0.90	742	A-n33-k6.opt
A-n34-k5.vrp	General	Euc 2D	33	5	100	0.92	778	A-n34-k5.opt
A-n36-k5.vrp	General	Euc 2D	35	5	100	0.88	799	A-n36-k5.opt
A-n37-k5.vrp	General	Euc 2D	36	5	100	0.81	669	A-n37-k5.opt
A-n37-k6.vrp	General	Euc 2D	36	6	100	0.95	949	A-n37-k6.opt
A-n38-k5.vrp	General	Euc 2D	37	5	100	0.96	730	A-n38-k5.opt
A-n39-k5.vrp	General	Euc 2D	38	5	100	0.95	822	A-n39-k5.opt
A-n39-k6.vrp	General	Euc 2D	38	6	100	0.88	831	A-n39-k6.opt
A-n44-k6.vrp	General	Euc 2D	43	6	100	0.95	937	A-n44-k6.opt
A-n45-k6.vrp	General	Euc 2D	44	6	100	0.99	944	A-n45-k6.opt
A-n45-k7.vrp	General	Euc 2D	44	7	100	0.91	1146	A-n45-k7.opt
A-n46-k7.vrp	General	Euc 2D	45	7	100	0.86	914	A-n46-k7.opt
A-n48-k7.vrp	General	Euc 2D	47	7	100	0.89	1073	A-n48-k7.opt
A-n53-k7.vrp	General	Euc 2D	52	7	100	0.95	1010	A-n53-k7.opt
A-n54-k7.vrp	General	Euc 2D	53	7	100	0.96	1167	A-n54-k7.opt
A-n55-k9.vrp	General	Euc 2D	54	9	100	0.93	1073	A-n55-k9.opt
A-n60-k9.vrp	General	Euc 2D	59	9	100	0.92	1354	A-n60-k9.opt
A-n61-k9.vrp	General	Euc 2D	60	9	100	0.98	1034	A-n61-k9.opt
A-n62-k8.vrp	General	Euc 2D	61	8	100	0.92	1288	A-n62-k8.opt
A-n63-k9.vrp	General	Euc 2D	62	9	100	0.97	1616	A-n63-k9.opt
A-n63-k10.vrp	General	Euc 2D	62	10	100	0.93	1314	A-n63-k10.opt
A-n64-k9.vrp	General	Euc 2D	63	9	100	0.94	1401	A-n64-k9.opt
A-n65-k9.vrp	General	Euc 2D	64	9	100	0.97	1174	A-n65-k9.opt
A-n69-k9.vrp	General	Euc 2D	68	9	100	0.94	1159	A-n69-k9.opt
A-n80-k10.vrp	General	Euc 2D	79	10	100	0.94	1763	A-n80-k10.opt

Augerat, et al. Set B (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Upper Bound	Optimal Solution
B-n31-k5.vrp	General	Euc 2D	30	5	100	0.82	672	B-n31-k5.opt
B-n34-k5.vrp	General	Euc 2D	33	5	100	0.91	788	B-n34-k5.opt
B-n35-k5.vrp	General	Euc 2D	34	5	100	0.87	955	B-n35-k5.opt
B-n38-k6.vrp	General	Euc 2D	37	6	100	0.85	805	B-n38-k6.opt
B-n39-k5.vrp	General	Euc 2D	38	5	100	0.88	549	B-n39-k5.opt
B-n41-k6.vrp	General	Euc 2D	40	6	100	0.95	829	B-n41-k6.opt
B-n43-k6.vrp	General	Euc 2D	42	6	100	0.87	742	B-n43-k6.opt
B-n44-k7.vrp	General	Euc 2D	43	7	100	0.92	909	B-n44-k7.opt
B-n45-k5.vrp	General	Euc 2D	44	4	100	0.97	751	B-n45-k5.opt
B-n45-k6.vrp	General	Euc 2D	44	6	100	0.99	678	B-n45-k6.opt
B-n50-k7.vrp	General	Euc 2D	49	7	100	0.87	741	B-n50-k7.opt
B-n50-k8.vrp	General	Euc 2D	49	8	100	0.92	1312	B-n50-k8.opt
B-n51-k7.vrp**	General	Euc 2D	50	7	100	0.98	1032	B-n51-k7.opt
B-n52-k7.vrp	General	Euc 2D	51	7	100	0.87	747	B-n52-k7.opt
B-n56-k7.vrp	General	Euc 2D	55	7	100	0.88	707	B-n56-k7.opt
B-n57-k7.vrp**	General	Euc 2D	56	7	100	1.00	1153	B-n57-k7.opt
B-n57-k9.vrp	General	Euc 2D	56	9	100	0.89	1598	B-n57-k9.opt
B-n63-k10.vrp	General	Euc 2D	62	10	100	0.92	1496	B-n63-k10.opt
B-n64-k9.vrp	General	Euc 2D	63	9	100	0.98	861	B-n64-k9.opt
B-n66-k9.vrp	General	Euc 2D	65	9	100	0.96	1316	B-n66-k9.opt
B-n67-k10.vrp	General	Euc 2D	66	10	100	0.91	1032	B-n67-k10.opt
B-n68-k9.vrp	General	Euc 2D	67	9	100	0.93	1272	B-n68-k9.opt
B-n78-k10.vrp	General	Euc 2D	77	10	100	0.94	1221	B-n78-k10.opt

** Note that for these instances, increasing the number of trucks by 1 decreases the optimal value.

Augerat, et al. Set P (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Upper Bound	Optimal Solution
P-n16-k8.vrp	General	Euc 2D	15	8	35	0.88	450	P-n16-k8.opt
P-n19-k2.vrp	General	Euc 2D	18	2	160	0.97	212	P-n19-k2.opt
P-n20-k2.vrp	General	Euc 2D	19	2	160	0.97	216	P-n20-k2.opt
P-n21-k2.vrp	General	Euc 2D	20	2	160	0.93	211	P-n21-k2.opt
P-n22-k2.vrp	General	Euc 2D	21	2	160	0.96	216	P-n22-k2.opt
P-n22-k8.vrp	General	Euc 2D	21	8	3000	0.94	603	P-n22-k8.opt
P-n23-k8.vrp	General	Euc 2D	22	8	40	0.98	529	P-n23-k8.opt
P-n40-k5.vrp	General	Euc 2D	39	5	140	0.88	458	P-n40-k5.opt
P-n45-k5.vrp	General	Euc 2D	44	5	150	0.92	510	P-n45-k5.opt
P-n50-k7.vrp	General	Euc 2D	49	7	150	0.91	554	P-n50-k7.opt
P-n50-k8.vrp	General	Euc 2D	49	8	120	0.99	631	P-n50-k8.opt
P-n50-k10.vrp	General	Euc 2D	49	10	100	0.95	696	P-n50-k10.opt
P-n51-k10.vrp	General	Euc 2D	50	10	80	0.97	741	P-n51-k10.opt
P-n55-k7.vrp	General	Euc 2D	54	7	170	0.88	568	P-n55-k7.opt
P-n55-k8.vrp	General	Euc 2D	54	8	160	0.81	588	P-n55-k8.opt
P-n55-k10.vrp	General	Euc 2D	54	10	115	0.91	694	P-n55-k10.opt
P-n55-k15.vrp	General	Euc 2D	54	15	70	0.99	989	P-n55-k15.opt
P-n60-k10.vrp	General	Euc 2D	59	10	120	0.95	744	P-n60-k10.opt
P-n60-k15.vrp	General	Euc 2D	59	15	80	0.95	968	P-n60-k15.opt
P-n65-k10.vrp	General	Euc 2D	64	10	130	0.94	792	P-n65-k10.opt
P-n70-k10.vrp	General	Euc 2D	69	10	135	0.97	827	P-n70-k10.opt
P-n76-k4.vrp	General	Euc 2D	75	4	350	0.97	593	P-n76-k4.opt
P-n76-k5.vrp	General	Euc 2D	75	5	280	0.97	627	P-n76-k5.opt
P-n101-k4.vrp	General	Euc 2D	100	4	400	0.91	681	P-n101-k4.opt

Christofides and Eilon (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Gap %	Upper Bound	Optimal Solution
E-n13-k4.vrp	General	Explicit	12	5	6000	0.76	0	247	E-n13-k4.opt
E-n22-k4.vrp	General	Euc 2D	21	4	6000	0.94	0	375	E-n22-k4.opt
E-n23-k3.vrp	General	Euc 2D	22	3	4500	0.75	0	569	E-n23-k3.opt
E-n30-k3.vrp**	General	Euc 2D	29	3	4500	0.94	0	534	E-n30-k3.opt
E-n31-k7.vrp**	General	Explicit	30	7	140	0.92	0	379	E-n31-k7.opt
E-n33-k4.vrp	General	Euc 2D	32	4	8000	0.92	0	835	E-n33-k4.opt
E-n51-k5.vrp	General	Euc 2D	50	5	160	0.97	0	521	E-n51-k5.opt
E-n76-k7.vrp	General	Euc 2D	75	7	220	0.89	0	682	E-n76-k7.opt
E-n76-k8.vrp	General	Euc 2D	75	8	180	0.95	0.82	735
E-n76-k10.vrp	General	Euc 2D	75	10	140	0.97	0	830	E-n76-k10.opt
E-n76-k14.vrp	General	Euc 2D	75	14	100	0.97	0	1021	E-n76-k14.opt
E-n101-k8.vrp	General	Euc 2D	100	8	200	0.91	0.49	815
E-n101-k14.vrp	General	Euc 2D	100	14	112	0.93	2.89	1071

** Note that for these instances, increasing the number of trucks by 1 decreases the optimal value.

Fisher (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Upper Bound	Optimal Solution
F-n45-k4.vrp	General	Euc 2D	44	4	2010	0.90	724	F-n45-k4.opt
F-n72-k4.vrp	General	Euc 2D	71	4	30000	0.96	237	F-n72-k4.opt
F-n135-k7.vrp	General	Euc 2D	134	7	2210	0.95	1162	F-n135-k7.opt

Gillet and Johnson (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Gap %	Upper Bound	Optimal Solution
G-n262-k25.vrp	General	Euc 2D	261	25	500	0.97	17.24	6119

Christofides, Mingozzi, and Toth (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Gap %	Upper Bound	Optimal Solution
M-n101-k10.vrp	General	Euc 2D	100	10	200	0.91	0	820	M-n101-k10.opt
M-n121-k7.vrp	General	Euc 2D	120	7	200	0.98	0	1034	M-n121-k7.opt
M-n151-k12.vrp	General	Euc 2D	150	12	200	0.93	7.69	1053
M-n200-k16.vrp	General	Euc 2D	199	16	200	1.00
M-n200-k17.vrp	General	Euc 2D	199	17	200	0.94	13.55	1373

Converted TSPLIB Problems (tar file)(zip file)

Problem Instance	Demand Type	Distance Type	# of Customers	# of Vehicles	Vehicle Capacity	Tightness (Demand/Capacity)	Upper Bound	Optimal Solution
att-n48-k4.vrp	Unit	Euc 2D	47	4	15	0.73	40002	att-n48-k4.opt
bayg-n29-k4.vrp	Unit	Explicit	28	4	8	0.88	2050	bayg-n29-k4.opt
bays-n29-k5.vrp	Unit	Explicit	28	5	6	0.93	2963	bays-n29-k5.opt
dantzig-n42-k4.vrp	Unit	Explicit	41	4	11	0.93	1142	dantzig-n42-k4.opt
fri-n26-k3.vrp	Unit	Explicit	25	3	10	0.83	1353	fri-n26-k3.opt
gr-n17-k3.vrp	Unit	Explicit	16	3	6	0.89	2685	gr-n17-k3.opt
gr-n21-k3.vrp	Unit	Explicit	20	3	7	0.95	3704	gr-n21-k3.opt
gr-n24-k4.vrp	Unit	Explicit	23	4	7	0.82	2053	gr-n24-k4.opt
gr-n48-k3.vrp	Unit	Explicit	47	3	16	0.98	5985	gr-n48-k3.opt
hk-n48-k4.vrp	Unit	Explicit	47	4	15	0.78	14749	hk-n48-k4.opt
swiss-n42-k5.vrp	Unit	Explicit	41	5	9	0.92	1668	swiss-n42-k5.opt
ulysses-n16-k3.vrp	Unit	Geo	15	3	5	1.00	7965	ulysses-n16-k3.opt
ulysses-n22-k4.vrp	Unit	Geo	21	4	6	0.88	9179	ulysses-n22-k4.opt

This page maintained by Ted Ralphs (ted@branchandcut.org)

Last updated October 3, 2003