Comparison of Genetic Algorithm and Prim’s Algorithm in Distribution Path Optimization

Abstract

Optimization is a way to get better and more efficient results from a problem, one of which is a transportation problem. Optimization in this research is used in minimizing the distribution path by using genetic algorithm and prim’s algorithm. This research aims to evaluate the performance of genetic algorithms and prim algorithms on distribution path optimization by considering more than one parameter, namely the distribution distance from source to destination, the amount of transportation, transportation capacity, and the number of product requests from distribution to destination. In addition, this research aims to apply the most effective algorithm to the dataset to see how optimal an algorithm is when applied to data on a transportation problem. The methods used in this research are genetic algorithm and prim’s algorithm. Genetic algorithm applies an evolutionary system while prim's algorithm applies a connected graph system. Genetic algorithm finds the optimal solution on the distribution path by looping until it finds the optimal solution of the optimal. Prim's algorithm finds the optimal solution on the transportation path by looking at the path with the shortest distance from the source to get the optimal result. Although the characteristics of these two methods are different, both methods can be used to minimize distribution lines with various parameters in transportation problems. This research is a simulation study. Simulation data is generated with three scenarios: short route transportation problem, medium route transportation problem, and long route transportation problem. The three scenarios are applied to three datasets repeated 50 times, with certain criteria on the constraint function. The datasets of the three scenarios are analyzed using genetic algorithms and prim’s algorithms to obtain the optimal model as in the objective function of minimizing distance. The optimal model obtained during 50 iterations will be collected and evaluated for the optimal value of the results of the genetic algorithm and the prim algorithm. The value with the smallest distance in both algorithms will be the most optimal. This is done for all three scenarios so that the simulated data generated matches the actual data and can be used for data on a wide scale, and is more flexible. The most effective algorithm will be used on simulated data to see the optimal model generated after using the most effective algorithm. This aims to be applied to data that occurs in the field. The results show that the genetic algorithm can optimize the distance better than the prim’s algorithm. This is seen in the results of the optimization model on the objective function, computation time, and vehicle usage. Genetic algorithms can minimize distance and vehicle usage better than the prim’s by using source, destination, demand, vehicle, and transportation capacity parameters. Genetic algorithms can solve complex problems such as the addition of parameters in transportation problems by considering all parameters by using iteration to determine the optimal path, so that not only is the distance optimized, the use of vehicles can be optimized. Although the prim algorithm is faster in computation, the difference in computation time is not too significant, so that the genetic algorithm can still be used for distribution line optimization. Simulation data analysis using genetic algorithms has an optimal model that can be used if this algorithm is applied to distribution line data, so that it is faster in case of transportation problems. In conclusion, this research succeeded in optimizing the distribution path by considering several parameters, namely the distribution distance from source to destination, the amount of transportation, transportation capacity, and the amount of product demand from distribution to destination. Genetic algorithm is a more effective algorithm when compared to the prim’s algorithm in transportation problems.