Permasalahan pengangkutan sampah di Kota Banjarbaru masih menghadapi kendala berupa rute pengangkutan yang belum optimal sehingga menyebabkan jarak tempuh, waktu operasional, dan biaya bahan bakar menjadi lebih besar. Penelitian ini bertujuan untuk mengoptimalkan rute pengangkutan sampah menggunakan metode Saving Matrix dan algoritma Floyd Warshall. Sistem pengangkutan digambarkan ke dalam graf berbobot, di mana Tempat Pembuangan Sementara (TPS) direpresentasikan sebagai simpul (vertex) dan jalur antar lokasi sebagai sisi (edge) yang memiliki bobot jarak. Metode Saving Matrix digunakan untuk menghitung penghematan jarak antar titik tempat pembuangan sementara (TPS) guna menghasilkan kombinasi rute yang lebih efisien, sedangkan algoritma Floyd Warshall digunakan untuk menentukan jalur terpendek antar simpul pada setiap rute yang terbentuk. Hasil penelitian menunjukkan bahwa metode Saving Matrix memberikan hasil optimasi terbaik dibandingkan rute eksisting DLH Kota Banjarbaru maupun algoritma Floyd Warshall. Rute hasil optimasi memiliki total jarak tempuh sebesar 1.927,12 km. waktu tempuh 3.874,19 menit, dan biaya transportasi Rp. 2.740.769. Dibandingkan dengan DLH Kota Banjarbaru, hasil tersebut mampu mengurangi jarak tempuh sebesar 3,81%, waktu tempuh sebesar 3,75%, dan biaya transportasi sebesar 4,02%. Dengan demikian, kombinasi metode Saving Matrix dan algoritma Floyd Warshall dapat menjadi alternatif dalam meningkatkan efektivitas sistem pengangkutan sampah di Kota Banjarbaru.