We study the capacitated vehicle routing problem (CVRP) which is a well-known NP-hard combinatorial optimization problem (COP). The aim of the problem is to serve different customers by a convoy of vehicles starting from a depot so that sum of the routing costs under their capacity constraints is minimized. Since the problem is very complicated, solving the problem using exact methods is almost impossible. So, one has to go for the heuristic/metaheuristic methods and genetic algorithm (GA) is broadly applied metaheuristic method to obtain near optimal solution to such COPs. So, this paper studies GAs to find solution to the problem. Generally, to solve a COP, GAs start with a chromosome set named initial population, and then mainly three operators-selection, crossover and mutation, are applied. Among these three operators, crossover is very crucial in designing and implementing GAs, and hence, numerous crossover operators were developed and applied to different COPs. There are two major kinds of crossover operators-blind crossovers and distance-based crossovers. We intend to compare the performance of four blind crossover and four distance-based crossover operators to test the suitability of the operators to solve the CVRP. These operators were originally proposed for the standard travelling salesman problem (TSP). First, these eight crossovers are illustrated using same parent chromosomes for building offspring(s). Then eight GAs using these eight crossover operators without any mutation operator and another eight GAs using these eight crossover operators with a mutation operator are developed. These GAs are experimented on some benchmark asymmetric and symmetric instances of numerous sizes and various number of vehicles. Our study revealed that the distance-based crossovers are much superior to the blind crossovers. Further, we observed that the sequential constructive crossover with and without mutation operator is the best one for the CVRP. This estimation is validated by Student’s t-test at 95% confidence level. We further determined a comparative rank of the eight crossovers for the CVRP.
There are numerous real-life distribution management problems, where constructing delivery route from a headquarters to some customers is very important. If same customers must be provided service very frequently, it is preferred to set up an optimal tour. This problem is called vehicle routing problem (VRP) which is a very challenging optimization problem. It was introduced first in [
We consider the CVRP for our study. Several researchers extensively studied on the CVRP, where a convoy of vehicles provides services to different customers from a depot (headquarters) so that sum of the routing costs under their capacity constraints is minimized. The CVRP is a mixture of the standard travelling salesman problem (TSP) and the bin packing problem (BPP). The CVRP has applications in many real-life problems, such as renting-sharing problems for urban bicycles [
Introduced first by John Holland, GAs are proposed according to the survival-of-the-fittest theory amongst various species produced by random differences in the structure of chromosomes in the natural science. Because GAs are easy, flexible and simple to code, they are extremely successful. Generally, GAs start with a chromosome set named initial population. Then mainly three operators, specifically, selection, crossover and mutation, are applied to find solution to any problem. Selection operator selects better chromosomes among the existing chromosomes, crossover operator probabilistically produces new chromosome(s) called offspring(s) by mating two chromosomes, and mutation probabilistically changes some genes in the chromosomes. Among these three operators crossover is very crucial in designing and implementing GAs [
This manuscript is prepared as follows: Section 2 reports definition and model of the CVRP. Section 3 briefly discusses existing literatures for the CVRP using genetic crossover operators. Section 4 discusses GAs using existing crossover operators for the CVRP. Section 5 reports the experimental results of the GAs on some asymmetric and symmetric instances. Section 6 presents a conclusion.
The CVRP can be stated as: Suppose
The CVRP aims to minimize the total cost of the tour, S, described as:
As shown in
We aim to compare the performances of numerous crossover operators to find solution to the CVRP. Therefore, we report a short review on the literatures that applied different crossover operators to find solution to the problem. It is noted that the crossover operators which are designed for the TSP could also be utilized for the CVRP.
In [
In [
In [
In [
In [
In [
In general, there are two kinds of crossover operators available in the literature. One is the distance-based crossover, and another is the blind crossover. The distance-based crossovers consider distances among customers (or cities or nodes) and the blind crossovers do not consider any data related to the problem instance. The comparison will not be fair if the effectiveness of the distance-based crossover is evaluated against the blind crossovers [
The aim of this current study is to evaluate the performance of various crossover operators in GAs for the CVRP. Therefore, the general structure of the developed GA is selected to differentiate the performance of the compared crossover operators.
To apply GA to solve any optimization problem, a representation of a solution as chromosome should be defined initially. In our GAs, an integer chromosome using path representation is considered whose length is
The initial population of chromosomes of predefined size (Ps) is created arbitrarily as in Algorithm 1.
We illustrate a chromosome generation through the 9 customers and 2 vehicles with given matrix (
Customer | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
1 | 999 | 16 | 22 | 15 | 5 | 17 | 14 | 9 | 17 |
2 | 16 | 999 | 6 | 9 | 21 | 16 | 10 | 15 | 3 |
3 | 13 | 7 | 999 | 16 | 13 | 8 | 9 | 8 | 15 |
4 | 17 | 11 | 22 | 999 | 6 | 14 | 21 | 16 | 14 |
5 | 19 | 15 | 21 | 24 | 999 | 17 | 4 | 14 | 8 |
6 | 17 | 21 | 14 | 10 | 26 | 999 | 21 | 15 | 22 |
7 | 13 | 9 | 12 | 22 | 14 | 11 | 999 | 8 | 23 |
8 | 15 | 11 | 8 | 20 | 13 | 9 | 13 | 999 | 28 |
9 | 19 | 5 | 21 | 14 | 9 | 18 | 5 | 27 | 999 |
Customer | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
---|---|---|---|---|---|---|---|---|---|---|
1 | 999 | 16 | 22 | 15 | 5 | 17 | 14 | 9 | 17 | 999 |
2 | 16 | 999 | 6 | 9 | 21 | 16 | 10 | 15 | 3 | 16 |
3 | 13 | 7 | 999 | 16 | 13 | 8 | 9 | 8 | 15 | 13 |
4 | 17 | 11 | 22 | 999 | 6 | 14 | 21 | 16 | 14 | 17 |
5 | 19 | 15 | 21 | 24 | 999 | 17 | 4 | 14 | 8 | 19 |
6 | 17 | 21 | 14 | 10 | 26 | 999 | 21 | 15 | 22 | 17 |
7 | 13 | 9 | 12 | 22 | 14 | 11 | 999 | 8 | 23 | 13 |
8 | 15 | 11 | 8 | 20 | 13 | 9 | 13 | 999 | 28 | 15 |
9 | 19 | 5 | 21 | 14 | 9 | 18 | 5 | 27 | 999 | 19 |
10 | 999 | 16 | 22 | 15 | 5 | 17 | 14 | 9 | 17 | 999 |
Demand | 0 | 24 | 13 | 20 | 27 | 25 | 29 | 18 | 12 | 0 |
Random list of customers | Select ‘customer p’ with qp and D | Is (D + qp≤ = Q)? | Chromosome with D |
---|---|---|---|
6, 9, 8, 5, 2, 4, 3, 7, 10 | ‘customer 6’ with q6 = 25 and D = 0 | Yes | (1, 6) with D = 25 |
9, 8, 5, 2, 4, 3, 7, 10 | ‘customer 9’ with q9 = 12 and D = 25 | Yes | (1, 6, 9) with D = 37 |
8, 5, 2, 4, 3, 7, 10 | ‘customer 8’ with q8 = 18 and D = 37 | Yes | (1, 6, 9, 8) with D = 55 |
5, 2, 4, 3, 7, 10 | ‘customer 5’ with q5 = 27 and D = 55 | Yes | (1, 6, 9, 8, 5) with D = 82 |
2, 4, 3, 7, 10 | ‘customer 2’ with q2 = 24 and D = 82 | No | (1, 6, 9, 8, 5) with D = 82 |
2, 4, 3, 7, 10 | ‘customer 4’ with q4 = 20 and D = 82 | No | (1, 6, 9, 8, 5) with D = 82 |
2, 4, 3, 7, 10 | ‘customer 3’ with q3 = 13 and D = 82 | Yes | (1, 6, 9, 8, 5, 3) with D = 95 |
2, 4, 7, 10 | ‘customer 7’ with q7 = 29 and D = 95 | No | (1, 6, 9, 8, 5, 3) with D = 95 |
2, 4, 7, 10 | ‘customer 10’ with q10 = 0 and D = 95 | Yes | (1, 6, 9, 8, 5, 3, 10) with D = 0 |
2, 4, 7 | ‘customer 2’ with q2 = 24 and D = 0 | Yes | (1, 6, 9, 8, 5, 3, 10, 2) with D = 24 |
4, 7 | ‘customer 4’ with q4 = 20 and D = 24 | Yes | (1, 6, 9, 8, 5, 3, 10, 2, 4) with D = 44 |
7 | ‘customer 7’ with q7 = 29 and D = 44 | Yes | (1, 6, 9, 8, 5, 3, 10, 2, 4, 7) with D = 73 |
The objective function value of a chromosome (solution) is the total service cost of the routes by all vehicles. The cost of every route is the addition of the service costs among the customers. Since the CVRP is a minimization problem, so, the fitness function,
In selection operator, a subpopulation (some chromosomes) is selected from the existing population for producing the next population. The performance of GA depends on selection operator without which GA is same as random sampling that produces different results in the generations. Several selection procedures exist in the literature. For our GAs, the fitness proportional selection (FPS) using roulette wheel selection (RWS) [
The selection process provides a consistency between exploration and exploitation of search area. The crossover is the most important process in GAs that is implemented on a chromosome pair to produce offspring(s). Selection and crossover operators together can speed up the convergence of GAs. The fundamental crossover operators cannot produce feasible offspring(s) for the CVRP. The crossover operators which were designed for the usual TSP can be implemented to the CVRP. As the blind crossovers and the distance-based crossover operators are two major kinds of crossover operators, we propose to utilize some of them and then compare them.
In [
Further, we set headquarters (1st gene) as ‘customer 1’. Assume that the arbitrarily selected cut points are between 2nd and 3rd genes, and between 6th and 7th genes which are shown by “|”.
P1: (1, 6 | 9, 8, 5, 3 | 2, 4, 7) and P2: (1, 8 | 6, 9, 4, 3 | 7, 5, 2).
The first gene is always ‘customer 1’. The mapping segments are between these cut points, and the systems are 9↔6, 8↔9, 5↔4, and 3↔3. These segments are copied in offsprings as below:
O1: (1, * | 9, 8, 5, 3 | *, *, *) and O2: (1, * | 6, 9, 4, 3 | *, *, *).
We add other genes from the alternative parents that do not lead to infeasible chromosome:
O1: (1, * | 9, 8, 5, 3 | 7, *, 2) and O2: (1, * | 6, 9, 4, 3 | 2, *, 7)
The 1st * in the 1st offspring would be 8 which is from 2nd parent, however, it is already available in the offspring, so we consider 9 using the map 8↔9, but 9 is also available in the offspring, so, we add 6 using the map 9↔6. Similarly, the 2nd * in that offspring would be 5 which is from 2nd parent, however, it is available in the offspring, so we add 4 using the map 5↔4. So, the 1st offspring leads to O1: (1, 6, 9, 8, 5, 3, 7, 4, 2). Likewise, the 2nd offspring is created as: O2: (1, 8, 6, 9, 4, 3, 2, 5, 7).
Next, we add dummy depots at the end of the offspring chromosomes. Then offsprings become: O1: (1, 6, 9, 8, 5, 3, 7, 4, 2, 10) and O2: (1, 8, 6, 9, 4, 3, 2, 5, 7, 10). Then calculate total demand of the customers. We have for O1, (q1 + q6 + q9 + q8 + q5 + q3) = 0 + 25 + 12 + 18 + 27 + 13 = 95. Now if we add q7 = 29, then 95 + 29 = 124 > 100 (=Q), hence, we exchange ‘customer 7’ with ‘customer 10’. So, the first offspring leads to O1: (1, 6, 9, 8, 5, 3, 10, 4, 2, 7) with cost 162. Likewise, the 2nd offspring is created as: O2: (1, 8, 6, 9, 4, 3, 10, 5, 7, 2) with cost 123.
In [
P1: (1, 6 | 9, 8, 5, 3 | 2, 4, 7) and P2: (1, 8 | 6, 9, 4, 3 | 7, 5, 2)
We always fix first gene as ‘customer 1’. First, we copy the genes between two cut points to the offspring as:
O1: (1, * | 9, 8, 5, 3 | *, *, *) and O2: (1, * | 6, 9, 4, 3 | *, *, *)
Next, starting from 2nd cut point of one parent, genes from other one, excluding existing ones, are copied by maintaining sequence. The order of genes in 2nd parent from 2nd cut point is “7→5→2→8→6→9→4→3.” After excluding existing genes 9, 8, 5 and 3, the order becomes “7→2→6→4”, that is put in 1st offspring starting from 2nd cut point as: O1: (1, 4 | 9, 8, 5, 3 | 7, 2, 6). Similarly, we build the second offspring as: O2: (1, 5 | 6, 9, 4, 3 | 2, 7, 8).
Next, we add dummy depots at the end of the offspring chromosomes. Then offsprings become: O1: (1, 4, 9, 8, 5, 3, 7, 2, 6, 10) and O2: (1, 5, 6, 9, 4, 3, 2, 7, 8, 10). Then calculate total demand of the customers. We have for O1, (q1 + q4 + q9 + q8 + q5 + q3) = 0 + 20 + 12 + 18 + 27 + 13 = 90. Now if we add q7 = 29, then 90 + 29 = 119 > 100 (=Q), hence, we exchange ‘customer 7’ with ‘customer 10’. So, the first offspring becomes O1: (1, 4, 9, 8, 5, 3, 10, 2, 6, 7) with cost 169. Similarly, we build the second offspring as: O2: (1, 5, 6, 9, 4, 3, 10, 7, 8, 2) with cost 142.
In [
Initially, the arc (1, 6) is chosen from 1st parent and copied to the offspring. Then arcs (6, 9) from 2nd one, and (9, 8) from 1st one, are chosen and copied to the offspring. Next, since the chosen arc (8, 6) from 2nd one makes a cycle, so, a random arc (8, 2) is chosen. Later, the arcs (2, 4) from 1st parent and (4, 3) from 2nd one, are chosen and copied to the offspring. Finally, the arcs (3, 5) and (5, 7) are chosen randomly. This way the following offspring is created: O: (1, 6, 9, 8, 2, 4, 3, 5, 7).
Next, we add dummy depots at the end of the offspring chromosome which becomes: O: (1, 6, 9, 8, 2, 4, 3, 5, 7, 10). Then calculate total demand of the customers. So, we have, (q1 + q6 + q9 + q8 + q2 + q4) = 0 + 25 + 12 + 18 + 24 + 20 = 99. Now if we add q3 = 13, then 99 + 13 = 112 > 100 (=Q), hence, we exchange ‘customer 3’ with ‘customer 10’. Finally, the offspring leads to O: (1, 6, 9, 8, 2, 4, 10, 5, 7, 3) with cost 137.
In [
The first position in the offspring 1, for 2nd position, we choose ‘customer 6’ from 1st parent, then the 1st offspring leads to: O1: (1, 6, *, *, *, *, *, *, *).
In the offspring, each gene is selected from any parent with the same location, so gene 8 must be considered, since gene 8, in 2nd parent, is below gene 6. In 1st parent, gene 8 is at 4th location; so, the offspring leads to: O1: (1, 6, *, 8, *, *, *, *, *).
Next, we select gene 9 as, in 2nd parent, it is below gene 8. In 1st parent, gene 9 is at 3rd location; so, the offspring leads to: O1: (1, 6, 9, 8, *, *, *, *, *).
Next, we select gene 6 as, in 2nd parent, it is below gene 9. However, it leads to a cycle. So, we fill up the empty positions by the genes available in corresponding positions in 2nd parent. So, the offspring leads to: O1: (1, 6, 9, 8, 4, 3, 7, 5, 2). Similarly, we build the second offspring as: O2: (1, 8, 6, 9, 5, 3, 2, 4, 7).
Next, we add dummy depots at the end of the offspring chromosomes. Then offsprings become: O1: (1, 6, 9, 8, 4, 3, 7, 5, 2, 10) and O2: (1, 8, 6, 9, 5, 3, 2, 4, 7, 10). Then calculate total demand of the customers. We have for O1, (q1 + q6 + q9 + q8 + q4 + q3) = 0 + 25 + 12 + 18 + 20 + 13 = 88. Now if we add q7 = 29, then 88 + 29 = 117 > 100 (=Q), hence, we exchange ‘customer 7’ with ‘customer 10’. So, the first offspring becomes O1: (1, 6, 9, 8, 4, 3, 10, 5, 2, 7) with cost 164.
Similarly, we build the second offspring as: O2: (1, 8, 6, 9, 5, 3, 10, 4, 7, 2) with cost 144.
In [
As the offspring is started with (1), its neighbors in both parents are 6 and 8 with their costs 17 and 9 respectively. As the customer 8 is the cheapest one, so, it is added to the offspring that leads to: (1, 8).
Next, the customer 8 has neighbours 5, 9, 6 and 1 with their costs 13, 28, 9 and 15 respectively. As the customer 6 is the cheapest one, so, it is added to the offspring that leads to: (1, 8, 6).
Next, the customer 6 has neighbours 9, 1, 9 and 8 with their costs 22, 17, 22 and 15 respectively. The customer 8 is the cheapest one, but it is available in the offspring. So, customer 2 is chosen randomly and added to the offspring that leads to: (1, 8, 6, 2).
Next, the customer 2 has neighbours 4, 3 and 5 with their costs 9, 6 and 21 respectively. The customer 3 is the cheapest one, and so, it is added to the offspring that leads to: (1, 8, 6, 2, 3).
Next, the customer 3 has neighbours 2, 5, 7 and 4 with their costs 7, 13, 9 and 16 respectively. The customer 2 is the cheapest one, but it is available in the offspring. So, customer 4 is chosen randomly and added to the offspring that leads to: (1, 8, 6, 2, 3, 4). This way, we create the complete offspring as: O: (1, 8, 6, 2, 3, 4, 5, 7, 9).
Next, we add dummy depots at the end of the offspring chromosome which becomes: O: (1, 8, 6, 2, 3, 4, 5, 7, 9, 10). Then calculate total demand of the customers. So, we have, (q1 + q8 + q6 + q2 + q3 + q4) = 0 + 18 + 25 + 24 + 13 + 20 = 100. Now if we add q5 = 27, then 100 + 27 = 127 > 100 (=Q), hence, we exchange ‘customer 5’ with ‘customer 10’. So, the offspring becomes O: (1, 8, 6, 2, 3, 4, 10, 7, 9, 5) with cost 143.
In [
As the offspring is started with (1), we look at the arcs 1→6 and 1→8 with costs 17 and 9 respectively in the parents and add customer 8 to the offspring that leads to: (1, 8).
Next, we look at the arcs 8→5 and 8→6 with their respective costs 13 and 9 in the parents and add customer 6 to the offspring that leads to: (1, 8, 6).
Next, we look at the arcs 6→9 and 6→9 in the parents and add customer 9 to the offspring that leads to: (1, 8, 6, 9). This way, we create the complete offspring as: (1, 8, 6, 9, 4, 2, 3, 7, 5).
Next, we add dummy depots at the end of the offspring chromosome which becomes: O: (1, 8, 6, 9, 4, 2, 3, 7, 5, 10). Then calculate total demand of the customers. So, we have, (q1 + q8 + q6 + q9 + q4 + q2) = 0 + 18 + 25 + 12 + 20 + 24 = 99. Now if we add q3 = 13, then 99 + 13 = 112 > 100 (=Q), hence, we exchange ‘customer 3’ with ‘customer 10’. So, the offspring becomes O: (1, 8, 6, 9, 4, 2, 10, 7, 5, 3) with cost 143.
In [
As the offspring is started with (1), we look at the arcs 1→6 and 1→8 with costs 17 and 9 respectively in the parents and add customer 8 to the offspring that leads to: (1, 8).
Next, we look at the arcs 8→5 and 8→6 with their respective costs 13 and 9 in the parents and add customer 6 to the offspring that leads to: (1, 8, 6).
Next, the arcs leaving the customer 6 are considered, i.e., both 6→9 with cost 22, so, add customer 9 to the offspring that leads to: (1, 8, 6, 9).
Next, between the arcs 9→8 and 9→4, the 1st creates a cycle, so, add customer 4 to the offspring that leads to: (1, 8, 6, 9, 4). Continuing in this way, one can obtain a complete offspring as: (1, 8, 6, 9, 4, 7, 5, 2, 3).
Next, we add dummy depots at the end of the offspring chromosome which becomes: O: (1, 8, 6, 9, 4, 7, 5, 2, 3, 10). Then calculate total demand of the customers. So, we have, (q1 + q8 + q6 + q9 + q4) = 0 + 18 + 25 + 12 + 20 = 75. Now if we add q7 = 29, then 75 + 29 = 104 > 100 (=Q), hence, we exchange ‘customer 7’ with ‘customer 10’. So, the offspring becomes O: (1, 8, 6, 9, 4, 10, 5, 2, 3, 7) with cost 119.
In [
Consider the same example parent chromosomes P1: (1, 6, 9, 8, 5, 3, 2, 4, 7) and P2: (1, 8, 6, 9, 4, 3, 7, 5, 2).
Initially, the offspring is (1). The legitimate customers after customer 1 in the parents are 6 and 8 with their costs 17 and 9 respectively. Since customer 8 is cheaper, we add it to the offspring that leads to: (1, 8).
The legitimate customers after customer 8 in the parents are 5 and 6 with their costs 13 and 9 respectively. Since customer 6 is cheaper, we add it to the offspring that leads to: (1, 8, 6).
Since the legitimate customer after customer 6 in the parents are same 9, we add it to the offspring that leads to: (1, 8, 6, 9).
The legitimate customers after customer 9 in the parents are 5 and 4 with their costs 9 and 14 respectively. Since customer 5 is cheaper, we add it to the offspring that leads to: (1, 8, 6, 9, 5).
The legitimate customers after customer 5 in the parents are 3 and 2 with their costs 21 and 15 respectively. Since customer 2 is cheaper, we add it to the offspring that leads to: (1, 8, 6, 9, 5, 2). This way, we create the complete offspring as: (1, 8, 6, 9, 5, 2, 4, 7, 3).
Next, we add dummy depots at the end of the offspring chromosome which becomes: O: (1, 8, 6, 9, 5, 2, 4, 7, 3, 10). Then calculate total demand of the customers. So, we have, (q1 + q8 + q6 + q9 + q5) = 0 + 18 + 25 + 12 + 27 = 82. Now if we add q2 = 24, then 82 + 24 = 106 > 100 (=Q), hence, we exchange ‘customer 2’ with ‘customer 10’. So, the offspring becomes O: (1, 8, 6, 9, 5, 10, 4, 7, 3, 2) with cost 139.
Amongst the above eight crossovers GX, HX, MHX and SCX are the distance-based crossovers, and OX, PMX, CX and AEX are the blind crossovers. We propose to compare both categories of crossovers for the CVRP.
To diversify the population, mutation operator is applied with a prespecified probability. Generally, mutation probability is set very low compared to crossover probability. The exchange mutation that chooses randomly two places in a chromosome within a route of any vehicle and exchanges their values. If there are
Our simple GA for the CVRP is presented in Algorithm 3.
We consider four blind crossovers and four distance-based crossovers. In each crossover selection, a single crossover is used. For mutation, two possibilities of selection–absence or presence of mutation, are applied. So, there are eight choices for crossover and two choices of mutation, thus provides sixteen variations of GAs. The aim of such individual implementation is to evaluate usefulness of the crossovers and to find their relative ranking. Notice that each GA is solely simple, not hybrid, that is developed of GA processes and basic operators, is not merging any other algorithm.
Basically, GA process is led by some GA parameters, specifically, population size which fixes number of chromosomes in every population, crossover probability for executing crossover between the parents, mutation probability for performing mutation operation, and a stopping criterion to end the GA process.
For comparing the effectiveness of various crossovers, simple GAs using various crossovers were encoded in Visual C++ on a Laptop with i7-1065G7 CPU@1.30 GHz and 8 GB RAM under MS Windows 10. We executed our GAs using various parameter sets, and finally, the parameters showed in
Parameters | Values |
---|---|
Population size | 50 |
Crossover probability | 100% |
Mutation probability | 10% |
Termination criterion | 5000 generations |
No. of runs for each instance | 50 times |
To verify the performance of crossovers, computational experiment is made on sixteen benchmark instances of many sizes. In these sixteen instances, A034-02f, A036-03f, A039-03f, A045-03f, A048-03f, A056-03f, A065-03f and A071-03f are asymmetric [
Instance | n | m | Instance | n | m | ||||
---|---|---|---|---|---|---|---|---|---|
A034-02f | 34 | 2 | 1000 | 1406 | E-n22-k4 | 22 | 4 | 6000 | 375 |
A036-03f | 36 | 3 | 1000 | 1644 | E-n51-k5 | 51 | 5 | 160 | 521 |
A039-03f | 39 | 3 | 1000 | 1654 | E-n76-k7 | 76 | 7 | 220 | 682 |
A045-03f | 45 | 3 | 1000 | 1740 | E-n76-k8 | 76 | 8 | 180 | 735 |
A048-03f | 48 | 3 | 1000 | 1891 | E-n76-k10 | 76 | 10 | 140 | 830 |
A056-03f | 56 | 3 | 1000 | 1739 | E-n76-k14 | 76 | 14 | 100 | 1021 |
A065-03f | 65 | 3 | 1000 | 1974 | E-n101-k8 | 101 | 8 | 200 | 815 |
A071-03f | 71 | 3 | 1000 | 2054 | E-n101-k14 | 101 | 14 | 112 | 1067 |
The experimental results by the sixteen GAs are summarized in
Instance | Results | PMX | OX | AEX | CX | GX | HX | MHX | SCX |
---|---|---|---|---|---|---|---|---|---|
A034-02f | Best Sol | 1965 | 1751 | 1806 | 3065 | 1679 | 1584 | 1485 | 1486 |
(1406) | Avg. Sol | 2252.40 | 1994.15 | 2054.50 | 3204.85 | 1746.15 | 1603.20 | 1503.80 | |
AvgExc(%) | 60.20 | 41.83 | 46.12 | 127.94 | 24.19 | 14.03 | 6.96 | ||
SD | 157.78 | 233.88 | 172.82 | 143.03 | 83.45 | 95.62 | 76.16 | 87.98 | |
Avg. Time | 0.02 | 0.06 | 0.05 | 0.01 | 0.02 | 0.05 | 0.06 | 0.00 | |
A036-03f | Best Sol | 2325 | 2338 | 1991 | 3342 | 1975 | 1835 | 1792 | 1731 |
(1644) | Avg. Sol | 2568.18 | 2532.28 | 2295.68 | 3660.34 | 2136.48 | 1990.40 | 1898.40 | |
AvgExc(%) | 56.22 | 54.03 | 39.64 | 122.65 | 29.96 | 21.07 | 15.47 | ||
SD | 198.81 | 128.53 | 163.68 | 181.56 | 119.24 | 94.21 | 80.33 | 82.63 | |
Avg. Time | 0.14 | 0.25 | 0.30 | 0.01 | 0.06 | 0.16 | 0.17 | 0.16 | |
A039-03f | Best Sol | 2665 | 2659 | 2126 | 3802 | 2057 | 1905 | 1838 | 1801 |
(1654) | Avg. Sol | 2849.50 | 2823.72 | 2327.88 | 4003.66 | 2202.06 | 2015.02 | 1917.02 | |
AvgExc(%) | 72.28 | 70.72 | 40.74 | 142.06 | 33.14 | 21.83 | 15.90 | ||
SD | 189.17 | 123.60 | 121.71 | 157.09 | 156.66 | 115.23 | 106.45 | 79.99 | |
Avg. Time | 0.16 | 0.34 | 0.54 | 0.01 | 0.16 | 0.12 | 0.13 | 0.28 | |
A045-03f | Best Sol | 2903 | 3207 | 2427 | 4444 | 2318 | 2143 | 2010 | 1943 |
(1740) | Avg. Sol | 3297.55 | 3490.30 | 2757.76 | 4793.11 | 2517.04 | 2227.04 | 2147.04 | |
AvgExc(%) | 89.51 | 100.59 | 58.49 | 175.47 | 44.66 | 27.99 | 23.39 | ||
SD | 250.77 | 144.36 | 163.38 | 157.08 | 93.37 | 105.77 | 114.38 | 141.53 | |
Avg. Time | 0.15 | 0.28 | 0.36 | 0.00 | 0.05 | 0.14 | 0.15 | 0.22 | |
A048-03f | Best Sol | 3131 | 3487 | 3258 | 4968 | 2982 | 2335 | 2220 | 2152 |
(1891) | Avg. Sol | 3729.96 | 3814.04 | 3653.22 | 5383.92 | 3204.96 | 2587.05 | 2472.10 | |
AvgExc(%) | 97.25 | 101.69 | 93.19 | 184.71 | 69.48 | 36.81 | 30.73 | ||
SD | 315.73 | 185.55 | 284.48 | 244.58 | 115.78 | 123.06 | 147.41 | 127.58 | |
Avg. Time | 0.19 | 0.32 | 0.33 | 0.01 | 0.11 | 0.27 | 0.29 | 0.45 | |
A056-03f | Best Sol | 3703 | 3828 | 3414 | 5415 | 2679 | 2105 | 1980 | 1924 |
(1739) | Avg. Sol | 4146.94 | 4121.34 | 3760.16 | 5848.96 | 2989.24 | 2358.06 | 2145.40 | |
AvgExc(%) | 138.47 | 136.99 | 116.23 | 236.34 | 71.89 | 35.60 | 23.37 | ||
SD | 281.57 | 192.53 | 254.08 | 251.54 | 198.22 | 105.23 | 117.47 | 130.14 | |
Avg. Time | 0.19 | 0.42 | 0.59 | 0.01 | 0.27 | 0.24 | 0.26 | 0.37 | |
A065-03f | Best Sol | 4779 | 4807 | 3870 | 6644 | 3354 | 2506 | 2356 | 2260 |
(1974) | Avg. Sol | 5069.92 | 5065.78 | 4386.82 | 7038.26 | 3564.58 | 2614.32 | 2469.60 | |
AvgExc(%) | 156.83 | 156.63 | 122.23 | 256.55 | 80.58 | 32.44 | 25.11 | ||
SD | 265.73 | 229.29 | 283.32 | 226.75 | 186.82 | 152.04 | 111.18 | 155.59 | |
Avg. Time | 0.33 | 0.71 | 0.97 | 0.06 | 0.30 | 0.06 | 0.10 | 0.15 | |
A071-03f | Best Sol | 5037 | 5161 | 3755 | 7439 | 3329 | 2687 | 2452 | 2446 |
(2054) | Avg. Sol | 5544.00 | 5472.96 | 4293.26 | 7901.64 | 3522.92 | 2695.03 | 2554.42 | |
AvgExc(%) | 169.91 | 166.45 | 109.02 | 284.70 | 71.52 | 31.21 | 24.36 | ||
SD | 304.82 | 293.10 | 298.67 | 275.55 | 185.07 | 152.03 | 121.67 | 171.86 | |
Avg. Time | 0.34 | 0.96 | 1.07 | 0.02 | 0.54 | 0.56 | 0.64 | 0.97 |
Amongst the distance-based crossovers, HX and GX could not find lowest average cost for any of experimented eight instances. Between GX and HX, HX is found better than GX. So, GX is observed to be the worst one among distance-based crossovers, yet GX is found better than AEX. The crossover MHX obtained lowest cost for only one instance, A034-02f, SCX obtained lowest cost for the remaining seven instances. So, among distance-based crossovers, SCX is observed to be best one. In fact, among all eight crossovers, SCX is observed to be best one. In addition, since the solutions obtained by SCX has lowest SD, one can conclude that the results by SCX is stable. Next, if one looks very carefully, then one can tell that MHX is the 2nd best and CX is the worst one. Further, the results of GX, HX, MHX and SCX are depicted in
To verify if GA using SCX (with no mutation) found much different average solution from the average solutions found by other GAs using distance-based crossovers, we conducted Student’s t-test. Further, we verify whether GA using AEX found much different average solution from the average solutions found by other GAs using blind crossovers. We applied following t-test formula for two large independent samples [
Instance | t-values against AEX | t-values against SCX | ||||
---|---|---|---|---|---|---|
PMX | OX | CX | GX | HX | MHX | |
A034-02f | 5.92 | −1.45 | 35.90 | 13.99 | 5.35 | −0.04 |
Better | AEX | ----- | AEX | SCX | SCX | ----- |
A036-03f | 7.41 | 7.96 | 39.08 | 16.35 | 10.77 | 6.13 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A039-03f | 16.23 | 20.01 | 59.03 | 13.43 | 7.50 | 2.75 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A045-03f | 12.62 | 23.52 | 62.86 | 21.39 | 9.03 | 5.69 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A048-03f | 1.26 | 3.31 | 32.29 | 40.85 | 15.30 | 9.78 |
Better | ----- | AEX | AEX | SCX | SCX | SCX |
A056-03f | 7.14 | 7.93 | 40.90 | 27.78 | 12.96 | 3.88 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A065-03f | 12.31 | 13.04 | 51.15 | 35.54 | 9.14 | 5.10 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A071-03f | 20.52 | 19.73 | 62.16 | 29.47 | 7.18 | 3.15 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
According to the results shown in
Instance | Results | PMX | OX | AEX | CX | GX | HX | MHX | SCX |
---|---|---|---|---|---|---|---|---|---|
A034-02f | Best Sol | 1575 | 1559 | 1619 | 1883 | 1562 | 1521 | 1414 | 1414 |
(1406) | Avg. Sol | 1874.24 | 1799.34 | 1702.16 | 2090.88 | 1634.64 | 1531.21 | 1448.56 | |
AvgExc(%) | 33.30 | 27.98 | 21.06 | 48.71 | 16.26 | 8.91 | 3.03 | ||
S.D. | 149.12 | 146.13 | 92.49 | 136.03 | 76.17 | 72.24 | 72.24 | 84.76 | |
Avg. Time | 0.13 | 0.36 | 0.36 | 0.29 | 0.49 | 0.37 | 0.38 | 0.56 | |
A036-03f | Best Sol | 2052 | 2299 | 1898 | 2440 | 1911 | 1766 | 1694 | 1694 |
(1644) | Avg. Sol | 2268.78 | 2513.32 | 2085.98 | 2779.42 | 1976.26 | 1890.32 | 1792.42 | |
AvgExc(%) | 38.00 | 52.88 | 26.88 | 69.06 | 20.21 | 14.98 | 9.03 | ||
S.D. | 158.32 | 135.90 | 107.26 | 152.63 | 85.21 | 77.51 | 64.29 | 69.60 | |
Avg. Time | 0.17 | 0.41 | 0.59 | 0.55 | 0.64 | 0.62 | 0.66 | 0.71 | |
A039-03f | Best Sol | 2241 | 2436 | 1977 | 2821 | 1886 | 1825 | 1768 | 1749 |
(1654) | Avg. Sol | 2570.38 | 2792.60 | 2204.58 | 3132.20 | 2032.00 | 1874.21 | 1788.16 | |
AvgExc(%) | 55.40 | 68.84 | 33.29 | 89.37 | 22.85 | 13.31 | 8.11 | ||
S.D. | 149.75 | 122.55 | 81.83 | 225.74 | 121.64 | 73.15 | 73.15 | 48.76 | |
Avg. Time | 0.19 | 0.38 | 0.56 | 0.55 | 0.33 | 0.51 | 0.54 | 0.60 | |
A045-03f | Best Sol | 2870 | 3200 | 2454 | 3208 | 2291 | 1954 | 1875 | 1858 |
(1740) | Avg. Sol | 3004.96 | 3405.90 | 2562.88 | 3640.22 | 2263.76 | 2064.22 | 1953.56 | |
AvgExc(%) | 72.70 | 95.74 | 47.29 | 109.21 | 30.10 | 18.63 | 12.27 | ||
S.D. | 159.55 | 153.31 | 138.13 | 182.69 | 68.58 | 91.21 | 77.20 | 69.64 | |
Avg. Time | 0.29 | 0.40 | 0.51 | 0.44 | 0.57 | 0.88 | 0.90 | 1.27 | |
A048-03f | Best Sol | 2898 | 3361 | 2891 | 3722 | 2631 | 2201 | 2017 | 2001 |
(1891) | Avg. Sol | 3174.40 | 3750.01 | 3014.40 | 3960.64 | 2836.05 | 2287.21 | 2104.64 | |
AvgExc(%) | 67.87 | 98.31 | 59.41 | 109.45 | 49.98 | 20.95 | 11.30 | ||
S.D. | 269.54 | 187.91 | 186.75 | 175.65 | 142.39 | 102.54 | 95.20 | 81.66 | |
Avg. Time | 0.24 | 0.45 | 0.62 | 0.49 | 1.23 | 0.95 | 1.00 | 0.90 | |
A056-03f | Best Sol | 3362 | 3816 | 3050 | 4117 | 2450 | 2045 | 1857 | 1831 |
(1739) | Avg. Sol | 3488.66 | 4095.44 | 3363.64 | 4385.42 | 2576.94 | 2094.62 | 2013.50 | |
AvgExc(%) | 100.61 | 135.51 | 93.42 | 152.18 | 48.19 | 20.45 | 15.78 | ||
S.D. | 172.62 | 177.55 | 281.92 | 230.87 | 190.61 | 112.02 | 93.94 | 91.93 | |
Avg. Time | 0.34 | 0.91 | 1.20 | 1.32 | 1.72 | 1.45 | 1.52 | 1.96 | |
A065-03f | Best Sol | 4161 | 4796 | 3965 | 5302 | 3060 | 2250 | 2042 | 2042 |
(1974) | Avg. Sol | 4491.94 | 5039.28 | 4152.68 | 5620.22 | 3152.58 | 2378.21 | 2261.64 | |
AvgExc(%) | 127.56 | 155.28 | 110.37 | 184.71 | 59.71 | 20.48 | 14.57 | ||
S.D. | 225.72 | 205.09 | 239.01 | 199.42 | 134.07 | 110.54 | 82.20 | 113.73 | |
Avg. Time | 0.51 | 0.90 | 1.31 | 1.16 | 1.86 | 1.41 | 1.49 | 1.86 | |
A071-03f | Best Sol | 4500 | 5126 | 3662 | 5369 | 2883 | 2339 | 2206 | 2206 |
(2054) | Avg. Sol | 4719.48 | 5436.40 | 4061.74 | 5868.64 | 3025.70 | 2544.12 | 2351.18 | |
AvgExc(%) | 129.77 | 164.67 | 97.75 | 185.72 | 47.31 | 23.86 | 14.47 | ||
S.D. | 200.98 | 234.93 | 332.35 | 279.62 | 175.79 | 120.32 | 93.88 | 109.87 | |
Avg. Time | 0.60 | 1.43 | 2.18 | 2.13 | 3.65 | 1.95 | 1.99 | 2.53 |
Further, to verify if GA using SCX (including mutation) found much different average solution from the average solutions found by other GAs using distance-based crossovers, we conducted Student’s t-test. Further, we verify whether GA using AEX found much different average solution from the average solutions found by other GAs using blind crossovers. The t-statistic values are reported in the
Instance | t-values against AEX | t-values against SCX | ||||
---|---|---|---|---|---|---|
PMX | OX | CX | GX | HX | MHX | |
A034-02f | 6.86 | 3.93 | 16.54 | 11.58 | 5.35 | 0.16 |
Better | AEX | AEX | AEX | SCX | SCX | ----- |
A036-03f | 6.69 | 19.70 | 26.02 | 15.89 | 11.00 | 4.86 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A039-03f | 15.01 | 32.68 | 27.04 | 14.20 | 8.60 | 1.75 |
Better | AEX | AEX | AEX | SCX | SCX | ----- |
A045-03f | 14.66 | 28.60 | 32.93 | 27.84 | 11.54 | 5.29 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A048-03f | 3.42 | 19.44 | 25.84 | 32.20 | 11.02 | 1.32 |
Better | AEX | AEX | AEX | SCX | SCX | ----- |
A056-03f | 2.65 | 15.38 | 19.63 | 21.75 | 8.46 | 5.01 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A065-03f | 7.22 | 21.93 | 33.00 | 38.08 | 8.03 | 3.26 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
A071-03f | 11.85 | 25.36 | 29.12 | 24.65 | 10.67 | 2.68 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
According to the results shown in
We now extend our study on symmetric instances.
Instance | Results | PMX | OX | AEX | CX | GX | HX | MHX | SCX |
---|---|---|---|---|---|---|---|---|---|
E-n22-k4 | Best Sol | 397 | 387 | 451 | 494 | 385 | 401 | 382 | 380 |
(375) | Avg. Sol | 415.85 | 414.95 | 489.05 | 548.55 | 439.75 | 408.23 | 399.55 | |
AvgExc(%) | 10.89 | 10.65 | 30.41 | 46.28 | 17.27 | 8.86 | 6.55 | ||
S.D. | 23.26 | 20.68 | 48.19 | 35.37 | 24.53 | 24.08 | 18.79 | 19.72 | |
Avg. Time | 0.06 | 0.08 | 0.14 | 0.01 | 0.07 | 0.12 | 0.13 | 0.11 | |
E-n51-k5 | Best Sol | 928 | 920 | 970 | 1262 | 863 | 564 | 526 | 528 |
(521) | Avg. Sol | 963.40 | 1015.15 | 998.10 | 1284.15 | 912.70 | 671.50 | 572.30 | |
AvgExc(%) | 84.91 | 94.85 | 91.57 | 146.48 | 75.18 | 28.89 | 9.85 | ||
S.D. | 37.24 | 27.20 | 38.24 | 38.66 | 45.07 | 40.21 | 31.07 | 26.75 | |
Avg. Time | 0.24 | 0.29 | 0.49 | 0.00 | 0.24 | 0.36 | 0.38 | 0.69 | |
E-n76-k7 | Best Sol | 1583 | 1524 | 1559 | 1861 | 1131 | 807 | 701 | 701 |
(682) | Avg. Sol | 1679.45 | 1681.05 | 1699.70 | 2055.75 | 1285.95 | 871.05 | 755.90 | |
AvgExc(%) | 146.25 | 146.49 | 149.22 | 201.43 | 88.56 | 27.72 | 10.84 | ||
S.D. | 50.45 | 56.13 | 59.87 | 63.33 | 47.29 | 39.74 | 25.57 | 34.59 | |
Avg. Time | 0.32 | 0.50 | 1.30 | 0.01 | 1.60 | 1.21 | 1.44 | 1.59 | |
E-n76-k8 | Best Sol | 1595 | 1676 | 1665 | 1905 | 1205 | 893 | 753 | 744 |
(735) | Avg. Sol | 1754.60 | 1773.05 | 1784.15 | 2111.65 | 1331.26 | 902.02 | 840.35 | |
AvgExc(%) | 138.72 | 141.23 | 142.74 | 187.30 | 81.12 | 22.72 | 14.33 | ||
S.D. | 40.53 | 52.80 | 64.74 | 65.11 | 40.16 | 45.06 | 26.63 | 31.71 | |
Avg. Time | 0.51 | 0.94 | 0.98 | 0.04 | 1.97 | 1.75 | 1.86 | 2.24 | |
E-n76-k10 | Best Sol | 1518 | 1535 | 1544 | 1845 | 1145 | 1013 | 855 | 848 |
(830) | Avg. Sol | 1802.95 | 1816.05 | 1750.60 | 2105.25 | 1367.75 | 1094.54 | 942.05 | |
AvgExc(%) | 117.22 | 118.80 | 110.92 | 153.64 | 64.79 | 31.87 | 13.50 | ||
S.D. | 58.16 | 57.02 | 134.42 | 58.09 | 34.69 | 35.12 | 26.87 | 28.53 | |
Avg. Time | 0.48 | 0.51 | 0.84 | 0.00 | 1.41 | 1.29 | 1.49 | 1.49 | |
E-n76-k14 | Best Sol | 1674 | 1636 | 1391 | 1973 | 1382 | 1165 | 1048 | 1046 |
(1021) | Avg. Sol | 1945.00 | 1914.90 | 1619.72 | 2196.48 | 1543.72 | 1306.21 | 1161.96 | |
AvgExc(%) | 90.50 | 87.55 | 58.64 | 115.13 | 51.20 | 27.93 | 13.81 | ||
S.D. | 64.32 | 47.98 | 64.70 | 56.80 | 28.16 | 35.14 | 23.99 | 27.54 | |
Avg. Time | 0.68 | 0.87 | 1.50 | 0.01 | 3.36 | 2.65 | 2.72 | 3.15 | |
E-n101-k8 | Best Sol | 2242 | 2268 | 2144 | 2702 | 1490 | 970 | 838 | 844 |
(815) | Avg. Sol | 2428.32 | 2439.64 | 2321.42 | 2897.20 | 1614.16 | 1045.52 | 930.40 | |
AvgExc(%) | 197.95 | 199.34 | 184.84 | 255.48 | 98.06 | 28.28 | 14.16 | ||
S.D. | 74.56 | 61.11 | 65.58 | 72.83 | 42.90 | 54.21 | 27.74 | 30.14 | |
Avg. Time | 0.59 | 0.95 | 1.56 | 0.02 | 4.57 | 2.94 | 3.00 | 3.34 | |
E-n101-k14 | Best Sol | 2386 | 2396 | 2307 | 2782 | 1654 | 1374 | 1090 | 1094 |
(1067) | Avg. Sol | 2484.55 | 2518.75 | 2403.10 | 2882.95 | 1678.45 | 1429.02 | 1250.25 | |
AvgExc(%) | 131.98 | 135.18 | 124.38 | 169.18 | 56.72 | 33.43 | 16.74 | ||
S.D. | 61.59 | 50.41 | 44.06 | 52.04 | 26.99 | 31.21 | 18.64 | 32.20 | |
Avg. Time | 0.66 | 0.96 | 1.32 | 0.01 | 2.57 | 1.82 | 1.88 | 2.22 |
Further, to verify if GA using SCX (excluding mutation) found much different average solution from the average solutions found by other GAs using the distance-based crossovers, we conducted Student’s t-test. Further, we verify whether GA using AEX found much different average solution from the average solutions found by other GAs using the blind crossovers. The t-statistic values are reported in the
Instance | t-values against AEX | t-values against SCX | ||||
---|---|---|---|---|---|---|
PMX | OX | CX | GX | HX | MHX | |
E-n22-k4 | −9.58 | −9.89 | 6.97 | 13.16 | 6.21 | 4.87 |
Better | PMX | OX | AEX | SCX | SCX | SCX |
E-n51-k5 | −4.55 | 2.54 | 36.82 | 45.46 | 14.38 | −0.61 |
Better | PMX | AEX | AEX | SCX | SCX | ----- |
E-n76-k7 | −1.81 | −1.59 | 28.60 | 63.83 | 15.86 | 0.69 |
Better | ----- | ----- | AEX | SCX | SCX | ----- |
E-n76-k8 | −2.71 | −0.93 | 24.97 | 68.81 | 9.37 | 2.05 |
Better | PMX | ----- | AEX | SCX | SCX | SCX |
E-n76-k10 | 2.50 | 3.14 | 16.95 | 69.28 | 26.51 | 3.37 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
E-n76-k14 | 24.96 | 25.65 | 46.89 | 67.85 | 22.62 | −0.51 |
Better | AEX | AEX | AEX | SCX | SCX | ----- |
E-n101-k8 | 7.54 | 9.23 | 41.13 | 91.29 | 12.99 | −0.81 |
Better | AEX | AEX | AEX | SCX | SCX | ----- |
E-n101-k14 | 7.53 | 12.09 | 49.26 | 74.22 | 30.61 | 3.25 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
According to
We now continue our study of the GAs with mutation on symmetric instances, and
Instance | Results | PMX | OX | AEX | CX | GX | HX | MHX | SCX |
---|---|---|---|---|---|---|---|---|---|
E-n22-k4 | Best Sol | 375 | 377 | 377 | 410 | 384 | 386 | 378 | 375 |
(375) | Avg. Sol | 391.80 | 398.75 | 406.20 | 454.70 | 391.45 | 404.31 | 383.40 | |
AvgExc(%) | 4.48 | 6.33 | 8.32 | 21.25 | 4.39 | 7.82 | 2.24 | ||
S.D. | 20.38 | 22.94 | 45.10 | 38.63 | 26.55 | 28.90 | 16.39 | 17.61 | |
Avg. Time | 0.13 | 0.15 | 0.13 | 0.16 | 0.14 | 0.22 | 0.23 | 0.21 | |
E-n51-k5 | Best Sol | 818 | 915 | 899 | 1085 | 830 | 542 | 523 | 526 |
(521) | Avg. Sol | 929.70 | 1005.80 | 977.90 | 1229.60 | 896.45 | 665.47 | 545.85 | |
AvgExc(%) | 78.45 | 93.05 | 87.70 | 136.01 | 72.06 | 27.73 | 4.77 | ||
S.D. | 54.06 | 39.13 | 33.68 | 62.84 | 42.76 | 33.54 | 13.92 | 12.40 | |
Avg. Time | 0.26 | 0.34 | 0.50 | 0.29 | 0.28 | 0.58 | 1.01 | 0.79 | |
E-n76-k7 | Best Sol | 1496 | 1541 | 1519 | 1678 | 1104 | 705 | 697 | 688 |
(682) | Avg. Sol | 1585.15 | 1665.25 | 1671.45 | 1820.55 | 1255.50 | 841.21 | 749.05 | |
AvgExc(%) | 132.43 | 144.17 | 145.08 | 166.94 | 84.09 | 23.34 | 9.83 | ||
S.D. | 50.24 | 48.32 | 62.16 | 53.23 | 21.18 | 34.85 | 16.72 | 21.98 | |
Avg. Time | 0.36 | 0.53 | 0.97 | 1.21 | 1.12 | 1.35 | 1.46 | 1.41 | |
E-n76-k8 | Best Sol | 1555 | 1661 | 1621 | 1749 | 1228 | 810 | 745 | 737 |
(735) | Avg. Sol | 1699.25 | 1766.50 | 1760.70 | 1945.10 | 1330.15 | 892.05 | 817.40 | |
AvgExc(%) | 131.19 | 140.34 | 139.55 | 164.64 | 80.97 | 21.37 | 11.21 | ||
S.D. | 49.07 | 36.58 | 46.51 | 60.63 | 30.56 | 31.24 | 25.56 | 22.60 | |
Avg. Time | 0.38 | 0.54 | 0.76 | 0.82 | 1.22 | 1.44 | 1.52 | 1.09 | |
E-n76-k10 | Best Sol | 1511 | 1527 | 1273 | 1839 | 1144 | 980 | 842 | 840 |
(830) | Avg. Sol | 1734.50 | 1777.85 | 1677.95 | 2076.65 | 1333.90 | 1049.75 | 928.24 | |
AvgExc(%) | 108.98 | 114.20 | 102.16 | 150.20 | 60.71 | 26.48 | 11.84 | ||
S.D. | 53.53 | 50.22 | 165.95 | 65.06 | 34.28 | 30.52 | 19.52 | 27.70 | |
Avg. Time | 0.40 | 0.46 | 0.82 | 0.05 | 1.38 | 1.33 | 1.34 | 1.12 | |
E-n76-k14 | Best Sol | 1661 | 1627 | 1336 | 1960 | 1346 | 1170 | 1041 | 1038 |
(1021) | Avg. Sol | 1770.00 | 1753.70 | 1467.10 | 2034.25 | 1384.15 | 1243.05 | 1130.40 | |
AvgExc(%) | 73.36 | 71.76 | 43.69 | 99.24 | 35.57 | 21.75 | 10.71 | ||
S.D. | 54.13 | 46.05 | 73.92 | 40.79 | 26.74 | 18.69 | 15.68 | 28.07 | |
Avg. Time | 0.47 | 0.53 | 1.17 | 0.04 | 1.62 | 1.18 | 1.49 | 1.18 | |
E-n101-k8 | Best Sol | 2137 | 2188 | 2140 | 2445 | 1466 | 909 | 842 | 832 |
(815) | Avg. Sol | 2235.50 | 2300.30 | 2227.80 | 2475.75 | 1470.30 | 947.90 | 891.70 | |
AvgExc(%) | 174.29 | 182.25 | 173.35 | 203.77 | 80.40 | 16.31 | 9.41 | ||
S.D. | 89.03 | 76.73 | 55.42 | 55.45 | 39.88 | 33.20 | 28.56 | 33.47 | |
Avg. Time | 0.73 | 1.12 | 1.49 | 2.16 | 2.13 | 2.29 | 2.38 | 2.14 | |
E-n101-k14 | Best Sol | 2313 | 2385 | 2246 | 2541 | 1591 | 1321 | 1090 | 1091 |
(1067) | Avg. Sol | 2429.15 | 2474.40 | 2303.60 | 2667.80 | 1628.80 | 1400.60 | 1196.30 | |
AvgExc(%) | 126.81 | 131.04 | 115.09 | 149.09 | 52.08 | 30.77 | 11.70 | ||
S.D. | 57.96 | 43.32 | 43.15 | 81.75 | 31.04 | 33.19 | 27.60 | 21.37 | |
Avg. Time | 1.08 | 1.04 | 1.23 | 1.33 | 2.38 | 1.95 | 2.36 | 2.52 |
Further, to verify if GA using SCX (including mutation) found much different average solution from the average solutions found by other GAs using the distance-based crossovers and mutation for symmetric instances, we conducted Student’s t-test. Further, we verify whether GA using AEX found much different average solution from the average solutions found by other GAs using the blind crossovers and mutation. The t-statistic values are reported in the
Instance | t-values against AEX | t-values against SCX | ||||
---|---|---|---|---|---|---|
PMX | OX | CX | GX | HX | MHX | |
E-n22-k4 | −2.04 | 2.01 | 5.72 | 3.16 | 5.64 | 1.85 |
Better | PMX | AEX | AEX | SCX | SCX | ----- |
E-n51-k5 | −2.00 | 7.85 | 24.71 | 58.27 | 23.42 | −0.68 |
Better | PMX | AEX | AEX | SCX | SCX | ----- |
E-n76-k7 | −7.56 | −0.55 | 12.75 | 127.02 | 18.62 | 4.42 |
Better | PMX | ----- | AEX | SCX | SCX | SCX |
E-n76-k8 | −6.36 | 4.24 | 16.89 | 98.90 | 17.95 | 4.98 |
Better | PMX | AEX | AEX | SCX | SCX | SCX |
E-n76-k10 | 2.27 | 4.03 | 15.66 | 72.59 | 29.36 | 6.48 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
E-n76-k14 | 23.14 | 23.04 | 47.02 | 50.26 | 28.49 | 5.36 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
E-n101-k8 | 0.51 | 5.36 | 22.14 | 80.03 | 9.33 | 1.06 |
Better | ----- | AEX | AEX | SCX | SCX | ----- |
E-n101-k14 | 12.16 | 19.55 | 27.58 | 86.99 | 39.03 | 3.17 |
Better | AEX | AEX | AEX | SCX | SCX | SCX |
According to
Overall, SCX is the best and MHX is the second best, and CX is the worst for the CVRP. To make a ranking of the crossovers, we conducted a series of Student’s t-tests on all kinds of instances together. In fact, for each pair of crossovers, we tested the hypothesis to know which one is better. We summarized the results in
Crossover | Inferior crossovers |
---|---|
SCX | MHX, HX, GX, AEX, PMX, OX, CX |
MHX | HX, GX, AEX, PMX, OX, CX |
HX | GX, AEX, PMX, OX, CX |
GX | AEX, PMX, OX, CX |
AEX | PMX, OX, CX |
PMX | OX, CX |
OX | CX |
In this research we studied the capacitated vehicle routing problem (CVRP) that is a mixture of the travelling salesman problem (TSP) and the bin packing problem (BPP). A number of crossovers in genetic algorithms (GAs) were suggested for the TSP that can be utilized for the CVRP. Selecting efficient crossover may lead to efficient GA. We developed eight GAs using four blind crossovers-partially mapped crossover (PMX), order crossover (OX), alternating edges crossover (AEX), and cycle crossover (CX), and four distance-based crossovers-heuristic crossover (HX), greedy crossover (GX), modified heuristic crossover (MHX) and sequential constructive crossover (SCX) without mutation, and another eight GAs using above eight crossovers with mutation operator. First, the crossovers were illustrated using same parent chromosomes for building offspring(s), and then all GAs were coded in Visual C++. The usefulness of the crossovers is determined by solving some asymmetric and symmetric instances of numerous sizes. The investigational results reveal the usefulness of AEX among the blind crossovers, and SCX among the distance-based crossovers for the CVRP. So, our study revealed that the distance-based crossovers are much superior to the blind crossovers. Further, we observed that the best crossover is SCX, the 2nd best is MHX, and the worst is CX. This estimation is validated by Student’s t-test at 95% confidence level. If only a single crossover operator is applied, then, whether mutation is applied or not, the best performance is accomplished SCX. Exceptionally bad performance is shown by CX, if mutation is present or not.
There are many crossover operators present in the literature, but all of them may not provide legal solution to the CVRP. Therefore, this paper is confined to study few crossover operators. We aimed to compare amongst eight crossovers without and with a mutation operator. Our aim was not to develop efficient GA. We did not apply either a local search method or merge some heuristics to enhance the solution value to obtain optimal solution. We restricted ourselves to design only simple GAs. Further, the highest crossover probability is set to present exact character of crossovers. Though SCX obtained very good results, still it got stuck in local minima in the initial generations. Hence, successful local search and immigration procedures might be merged to hybridize the GA for obtaining improved results to various instances, which is our next research.