Known Best Results

The known best so far values for many of the instances published in this site are shown here.

Figures with an ‘*’ correspond to optimal values, which are obtained from [ABBCNR], [BH00], [FPRU03], [LLE03], [RKPT03], [Weng03] and [RT95].

New best results

Augerat et al. instances

For the instances in the class `A’, both customer locations and demands are random. The instances in class `B’, however, are clustered instances. The instances in class `P’ are modified versions of instances from the literature.

Instance (Set A) Best Known Value
A-n32-k5 784*
A-n33-k5 661*
A-n33-k6 742*
A-n34-k5 778*
A-n36-k5 799*
A-n37-k5 669*
A-n37-k6 949*
A-n38-k5 730*
A-n39-k5 822*
A-n39-k6 831*
A-n44-k6 937*
A-n45-k6 944*
A-n45-k7 1146*
A-n46-k7 914*
A-n48-k7 1073*
A-n53-k7 1010*
A-n54-k7 1167*
A-n55-k9 1073*
A-n60-k9 1354*
A-n61-k9 1034*
A-n62-k8 1288*
A-n63-k9 1616*
A-n63-k10 1314*
A-n64-k9 1401*
A-n65-k9 1174*
A-n69-k9 1159*
A-n80-k10 1763*
Instance (Set B) Best Known Value
B-n31-k5 672*
B-n34-k5 788*
B-n35-k5 955*
B-n38-k6 805*
B-n39-k5 549*
B-n41-k6 829*
B-n43-k6 742*
B-n44-k7 909*
B-n45-k5 751*
B-n45-k6 678*
B-n50-k7 741*
B-n50-k8 1312*
B-n51-k7 1018*
B-n52-k7 747*
B-n56-k7 707*
B-n57-k7 1144*
B-n57-k9 1598*
B-n63-k10 1496*
B-n64-k9 861*
B-n66-k9 1316*
B-n67-k10 1032*
B-n68-k9 1272*
B-n78-k10 1221*
Instance (Set P) Best Known Value
P-n16-k8 450*
P-n19-k2 212*
P-n20-k2 216*
P-n21-k2 211*
P-n22-k2 216*
P-n22-k8 590*
P-n23-k8 529*
P-n40-k5 458*
P-n45-k5 510*
P-n50-k7 554*
P-n50-k8 629*
P-n50-k10 696*
P-n51-k10 741*
P-n55-k7 568*
P-n55-k10 694*
P-n55-k15 945*
P-n60-k10 744*
P-n60-k15 968*
P-n65-k10 792*
P-n70-k10 827*
P-n76-k4 593*
P-n76-k5 627*
P-n101-k4 681*

Christofides and Eilon instances

Instance Best Known Value
E-n13-k4 247*
E-n22-k4 375*
E-n23-k3 569*
E-n30-k3 534*
E-n30-k4 —
E-n31-k7 379*
E-n33-k4 835*
E-n51-k5 521*
E-n76-k7 682*
E-n76-k8 735
E-n76-k10 830*
E-n76-k14 1021*
E-n76-k15 —
E-n101-k8 815
E-n101-k14 1071

Christofides, Mingozzi and Toth

Instance Best Known Value
vrpnc1 524.61
vrpnc2 835.26
vrpnc3 826.14
vrpnc4 1028.42
vrpnc5 1291.29
vrpnc6 555.43
vrpnc7 909.68
vrpnc8 865.94
vrpnc9 1162.55
vrpnc10 1395.85
vrpnc11 1042.11
vrpnc12 819.56
vrpnc13 1541.14
vrpnc14 866.37

Fisher

Instance Best Known Value
F-n45-k4 724*
F-n72-k4 237*
F-n135-k7 1162*

Taillard

Instance Best Known Value
tai75a 1618.36 [Tai93]
tai75b 1344.62
tai75c 1291.01 [Tai93]
tai75d 1365.42 [Tai93]
tai100a 2041.34 [GTA99]
tai100b 1940.61 [MB05]
tai100c 1406.20 [GTA99]
tai100d 1581.25 [GTA99]
tai150a 3055.23 [Tai93]
tai150b 2656.47 [GTA99]
tai150c 2341.84 [Tai93]
tai150d 2645.39 [Tai93]
tai385 24431.44 [RT95]

Golden et al.

Instance Best Known Value
1 5627.54 [MB05]
2 8447.92 [TK02]
3 11036.23 [TK02]
4 13624.52 [TK02]
5 6460.98 [TK02]
6 8412.88 [TK02]
7 10195.56 [TK02]
8 11663.55 [MB05]
9 583.39 [MB05]
10 742.03 [LGW05]
11 918.45 [MB05]
12 1107.19 [MB05]
13 859.11 [MB05]
14 1081.31 [MB05]
15 1345.23 [MB05]
16 1622.69 [MB05]
17 707.79 [MB05]
18 998.73 [MB05]
19 1366.86 [MB05]
20 1821.15 [MB05]

Van Breedam

Instance Best Known Value
1 1106.00 [AD05]
2 1506.00 [AD05]
3 1751.00 [AD05]
4 1470.00 [AD05]
5 950.00 [AD05]
6 969.00 [AD05]
7 1032.00 [Bre01]
8 1067.00 [Bre01]
9 1690.00 [AD05]
10 1026.00 [AD05]
11 1028.00 [AD05]
12 1616.00 [Bre01]
13 983.00 [Bre01]
14 2337.00 [Bre01]
15 1083.00 [Bre01]