4.4 The Supporting Operators
4.4.2 Geographical Merge
The role ofGeographical Merge (GM) is to merge two routes, which are close to each other, within the same individual. Horizontal Line Crossover and Uniform Crossover, explained in section 4.2.3 and 4.2.4 respectively, tend to generate offsprings with relatively short routes. In order to illustrate that, the average difference from the capacity was calculated, separately for the routes with too much total demand and for those with total demand within the capacity of the vehicles. Equation 4.8 illustrates the formula, which was used to calculate the difference dp for routes attaining the capacity constraint, where p stands for plus. If a route does no contain any routes of either kind the difference is set to zero. The formula for the routes violating the capacity constraint is corresponding. The following formula shows the difference for the routes attaining the capacity constraint.
dp =
P(K−totdemp) nrp,r
(4.8) where:
K is the capacity of the vehicles,
totdemp is the total demand of a route r where it is less than K and nrp denotes number of routes with total demand less than K.
In the following figures the results, which were obtained by solving problem instance A-n80-k10 from [20] using the two crossover operators, Simple Random Mutation (pSame
= 30% and rate = 100%) and Steepest Improvement Algorithm. The algorithm was run once with a population size 50 and 10000 iterations. The capacity of the vehicles is 100.
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
−30
−20
−10 0 10 20 30 40 50
Number of iterations
K−totdem
Figure 4.12: Average difference from capacity using Horizontal Line Crossover.
0 1000 2000 3000 4000 5000 6000 7000 8000 9000 10000
−20
−10 0 10 20 30 40 50 60 70 80
Number of iterations
K−totdem
Figure 4.13: Average difference from capacity using Uniform Crossover.
The positive difference in the figures indicates how much more demand could be added to the routes on average in order to fill the vehicles and the negative difference shows how much more demand than can be carried by the vehicles is in the routes on average.
Particularly when using HLC, there is a relatively large gap between the total demand and the capacity of the vehicles for feasible routes. The gap is at least 10 capacity
4.4 The Supporting Operators 61 units, besides from the first iterations. The gap is smaller for UC or usually more than 5 capacity units. Furthermore, figure 4.13 clearly shows that UC does seldom generate infeasible routes and those that are generated are usually very close to being feasible.
The UC operator uses both the capacity of the routes in addition to the distance between them to combine them. The distance between every two routes is measured using their bounding boxes, see section 4.2.2. The pseudocode is rather detailed in order to explain the operator well enough.
Merge(offspring)
NR ←number of routes in offspring for g ←0 to NR
dem1← demand of route offspring[g]
for h← g to NR
dem2 ← demand of route offspring[h]
if dem1 + dem2 ≤ K
if bol6= 0 andbol >biggestoverlap biggestoverlap ←bol
olroute1 ← e olroute2 ← f
else if biggestoverlap = 0 cl← findClosest(e,f)
insert route clroute2 at the end of clroute1 returnoffspring
The operator is applied on a single individual. It starts by identifying pairs of routes that together have the total demand within the limits of the capacity, thus it does not generate infeasible routes. Then the pair of routes closest to each other is selected. If the bounding boxes of the routes overlap, the pair with the largest overlap is chosen.
Otherwise, it selects the pair with the shortest distance between the bounding boxes.
Finally, the routes are merged together by adding the one route at the end of the other.
4.5 Summary
In this chapter the development process of the fitness value and 7 operators is dis-cussed. Four crossover operators are explained; Simple Random Crossover, Biggest Over-lap Crossover, Horizontal Line Crossover and Uniform Crossover. Simple Random Muta-tion, the only mutation operator, is described and also two supporting operators; Repair-ing Operator and Geographical Merge. In the next chapter some implementation issues are discussed.
63
Chapter 5
Implementation
In this chapter implementation issues are discussed, such as information about the com-puter, the experiments that were carried out and computation of Euclidean distances, among other things.
Computational experiments were carried out on a Zitech PC with a 800 MHz AMD Athlon(tm) processor. The program was implemented using the Java 1.3.1_01 Standard Edition and compiled using the java compiler.
The CPU-time was calculated using the functioncurrentTimeMillis() in Java. It returns the current time in milliseconds since midnight January 1, 1970 GMT. The function is used right before the algorithm is applied in the code and again afterwards. The execution time of the algorithm is the difference between two measurements.
The cost of travelling between every two customers was calculated using Euclidean dis-tances. Some problem instances have been calculated using real numbers in which the best results are presented. Others are calculated with integers. When integers are used, the rounding function Nearest Integer function nint was used to convert the Euclidean distances into integers. The function returns the integer closest to the given number and half-integers are rounded up to the smallest integer bigger than the number, i.e.
nint(1.4) = 1, nint(3.8) = 4 and nint(5.5) = 6. When Java rounds real numbers, all numbers are rounded down to the nearest integer. Therefore, a constant 0.5 was added to all the real numbers in order to simulate nint. For instance, Java rounds 3.8 down to 3 by Java but by adding 0.5 to it, 3.8 + 0.5 = 4.3, it is instead rounded ”up” to 4!
In section 2.2.2 the representation of the VRP solution used in this project is described.
The population is implemented as a 3-dimensional array M×dim× dim, where M is the population size and dim is the number of customers in each problem. So Pop[2][5][3] = 5 means that customer no. 5 is visited number 4 in route 6 in the third individual in the population (indices start in 0 in Java).
The advantage of presenting the population in this way is that it is very simple to imple-ment. Furthermore, it simplifies communication and gives a good overview. The drawback is that it contains a lot of empty spaces that use memory, where either the number of customers is less than dim or the number of routes is less than dim. The memory need
of the population could be reduced by using upper bound on the number of customers within a route or on the number of routes, based on the problem to be solved. However, one should be careful about using upper bounds because Java is not able to enlarge an array dynamically. Thus if the program tries to insert a customer outside the array the program terminates.
In order to save computational time, the total cost of each individual was kept in separate arrays for the cost and the penalty. Since the program used a steady-state algorithm (see section 2.2.2) only few solutions were changed in each iteration. When a solution was changed, it was noted in the cost and the penalty array and next time it was selected the cost was recalculated. In a similar way the bounding boxes were also kept in an array.
65
Chapter 6
Parameter Tuning
Many parameters are involved in solving VRP with GA. The values of those need to be tuned. Good parameter tuning is important for all GA to generate good solutions.
Usually, it is complex to tune the parameters because the relationship between them can be rather complicated and unclear. Most algorithms contain many parameters and the more they get the more time consuming the tuning becomes. Ideally, all parameters should be tuned but that is in general too time consuming. However, it is important to tune as many as possible. In the following section all parameters are listed, it is explained how they were tuned and the values they were given are shown.
6.1 The Parameters and the Tuning Description
The parameters are divided into two groups of more or less important parameters. In the group of more important parameters are those that are believed to have more influence on the effectivity of the algorithm. In the other group are parameters of less significance and the effect of some of them has been discussed in the previous chapter. The parameters are listed in the two tables below:
1. The Population size (M).
2. The rate of SRM.
3. The rate of RO.
4. The rate of GM.
Table 6.1: The more important parameters.
5. A scaling factor forα in the penalty function.
6. The power in the penalty function.
7. The power in the α function.
8. The tournament size when choosing parent solutions.
9. The probability of Tournament Selection when choosing parent.
solutions.
10. The tournament size when choosing an individual leaving the population.
11. The probability of Tournament Selection when choosing an individual out of population.
12. The rate of SRC.
13. The subroute length in SRC.
14. The rate of BOC.
15. The subroute length in BOC.
16. Number of routes closest to the subroute in BOC.
17. The rate of HLC.
18. The rate of UC.
19. The scaling factor for evaluating the quality of the routes in UC.
20. The probability of inserting the subroute into the same route again in SRM (pSame).
21. Number of customers moved in SRM.
22. Number of customers moved in RO.
Table 6.2: The less important parameters.
Although it is desirable to tune all possible parameters, it is hardly never possible for a program of this size because it takes too much time. Here only the more important parameters are tuned. The reasons for why the less important parameters are considered so and why they are not tuned are the following:
Parameter 5: The effect of different values ofα was discussed shortly in section 4.1 and because of limited time it is not tuned here.
Parameters 6 and 7: The power in neither the penalty function nor theα-function are tuned, because that will have similar effect as tuning of α. For simplification and to save time they are kept constant.
Parameters 8 and 10: The tournament sizes of neither selection of parent solutions nor the solution leaving the population are tuned. The convergence depends both on the selection pressure and the population size and to save time the convergence will be balanced by tuning the population size with constant tournament size of two.
Parameters 9 and 11: It is not important to tune the probability of tournament selec-tion when using a steady-state algorithm. On the other hand, it can be necessary
6.1 The Parameters and the Tuning Description 67 to reduce the selection pressure by applying the tournament selection with a certain probability when generational algorithms are used, see page 20.
Parameters 12, 14, 17 and 18: The probability of applying a crossover operator is not tuned. Skipping a crossover in some iterations can be done to be better able to pre-serve a part of the population from one iteration to another. That is not important here because a steady-state algorithm is used.
Parameters 13 and 15: The lengths of the subroutes in SRC and BOC are not tuned because it is important to keep some randomness in the crossover operators.
Parameters 16, 19 and 20: The number of routes or candidates in BOC, is not tuned since it will most likely not have much influence compared to the time it takes to tune it. For the same reasons a possible scaling factor in UC and pSame are not tuned. The parameter pSame is set to 30%, which has worked out fine during the development process of the project.
Parameters 21 and 22: Instead of tuning the number of customers moved in SRM and RO directly they are tuned at some degree by tuning the rate of the operators where it is possible to apply them twice.
Two algorithms are defined; a fast algorithm with10000 iterations and a slow algorithm with 100000 iterations. The algorithms are tuned for different sets of population sizes but parameters 2, 3 and 4 are tuned for the same values for both algorithms. Since there is not a linear correlation between the population size and the number of iterations, the slow algorithm is not necessarily expected to perform better than the fast algorithm.
The problem instances that are used for both tuning and testing are divided into two groups of small instances with less than 100 customers and large instances with 100 cus-tomers or more. The size of the large instances limits the possible population size to 100 due to the memory of the computer that is used. Furthermore, running the slow algo-rithm using a relatively large population for large problems is extremely time consuming.
Thus, the large instances are only tuned for the fast algorithm and smaller populations.
The values of parameters 2, 3 and 4 for the slow algorithm and the large instances are borrowed from the tuning of the small instances for the slow algorithms. The possible values of parameters are chosen based on the experience that has been gained during the development process. The following tables show the possible values for small problems using fast and slow algorithm and large problems using fast algorithm.
Parameters Fast Slow 1 Population size (M) 50,100,200 200,400 2 SRM rate (%) 0,50,100,200 0,50,100,200 3 RO rate (%) 0,50,100,200 0,50,100,200 4 GM rate (%) 0,50,100,200 0,50,100,200
Table 6.3: Possible values of parameters for small problems using a fast or a slow algo-rithm.
Parameters Fast
1 Population size (M) 50,100 2 SRM rate (%) 0,50,100,200 3 RO rate (%) 0,50,100,200 4 GM rate (%) 0,50,100,200
Table 6.4: Possible values of parameters for large problems using fast algorithm.
Ideally, it is preferred to tune all possible combinations of operators. For time reasons, that will not be done here. Instead 8 combinations of operators are considered. Each crossover operator is tuned with SRM and a corresponding supporting operator, RO or GM. Furthermore, they are tuned with and without SIA. The different combinations are:
1. SRC, SRM, RO and SIA 2. SRC, SRM and RO 3. BOC, SRM, RO and SIA 4. BOC, SRM and RO 5. HLC, SRM, GM and SIA 6. HLC, SRM and GM 7. UC, SRM, GM and SIA 8. UC, SRM and GM
It is essential not to use the same problem instances for tuning and testing. Four problem instances are chosen for the parameter tuning; two small problems and two large prob-lems. The final testing is performed with 12 small problem instances and 7 large problem instances, thus the sets of tuning problems are 17 and 29 of the whole set of problems.
Table 6.5 illustrates the problems. The bold results correspond to optimal values and the regular results denote the best know values.