PT RSG (Rezeki Surya Gasindo) merupakan perusahaan swasta yang menjual produk gas medis dan gas industri serta menyediakan layanan pengiriman kepada pelanggan. Namun, layanan pengiriman tersebut belum sepenuhnya optimal sehingga sering terjadi keterlambatan pengantaran gas yang berdampak pada menurunnya tingkat kepuasan pelanggan. Oleh karena itu, diperlukan solusi untuk mengoptimalkan rute pengiriman agar dapat meminimalkan jarak tempuh dan meningkatkan efisiensi layanan. Salah satu metode yang dapat digunakan adalah Algoritma Nearest Neighbor, yaitu metode heuristik yang sederhana dan cepat dalam menyelesaikan permasalahan Traveling Salesman Problem (TSP), dengan memilih jarak terdekat dari posisi awal tanpa mempertimbangkan jarak lainnya. Penelitian menunjukkan terdapat dua kondisi awal yang memiliki jarak terdekat yang sama dari Perusahaan yaitu kondisi Perusahaan ke Bagan Pete dan kondisi Perusahaan ke Mayang. Hasil penelitian menunjukkan bahwa kondisi Perusahaan ke Bagan Pete menghasilkan rute optimal karena berhasil mengunjungi seluruh pelanggan dan kembali ke Perusahaan dengan total jarak km. sementara itu, kondisi Perusahaan ke Mayang tidak mampu mengunjungi seluruh pelanggan. Dengan demikian, algoritma nearest neighbor terbukti efektif digunakan untuk menyusun rute pengiriman yang optimal dan praktis di PT. Rezeki Surya Gasindo.