Penentuan Rute Pengiriman Ice Tube di Kota Malang dengan Algoritma Genetika
DOI:
https://doi.org/10.24002/jbi.v11i1.2559Abstract
Abstract. Determining routes for ice tube delivery in Malang is a complex combinatorial problem classified as NP-hard problem. This study aims for optimizing the sales travel routes determination for the delivery to several customers by considering the efficiency of distance traveled. This problem is modeled in the form of Multi Salesman Traveling Problem. Genetic algorithm was used to optimize the determination of ice tube delivery routes that must be taken by each sales. Problems were coded by using permutation representation in which order crossover and swap mutation methods were used for the reproduction process. The process of finding solution was done by using elitism selection. The best genetic algorithm parameters obtained from the test results are the number of iterations of 40 and the population of 40, with the shortest route of 30.3 km. The final solution given by the genetic algorithm is in the form of a travel route that must be taken by each ice tube sales.
Keywords: genetic algorithm, mutli travelling salesman problem, optimization, route
Abstrak. Penentuan rute pengiriman ice tube di kota Malang merupakan permasalahan kombinatorial kompleks yang diklasifikasikan sebagai permasalahan NP-hard. Penelitian ini bertujuan untuk melakukan optimasi dalam pembentukan rute perjalanan sales dalam melakukan pengiriman ke beberapa pelanggan dengan mempertimbangkan efisiensi jarak tempuh. Permasalahan ini dimodelkan dalam bentuk Multi Salesman Travelling Problem. Algoritme genetika digunakan untuk mengoptimalkan pembentukan rute pengiriman ice tube yang harus dilalui oleh setiap sales. Permasalahan dikodekan menggunakan representasi permutasi, dengan proses reproduksi menggunakan metode order crossover dan swap mutation. Proses pencarian solusi dilakukan menggunakan elitism selection. Parameter algoritme genetika terbaik yang didapatkan dari hasil pengujian adalah banyaknya iterasi sebesar 40 dan banyaknya populasi sebesar 40, dengan rute terpendek sebesar 30.3 km. Solusi akhir yang diberikan oleh algoritme genetika berupa rute perjalanan yang harus ditempuh oleh setiap sales ice tube.
Kata Kunci: algoritme genetika, multi travelling salesman problem, optimasi, rute
References
Y. Ding, Research on TSP problem in e-commerce tourist based on ant colony algorithm, Int. J. u- e-Service, Sci. Technol., vol. 7(3), pp. 277–288, 2014.
M. Dorigo, V. Maniezzo, and A. Colorni, Ant System: optimization by a colony of cooperating agents, IEEE Trans. Syst. Man, Cybern. Part B Cybern., vol. 26(1), pp. 29–41, 1996.
F. Ramadhani, F. A. Fathurrachman, R. Fitriawanti, A. C. Rongre, and V. N. Wijayaningrum, Optimasi pendistribusian barang farmasi menggunakan algoritma genetika, Kumpul. J. Ilmu Komput., vol. 5(2), pp. 159–168, 2018.
V. N. Wijayaningrum and W. F. Mahmudy, Optimization of ship’s route scheduling using genetic algorithm, Indones. J. Electr. Eng. Comput. Sci., vol. 2(1), pp. 180–186, 2016.
E. Suhartono, Optimasi penjadwalan mata kuliah dengan algoritma genetika (studi kasus di amik jtc semarang), INFOKAM, vol. 11(5), pp. 132–146, 2015.
N. A. S. Otalora and F. D. la Rosa, “Path Planning and Following using Genetic Algorithms to Solve the Multi-Travel Salesman Problem in Dynamic Scenarios,” in Proceedings of the 2017 18th International Conference on Advanced Robotics (ICAR), 2017, pp. 204–209.
X.-S. Yang, Nature-Inspired Metaheuristic Algorithms, Second Edi. Luniver Press, 2010.
S. Singh and E. A. Lodhi, Comparison study of multiple traveling salesmen problem using genetic algorithm, Int. J. Comput. Sci. Netw. Secur., vol. 14(7), pp. 107–110, 2014.
F. Y. Saptaningtyas, Multi traveling salesman problem (MTSP) dengan algoritma genetika untuk menentukan rute loper koran di agen surat kabar, Pythagoras, vol. 7(2), pp. 55–64, 2012.
Q. Kotimah, W. F. Mahmudy, and V. N. Wijayaningrum, Optimization of fuzzy tsukamoto membership function using genetic algorithm to determine the river water, Int. J. Electr. Comput. Eng., vol. 7(5), pp. 2838–2846, 2017.
F. Glover and G. A. Kochenberger, Handbook of Metaheuristics. United States of America: Kluwer Academic Publisher, 2003.
R. L. Haupt and S. E. Haupt, Practical Genetic Algorithms. United States of America: John Willey & Sons, Inc., 2004.
D. Gupta and S. Ghafir, An overview of methods maintaining diversity in genetic algorithms, Int. J. Emerg. Technol. Adv. Eng., vol. 2(5), pp. 56–60, 2012.
A. E. Eiben and J. E. Smith, Introduction to Evolutionary Computing, Second Edi. United States of America: Springer, 2015.
A. P. Engelbrecht, Computational Intelligence. England: John Wiley & Sons. Inc., 2007.
Downloads
Published
Issue
Section
License
Copyright of this journal is assigned to Jurnal Buana Informatika as the journal publisher by the knowledge of author, whilst the moral right of the publication belongs to author. Every printed and electronic publications are open access for educational purposes, research, and library. The editorial board is not responsible for copyright violation to the other than them aims mentioned before. The reproduction of any part of this journal (printed or online) will be allowed only with a written permission from Jurnal Buana Informatika.
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.
