Pertumbuhan penduduk kota yang sangat tinggi serta meningkatnya kegiatan pembangunan di berbagai sektor menimbulkan berbagai masalah di wilayahwilayah perkotaan seperti permukiman kumuh, persampahan dan sebagainya. pada tahun 2015 ada sekitar 600 m3 Sampah per hari yang di angkut dari TPST ke TPA di kota Tegal. Dalam proses pengangkutan sampah hanya berfokus mencari jalur terpendek saja tetapi tidak memperhatikan kenyamanan penduduk yang berada di salah satu jalur pengangkutan sampah. Tujuan penelitian ini adalah melakukan pemilihan rute dengan memperhatikan kondisi persebaran penduduk dari sebuah jalur TPST menuju ke TPA Mataram, kota Tegal. Algoritma A* digunakan untuk mencari jalur pengangkutan sampah tersebut di kota Tegal. Perhitungan dimulai dengan membuat graf jaringan pengangkutan sampah terlebih dahulu. TPST, TPA dan persimpangan jalan sebagai node, sedangkan jalan yang menghubungkan antar node sebagai sisinya. Setelah jaringan terbentuk, selanjutnya di proses menggunakan algoritma A* dengan mempertimbangkan nilai kepadatan penduduk dari setiap node ketetanggaan pada jaringan tersebut hingga mendapatkan solusi jalur dengan kepadatan penduduk yang sesuai antar tiap titik yang optimum. Penerapan algoritma ini di lakukan di kota Tegal karena belum adanya rute yang pasti dalam proses pengangkutan sampah dari TPST ke TPA . Algoritma A* digunakan dalam masalah ini karena dalam proses pencaraian jalur pada algoritma A* menggunakan nilai heuristuik, sehingga dalam pemilihan rute dapat di hasilkan rute yang akurat. Pada masalah ini hasil yang ingin di capai adalah rute terpendek dengan meminimalkan melewati jalur – jalur dengan jumlah penduduk yang padat.