TRAVELLING SALESMAN PROBLEM (TSP) OPTIMIZATION SEED DIS-TRIBUTION USING GENETIC ALGORITHM
Abstract
Abstract: Distribution is an important the business sector, the agricultural sector for distributing seeds to ensure the location of customers selling seeds. Problems that are often encountered seed distribution process are the efficiency of the time and distance distribution. Re search will build software entering initial location data and several dynamically added consumer agents. The distance parameter uses latitude-longitude integrated on google maps and detects varying store locations, the generation of chromosomes or the best distribution path with the minimum distance route. The heuristic approach using the Genetic Algorithm imitates the concept of biological evolution of random exchange structure series. This study is to distribute 3 types of seeds with a choice of weights that have been divided into 3 areas located on the map of Indonesia using land routes. The results of the test of the population of the average fitness value tend to remain from the previous value of 1-10 the fitness value and the optimum iteration with 9-12 with an average fitness value of 44.2. Optimal results are obtained when Mr is higher than the Cr values. Thus, the Genetic Algorithm can be used for TSP seed distribution paths. 1:2 fitness evaluation compared with the usual estimates used .
Keywords: Genetic Algorithm; Route Optimization; Seed Distribution; TSP
Abstrak: Distribusi menjadi hal penting berwirausaha, salah satunya pada bidang pertanian untuk pendistribusian benih sampai lokasi tujuan. Permasalahan sering ditemui dalam proses pendistribusian adalah efektifan, efisiensi waktu dan jarak tempuh. Sehingga penelitian akan membangun perangkat lunak dengan memasukan data titik lokasi awal dan beberapa lokasi tujuan agen konsumen ditambahkan secara dinamis. Parameter jarak menggunakan latitude-longitude terintegrasi pada google maps yang mendeteksi keberadaan lokasi, selanjutnya diketahui generasi kromosom atau jalur distribusi terbaik dengan rute minimum. Pendekatan Heuristic menggunakan Algoritma Genetika meniru konsep evolusi biologis deretan struktur pertukaran informasi secara acak. Tujuan dalam penelitian ini dapat mendistribusikan jenis benih dengan pilihan bobot yang telah terbagi dalam wilayah lokasi. Satu wilayah lokasi terdapat beberapa lokasi toko ditambahkan secara dinamis, dengan proses yang sudah ditentukan titik awal keberangkatan. Penelitian ini menekankan pada proses penentuan rute lokasi saja. Hasil pengujian jumlah populasi rata-rata nilai fitness cenderung bersifat tetap dari nilai sebelumnya selisih 1-10 nilai fitness dan iterasi optimum dengan 9-12 dengan rata-rata nilai fitness 44,2. Hasil optimum didapatkan ketika Mutation rate (Mr) lebih tinggi dibanding nilai Crossover rate (Cr). Maka, Algoritma Genetika bisa digunakan untuk TSP jalur distribusi benih pengujian menghasilkan evaluasi fitnes 1:2 untuk Algoritma Genetika dibandingkan dengan estimasi jarak biasa digunakan.
Kata kunci: Algoritma Genetika; Distribusi Benih; Optimalisasi Rute; TSP
References
Minister of Agriculture Regulation, “Plant Cultivation System,†2014.
JB Fant et al. , “What to do when we can't bank on seeds: What botanic gardens can learn from the zoo community about conserving plants in living collections,†Am. J. Bot , vol. 103, pp. 1541–1543, 2016.
L. Han, BT Luong, and S. Ukkusuri, “An Algorithm for the One Commodity Pickup and Delivery Traveling Salesman Problem with Restricted Depot,†Networks Spat. econ. , vol. 16, no. 3, pp. 743–768, Sept. 2016, doi:10.1007/s11067-015-9297-3.
DT Wiyanti, “Optimization Algorithm for Solving the Traveling Salesman Problem,†J. Transform. , vol. 11, no. 1, pp. 1–6, 2013.
EE Yurek and HC Ozmutlu, “A decomposition-based iterative optimization algorithm for traveling salesman problem with drones,†Transp. res. Part C Emerg. Technol. , vol. 91, pp. 249–262, Jun. 2018, doi:10.1016/j.trc.2018.04.009.
AA Alfaraby, AM Hilda, and M. Kamayani, "Scheduling of Memorizing the Qur'an with Genetic Algorithms," in Proceedings of the Teknoka National Seminar , 2018, vol. 3, no. 2502, pp. 35–41.
L. Xie and A. Yuille, “Genetic CNN,†in Computer Vision Foundation , 2017, pp. 1379–1388.
J. Wang, OK Ersoy, M. He, and F. Wang, “Multi-offspring genetic algorithm and its application to the traveling salesman problem,†Appl. Soft Computing. , vol. 43, pp. 415–423, Jun. 2016, doi:10.1016/j.asoc.2016.02.021.
H. Yang and X. Hu, “Wavelet neural network with improved genetic algorithm for traffic flow time series prediction,†Optik (Stuttg). , vol. 127, no. 19, pp. 8103–8110, Oct. 2016,
SK Pal and PP Wang, Genetic algorithms for pattern recognition . CRC press, 2017.
VN Wijayaningrum and WF Mahmudy, “Optimization of Ship's Route Scheduling Using Genetic Algorithm,†Indonesia. J. Electr. eng. Comput. science. , vol. 2, no. 1, pp. 180–186, 2016.
N. Metawa, MK Hassan, and M. Elhoseny, “Genetic algorithm based model for optimizing bank lending decisions,†Expert Syst. app. , vol. 80, pp. 75–82, 2017.
AAR Hosseinabadi, J. Vahidi, B. Saemi, AK Sangaiah, and M. Elhoseny, “Extended Genetic Algorithm for solving open-shop scheduling problems,†Soft Comput. , vol. 23, no. 13, pp. 5099–5116, Jul. 2019, doi:10.1007/s00500-018-3177-y.
V. Ho-Huu, T. Nguyen-Thoi, T. Truong-Khac, L. Le-Anh, and T. Vo-Duy, “An improved differential evolution based on roulette wheel selection for shape and size optimization of truss structures with frequency constraints,†Neural Comput. app. , vol. 29, no. 1, pp. 167–185, 2018.
MZ Ali, NH Awad, PN Suganthan, AM Shatnawi, and RG Reynolds, “An improved class of real-coded Genetic Algorithms for numerical optimization,†Neurocomputing , vol. 275, pp. 155–166, Jan. 2018,
AM Aibinu, H. Bello Salau, NA Rahman, MN Nwohu, and CM Akachukwu, “A novel Clustering based Genetic Algorithm for route optimization,†Eng. science. Technol. an Int. J. , vol. 19, no. 4, pp. 2022–2034, Dec. 2016, doi:10.1016/j.jestch.2016.08.003.
RS Zebulum, MA Pacheco, and MMB Vellasco, Evolutionary Electronics: Automatic Design of Electronic Circuits and Systems by Genetic Algorithms . CRC press, 2018.
ASC Alencar, ARR Neto, and JPP Gomes, “A new pruning method for extreme learning machines via genetic algorithms,†Appl. Soft Computing. , vol. 44, pp. 101–107, 2016.
J. Kratica, “Computing strong metric dimension of some special classes of graphs by genetic algorithms,†Yugosl. J. Opera. res. , vol. 18, no. 2, 2016.
S. Fachrurrazi, “Application of Genetic Algorithm in Optimizing Fertilizer Distribution at PT Pupuk Iskandar Muda Aceh Utara,†TECHSI , vol. 5, pp. 47–66, 2013.
A. Hussain, YS Muhammad, MN Sajid, I. Hussain, AM Shoukry, and S. Gani, “Genetic Algorithm for Traveling Salesman Problem with Modified Cycle Crossover Operator,†vol. 2017, pp. 1–8, 2017.
P. Vaishnav, N. Choudhary, and K. Jain, “Traveling Salesman Problem Using Genetic Algorithm : A Survey,†vol. 2, no. 3, pp. 105–108, 2017.
S. Rohman, L. Zakaria, A. Asmiati, and A. Nuryaman, “Optimization of Traveling Salesman Problem with Genetic Algorithm in the Case of Goods Distribution of PT. Pos Indonesia in Bandar Lampung City,†J. Mat. Integra. , vol. 16, no. 1, pp. 61–73, 2020.
DA Suprayogi and WF Mahmudy, “Application of Genetic Algorithm Traveling Salesman Problem with Time Window: A Case Study of Laundry Shuttle Routes,†J. Buana Inform. , vol. 6, no. 2, pp. 121–130, 2015.
SS Choong, L. Wong, and C. Peng, “An Artificial Bee Colony Algorithm With a Modified Choice Function for the Traveling Salesman Problem,†Elsevier , vol. 44, no. June 2018, pp. 622–635, 2019, doi:10.1016/j.swevo.2018.08.004.
M. Mavrovouniotis, FM Müller, S. Yang, and S. Member, “Ant Colony Optimization With Local Search for Dynamic Traveling Salesman Problems,†vol. 47, no. 7, pp. 1743–1756, 2017, doi:10.109/TCYB.2016.2556742.
R. Rais, “Classification of Pests and Diseases of Corn Plants Using Neural Networks Based on Genetic Algorithms,†in SENIT , 2016, vol. 1, pp. 51–56.
RH Saputra, J. Nangi, and LMB Aksara, “Application of the Branch and Bound Algorithm in Determining the Shortest Path to Search Lodging and Hotels in Kendari City,†vol. 3, no. 1, pp. 127–134, 2017.
