Pengiriman barang oleh kurir distributor DaysParfum.indo di Kota Medan mengalami kesulitan dalam menentukan rute terpendek dan menghindari jalan yang sama. Untuk mengatasi masalah ini, digunakan algoritma A* dengan fungsi heuristik Euclidean Distance dan Manhattan Distance. Algoritma A* dilengkapi fungsi heuristik merupakan salah satu algoritma yang dapat menyelesaikan pencarian jalur terpendek. Fungsi heuristik yang paling umum digunakan yakni Euclidean Distance dan Manhattan Distance. Penelitian ini bertujuan untuk membandingkan kedua fungsi heuristik tersebut dalam menyelesaikan pencarian rute terdekat pengiriman barang. Hasil penelitian menunjukkan bahwa fungsi heuristik Manhattan Distance lebih baik daripada Euclidean Distance dalam algoritma A*, dengan nilai rata-rata total jarak sebesar 27.30338 km dari 10 data transaksi dengan jumlah titik pengiriman yang berbeda-beda. Pengujian menunjukkan bahwa jumlah titik pengiriman tidak mempengaruhi nilai waktu eksekusi.