Pada sebuah perusahaan, saluran distribusi memiliki peranan yang sangat penting. Saluran distribusi yang dimaksud adalah saluran yang digunakan oleh produsen untuk menyalurkan barang dari produsen ke konsumen atau pemakai industri. Dengan kondisi tersebut, optimasi pembentukan rute dan jadwal pengiriman yang terstruktur perlu dilakukan. Pada penelitian kali ini, dilakukan survey langsung ke salah satu perusahaan di Surabaya yaitu PT. Tirta Bahagia yang merupakan perusahaan air mineral merk Club yang memiliki depo sebagai distributor serta beberapa agen yang tersebar di wilayah Surabaya Timur.
Pembentukan rute dan jadwal kendaraan yang dibahas dalam penelitian ini menggunakan dua metode. Metode yang digunakan adalah Algoritma Dijkstra dan Algoritma Simulated Annealing. Algoritma Simulated Annealing digunakan untuk menentukan urutan agen yang harus dikunjungi, sedangkan Algoritma Dijkstra digunakan untuk mencari jarak terpendek antar node agen.
Pada hasil pengujian dengan teknik cooling schedule pertama, kedua dan ketiga yang dihasilkan pada proses optimasi metode Simulated Annealing dengan varian nilai jumlah iterasi 50,100, dan 150 pada pengujian proses optimasi 15 user/customer didapatkan nilai jumlah iterasi yang paling optimum terjadi pada jumlah iterasi (N) sebesar 150 dengan energi optimal yang dihasilkan sebesar Rp.18484 pada pengujian teknik cooling schedule yang kedua. Penggunaan iterasi yang besar dapat menghasilkan prediksi rute yang lebih banyak dan menghasilkan energi yang paling optimal, sehingga didapatkan total jarak terpendek sebesar 36968 m, dan nilai waktu komputasi sebesar 17,506 detik.
Kata kunci: Optimasi rute, penjadwalan, Algoritma Dijkstra, Simulated Annealing.
