PENGGUNAAN ALGORITMA GENETIKA UNTUK MENENTUKAN LINTASAN TERPENDEK. STUDI KASUS LINTASAN BRT (BUS RAPID TRANSIT) MAKASSAR
| Main Author: | Rheeza Effrains, Karels |
|---|---|
| Format: | Article |
| Terbitan: |
, 2017
|
| Subjects: | |
| Online Access: |
http://repository.unhas.ac.id/handle/123456789/23616 |
Daftar Isi:
- ABSTRAK Lintasan terpendek merupakan salah satu kajian yang berkaitan dengan graf. Permasalahan BRT (Bus Rapid Transit) merupakan salah satu contoh kasus yang dapat dirumuskan sebagai sebuah permasalahan graf yang berkaitan dengan lintasan terpendek. Pada kasus ini, titik (vertex) merepresentasikan halte sedangkan sisi (edge) merepresentasikan jalur penghubung antara dua halte. Jika bobot sisi menyatakan panjang jalur antara dua halte, maka dengan mengasumsikan setiap dua halte memiliki jalur penghubung, maka permasalahan lintasan terpendek berkaitan dengan pencarian jalur yang melalui semua halte tepat sekali dan dengan total jarak terkecil. Pada tulisan ini, penentuan lintasan terpendek dilakukan melalui metode pencarian heuristic yaitu Algoritma genetika. Algoritma genetika bekerja dengan meniru proses evolusi alamiah, dimana individu dengan fitness terbesar memiliki kemampuan lebih besar untuk bertahan. Dalam kasus ini, fitness terbesar berkaitan dengan total jarak rute yang terkecil. Selanjutnya, dengan menerapkan operator-operator genetika, yaitu seleksi, crossover dan mutasi yang di terjemahkan ke dalam bahasa pemrograman Java diperoleh bahwa rute terpendek dengan kode 1 7 6 11 8 5 4 2 3 9 10 adalah 19,67 km. Kata Kunci : BRT (Bus Rapid Transit), TSP (Traveling Salesman Problem), lintasan terpendek, algoritma genetika ABSTRACT The shortest path is one of the research relating to the graph. BRT (Bus Rapid Transit) problem is one example of a case that can be formulated as a graph problems that associated with the shortest path. In this case, point (vertex) represents the bus stop while the side (edge) represents the link between the two bus stops. If the weight of the edge stated length of the path between the two bus stops, by assuming every two bus stops have connecting lines, then the shortest path problems associated with the search path through all the appropriate bus stops once and with the smallest total distance. In this paper, the determination of the shortest path is done through a heuristic search method namely genetic algorithm. Genetic algorithm works by duplicate the natural evolution process, where the individual with the greatest fitness has a greater ability to survive. In this case, the largest fitness associated with the smallest total distance. Furthermore, by applying genetic operators, that are selection, crossover and mutation are translated into the Java programming language is obtained that the shortest route with the code 1 7 6 11 8 5 4 2 3 9 10 is 19,67 km. Keywords : BRT (Bus Rapid Transit), TSP (Traveling Salesman Problem), shortest path, genetic algorithm