A Hybrid Genetic-Variable Neighborhood Algorithm for Optimization of Rice Seed Distribution Cost

The distribution process from the production plant to consumers must go through several local distributors in several areas (multi-level) such as distributor centers, retailers, and agents [1]. The number of possible distribution networks that are formed to obtain minimal costs is a problem that needs to be considered. Determining the distribution network will be more complex when a company produces more than one type of product (multi-product) [2-4].

1.png

Figure 1. Multi-level distribution model

Based on Figure 1, the multi-level distribution model has many possible solutions to form the right distribution network, characterized by minimal costs [5, 8]. To minimize distribution costs, it is necessary to formulate a mathematical formulation in several variables to search for minimal costs and several main constraints that will affect the distribution network [5].

The data in this study are obtained through an interview process at a rice seed company. The data is adjusted to the problems in this study so that the data used are data on the stock capacity of each product for each level, vehicle capacity, number of vehicles, vehicle fixed costs, and costs of several products for each level of a distributor [8]. So the distribution problem can be adequately solved, and it is necessary to form a mathematical formulation for both the objective function and the constraints that follow it. The first is to form a formulation to describe the objective function of the distribution, which is the most minimal cost, so that to search for costs, the function used is in Eq. (1) which consists of several variables.

$z=\sum_{i=0}^{I}\left[\sum_{j=0}^{J} \sum_{k=0}^{K j} \sum_{r=0}^{R} \sum_{p=0}^{P j}\left(\left(X_{i j k r p} C_{i j p}\right)+C f_{i j k r}\right) S t_{i j k r}\right]$    (1)

i $\in$ {1, 2,..., I} is the level of distribution delivery, j $\in$ {1, 2,..., J} is the distributor unit that acts as the sender while r {1, 2,..., R} as order. P $\in$ {1, 2,..., P} is the type of product ordered, and k $\in$ {1, 2,..., K} is the vehicle owned by the distributor unit sending j to distribute its products. X_ijkrp represents the number of units of goods to be shipped, C_vbijp is a variable cost for each product, C_fijkr is the fixed cost of delivery, and S_tijkr is the status that the distributor at level i is shipping or not with his k vehicles {0,1}. After knowing the mathematical formulation of the following distribution problem is to form a mathematical formulation for the constraints that must be met so that the resulting solution is minimal in cost and meets the existing constraints so that the distribution problem can be solved correctly.

The demand constraint function is related to the limit on the number of orders from the customer so that the number of goods ordered by the customer (O_irp) must be the same as the goods sent later to the customer. The constraint function for the number of orders is shown in Eq. (2).

$\sum_{j=0}^{J} \sum_{k=0}^{K j} \sum_{r=0}^{R} \sum_{p=0}^{P j} X_{i j k r p}=O r_{i r p}$    (2)

The function of the vehicle capacity constraint for each distributor unit is the capacity of the vehicle used. An item is sent to the customer or the level below then the goods will be transported by the vehicle. The problem is that the vehicle capacity of each sending distributor (C_pijp) has a capacity limit that should not be violated. The constraint function for vehicle capacity is shown in Eq. (3).

$\sum_{j=0}^{J} \sum_{k=0}^{K j} \sum_{r=0}^{R} \sum_{p=0}^{P j} X_{i j k r p} \leq C p_{i j p}$    (3)

The inventory constraint function for each product at the distributor unit (K_cpijkp). Each distribution always has stock availability of goods. When a distributor acts as a sender, a stock check is carried out, the number of goods to be sent must not exceed the stock. The constraint function for the distribution unit stock of the sender is shown in Eq. (4).

$\sum_{j=0}^{J} \sum_{k=0}^{K j} \sum_{r=0}^{R} \sum_{p=0}^{P j} X_{i j k r p} \leq K c p_{i j k p}$    (4)

GA is a method that adopts individual biological traits in natural selection [14]. There are several steps in solving problems using GA, namely starting from chromosomal representation, reproduction, evaluation, and selection. The evaluation process in GA is used to measure how well an individual can provide a solution by considering the fitness value. The higher the fitness value produced by an individual in the next generation, the higher the probability of being selected as a solution [15]. Pseudocode hybrid GA-VNS is show in Figure 2. The GA-VNS hybridization process begins by running the GA algorithm until a certain iteration and then running the VNS algorithm to obtain the optimal fitness value. The GA-VNS hybridization architecture is shown in Figure 3.

2.png

Figure 2. Pseudocode VNS algorithm

3.png

Figure 3. GA-VNS hybridization architecture

The proportion of genetic algorithm hybridization is done with a percentage of 50 percent of iterations. The hybridization scenario of genetic algorithms and VNS to improve reproductive outcomes was carried out in the mid to late generation.

4.1 Chromosome representation and population initialization

Chromosome representation is a process for modeling the solution of a problem. Chromosome representation is the initial and most important process to provide a solution to a problem. There are various kinds of coding in genetic algorithms, in this study using real-coded. The structure of the chromosomes in the genetic algorithm has a solution structure, as shown in Figure 4.

4.png

Figure 4. GA-VNS hybridization architecture

Each column contained in the solution represents the number of units of goods that will be sent to the ordering distributor. Each chromosome is also divided into segments. The number of segments depends on the number of levels required based on the order. Each segment has several subsegments. A subsegment of the "i" level segment is the sending distributor unit "j". The sending distributor sub-segment has a vehicle sub-segment that is used to make deliveries. Vehicle sub-segment is a distributor unit that places an order. The type of product ordered "p" becomes a sub-segment of the ordering distributor

4.2 Fitness function

A chromosome in the genetic algorithm has a function value used to measure the quality of the resulting solution. The function used is the fitness function. In the selection process, the fitness value is used to determine the selected chromosome. The greater the fitness value on the chromosome, the more likely it is to be selected as a solution. In this study, the fitness function is used to obtain the minimum distribution cost value. The formula used to find the fitness value is shown in Eq. (5).

fitness $=\frac{1}{Z}$    (5)

Z is the distribution cost shown in Eq. (1) which is owned by each chromosome.

4.3 Reproduction

The reproduction stage is a unique process owned by genetic algorithms to produce new individuals. Each new individual represents the solution to a problem. The reproduction process has two operators, namely crossover and mutation, which aim to explore further and deeper to find new individuals. Both operators aim to find new individuals who are better at solving problems [16]. There is a crossover rate (cr), and in the mutation operator, there is a mutation rate (Mr). The crossover rate and mutation rate function determine the number of new individuals produced in each process in one generation.

4.4 Crossover

One of the operators forming new individuals in the reproduction process is crossover. Crossover forms a new individual from two parents. The results obtained will vary because it inherits the properties of its two parents. The number of new individuals is obtained by multiplying the population size (Pop size) and the crossover rate (Cr). The crossover operator has various models that can be used, including one-cut-point, two-cut-point, and extended intermediate.

4.4.1 One-cut-point crossover

One-cut-point is a crossover model with one cut-off point for each gen. The mechanism is to cut the position of the gen in the two-parent individuals that have been randomly selected. Each parent was crossed until the cutting point between the first parent and the second parent [17]. An illustration of the crossover process with a one-cut-point model is shown in Figure 5.

5.png

Figure 5. One-cut-point crossover Mechanism

where, {x1, ..., } and yε{y1, ..., yn} are two randomly selected parent individuals and {z1, ..., } is the result of a crossover process called a new individual / child.

4.4.2 Two-cut-point crossover

Two-cut-point is developing the one-cut-point model that applies a cut point at two random gene positions on the chromosome. The new individual in this model results from the exchange of gene values between the two selected positions to the second individual [17]. An overview of the two-cut-point model at the second and sixth gene positions is illustrated in Figure 6.

6.png

Figure 6. Two-cut-point crossover mechanism

4.4.3 Extended intermediate

Extended intermediate crossover is a model that aims to change gene values based on a random number "α" with the difference in gene values in both individuals [18]. Eq. (6) is the result search function with an extended intermediate model.

$Z_{i}=x_{i}+a\left(y_{i}-x_{i}\right)$    (6)

4.5 Mutation

The second operator in the reproduction process that characterizes the genetic algorithm is mutation. Unlike the crossover operator, which must use two parents, the mutation operator only uses one parent to generate new individuals. The number of new individuals resulting from the multiplication of population size (pop size) and mutation rate (Mr). The mutation operator has several models, including: swap, insertion and simple random.

4.5.1 Swap

One of the mutation operator models is swap. This mutation operator model is to exchange values between two randomly selected gene positions [19].

4.5.2 Insertion

The insertion model is inserting the value of a particular position gene into another gene position. Gene values are generated randomly. The genes included in the insertion range will be shifted until they occupy the correct position with the number of genes [19, 20].

4.5.3 Simple random

Simple random is a mutation operator model that generates a random number (r) to increase or decrease the value of each gene after being added to 1. Variable Range (r) has a value of -0.1 to 0.1. Eq. (7) is a mathematical formulation on simple random mutation.

$x_{i}=x_{i}(1+r) \quad i=1, \ldots, n$    (7)

The reproductive process will be decided whether it needs to be repaired. If the reproduction results still reach the optimum local value, it will proceed to the hybridization process using variable neighborhood search (VNS). The hybridization process is carried out based on the generation parameters. In this mechanism, the percentage of hybridization is 50%. The hybridization process is carried out when the number of generations reaches half of the generations. For example, if the initially declared generation is 1000, then hybridization to improve reproduction results starts from the 500th generation. This reproduction will enter the selection process.

4.6 Selection

The selection process is to choose several chromosomes of population size (pop size) that will survive to become a new population in the following generation process based on the fitness value obtained. Several types of selection models in genetic algorithms, such as the roulette wheel, consider the cumulative probability of each individual's fitness value and elitism used in solving multi-level distribution problems [8]. The elitism selection model is to sort in descending order. In addition to the roulette wheel and elitism, there is also a binary tournament selection model. The binary tournament selection model compares the fitness value between two randomly selected individuals, and the individual with the most excellent fitness will be selected in the new population in the next generation.

The multi-level and multi-product distribution problem in this research is solved by forming a mathematical model of several variables whose goal is to get the minimum cost. The variables used are the number of products, variable costs, vehicles used, fixed costs, and delivery status. The variables used to resolve some of the constraints that occur in the distribution process, such as the number of products distributed, must be the same as the number of orders and do not exceed the vehicle's maximum capacity or the amount of stock owned.

Based on the mathematical model compiled, the solution to the problem of rice seed distribution consists of a series of genes. Each gene of the chromosome contains an actual number indicating the number of products to be distributed. The best solution is selected based on the resulting fitness value. The greater the fitness value indicates the minimal cost of the distribution process.

Based on the test results of several selection models, the elitism model obtains the best fitness value. Based on testing the parameter values and the production operator model on the GA-VNS algorithm, the GA-VNS algorithm provides a solution with near-optimal results with relatively the same computational time compared to the GA algorithm, namely 279332 ms and 265091 ms. The fitness results obtained from the GA-VNS algorithm are also better, namely 32392960 and the classic GA, which is 32716150. The fitness results generated by the GA-VNS algorithm provide the most minimal cost with a savings of 16391815.8.