makalah€¦ · makalah matematika ekonomi ... dimana terdapat beragam teori algoritma yang dapat...
TRANSCRIPT
1
MAKALAH
MATEMATIKA EKONOMI
“TRAVELLING SALESMAN PROBLEM DALAM PENDISTRIBUSIAN
BARANG PT. SADAR JAYA MANUNGGAL MENGGUNAKAN
ALGORITMA GREED”
OLEH :
ABDUL GAZIR S. (G1D016001)
FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM
PROGRAM STUDI MATEMATIKA
UNIVERSITAS MATARAM
2017
2
BAB I
PENDAHULUAN
1.1 Latar Belakang
Setiap usaha selalu mengedepankan komitmen untuk memenuhi kebutuhan pelanggan
secara cepat dan tepat, hal tersebut seiring dengan pertumbuhan persaingan dalam dunia
bisnis yang semakin pesat, sehingga diperlukan kecepatan dan ketepatan dalam
pendistribusian barang produksi yang sesuai. Setiap perusahaan menghendaki adanya
peningkatan penjualan dan pendapatan, maka perusahaan harus aktif dalam proses pemasaran
sehingga tujuan perusahaan bisa tercapai. Salah satu perusahaan yang aktif dalam proses
pemasaran di Indonesia adalah PT. Sadar Jaya Manunggal, perusahaan ini bergerak di
industri bahan bangunan, perusahaan ini berusaha untuk menjangkau pasar yang lebih luas
dengan cara mendirikan cabang-cabang distributor di beberapa kota besar yang ada di
Indonesia. Salah satu cabang distributor didirikan berada di Lombok, Nusa Tenggara
barat yang beralamatkan Jln Teguh faisal no 78 Mataram, Nusa Tenggara barat. Hal ini
dilakukan perusahaan sebagai upaya memepermudah distribusi produk ke konsumen.
Dikarenakan distribusi menjadi bagian penting dalam proses penyampaian produk dari
perusahaan manufaktur/produsen kepada konsumen akhir.
Pendistribusian memegang peranan yang sangat penting karena tanpa pola distribusi yang
tepat, maka proses ini akan menghabiskan biaya tinggi dan mengakibatkan pemborosan,
baik dari segi waktu, biaya, maupun jarak sehingga akan mengurangi keuntungan. Menurut
Rosa, dkk. (2012), Travelling Salesman Problem (TSP) adalah masalah optimasi, yaitu
mengunjungi setiap tempat dari himpunan tempat-tempat yang ditentukan sekali dan hanya
satu kali kemudian kembali ke tempat awal pada akhir dari rute perjalanan dengan
jarak, waktu, dan biaya yang minimum. . Permasalahan yang timbul yaitu seorang sales harus
bisa menentukan rute terpendek dengan waktu yang lebih efektif sehingga suatu tempat tidak
terlewati lebih dari satu kali. Oleh karena itu kami menggunakan yang namanya algoritma.
Dimana terdapat beragam teori algoritma yang dapat digunakan untuk menyelesaikan
permasalahan Travelling Salesmen Problem (TSP) seperti, algoritma brute force, algoritma
greedy, algoritma genetic, algoritma branch and bound dll.
Dalam menemukan rute perjalanan yang paling optimum untuk permasalahan
pendistribusian bahan bangunan ini, kami memilih salah satu algoritma di atas untuk
menyelesaikan masalah Travelling Salesmen Problem (TSP) yaitu dengan menggunakan
algoritma greedy. Algoritma greedy memiliki pendekatan untuk membangun solusi secara
bertahap melalui urutan yang terus berkembang sampai solusi dari masalah telah tercapai
3
(Levitin,dkk., 2007). Greedy memberikan alternatif optimal lokal dengan harapan setiap
alternatif lokal menghasilkan alternatif global yang optimal secara keseluruhan. Algoritma
greedy dapat menyelesaikan Travelling Salesman Problem dengan menghitung nilai lokal
optimal setiap mengunjungi kota dan mendapatkan nilai optimasi global pada akhir
perjalanan (Lukman,dkk., 2011).
1.2 Perumusan Masalah
Rumusan masalah pada makalah ini adalah sebagai berikut :
a. Bagaimana menentukan rute terpendek pendistribusian bahan bangunan PT. Sadar
Jaya Manunggal ke toko-toko bangunan yang terdapat di Lombok Tengah dengan
Algoritma greedy?
b. Bagaimana menentukan biaya operasional dalam pendistribusian bahan bangunan
PT. Sadar Jaya Manunggal ke toko-toko bangunan yang terdapat di Lombok
Tengah setelah menggunakan Algoritma greedy?
1.3 Tujuan Penelitian
Adapun tujuan makalah ini adalah sebagai berikut :
a. Untuk mengoptimalkan waktu dan jarak dalam pendistribusian bahan bangunan PT.
Sadar Jaya Manunggal ke toko-toko bangunan yang terdapat di Lombok Tengah
b. Untuk mengoptimalkan biaya operasional dalam pendistribusian bahan bangunan
PT. Sadar Jaya Manunggal ke toko-toko bangunan yang terdapat di Lombok
Tengah.
1.4 Manfaat Penelitian
Manfaat dari penelitian ini adalah :
a. Membantu PT. Sadar Jaya Manunggal dalam menentukan rute pendistribusian bahan
bangunan sehingga dapat meminimalkan biaya operasional dan memperoleh
keuntungan yang maksimal.
b. Mengatasi masalah pendistribusian bahan bangunan secara optimal dengan
menggunakan algoritma greedy.
1.5 Batasan Masalah
a. Jalan-jalan kecil atau jalan tikus di abaikan.
b. Kemacetan jalan dan lampu lalulintas diabaikan.
c. Bensin Penuh.
d. Hanya menggunakan satu truk kontainer.
e. Kecepatan rata-rata 60 Km/jam.
f. Hanya memperhitungkan biaya operasional berupa biaya bensin dan gaji sopir.
1.6 Tinjauan Pustaka
4
Menurut Kusumawati (2017) Salah satu cara pendistribusian barang dari
supplier ke tempat tujuan dengan cepat dan tepat perlu dilakukan secara baik, salah
satunya melalui teknik graph dengan menggunakan algoritma greedy. Dimana supplier
dapat mendistribusikan barang ke toko secara sistematis melalui rute jalur terpendek
dari lokasi kantorke tempat lokasi toko yang terdekat hingga terjauh. Rancangan
pendistribusian barang dengan menggunakan algoritma greedy dapat memberikan solusi
bagi supplier untuk melaksanakan kegiatan pengiriman barang secara baik. Dengan
menggunakan algoritma greedy diperoleh urutan lintasan terpendek didapat dari 1-2-4-
5-3-6-7. Perhitungan total edge yang telah dioptimasi dengan Algoritma Greedy adalah
sebagai berikut:1 ke 2 = 6 km; 2 ke 4 = 6,9 km; 4 ke 5 = 3,5 km; 5 ke 3 = 1,7 km; 3 ke 6
= 3,3 km; 6 ke 7 = 7,9 km. Optimasi : 6+6,9+3,5+1,7+3,3+7,9 = 29,3 km. Maka dapat
diambil kesimpulan bahwa seorang supplier dengan lintasan terpendeknya yaitu: dari
kantor ke arah Citos, Metro Pondok Indah, Metro Gandaria, Plaza Blok M, Metro
Senayan, Metro Taman Anggrek.
Dunia perfilman di era globalisasi sudah semakin maju. Perusahaan distributor
film berpengaruh dalam perkembangan dunia perfilman tersebut. Dimana perusahaan
perusahaan distributor harus mendistribusikan film -film dari Production House ke
cabang perusahaan tersebut yang ada di Indonesia. Untuk itu, dibutuhkan kurir yang
menjadi ujung tombak bagian dari pendistribusian. Diperlukan minimum waktu untuk
menyelesaikan tugas mereka. Dengan menggunakan algoritma dijkstra diperoleh hasil
terefektif dari berbagai rute yang ada dimulai dari rute pertama menghasilkan distribusi
yang paling efisien dengan jarak dan waktu tempuh: 25,8 Km dan 0,43 jam. Kemudian
rute kedua menghasilka distribusi yang paling efisien dengan jarak dan waktu
tempuh:20,1 Km dan 0,33 jam. Selan-jutnya distribusi yang paling efisien dengan jarak
dan waktu tempuh:21 Km dan 0,35 jam. Terakhir, distribusi yang paling efisien dengan
jarak dan waktu tempuh:17,3 Km dan 0,28 jam (kurnia, dkk.,2012)
Berdasarkan penelitian oleh pratiwi (2014) dapat disusun langkah-langkah
penyelesaian masalah knapsack menggunakan algoritma Branch and Bound. Dalam
jurnal tersebut permasalah knapsack yang diselesaikan adalah masalah knapsack 0-1.
Kasus yang dibahas adalah bagaimana menentukan pemilihan investasi Bank ke setiap
perusahaan supaya memperoleh total pendapatan yang maksimum. Kasus ini serupa
dengan studi kasus ini serupa dengan studi kasus yang dilakukan peneliti di CV.
Pangestu Interaksi Semarang, yaitu, menentukan pemilihan pengangkutan barang untuk
dipasarkan supaya diperoleh keuntungan penjualan yang maksimum.
5
BAB II
LANDASAN TEORI
2.1 Pengertian Pendistribusian
Pendistribusian adalah kegiatan pemasaran yang berusaha mempelancar serta
mempermudah penyampaian produk dan jasa dari produsen kepada konsumen
sehingga penggunaan sesuai (jenis, jumlah, harga, tempat dan saat) dengan yang
diperlukan (Tjiptono, 2008:185).
Distribusi yang efektif akan memperlancar arus atau akses barang oleh
konsumen sehingga dapat diperoleh kemudahan memperolehnya. Di samping itu
konsumen juga akan dapat memperoleh barang sesuai dengan yang diperlukan.
Produsen dan konsumen mempunyai kesenjangan spasial, waktu, nilai,
keragaman, dan kepemilikan produk karena perbedaan tujuan serta persepsi masing-
masing. Dengan distribusi dapat diatasi kesenjangan antara produsen dan konsumen.
2.2 Graf
Graf pertama kali ditemukan oleh Leonhard Euler, seorang matematikawan
kebangsaan Swiss pada tahun 1736. Dimana saat itu Euler berhasil menulis upaya
pemecahan Jembatan Koningsberg yang terkenal di Rusia. Graf merupakan sebuah
kumpulan yang terdiri dari titik (vertex) dan garis dimana pasangan titik – titik
tersebut dihubungkan dengan segmen garis. Verteks ini sering disebut sebagai titikdan
segmen garis disebut sebagai edge. Maka direpresentasikan dengan G = (V,E)
(Lipschutz, 2002).
Dalam matematika dan ilmu computer, teori graf adalah cabang kajian yang
mempelajari sifat – sifat graf. Secara informal, suatu graf adalah himpunan benda –
benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau
busur (arc). Biasanya graf digambarkan sebagai kumpulan titik – titik (melambangkan
simpul) yang dihubungkan oleh garis – garis (melambangkan sisi) atau garis berpanah
(melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul
yang sama. Sisi yang demikian dinamakan gelang (loop).
6
Gambar 2.1 Graf dengan 5 verteks dan 6 edge
Gambar 2.1 menggambarkan 5 verteks yaitu A, B, C, D dan E serta 6 edge
yang menghubungkan antara vertex lainnya seperti AB, AC, BC, dan seterusnya. Graf
terbagi atas dua jenis yaitu graf berarah (Directed Graph) dan graf tidak berarah
(Undirected Graph). Graf berarah adalah suatu graf yang mana garis – garisnya
memiliki arah. Sedangkan graf tidak berarah adalah dimana garis – garis dalam graf
tidak memiliki arah.
2.4 Travelling Salesman Problem
Permasalahan tentang Traveling Salesman Problem dikemukakan pada tahun
1800 oleh matematikawan Irlandia William Rowan Hamilton dan matematikawan
Inggris Thomas Penyngton. Gambar dibawah ini adalah foto dari permainan Icosian
Hamilton yang membutuhkan pemain untuk menyelesaikan perjalanan dari 20 titik
menggunakan hanya jalur-jalur tertentu.
Bentuk umum dari TSP pertama dipelajari oleh para matematikawan mulai
tahun 1930. Diawali oleh Karl Menger di Viena dan Harvard. Setelah itu
permasalahan TSP dipublikasikan oleh Hassler Whitney dan Merrill Flood di
Princeton. Selanjutnya dengan permasalahan ini, TSP dibuat menjadi permasalahan
yang terkenal dan popular untuk dipakai sebagai model produksi, transportasi dan
komunikasi (Amin, dkk., 2006).
TSP dikenal sebagai suatu permasalahan optimasi yang bersifat klasik dan
Non-Deterministic Polynomial-time Complete (NPC), dimana tidak ada penyelesaian
yang paling optimal selain mencoba seluruh kemungkinan penyelesaian yang ada.
Permasalahan ini melibatkan seorang traveling salesman yang harus melakukan
kunjungan sekali pada semua kota dalam sebuah lintasan sebelum dia kembali ke titik
awal, sehingga perjalanannya dikatakan sempurna. Definisi dari Traveling Saleman
Problem yaitu diberikan n buah kota dan Cij yang merupakan jarak antara kota i dan
kota j, seseorang ingin membuat suatu lintasan tertutup dengan mengunjungi setiap
kota satu kali. Tujuannya adalah memilih lintasan tertutup yang total jaraknya paling
minimum diantara pilihan dari semua kemungkinan lintasan.
Berikut ini adalah bentuk modelnya :
Meminimalkan ∑ ( ) (2.1)
Dengan batas :
∑
(2.2)
7
∑
(2.3)
Parameter :
N = jumlah kota / lokasi / pelanggan yang akan dikunjungi (n tidak
termasuk tempat asal (base), yang diindekkan dengan i = 0).
Cij = biaya / jarak traveling dari kota i ke kota j
A = sepasang arc / edge (i,j) yang ada. Note bahwa (i,j) yang dimaksud
adalah arc yang ada dari node i ke node j.
Variable :
{
2.5 Lintasan Terpendek
Persoalan mencari lintasan terpendek di dalam graf merupakan salah satu persoalan
optimasi. Graf yang digunakan dalam pencarian lintasan terpendek adalah graf berbobot
(weighted graph), yaitu graf yang setiap sisinya diberikan suatu nilai atau bobot. Bobot
pada sisi graf dapat menyatakan jarak antar kota, waktu pengiriman pesan, ongkos
pembangunan dan sebagainya. Asumsi yang digunakan disini adalah bahwa semua
bobot bernilai positif. Kata “terpendek” jangan selalu diartikan secara fisik sebagai
panjang minimum, sebab kata “terpendek” berbeda- beda maknanya bergantung pada
tipikal persoalan yang akan diselesaikan. Namun, secara umum “terpendek” berarti
meminimisasi bobot pada suatu lintasan di dalam graf.
Misalnya simpul pada graf dapat merupakan kota, sedangkan sisi menyatakan jalan yang
menghubungkan dua buah kota. Bobot sisi graf dapat menyatakan jarak antara dua buah
kota atau rata- rata waktu tempuh antara dua buah kota. Apabila terdapat lebih dari satu
lintasan dari kota A ke kota B, maka persoalan lintasan terpendek di sini adalah
menentukan jarak terpendek atau waktu tersingkat dari kota A ke kota B.
Misalkan simpul pada graf dapat merupakan terminal komputer atau simpul komunikasi
dalam suatu jaringan, sedangkan sisi menyatakan saluran komunikasi yang
menghubungkan dua buah terminal. Bobot pada graf dapat menyatakan biaya pemakaian
saluran komunikasi antara dua buah terminal, jarak antara dua buah terminal, atau waktu
pengiriman pesan (message) antara dua buah terminal.Persoalan lintasan terpendek di
sini adalah menentukan jalur komunikasi terpendek antara dua buah terminal komputer.
8
Lintasan terpendek akan menghemat waktu pengiriman pesan dan biaya komunikasi. Ada
beberapa macam persoalan lintasan terpendek, antara lain:
a) Lintasan terpendek antara dua buah simpul tertentu.
b) Lintasan terpendek antara semua pasangan simpul.
c) Lintasan terpendek dari simpul tertentu ke semua simpul yang lain.
d) Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu.
2.6 Algoritma Greedy
Algoritma Greedy memiliki pendekatan untuk membangun solusi secara bertahap
melalui urutan yang terus berkembang sampai solusi dari masalah telah tercapai (Levitin,
dkk., 2007). Greedy memberikan alternatif optimal lokal dengan harapan setiap alternatif
lokal menghasilkan alternatif global yang optimal secara keseluruhan. Algoritma Greedy
dapat menyelesaikan Travelling Salesman Problem dengan menghitung nilai lokal
optimal setiap mengunjungi kota dan mendapatkan nilai optimasi global pada akhir
perjalanan (Lukman, dkk., 2011)
Algoritma Greedy dalam penelitian terdahulu dapat diimplementasikan dalam melakukan
optimasi jarak seperti dalam menentukan lintasan terdekat atau shortest path dan
Travelling Salesman Problem (TSP). Algoritma Greedy dapat menentukan jalur mana
yang akan diambil terlebih dahulu atau dapat disebut dengan jalur optimum lokal
sehingga sampai seluruh jalur diambil pada akhir perjalanan dan menciptakan rute
perjalanan terpendek atau disebut dengan optimum global sehingga dapat pula
menyelesaikan TSP. Persoalan optimasi dalam konteks Algoritma Greedy disusun oleh
komponen- komponen sebagai berikut (Efendi, dkk., 2012) :
1. Himpunan Kandidat, (C) : Merupakan himpunan yang berisi elemen- elemen
pembentuk solusi. Padasetiap langkah, satu buah kandidat diambil dari
himpunannya.
2. Himpunan Solusi ,(S) : Merupakan himpunan-himpunan yang berisi elemen
solusi pemecahan masalah.
3. Fungsi Seleksi : Merupakan fungsi yang pada setiap langkah memilih kandidat
yang palingmemungkinkan mencapai solusi optimal. Kandidat yang sudah
dipilih pada suatu langkah tidak pernah dipertimbangkan lagi pada langkah
selanjutnya.
4. Fungsi Kelayakan : Merupakan fungsi yang memeriksa apakah suatu kandidat
yang dipilih dapatmemberikan solusi yang layak, yakni kandidat tersebut
bersama- sama dengan himpunan solusi yang sudah terbentuk tidak melanggar
kendala yang ada.
9
5. Fungsi Objektif : Merupakan fungsi yang memaksimumkan atau
meminimumkan nilai solusi.
Dalam penggunaan metode algoritma Greedy pertama membuat sebuah graf dan
menentukan bobot setiap sisi (edge). Untuk menentukan bobot setiap sisi dilakukan
dengan bantuan Google Maps.
Diberikan sebuah graph berbobot G(V,E). Tentukan lintasan terpendek dari verteks awal
a, ke setiap verteks lainnya di G. Asumsi bahwa bobot semua edge(arc) bernilai positif.
Algoritma Greedy untuk mencari lintasan terpendek dapat dirumuskan sebagai berikut :
1) Periksa semua edge(arc) yang langsung bersesuaian dengan verteks a. Pilih edge(arc)
yang berbobot terkecil. Edge(arc)ini menjadi lintasan terpendek pertama, sebut saja
L(1).
2) Tentukan lintasan terpendek ke dua dengan cara sebagai berikut :
a. Hitung d(i) = panjang L(1) + bobot edge(arc) dari verteks akhir L(1) ke verteks
I yang lain.
b. Pilih d(i) yang terkecil
c. Bandingkan d(i) dengan bobot edge(arc) (a,i) lebih kecil daripada d(i), maka
L(2)
d. Dengan cara yang sama, ulangi langkah (2) untuk menentukan lintasanterpendek
berikutnya.
2.7 Android
Android merupakan subset perangkat lunak untuk ponsel yang meliputi sistem operasi,
middleware dan aplikasi kunci yang berbasis Linux yang di rilis oleh Google. Saat ini
disediakan Android SDK (SoftwareDevelopment Kit) sebagai alat bantu dan Android
menyediakan platform terbuka bagi para pengembanguntuk menciptakan aplikasi mereka
sendiri untuk digunakan oleh bermacam peranti bergerak
10
BAB III
METODOLOGI PENELITIAN
3.1 Jenis Penelitian
Jenis penelitian yang digunakan dalam penelitian ini adalah penelitian terapan
(Applied Research), yaitu penelitian yang kegunaannya diarahkan dalam rangka
memecahkan masalah-masalah pada kehidupan nyata.
3.2 Jenis Data
Jenis data dalam penelitian ini adalah data primer. Data primer adalah data penelitian
yang diperoleh secara langsung dari sumber aslinya, yang dalam hal ini data diperoleh
dari PT. Sadar Jaya Manunggal cabang Kota Mataram dan google maps.
3.3 Diagram Alir Penelitian
Start
Mengidentifikasi masalah
Menentukan rumusan masalah,
tujuan, dan manfaat penelitan
Jenis penelitian Jenis data
Penelitian terapan Data primer
Hasil dan pembahasan
Penarikan kesimpulan
End
Pengolahan data
11
3.4 Tahap-Tahap Penelitian
Tahap-tahap yang dilakukan dalam penelitian ini adalah sebagai berikut:
1. Mengidentifikasi masalah
Pada tahap ini dicari sumber pustaka yang berhubungan dengan penelitian yang
akan dilakukan dan dipilih bagian dari sumber pustaka sehingga dapat
memunculkan ide yang pada akhirnya akan dikaji oleh peneliti sebagai landasan
dalam melakukan penelitian.
2. Merumuskan masalah
Merumuskan masalah diperlukan agar permasalahan yang dibahas dalam
penelitian jelas dan tidak melebar, sehingga akan lebih mudah untuk menentukan
pemecahan masalah tersebut.
3. Mengumpulkan data
Dalam tahap ini penulis mengumpulkan data-data yang diperlukan seperti data
customer PT. Sadar Jaya Manunggal cabang Kota Mataram dan data jarak setiap
alamat customer PT. Sadar Jaya Manunggal.
4. Pengolahan data
Pengolahan data dapat dilakukan dengan tahap-tahap berikut:
a. Membentuk Graf
Untuk membentuk graf rute pendistribusian bahan bangunan PT. Sadar Jaya
Manunggal, terlebih dahulu ditentukan simpul, sisi dan bobot masing-masing
sisi. Pada penelitian ini yang menjadi simpul adalah alamat customer atau
tujuan pendistribusian bahan bangunan oleh PT. Sadar Jaya Manunggal. Yang
menjadi sisi adalah jalan yang menghubungkan tempat yang satu ke tempat
lainnya. Sedangkan jarak dari masing-masing tempat merupakan bobot pada
penelitian ini.
b. Membuat Matriks Ketetanggaan
Dari graf yang dibentuk, kemudian di buat matriks ketetanggan masing–
masing.
c. Menentukan rute dengan Bobot Minimum
Dari matriks ketetanggaan yang dibentuk, dapat dicari rute terpendek dari
simpul satu ke simpul lainnya.
12
5. Menarik kesimpulan
Setelah tahap-tahap di atas terselesaikan, maka didapatkan hasil rute terpendek
pendistribusian bahan bangunan oleh PT. Sadar Jaya Manunggal cabang Kota
Mataram ke setiap customer.
13
BAB IV
HASIL DAN PEMBAHASAN
Dalam penelitian ini, data yang digunakan merupakan data dari hasil pencarian jarak
pada Google Maps yang dinyatakan dalam satuan kilometer (km). Berdasarkan data yang
didapat, dibentuk sebuah graf lengkap dengan jumlah 8 simpul dan 28 sisi. Graf lengkap yang
terbentuk dapat dilihat pda gambarberikut:
Keterangan:
Simpul 1: PT. Sadar Jaya
Manunggal Kota Mataram
Simpul 2: UD. IkhlasBersama
Simpul 3: Kurnia Jaya
Simpul 4: PosBangunan
Simpul 5: KunciPelita
Simpul 6: UD. MitraUtama
Simpul 7: UD. Salha
Simpul 8: UD. Budi Rahman
Pada graf tersebut alamat konsumen diasumsikan sebagai simpul dan jalan diasumsikan
sebagai sisi. Dengan pembentukan graf lengkap tersebut, akan menjadi lebih mudah
menganalisa permasalahan yang akan dibahas dalam penelitian ini yaitu Travelling
Salesperson Problem (TSP). Masalah yang muncul dari TSP berhubungan dengan rute
perjalanan untuk mengantarkan atau menjual barang pada beberapa kota dengan waktu atau
jarak perjalanan seminimal mungkin. Uraian persoalannya adalah diberikan sejumlah kota
dan jarak antar kota. Tentukan rute terpendek yang harus dilalui oleh pedagang bila pedagang
itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali, dan kembali
lagi ke kota sal keberangkatan dengan pencarian relatif singkat. Untuk menyelesaikan
masalah TSP terdapat banyak algoritma yang dapat digunakan diantaranya adalah algoritma
14
Genetik, algoritma Greedy,Generate and Test, algoritma Branch and Bound, dan lain-lain.
Dalam permasalahan ini digunakan algoritma greedy untuk menyelesaikan masalah TSP.
Algoritma greedy memiliki pendekatan untuk membangun solusi secara bertahap melalui
urutan yang terus berkembang sampai solusi dari masalah telah tercapai
4.2 Data Pengujian
Pada TSP ini menggunakan graf lengkap berbobot yaitu jika setiap simpul mempunyai
sisi atau jarak ke simpul yang lain. Graf ini terdiri dari 8 simpul yang mewakili banyaknya
konsumen yang memesan bahan bangunan pada PT Sadar Jaya Manunggal yang akan dicari
(Khususnya daerah Lombok Tengah) Dibawah ini merupakan matriks jarak antar alamat
konsumen yang memesan bahan bangunan yang akan di cari.
Tabel 4.1 Matriks ketetanggan jarak 7 alamat konsumen dan PT. Sadar Jaya Manunggal
1 2 0 4 5 6 7 8
1 0 21 39 13 21 9 28 20
2 21 0 36 15 13 16 11 19
3 39 36 0 29 25 34 40 19
4 13 15 29 0 7.1 5.8 25 9.7
5 21 13 25 7.1 0 12 19 9,4
6 9 16 34 5.8 12 0 26 17
7 28 11 40 25 19 26 0 28
8 20 19 19 9.7 9,4 17 28 0
Langkah pertama yaitu menentukan titik awal dimana i=1. Selanjutnya menentukan
bobot terkecil dari titik awal ke semua verteks. Dapat dilihat dari matrik dibawah ini :
i=1 1 2 3 4 5 6 7 8
1 0 21 39 13 21 9 28 20
Maka bobot yang terkecil yaitu 1 ke 6, ini menjadi lintasan pertama.
15
Langkah kedua yaitu menentukan lintasan terpendek selanjutnya dari verteks 6.
Dilihat dari tabel matriks dibawah maka didapat bobot terkecilnya yaitu dari 6 ke 4,
ini menjadi lintasan kedua.
i=1 1 2 3 4 5 6 7 8
6 9 16 34 5.8 12 0 26 17
Langkah ketiga yaitu menentukan lintasan terpendek selanjutnya dari verteks 4.
Dilihat dari tabel matriks dibawah maka didapat bobot terkecilnya yaitu dari 4 ke 5,
ini menjadi lintasan ketiga.
i=1 1 2 3 4 5 6 7 8
4 13 15 29 0 7.1 5.8 25 9.7
Langkah keempat yaitu menentukan lintasan terpendek selanjutnya dari verteks 5.
Dilihat dari tabel matriks dibawah karena verteks 4 sudah terseleksi didapat bobot
terkecilnya yaitu dari 5 ke 8, ini menjadi lintasan empat.
i=1 1 2 3 4 5 6 7 8
5 21 13 25 7.1 0 12 19 9,4
Langkah kelima yaitu menentukan lintasan terpendek selanjutnya dari verteks
8.Dilihat dari tabel matriks dibawah karena verteks 4, 5 dan 6 sudah terseleksi maka
didapat bobot terkecilnya yaitu dari 8 ke 2, ini menjadi lintasan kelima.
i=1 1 2 3 4 5 6 7 8
8 20 19 19 9.7 9,4 17 28 0
Langkah keenam yaitu menentukan lintasan terpendek selanjutnya dari verteks 2.
Dilihat dari tabel matriks dibawah maka didapat bobot terkecilnya yaitu dari 2 ke 7,
ini menjadi lintasan keenam.
16
i=1 1 2 3 4 5 6 7 8
2 21 0 36 15 13 16 11 19
Langkah keenam yaitu menentukan lintasan terpendek selanjutnya dari verteks 6.
Dilihat dari tabel matriks dibawah maka didapat bobot terkecilnya yaitu dari 6 ke 7,
ini menjadi lintasan keenam.
i=1 1 2 3 4 5 6 7 8
7 28 11 40 25 19 26 0 28
Jadi urutan lintasan terpendek didapat dari 1-6-4-5-8-2-7-3. Perhitungan total edge
yang telah dioptimasi dengan Algoritma Greedy adalah sebagai berikut:1 ke 6 = 9 km;
6 ke 4 = 5,8 km; 4 ke 5 = 7,1 km; 5 ke 8 = 9,4 km; 8 ke 2 = 19 km; 2 ke 7 = 11 km; 7
ke 3 = 40
Optimasi : 9+5,8+7,1+9,4+19+11+40 = 101,3 km, maka dapat diambil kesimpulan
bahwa seorang supplier dengan lintasan terpendeknya yaitu: dari PT. Sadar Jaya
Manunggal ke arah UD. Mitra Utama, Pos Bangunan, , Kunci Pelita, UD. Budi
Rahman, UD. Ikhlas Bersama, UD. Sahla, Kurnia Jaya.
Optimasi waktu
,3 = 0,59 jam = 59 menit artinya semakin pendek rute
yang kita dapatkan maka semakin optimal atau cepat waktu pendistribusian. Dengan
pendistribusian yang cepat ini maka menguntungkan bagi PT. Sadar Jaya Manunggal
karena dapat memenuhi permintaan toko-toko dan semakin mengurangi biaya
operasional pendistribusian.
Biaya operasional ini berupa bensin yang terpakai dan gaji sopir. Penggunaan bensin
dan gaji sopir ini dipengaruhi oleh jarak yang ditempuh dalam proses pendistribusian.
Semakin jauh jarak yang ditempuh semakin banyak uang yang dikeluarkan. Adapun
dari data yang kami peroleh gaji sopir + bensi per 50 km adalah Rp. 525.000,-
sehingga pengeluaran biaya operasional setiap 1 km yaitu Rp. 525.000,-/ 50 km = Rp.
10.500,- akibatnya diperoleh biaya operasional total
Biaya operasional = (Gaji sopir + Bensin) x Jarak tempuh
17
= Rp. 10.500,- x 101,3 km
= Rp. 1.063.650,-
Untuk biaya operasional sebelumnya dengan jarak rata-rata yang ditempuh sopir
adalah 160,13 km sehingga
Biaya operasional = (Gaji sopir + Bensin) x Jarak tempuh
= Rp. 10.500,- x 160,13 km
= Rp. 1.681.365,-
Jadi, selisih dari kedua biaya operasional tersebut adalah Rp. 617.715,- atau 36%
biaya yang dihemat dalam proses pendistribusian.
18
BAB V
PENUTUP
5.1 Kesimpulan
Berdasarkan hasil pengamatan, analisis graf serta pembahasan dapat disimpulkan
bahwa:
1. Semakin minimal rute yang ditempuh maka semakin optimal waktu yang diperoleh
sehingga dapat menghemat tenaga dan dapat secara cepat dalam pendistribusian
berikutnya
2. Semakin minimal rute yang ditempuh maka biaya operasional yang dikeluarkan
semakin sedikit sehingga diperoleh keuntungan yang lebih maksimal
5.2 Saran
Diharapkan dapat dikembangkan dengan metode atau algoritma yang lain, serta
mampu mengkombinasikan antara jarak dan waktu tempuh dan variabel yang lainnya.
19
DAFTAR PUSTAKA
Amin, Rahma Aulia, dkk, 2006. Traveling Salesman Problem, Bandung: Institut Teknologi
Bandung.
Haseman, Chris. 2008, Android Essential. Heidelberg: Appres.
Kotlerdan Keller. 2009. Manajemen Pemasaran. Jilid I. Edisike 13 Jakarta: Erlangga.
Kurnia, Albert, dkk.2012. Penerapan Metode Dijkstra Dalam Pencarian Jalur Terpendek Pada
Perusahaan Distribusi Film. Prosiding Seminar Ilmiah Nasional Komputer dan Sistem
Intelijen (KOMMIT 2012). 36-41.
Kusunawati, kiki.2017.Travelling Salesman Problem Dalam Pendistribusian Barang
Menggunakan Algoritma Greedy. Jurnal Ilmiah Fakultas Teknik LIMIT’S.13(1), 1-7.
Lipschutz, Ronald D. 2002. The Clash of Governmentalities. The Fall of the UN Republic
and America’s Reach for Empire. Contemporary Security Policy.23: 3, 214-31.
Lukman A., AR., R., & Nurhayati. 2011. Penyelesaian Travelling Salesman Problem Dengan
Algoritma Greedy, Makassar : Prosiding Konferensi Nasional Forum Pendidikan
Tinggi Teknik Elektro Indonesia (FORTEI).
Munir, Rinaldi. 2005. Matematika Diskrit. Bandung: Penerbit Informatika.
Nazruddin, Safaat H.2011. Android Pemrograman Aplikasi Mobile Smartphone dan Tablet
PC Berbasis Android.Informatika Bandung.
Pratiwi, Arum, Muliyono, Rochmad.2014. Implementasi Algoritma Branch And Bound Pada
0-1 Knapsack Problem Untuk Mengoptimalkan Muatan Barang. UNNES Journal of
Mathematics.90-96.
Tjiptono, Fandy. 2008. Strategi Pemasaran, Edisi 3. ANDI: Yogyakarta.