Distribusi merupakan salah satu kegiatan yang
harus diperhatikan dalam Supply Chain Management. PT. X
merupakan perusahaan distribusi air minum di Yogyakarta.
Perusahaan ini mengategorikan pelanggan menjadi kategori
dropping, horeka, rumah tangga, dan kantor. Dua jenis
kendaraan berbeda digunakan untuk melayani pelanggan
galon.Pengategorian pelanggan tersebut membuat banyak
salesman beroperasi dalam satu kabupaten.Rute distribusi PT. X juga kurang efisien sehingga menyebabkan jarak tempuh salesman menjadi panjang.Cluster-first route-second merupakan metode pendekatan heuristik yang dapat
digunakan dalam penyelesaian kasus ini. Pembuatan cluster
menggunakan modifikasi k-means yang mempertimbangkan
kapasitas, penghitungan jarak menggunakan haversine
formula. Pembuatan rutenya menggunakan empat TSP
heuristik WINQSB.