Known Results for Solomon Instances
This section reports computational results showing the efficiency of the main algorithms for VRP. The algorithms have been tested on a classical set of 56 benchmark problems (Solomon, 1987) composed of six different problem types (C1, C2, R1, R2, RC1, RC2). Each data set contains between eight and twelve 100-node problems. The names of the six problem types have the following meaning. Sets C have clustered customers whose time windows were generated based on a known solution. Problem sets R have customer locations generated uniformly randomly over a square. Sets RC have a combination of randomly placed and clustered customers. Sets of type 1 have narrow time windows and small vehicle capacity. Sets of type 2 have large time windows and large vehicle capacity. Therefore, the solutions of type 2 problems have very few routes and significantly more customers per route.
Tables 1 and 2 below include the results of the main heuristic methods for solving VRP. Table 1 contains route construction heuristics, while Table 2 features local search algorithms. For each problem class, the average number of vehicles (bold) and the average tour length are shown.
| Author | R1 | R2 | C1 | C2 | RC1 | RC2 |
|---|---|---|---|---|---|---|
| (1) Solomon (1987) | 13.58 1436.7 | 3.27 1402.4 | 10.00 951.9 | 3.13 692.7 | 13.50 1596.5 | 3.88 1682.1 |
| (2) Potvin et al. (1993) | 13.33 1509.04 | 3.09 1386.67 | 10.67 1343.69 | 3.38 797.59 | 13.38 1723.72 | 3.63 1651.05 |
| (3) Ioannou et al. (2001) | 12.67 1370 | 3.09 1310 | 10.00 865 | 3.13 662 | 12.50 1512 | 3.50 1483 |
Computational effort: (1) DEC 10, 1 run, 0.6 min., (2) IBM PC, 1 run, 19.6 min., (3) Intel Pentium 133 MHz, 1 run, 4.0 min.
| Author | R1 | R2 | C1 | C2 | RC1 | RC2 |
|---|---|---|---|---|---|---|
| (1) Thompson et al. (1993) | 13.00 1356.92 | 3.18 1276.00 | 10.00 916.67 | 3.00 644.63 | 13.00 1514.29 | 3.71 1634.43 |
| (2) Potvin et al. (1995) | 13.33 1381.9 | 3.27 1293.4 | 10.00 902.9 | 3.13 653.2 | 13.25 1545.3 | 3.88 1595.1 |
| (3) Russell (1995) | 12.66 1317 | 2.91 1167 | 10.00 930 | 3.00 681 | 12.38 1523 | 3.38 1398 |
| (4) Antes et al. (1995) | 12.83 1386.46 | 3.09 1366.48 | 10.00 955.39 | 3.00 717.31 | 12.50 1545.92 | 3.38 1598.06 |
| (5) Prosser et al. (1996) | 13.50 1242.40 | 4.09 977.12 | 10.00 843.84 | 3.13 607.58 | 13.50 1408.76 | 5.13 1111.37 |
| (6) Shaw (1997) | 12.31 1205.06 | ____ | 10.00 828.38 | ____ | 12.00 1360.40 | ____ |
| (7) Shaw (1998) | 12.33 1201.79 | ____ | 10.00 828.38 | ____ | 11.95 1364.17 | ____ |
| (8) Cordone et al. (1998) | 12.50 1241.89 | 2.91 995.39 | 10.00 834.05 | 3.00 591.78 | 12.38 1408.87 | 3.38 1139.70 |
| (9) Caseau et al. (1999) | 12.42 1233.34 | 3.09 990.99 | 10.00 828.38 | 3.00 596.63 | 12.00 1403.74 | 3.38 1220.99 |
| (10) Bräysy (2001a) | 12.17 1253.24 | 2.82 1039.56 | 10.00 832.88 | 3.00 593.49 | 11.88 1408.44 | 3.25 1244.96 |
Computational effort: (1) PC/AT 12 MHz, 4 runs, 1.8 min., (2) Sparc workstation, number of runs not reported, 3.0 min., (3) PC/486/DX2 66 MHz, 3 runs, 1.4 min., (4) RS6000/530, 4 runs, 3.6 min., (5) Computational effort not reported, (6) DEC Alpha, 3 runs, 2 hours, (7) Sun Ultra Sparc 143 MHz, 6 runs, 1 hour, (8) Pentium 166 MHz, 1 run, 15.7 min., (9) Pentium 300 MHz, 1 run, 5 min., (10) Pentium 200 MHz, 1 run, 4.6 min.
The table below includes the results of the methods of Rochat and Taillard (more results of Tabu Search Algorithms), 1995 (RT), Taillard et al., 1997 (TB), the hybrid method of Chiang and Russel, 1993 (CR), the genetic algorithm of Potvin and Bengio (results with other Genetic Algorithms), 1996 (PB) and the hybrid method of Thangiah et al., 1994 (TH). It contains the average number of vehicles (VEI, main goal) and the average tour length (DIST). Values in bold are the best among the methods shown.
| Algorithm | R1 | C1 | RC1 | R2 | C2 | RC2 | ||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| VEI | DIST | VEI | DIST | VEI | DIST | VEI | DIST | VEI | DIST | VEI | DIST | |
| MACS-VRPTW | 12.00 | 1217.73 | 10.00 | 828.38 | 11.63 | 1382.42 | 2.73 | 967.75 | 3.00 | 589.86 | 3.25 | 1129.19 |
| RT | 12.25 | 1208.50 | 10.00 | 828.38 | 11.88 | 1377.39 | 2.91 | 961.72 | 3.00 | 589.86 | 3.38 | 1119.59 |
| TB | 12.17 | 1209.35 | 10.00 | 828.38 | 11.50 | 1389.22 | 2.82 | 980.27 | 3.00 | 589.86 | 3.38 | 1117.44 |
| CR | 12.42 | 1289.95 | 10.00 | 885.86 | 12.38 | 1455.82 | 2.91 | 1135.14 | 3.00 | 658.88 | 3.38 | 1361.14 |
| PB | 12.58 | 1296.80 | 10.00 | 838.01 | 12.13 | 1446.20 | 3.00 | 1117.70 | 3.00 | 589.93 | 3.38 | 1360.57 |
| TH | 12.33 | 1238.00 | 10.00 | 832.00 | 12.00 | 1284.00 | 3.00 | 1005.00 | 3.00 | 650.00 | 3.38 | 1229.00 |