Optimisasi Rute Traveling Salesman Problem Menggunakan Algoritme Bee Colony Optimization

Abstract

Traveling Salesman Problem (TSP) merupakan masalah penentuan rute guna mengunjungi sekumpulan kota/tempat yang sepenuhnya terhubung dimana setiap koneksi antar dua kota dikaitkan dengan jarak atau biaya. Ada beberapa metode yang digunakan untuk penyelesaian masalah ini. Pada karya ilmiah ini, digunakan metode eksak Integer Linear Programming (ILP) dan metode meta-heuristic Bee Colony Optimization (BCO) untuk menyelesaikan TSP. Metode eksak ILP diselesaikan dengan bantuan perangkat lunak optimisasi LINGO 18.0, sedangkan metode BCO diselesaikan dengan bantuan bahasa pemrograman Python 3.6.9. Hasil yang diperoleh menunjukan bahwa waktu eksekusi metode BCO lebih cepat dibandingkan metode eksak namun, metode BCO menghasilkan selisih jarak yang relatif besar dibandingkan metode eksak.

Traveling salesman problem (TSP) is a problem of determining a route to visit a group of fully connected cities/places where each connection between two cities is related to distance or cost. There are several methods to solve this problem. In this manuscript, integer linear programming (ILP) as an exact method and bee colony optimization (BCO) as a meta-heuristic method will be used to solve TSP. The exact ILP method is solved by LINGO 18.0 optimization software, while the BCO method is solved by Python 3.6.9 programming language. The results obtained show that the BCO execution time is faster than the exact method, but the BCO method produces a relatively large distance difference compared to the exact method.