Pertumbuhan ekonomi dan urbanisasi yang masif menyebabkan meningkatnya rata-rata konsumsi sampah. Kota Surakarta memproduksi sampah dengan jumlah yang besar namun tidak diimbangi dengan penanganan sampah yang maksimal. Pengelolaan sampah rumah tangga dikelola oleh setiap kelurahan, tidak terkecuali Kelurahan Jebres. Adanya kebijakan zero Tempat Pembuangan Sementara (TPS) statis membuat pengelolaan sampah beralih menggunakan TPS mobile. Biaya yang dibutuhkan untuk menjalankan TPS mobile ini lebih mahal karena biaya yang dikeluarkan untuk ongkos bahan bakar dan operator menjadi tinggi. Salah satu upaya untuk mengurangi biaya yaitu dengan mengoptimalkan rute kendaraan. Penelitian ini bertujuan untuk meminimasi biaya transportasi yang ditimbulkan dengan cara optimasi rute kendaraan menggunakan pendekatan Vehicle Routing Problem (VRP) dan metode heuristik Cluster-First Route-Second. Hasilnya, penelitian ini dapat memperpendek jarak tempuh hingga 63%, mempercepat waktu perjalanan hingga 46,73% dan menghemat biaya bahan bakar 21,5% per hari dari semua armada. Penelitian ini juga memaksimalkan penggunaan TPS mobile dengan cara menghapus penggunaan 16 gerobak tarik yang dibawa menggunakan motor dalam pengiriman sampah ke TPA.

Kata kunci: Cluster-First Route-Second, Rute, Sampah, TPS mobile, Vehicle Routing Problem