MENENTUKAN RUTE TERPENDEK DENGAN MEMANFAATKAN METODE HEURISTIK BERBASIS ALGORITMA A*

Mohammad Taufiq, Amin Suyitno, Dwijanto Dwijanto

Abstract


Penelitian ini mengkaji tentang sebuah permasalahan untuk mencari solusi terkait penentuan rute terpendek yang harus ditempuh. Tujuan dari penelitian ini adalah unutk mengetahui dasar-dasar algoritma A* yang berguna untuk meneliti rute pendistribusian bahan baku berupa kacang tanah dari PT. Dua Kelinci ke beberapa daerah di Kabupaten Pati. Penelitian ini menggunakan bantuan program MATLAB. Data yang dibutuhkan berupa tempat-tempat produksi kacang tanah yang diperoleh dari kantor PT. Dua Kelinci. Selanjutnya, peneliti melakukan pencarian jarak dengan menggunakan bantuan Google Maps. Data tersebut dianalisis dengan menggunakan penghitungan manual yang kemudian hasilnya dibandingkan dengan hasil penghitungan yang menggunakan program MATLAB. Dari kedua cara penghitungan data tersebut, jarak terpendek pendistribusian kacang tanah di Kabupaten Pati adalah 218,4 km. Rute nya adalah sebagai berikut: PT. Dua Kelinci – Kecamatan Margorejo – Kecamatan Pati – Kecamatan Tayu – Kecamatan Tlogowungu –Kecamatan Gembong – Kecamatan Tambakkromo – Kecamatan Gunung Wungkal – Kecamatan Trangkil – Kecamatan Puncakwangi – PT. Dua Kelinci. Analisis penghitungan dengan cara manual maupun MATLAB menghasilkan jarak tempuh dan rute yang sama untuk mencapai semua titik dengan jarak minimal.

 

This research studies a problem solution related to the determination of the shortest route to pass. It aims to find out the basics of algorithm A* due to the analysis of the shortest route to distribute peanuts materials from Dua Kelinci Company to the certain subdistricts in Pati Regency. This analysis uses the help of MATLAB program. The collected data is about the places of peanuts production. It was taken from the office of Dua Kelinci Company. After collecting the data, the mileage between the company and the distribution places was taken using Google Maps application. The data is analysed by using manual calculation. The result of it is then compared with the result of MATLAB calculation. The analysis using both ways of calculation shows that the shortest mileage to distribute peanuts materials in Pati Regency is 218,4 km. The route is described as follows: Dua Kelinci Company – Margorejo Subdistrict – Pati Subdistrict – Tayu Subdistrict – Tlogowungu Subdistrict – Gembong Subdistrict – Tambakkromo Subdistrict – Gunung Wungkal Subdistrict – Trangkil Subdistrict – Puncakwangi Subdistrict – Dua Kelinci Company. Both manual and MATLAB calculation result the same mileage and route to reach all points with the minimum distance.


Keywords


Algorithm A*; Goods Distribution; Shortest Route

Full Text:

PDF

References


Budayasa, I. K. 2007. Teory Graf dan Aplikasinya. Unesa University Press.

Bell, E. T. 1952. Mathematics: Queen and Servant of Science. London: G. Bell & Sons, Ltd.

Firmansyah, A. 2007. Dasar-dasar Pemograman MATLAB. IlmuKomputer.com.

Harianja, F. 2013. Penerapan Algoritma A* dalam permasalahan optimalisasi pencarian solusi dynamic water jug. Jurnal Pelita Informatika Budi Darma, Volume : IV, Nomor: 3. ISSN : 2301-9425.

Hart, P. E., Nilsson, N. J. and Raphael, B. 1968. A Formal Basis for the Heuristic Determination of Minimum Cost Paths. IEEE Transactions on Systems Science and Cybernetics SSC4 4 (2): 100–107.

Muttaqien, M. A., Mulyono, dan Suyitno, A. 2013. Pelabelan total sisi ajaib pada graf double star dan graf Sun. Journal of Mathematics, 2 (2). 85 – 89.

Pugas, D. O., Somantri, M., dan Satoto, K. I. 2011. Pencarian Rute Terpendek Menggunakan Algoritma Dijkstra dan Astar (A*) pada SIG Berbasis Web untuk Pemetaan Pariwisata Kota Sawahlunto. Jurnal TRANSMISI, 13 (1), 2011, 27-32.


Refbacks

  • There are currently no refbacks.