Known Best Results

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

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

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.

Some new best results can be seen at:

 

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

In the next tables we place the known best results for Christofides and Eilon, Christofides, Mingozzi and Toth, Fisher, Taillard, Golden et al. and Van Breedam instances.

Christofides and Eilon
Christofides, Mingozzi and Toth
Fisher
Taillard
Instance Best Known Value
Instance Best Known Value
Instance Best Known Value
Instance Best Known Value
E-n13-k4
247*
vrpnc1
524.61
F-n45-k4
724*
tai75a
1618.36 [Tai93]
E-n22-k4
375*
vrpnc2
835.26
F-n72-k4
237*
tai75b
1344.62 []
E-n23-k3
569*
vrpnc3
826.14
F-n135-k7
1162*
tai75c
1291.01 [Tai93]
E-n30-k3
534*
vrpnc4
1028.42
 
tai75d
1365.42 [Tai93]
E-n30-k4
----
vrpnc5
1291.29
 
tai100a
2041.34 [GTA99]
E-n31-k7
379*
vrpnc6
555.43
 
tai100b
1940.61 [MB05]
E-n33-k4
835*
vrpnc7
909.68
 
tai100c
1406.20 [GTA99]
E-n51-k5
521*
vrpnc8
865.94
 
tai100d
1581.25 [GTA99]
E-n76-k7
682*
vrpnc9
1162.55
 
tai150a
3055.23 [Tai93]
E-n76-k8
735
vrpnc10
1395.85
 
tai150b
2656.47 [GTA99]
E-n76-k10
830*
vrpnc11
1042.11
 
tai150c
2341.84 [Tai93]
E-n76-k14
1021*
vrpnc12
819.56
 
tai150d
2645.39 [Tai93]
E-n76-k15
----
vrpnc13
1541.14
 
tai385
24431.44 [RT95]
E-n101-k8
815
vrpnc14
866.37
 
 
E-n101-k14
1071
     

 

Golden et al.
Van Breedam
Instance Best Known Value
Instance Best Known Value
1
5627.54 [MB05]
1
1106.00 [AD05]
2
8447.92 [TK02]
2
1506.00 [AD05]
3
11036.23 [TK02]
3
1751.00 [AD05]
4
13624.52 [TK02]
4
1470.00 [AD05]
5
6460.98 [TK02]
5
950.00 [AD05]
6
8412.88 [TK02]
6
969.00 [AD05]
7
10195.56 [TK02]
7
1032.00 [Bre01]
8
11663.55 [MB05]
8
1067.00 [Bre01]
9
583.39 [MB05]
9
1690.00 [AD05]
10
742.03 [LGW05]
10
1026.00 [AD05]
11
918.45 [MB05]
11
1028.00 [AD05]
12
1107.19 [MB05]
12
1616.00 [Bre01]
13
859.11 [MB05]
13
983.00 [Bre01]
14
1081.31 [MB05]
14
2337.00 [Bre01]
15
1345.23 [MB05]
15
1083.00 [Bre01]
16
1622.69 [MB05]
 
17
707.79 [MB05]
 
18
998.73 [MB05]
 
19
1366.86 [MB05]
 
20
1821.15 [MB05]