MACS-VRPTW:  A Multiple Ant Colony System for Vehicle Routing Problems with  Time Windows (VRPTW)

IDSIA  Istituto Dalle Molle di Studi sull'Intelligenza Artificiale Galleria 2, 6928 Manno-Lugano - CH Phone: +41 91 - 6108663 Fax: +41 91 - 6108661 email: luca@idsia.ch

Numerical results for the Solomon Problems

MACS-VRPTW has 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 to 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 customers location 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.

Experiments are made by executing, for each problem data, 3 runs that are stopped after a fixed computation time. Solutions are then averaged for each problem type and the result is reported in the tables. Experiments have been done with the following parameter settings: m=10 ants, q₀=0.9, b =1 and r =0.1. The code was written in C++.

Table 1. Performance comparison among the best VRPTW algorithms for different computational time (in seconds). RT=Rochat and Taillard (1995), SW = Shaw (1998), KPS = Kilby, Prosser and Shaw (1999), CW = Cordone and Wolfler-Calvo (1998), TB= Taillard et al. (1997)

Table 1 compares MACS-VRPTW with a number of the best methods available for the VRPTW. The methods considered are: the adaptive memory programming of Rochat and Taillard, 1995 (RT), the large neighbourhood search of Shaw, 1998 (SW), the guided local search of Kilby, Prosser and Shaw, 1999 (KPS), the alternate K-exchange Reduction of Cordone and Wolfler-Calvo, 1998 (CW) and the adaptive memory programming of Taillard et al., 1997 (TB). Table 1 provides 3 columns for each data set: the average number of vehicles (main goal), the average tour length and the computation time (in seconds). The computational times cannot be directly compared for different reasons. First, the authors have used different computers; second, some methods (RT and TB) were designed to solve harder problems than the VRPTW and implementations specifically designed for the VRPTW might be faster.

Table 2. Average of the best solutions computed by different VRPTW algorithms. Best results are in boldface. RT=Rochat and Taillard (1995), TB= Taillard et al. (1997), CR=Chiang and Russel (1993), PB=Potvin and Bengio (1996), TH= Thangiah et al. (1994)

MACS-VRPTW was executed on a Sun UltraSparc 1 167MHz, 70 Mflop/s (Dongarra, 1997), RT used a 15 Mflop/s Silicon Graphics computer, SW used a 63 Mflop/s Sun UltraSparc, KPS used a 25Mflops/s DEC Alpha, CW used a 18 Mflop/s Pentium and TB used a 10 Mflop/s Sun Sparc 10. Table 1 provides computational results for MACS-VRPTW when stopped after 100, 300, 600, 1200 and 1800 seconds. The RT, SW and TB iterative methods were also stopped after different computation times while KPS and CW provide results for a unique computation time.

In Table 1 is shown that MACS-VRPTW is very competitive: for C1 and RC2 types it is clearly the best method and it is always among the best methods for the other problem sets. A characteristic of MACS-VRPTW is that it is able to produce relatively good solutions in a short amount of time.

Table 2 reports the average of the best solutions obtained in all our experiments. Similar results were also provided by other authors. In addition to the methods of Rochat and Taillard, 1995 (RT) and Taillard et al., 1997 (TB) already compared in Table 1, Table 2 includes the results of the hybrid method of Chiang and Russel (CR, 1993), the genetic algorithm of Potvin and Bengio (PB, 1996) and the hybrid method of Thangiah et al. (TH, 1994). With the exception of RC1 type problem, MACS-VRPTW has been able to produce the best results for all other problem types.

During this experimental campaign, the best solution known of a number of problem instances have been improved. The value of these new best solutions are reported in Table 3. In addition to the VRPTW instances the ACS-TIME colony has been tested on CVRP instances. In Table 3 are also reported new best solution value for CVRP problem instances tainnn used in Rochat and Taillard (1995), where nnn stands for the number of customers.

Table 3. New best solution values computed by MACS-VRPTW.

RT=Rochat and Taillard (1995), S = Shaw (1998), TB= Taillard et al. (1997)

MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows