Traveling Salesman Problem (TSP) merupakan permasalahan seorang salesman harus mengunjungi semua kota tujuan tepat satu kali dan harus kembali ke kota awal. Salah satu algoritma yang bisa digunakan untuk mengoptimasi masalah TSP adalah Particle Swarm Optimization (PSO). Penelitian ini bertujuan untuk menerapkan algoritma PSO untuk menyelesaikan masalah pencarian rute terpendek pendistribusian Bahan Bakar Minyak (BBM) di Kota Samarinda. Rute pendistribusian BBM dilakukan dari titik awal yaitu PT Pertamina Patra Niaga Fuel Terminal Samarinda menuju 16 lokasi SPBU yang ada di Kota Samarinda. Berdasarkan hasil penelitian, diperoleh rute jarak terpendek yang dimulai dari Fuel Terminal di Jl. Cendana-SPBU Jl. Ir. H. Juanda Kel Air Putih-SPBU Jl. Ir. H. Juanda-SPBU Jl. Kadrie Oening-SPBU Jl. Kesuma Bangsa-SPBU Jl. Sultan Sulaeman-SPBU Jl. Kebaktian-SPBU Jl. A. W. Syahrani-SPBU Jl. PM. NoorSPBU Jl. Wahid Hasyim-SPBU Jl. Ahmad Yani-SPBU Jl. Sentosa-SPBU Jl. Gatot Subroto-SPBU Jl. Diponegoro-SPBU Jl. Slamet Riyadi-SPBU Jl. Rapak DalamSPBU Jl. Teuku Umar-Fuel Terminal di Jl. Cendana, dengan jarak tempuh 50, 58 km.