Results

Best Known Results

The best values reported in the literature collected here for many of the instances published on this site are shown below. Specifically:

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

Some new best results can be seen at:

Augerat et al. Instances

For the instances in 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.

Augerat et al. Set A: best known values.
InstanceBest Known Value
A-n32-k5784*
A-n33-k5661*
A-n33-k6742*
A-n34-k5778*
A-n36-k5799*
A-n37-k5669*
A-n37-k6949*
A-n38-k5730*
A-n39-k5822*
A-n39-k6831*
A-n44-k6937*
A-n45-k6944*
A-n45-k71146*
A-n46-k7914*
A-n48-k71073*
A-n53-k71010*
A-n54-k71167*
A-n55-k91073*
A-n60-k91354*
A-n61-k91034*
A-n62-k81288*
A-n63-k91616*
A-n63-k101314*
A-n64-k91401*
A-n65-k91174*
A-n69-k91159*
A-n80-k101763*
Augerat et al. Set B: best known values.
InstanceBest Known Value
B-n31-k5672*
B-n34-k5788*
B-n35-k5955*
B-n38-k6805*
B-n39-k5549*
B-n41-k6829*
B-n43-k6742*
B-n44-k7909*
B-n45-k5751*
B-n45-k6678*
B-n50-k7741*
B-n50-k81312*
B-n51-k71032*
B-n52-k7747*
B-n56-k7707*
B-n57-k71153*
B-n57-k91598*
B-n63-k101496*
B-n64-k9861*
B-n66-k91316*
B-n67-k101032*
B-n68-k91272*
B-n78-k101221*
Augerat et al. Set P: best known values.
InstanceBest Known Value
P-n16-k8450*
P-n19-k2212*
P-n20-k2216*
P-n21-k2211*
P-n22-k2216*
P-n22-k8603*
P-n23-k8529*
P-n40-k5458*
P-n45-k5510*
P-n50-k7554*
P-n50-k8631*
P-n50-k10696*
P-n51-k10741*
P-n55-k7568*
P-n55-k10694*
P-n55-k15989*
P-n60-k10744*
P-n60-k15968*
P-n65-k10792*
P-n70-k10827*
P-n76-k4593*
P-n76-k5627*
P-n101-k4681*

Other Benchmark Instances

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

Christofides and Eilon instances: best known values.
InstanceBest Known Value
E-n13-k4247*
E-n22-k4375*
E-n23-k3569*
E-n30-k3534*
E-n30-k4----
E-n31-k7379*
E-n33-k4835*
E-n51-k5521*
E-n76-k7682*
E-n76-k8735
E-n76-k10830*
E-n76-k141021*
E-n76-k15----
E-n101-k8815
E-n101-k141071
Christofides, Mingozzi and Toth instances: best known values.
InstanceBest Known Value
vrpnc1524.61
vrpnc2835.26
vrpnc3826.14
vrpnc41028.42
vrpnc51291.29
vrpnc6555.43
vrpnc7909.68
vrpnc8865.94
vrpnc91162.55
vrpnc101395.85
vrpnc111042.11
vrpnc12819.56
vrpnc131541.14
vrpnc14866.37
Fisher instances: best known values.
InstanceBest Known Value
F-n45-k4724*
F-n72-k4237*
F-n135-k71162*
Taillard instances: best known values.
InstanceBest Known Value
tai75a1618.36 [Tai93]
tai75b1344.62
tai75c1291.01 [Tai93]
tai75d1365.42 [Tai93]
tai100a2041.34 [GTA99]
tai100b1940.61 [MB05]
tai100c1406.20 [GTA99]
tai100d1581.25 [GTA99]
tai150a3055.23 [Tai93]
tai150b2656.47 [GTA99]
tai150c2341.84 [Tai93]
tai150d2645.39 [Tai93]
tai38524431.44 [RT95]
Golden et al. instances: best known values.
InstanceBest Known Value
15627.54 [MB05]
28447.92 [TK02]
311036.23 [TK02]
413624.52 [TK02]
56460.98 [TK02]
68412.88 [TK02]
710195.56 [TK02]
811663.55 [MB05]
9583.39 [MB05]
10742.03 [LGW05]
11918.45 [MB05]
121107.19 [MB05]
13859.11 [MB05]
141081.31 [MB05]
151345.23 [MB05]
161622.69 [MB05]
17707.79 [MB05]
18998.73 [MB05]
191366.86 [MB05]
201821.15 [MB05]
Van Breedam instances: best known values.
InstanceBest Known Value
11106.00 [AD05]
21506.00 [AD05]
31751.00 [AD05]
41470.00 [AD05]
5950.00 [AD05]
6969.00 [AD05]
71032.00 [Bre01]
81067.00 [Bre01]
91690.00 [AD05]
101026.00 [AD05]
111028.00 [AD05]
121616.00 [Bre01]
13983.00 [Bre01]
142337.00 [Bre01]
151083.00 [Bre01]

Back to top