Penyelesaian Traveling Salesman Problem (TSP) adalah mencari lintasan terpendek kunjungan ke semua kota. Dengan lintasan terpendek tersebut maka waktu tempuh diharapkan juga akan menjadi lebih cepat. Pada kenyataannya seorang salesman ketika mengunjungi semua kota dalam daftar kunjungannya banyak terkendala dengan kondisi jalan seperti kemacetan, jalan yang rusak, atau kendalakendala lain. Sehingga walaupun lintasan terpendek sudah didapatkan tetapi jika pada lintasan tersebut terdapat ruas jalan yang mengalami gangguan akan menyebabkan waktu tempuh ke semua kota menjadi lebih panjang. Salah satu cara menyelesaikan permasalahan TSP adalah menggunakan algoritma semut. Dari banyak penelitian yang sudah dilakukan, kondisi jalan selalu dianggap baik tanpa gangguan. Penelitian penulis menggunakan algoritma semut paling sederhana yaitu Ant System untuk menyelesaikan permasalahan TSP dengan kekangan kondisi jalan. Penulis melakukan modifikasi pada Ant System dengan memberi kekangan feromon pada tiap ruas jalan yang tidak bisa dilewati dan memberi jarak panjang pada ruas yang tidak boleh dilewati tersebut. Dengan modifikasi ini diharapkan semut tidak pernah melewati ruas jalan yang mengalami kekangan. Sehingga semut akan mencari jalur lain dalam mengunjungi semua kota yang ada. Data yang digunakan untuk penelitian adalah square grid 3x3 sampai 6x6, dan dua data dari http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/ yaitu ulysses16 dan ulysses22. Hasil penelitian ini menunjukkan semut tidak pernah melewati ruas berkekangan, baik untuk data square grid maupun dua data dari TSPLIB95. Semakin banyak kekangan, mengakibatkan waktu komputasi semakin lama.

The completion of Traveling Salesman Problem (TSP) is to find the shortest path to visit all of the cities. With the shortest path, it is expected that the travel time will also be shorter. In fact, when a salesman visits all of the cites in his list, he will find obstacles such as poor road conditions, congestion, damaged roads, or other constraints. Therefore, although the shortest path has been established, if there is an obstacle the travel time to all cities will be longer. One way to solve the TSP is by ant algorithm. From a lot of research that have been done, the road conditions are always considered to be fine without disturbance. The research used the simplest ant algorithm, it is the Ant System to solve TSP with constraint road conditions. The modifications were made to the Ant System by providing constraint pheromone to each road which could not be passed and also gave a long distance to the roads that should not be passed. With this modification, it is expected that the ants never pass the roads which have constraint. Therefore, the ants will find another path to visit all the cities. The data which is used for research are square grid 3x3 to 6x6, and two data from http://www.iwr.uniheidelberg. de/groups/comopt/software/TSPLIB95/, that is the ulysses16 and ulysses22 The results of this study indicate that the ants never pass constrained sections, for square grid data also two data from TSPLIB95. This occurs because the segments were given constraints, the pheromone were weighted 0 and given the longest distance. More constraints make the computational time longer.

Kata Kunci : TSP, algoritma semut, Ant System, kekangan kondisi jalan, kemacetan, feromon.