Research on New Tabu Search Algorithm for Min-Max Vehicle Routing Problem - Advanced Research on Computer Education, Simulation and Modeling - page 83

Fig. 1. Optimization route of MMVRP using new tabu search algorithm

Table 2. Optimal results by new tabu search algorithm

Line No. Running Path Mileage

1 0-16-2-8-20-0 181.416

0-9-11-13-4-0 201.293

2

0-18-10-7-0 152.486

3

0-6-5-17-14-0 196.754

4

5 0-15-0 205.767

6 0-12-1-3-19-0 145.202

The Total Mileage 1082.918 km

Average Mileage 180.486

The longest line 205.767

amount is 50. Here, the longest line is 205.767 km, the corresponding optimal total
length of 1082.918 km. The concrete route can be seen in table 2 and figure 1.

4.2 Analysis on Three Algorithms

Compared the optimal scheme of reference [6], the proposed new tabu search algo-
rithm has a strong search capability, high computational efficiency.

Table 3. Comparison among GA, TS and Algorithm of this study

GA TS NTS

The Total Mileage 1106.237 1095.136 1083.411

Average Mileage 184.373 182.523 180.5685

The longest line 205.767 205.767 205.767