Algoritma Warshall untuk Penyelesaian Masalah Vehicle Routing (Studi Kasus : Pendistribusian PT Semen Bosowa di Makassar)

Abstract

Abstrak. Warshall merupakan algoritma untuk menghitung jarak terpendek untuk semua pasangan titik pada sebuah lokasi yang dapat diubah menjadi sebuah graf berarah dan berbobot, yang berupa titik-titik (V) dan sisi-sisi (E) serta paling memiliki minimal satu sisi pada setiap titik. Vehicle Routing Problem (VRP) termasuk dalam kelas NP-hard problem dalam combinatorial optimization, sehingga sulit diselesaikan dengan metode eksak yang berlaku secara umum. Penelitian ini diawal dengan konsep matematis Penerapan Algoritma Warshall, yaitu pengambilan data Pendistribusian dari Perusahaan, pencarian bobot lintasan, mengubah kedalam matriks dengan ukuran  dalam hal ini matriks yang digunakan berukuran , menerapkan Algoritma Warshall dalam matriks yang diperoleh. Persamaan yang digunakan adalah pertama Representasi graf ke matriks berbobot berjarak D = [d_ij] yaitu jarak dari vertex i ke j; Kedua Dekomposisi dengan urutan d_ij^(k). D^(k) menjadi matriks nxn [d_ij^(k)] batasi k sampai n sehingga k = 0, 1, …, n; Ketiga Pengamatan struktur shortest path dilakukan dengan dua cara yaitu jika k bukan merupakan vertex pada path (path terpendek memiliki panjang d_ij(k-1)) dan k merupakan vertex pada path (path terpendek memiliki panjang d_ij(k-1)+d_ij(k-1)), hal tersebut memuat sebuah subpath dari i ke k dan sebuah subpath dari k ke j. Keempat Iterasi yang dimulai dari 0 sampai dengan n. Berdasarkan hasil penelitian diperoleh bahwa dengan Metode Algoritma Warshall dapat menyelesaikan permasalahan penentuan rute terpendek dalam pendistribusian PT Semen Bosowa dengan menghitung jarak seluruh jalur lintasan yang ada dalam pendistribusian semen Bosowa di Makassar.

Kata Kunci : Algoritma Warshall, Masalah Vehicle Routing, Graf Berarah, Graf Berbobot, Jalur Terpendek.

Abstract  Warshall is an algorithm to calculate the shortest distance for every pair of points in a location that can be converted into a directed and weighted graph, in the form of vertex (V) and edges (E), and most have at least one side at any vertex. Vehicle Routing Problem (VRP) is included in the class of NP-hard problem in combinatorial optimization, making it difficult to solve with exact methods applicable in general. This study beginning with mathematical concepts Implementation of Algorithms Warshall, which is taking the data distribution from the Company, the search for weight trajectory, changing into a matrix with n × n squares in this case matrix used measuring 11 x 11, apply the algorithm Warshall in the matrix obtained, the second is the implementation of Algorithms Warshall using Microsoft Visual Basic programming language. The equation used is the first representation of the graph to a weighted matrix D = [d_ij] ie the distance from the vertex i to j; The second order decomposition with d_ij^(k). D ^(k) be the nxn matrix [d_ij^(k)] so that the limit k to n for k = 0, 1, ..., n; Third observation structures shortest path done in two ways: if k is not a vertex on the path (the shortest path length d_ij (k-1)) and k is the vertex on the path (the shortest path length d_ij (k-1) + d_ij (k -1)), it contains a subpath from i to k and a subpath from k to j. The fourth iteration numbered 0 through n. The result showed that the method Warshall algorithm can solve the problems of determining the shortest route in the distribution of PT Semen Bosowa by calculating the distance of the entire passage is in the distribution of cement Bosowa in Makassar.

Keywords: Algorithm Warshall, Vehicle Routing Problem, trending Graf, Graf Weighted, Shortest Path.