## 4 Computational Testing Experiments  
In this section, we conduct extensive computational testing experiments to access the performance of two VNS algorithms using the local search with static case selection probability (VNS_S) and VNS algorithm using the local search with dynamic case selection probability (VNS_D). Since the problem complexity increases as the number of jobs (_J_) increases, we divided the test problems into two groups using \(J\). The first group is to compare the performances of VNS algorithms with the optimal solution, and the test problems in the group are randomly generated with \(J\) selecting between 5 and 10. For the optimal solution, ILOG CPLEX 12.7 was adopted to solve the MILP formulation in Section 2. We terminated a particular run if an optimal solution was not found in an imposed 7200 (s) time limit. The test problems in the second group are randomly generated with \(J\) selecting more than 10. The group is to compare the relative performance of the solutions obtained by VNS algorithms. VNS algorithms were coded with the language C#, and all experiments were tested on a PC with 1.86 GHz Intel Core 2 CPU processor and 2 GB RAM. The problem complexity is affected by five problem parameters which are the number of jobs (_J_), the number of machines (_M_), the number of trucks (_T_), the number of customers (_C_), and tardiness factor (_\(\delta\)_). Test problems are randomly made according to the five parameters. The tardiness factor \(\delta\) (\(0\leq\delta\leq 1\)) is to generate the due times for each job. The due times for each job generated are more scattered as the value of \(\delta\) is increased. Three values, 0.1, 0.3, and 0.5, are considered for the tardiness factor. In the small-sized group, eight test problems were randomly generated for each tardiness factor. Under the predetermined one of tardiness factor values, the size of four problem parameters, which are the numbers of jobs, machines, trucks, and customers, were randomly selected by U [5,10], U [2,6], U [2,4], and U [3,4], respectively. In the large-sized group, a total of 24 test problems with 20, 40, and 60 jobs were randomly generated for each tardiness factor. Under the predetermined one of job sizes and one of tardiness factor values, the size of three problem parameters, which are the numbers of machines, trucks, and customers, were randomly selected by U [3,6], U [2,4], and U [3,6], respectively. The processing time and the transportation time were randomly selected by U [60,120] and U [60,240]. The volume of jobs was randomly selected by U [5,10] with a fixed value of the batch capacity as 20. The relative interval ratio selected by truck schedule were predetermined as [0.05, 0.1, 0.2, 0.4, 0.7, 1.0]. The performance of VNS algorithms were relatively compared, and two performance measures, called relative deviation index (RDI) and mean absolute deviation (MAD), were defined. The measures are expressed by Equations (22) and (23), respectively. Figure 3: Encoding and decoding procedures. \[\text{RDI}=\frac{OBJ_{\text{sol}}-OBJ_{\text{best}}}{OBJ_{\text{worst}}-OBJ_{ \text{best}}}, \tag{22}\]  
where \(OBJ_{\text{best}}\) and \(OBJ_{\text{worst}}\) are the objective function values of the best feasible solution obtained by one of the algorithms (or the optimal solution by CPLEX) and the worst feasible solution obtained by one of the algorithms, respectively. \(OBJ_{\text{sol}}\) is an objective function value obtained by any VNS algorithm. \[\text{MAD}(\%)=\frac{|OBJ_{\text{sol}}-OBJ_{\text{mean}}|}{OBJ_{\text{mean} }}\times 100, \tag{23}\]  
where \(OBJ_{\text{mean}}\) is a mean value of the replicated objective function values by any VNS algorithm. All problems were tested by 30 replications. The performance results of the small-sized group are presented in Table 4. The objective function values of the optimal solution by CPLEX are represented, and the average RDI and MAD by VNS algorithms are compared.