## 1 Introduction
Experimental tests were performed with several Gehring and Homberger benchmark problems and with 65 Wang and Chen benchmark problems. Results show the algorithm effectiveness since it obtains better solutions for 12 Wang and Chen instances, and also reach the best-known solution for the remaining instances. On the other hand, the use of grid environments to solve optimization problems has been scarcely documented in the existing literature. For example, [PERSON] et al. [27] describe the use of a clusters grid to solve several optimization problems such as the nonconvex quadratic optimization problem and the semidefinite problem, as well as to solve polynomial systems of equations, and [PERSON] et al. [28] introduce a general framework to implement exact optimization algorithms on a grid environment. In particular, [PERSON] et al. [29] implement a parallel GA using a two-stage communication scheme to share the population of candidate solutions in the nodes of an experimental grid with two clusters. First, the populations evolve in each cluster in independent form using point-to-point communication with send/receive methods provided by the MPI library, and then the information exchange between the clusters of the grid is achieved through the FTP protocol using only one node in each cluster. In general, algorithms implemented in grid environments can be classified into two groups: The first one include those developed over the middleware supporting a grid environment such as NetSolve [30], Condor [31; 32], Globus [33], and gLite [34], and the other are those applied in grids configured as one VPN [29; 35; 36]. Each one has its advantages and disadvantages. In this work, GGA is implemented in an experimental MiniGrid configured as one VPN to solve VRPTW instances. The main contributions of this work are: (a) The proposed structure for the GGA including the migration scheme of mutated segments between grid nodes, (b) the communication scheme among the clusters of the MiniGrid, using collective communication methods provided by the MPI library, and (c) the use of the grid computing to efficiently solve complex problems. It can be used to solve problems using the total computing capacity (number of cores) of one virtual supercomputer (grid). The resolution of the NP-hard problems is intractable [37] due to the significant size problem, and the use of many computer resources is required to allow an extensive exploration of the solution space and one full exploitation of promising areas in relatively shorter times. Parallelization of algorithmic processes can lead to improved algorithmic designs for the treatment of these problems. This impact is stronger where computing infrastructure is a constraint in the study of these problems, and the use of several computational clusters to build a grid environment is a viable option in the study of these complex problems. The rest of this document is structured as follows: Section 2 describes the VRPTW and the application of metaheuristics to solve this problem. A description of the MiniGrid components is included in Section 3, and Section 4 describes the proposed approach for the GA parallelization and its implementation in a grid environment. Section 5 presents the experimental study. Finally, the results and discussion of this approach are summarized in Section 6.