APLIKASI PENENTUAN RUTE PERJALANAN SALESMAN DENGAN SIRKUIT HAMILTON PADA PT. HEALTH WEALTH INTERNATIONAL

APLIKASI PENENTUAN RUTE PERJALANAN SALESMAN DENGAN SIRKUIT HAMILTON PADA PT. HEALTH WEALTH INTERNATIONAL

SKRIPSI

Oleh:

VERA NIM.1145055

PROGRAM STUDI SISTEM INFORMASI SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER STMIK TIME MEDAN 2015

ABSTRAK

PT.Health Wealth International merupakan perusahaan yang bergerak di bidang pemasaran produk kesehatan. Saat ini, PT.Health Wealth International menggunakan Microsoft Excel dalam mencatat transaksi penjualannya. Laporan yang dibuat dapat membantu salesman dalam melakukan pengiriman barang ke customer. Namun, kendala yang dihadapi oleh perusahaan dengan menggunakan sistem ini adalah tidak bisa menentukan rute perjalanan yang harus di lalui oleh setiap salesman dengan waktu yang cepat. Penelitian ini bertujuan untuk menganalisis dan merancang aplikasi rute perjalanan salesman dengan Sirkuit Hamilton pada PT. Health Wealth International yang mencakup pembelian, penjualan, dan rute perjalanan. Metodologi yang digunakan untuk melakukan proses analisis dan perancangan pada penelitian ini adalah metode Breadth First Search (BFS). Tools yang digunakan untuk melakukan analisis dan desain adalah Data Flow Diagram (DFD). Hasil dari penelitian ini adalah Aplikasi Rute Perjalanan dengan Sirkuit Hamilton pada PT.Health Wealth International yang terkomputerisasi yang dapat digunakan untuk menyediakan informasi rute perjalanan yang berguna dalam kegiatan pengiriman barang perusahaan.

Kata Kunci : Sirkuit Hamilton, Sirkuit Euler, Graf, Travelling Salesperson Problem (TSP)

i

ABSTRACT

PT.Health Wealth International is a company which market health products. Until now, PT.Health Wealth International still used Microsoft Excel to record the sales data. The report making could be used to help salesman to shipping product to customer. But, by using this system, the company cannot determine the route of travel that must be passed by each salesman with faster time. The goal of this research is to analyze and design applications for salesman travel route with Hamilton Circuit in PT.Health Wealth International which includes the purchase, sales, and travel route. The methodology used for analyzing and designing the system is BFS method. The tools used to analyze and design is Data Flow Diagram (DFD). The result of this research is a Computerize Applications of Salesman Travel Route with Hamilton Circuit in PT.Health Wealth International which can be used to provide information of route travel that is useful for company shipping products.

Keywords : Hamilton Circuit, Euler Circuit, Graph, Travelling Salesperson Problem (TSP)

ii

KATA PENGANTAR

Puji dan syukur penulis panjatkan kehadirat Tuhan Yang Maha Esa yang telah memberikan hidayah-Nya sehingga penulis dapat menyelesaikan skripsi ini dengan judul : “Aplikasi Penentuan Rute Perjalanan Salesman dengan Sirkuit Hamilton pada PT. Health Wealth Internaitonal”.

Skripsi ini disusun untuk melengkapi

persyaratan studi program Strata 1 (S-1) Sekolah Tinggi Manajemen Informatika Komputer (STMIK) TIME Medan. Penulis menyadari bahwa dalam penulisan skripsi ini banyak menemukan kesulitan-kesulitan dan kekurangan pada penulisan. Namun berkat bantuan dan dorongan dari berbagai pihak akhirnya penulis dapat menyelesaikannya dengan baik. Oleh karena itu, dalam kesempatan ini penulis ingin mengucapkan terima kasih yang sebesar-besarnya kepada : 1. Bapak Edi Wijaya, S.kom, M.Kom, selaku Pembimbing I yang telah memberikan saran dan masukan, serta bimbingan dalam penulisan maupun pembuatan pemrograman skripsi ini. 2. Bapak Rudiyanto Tanwijaya, SE, selaku Pembimbing II yang telah memberikan saran dan masukan, serta bimbingan dalam penulisan skripsi ini. 3. Bapak Simon Kanggali, selaku Ketua Yayasan STMIK TIME Medan 4. Bapak Prof. Chainur Arrasyid, S. H. , selaku Ketua BPH STMIK TIME Medan

iii

5. Bapak Prof. Harlem Marpaung, Ph. D, selaku Ketua STMIK TIME Medan 6. Bapak Jackri Hendrik, S.T, M. Kom, selaku Pembantu Ketua I STMIK TIME Medan 7. Ibu Feriani Astuti Tarigan, S. Kom, M. Kom, selaku Ketua Program Studi Sistem Informasi STMIK TIME Medan 8. Orangtua dan teman-teman mahasiswa serta seluruh dosen di STMIK TIME yang telah banyak memberikan dukungan dan saran untuk penulis Penulis menyadari tanpa adanya dukungan dari teman-teman sekalian semua ini tidak akan terwujud. Hanya dengan doa kepada Tuhan Yang Maha Esa penulis memohon agar kebaikan dan bimbingan dari teman-teman semua dapat dibalas dengan kebahagiaan dan kesehatan. Akhir kata, penulis mengucapkan terimakasih sebesar-besarnya kepada semua pihak yang telah membantu terhadap penyelesaian penulisan skripsi ini.

Medan, 15 Mei 2015 Penulis,

Vera

iv

DAFTAR ISI

ABSTRAK ..............................................................................................................

i

ABSTRACT .............................................................................................................. ii KATA PENGANTAR ............................................................................................. iii DAFTAR ISI ............................................................................................................ v DAFTAR GAMBAR ...............................................................................................viii DAFTAR TABEL ................................................................................................... xi DAFTAR LAMPIRAN ........................................................................................... xii BAB I

PENDAHULUAN ............................................................................ 01 1.1 Latar Belakang Masalah .............................................................. 01 1.2 Identifikasi Masalah .................................................................... 02 1.3 Batasan Masalah ......................................................................... 02 1.4 Tujuan dan Manfaat Penelitian ................................................... 03 1.5 Sistematika Penulisan .................................................................. 03

BAB II

LANDASAN TEORI ....................................................................... 05 2.1 Travelling Salesperson Problem ( TSP ) ..................................... 05 2.2 Aplikasi ....................................................................................... 08 2.3 Graf .............................................................................................. 9 2.4 Jenis-Jenis Graf ............................................................................ 12 2.4.1 Graf Sederhana ( Simple Graph ) ...................................... 12 2.4.2 Graf Tak Sederhana ( Unsimple Graph ) .......................... 13 2.4.3 Graf Tak Berarah ( Undirected Graph ) ........................... 14 2.4.4 Graf Berarah ( Directed Graph )....................................... 15 2.5 Istilah-Istilah Dasar dalam Graf .................................................. 17 2.6 Representasi Graf ........................................................................ 22 2.7 Jarak Euclidean ........................................................................... 24 2.8 Lintasan dan Sirkuit Hamilton .................................................... 24 2.9 Lintasan dan Sirkuit Euler ............................................................ 31 2.10 Microsoft Visual Basic.NET ...................................................... 33

v

BAB III

METODE PENELITIAN ............................................................... 36 3.1 Tempat dan Jadwal Penelitian .................................................... 36 3.2 Kerangka Kerja ........................................................................... 36 3.2.1 Pengumpulan Data ........................................................... 37 3.2.2 Analisa Sistem .................................................................. 38 3.2.3 Perancangan Sistem ......................................................... 38 3.2.4 Pembangunan Sistem ....................................................... 39 3.2.5 Uji Coba Sistem ............................................................... 40

BAB IV

ANALISIA DAN PERANCANGAN............................................... 41 4.1 Analisa ........................................................................................ 41 4.1.1 Analisa Dokumen Keluaran ............................................. 41 4.1.2 Analisia Dokumen Masukan ............................................ 42 4.1.3 Analisia Data .................................................................... 45 4.1.4 Analisia Cara Kerja

...................................................... 46

4.2 Perancangan ................................................................................ 52 4.2.1 Data Flow Diagram (DFD) ............................................... 52 4.2.2 Kamus Data ...................................................................... 54 4.2.3 Rancangan Output ............................................................ 55 4.2.4 Rancangan Input ............................................................... 59 4.2.5 Rancangan Basis Data ...................................................... 65 4.2.6 Rancangan Site Map ........................................................ 69 BAB V

HASIL DAN PEMBAHASAN ........................................................ 70 5.1 Tampilan Hasil ............................................................................. 70 5.2 Pembahasan ................................................................................. 76 5.2.1 Keunggulan dan Kelemahan Sistem Usulan ..................... 76 5.2.2 Kebutuhan Sistem ............................................................ 77

BAB V1

KESIMPULAN DAN SARAN ........................................................ 79 6.1 Kesimpulan .................................................................................. 79 6.2 Saran ............................................................................................. 79

vi

DAFTAR PUSTAKA LAMPIRAN

vii

DAFTAR GAMBAR Gambar 2.1.

Tiga Buah Graf ( Graf Sederhana, Graf Ganda dan Graf Semu ) ..... 11

Gambar 2.2.

Contoh Graf Sederhana ..................................................................... 12

Gambar 2.3.

Contoh Graf Ganda ............................................................................ 13

Gambar 2.4.

Contoh Graf Semu ............................................................................. 14

Gambar 2.5.

Contoh Graf Tak Berarah .................................................................. 15

Gambar 2.6.

Contoh Graf Berarah .......................................................................... 16

Gambar 2.7.

Contoh Graf Ganda Berarah .............................................................. 16

Gambar 2.8.

Contoh Sirkuit Hamilton .................................................................... 26

Gambar 2.9.

Contoh Lintasan Hamilton ................................................................. 26

Gambar 2.10. Contoh Graf Hamilton Teorema 1 ..................................................... 27 Gambar 2.11. Contoh Graf Hamilton Teorema 2 ..................................................... 28 Gambar 2.12. Contoh Graf Hamilton Teorema 3 ..................................................... 28 Gambar 2.13. Contoh Graf Hamilton Teorema 4 ..................................................... 29 Gambar 2.14. Contoh Graf Hamilton Teorema 5 ..................................................... 30 Gambar 2.15. Contoh Graf Hamilton Teorema 6 ..................................................... 31 Gambar 2.16. Contoh Lintasan Euler........................................................................ 32 Gambar 2.17. Contoh Sirkuit Euler .......................................................................... 33 Gambar 2.18. Contoh Tampilan New Project ........................................................... 33 Gambar 3.1.

Kerangka Kerja ................................................................................ 37

Gambar 4.1.

Laporan Penjualan .............................................................................. 41

Gambar 4.2.

Formulir Data Pelanggan ................................................................... 42

Gambar 4.3.

Formulir Data Salesman ..................................................................... 43

Gambar 4.4.

Formulir Data Produk ........................................................................ 44

Gambar 4.5.

Contoh Lintasan yang akan dicari solusinya ..................................... 47

Gambar 4.6.

Prosedur Pencarian BFS .................................................................... 48

Gambar 4.7.

Prosedur Pencarian DFS .................................................................... 49

Gambar 4.8.

Diagram Konteks Logika dari Sistem Usulan ................................... 53

Gambar 4.9.

DFD Logika Level 0 dari Sistem Usulan .......................................... 53

Gambar 4.10. Rancangan Daftar Customer ............................................................. 55 Gambar 4.11. Rancangan Daftar Salesman .............................................................. 56 Gambar 4.12. Rancangan Daftar Barang .................................................................. 57 viii

Gambar 4.13. Rancangan Laporan Penjualan ........................................................... 58 Gambar 4.14. Rancangan Form ”Master Barang” ................................................... 60 Gambar 4.15. Rancangan Form ”Master Kota” ........................................................ 61 Gambar 4.16. Rancangan Form ”Master Customer” ................................................ 62 Gambar 4.17. Rancangan Form ”Master Salesman” ................................................ 63 Gambar 4.18. Rancangan Form ”Transaksi Penjualan” ........................................... 64 Gambar 4.19. Rancangan Form “Penentuan Rute Perjalanan Salesman” ............... 65 Gambar 4.20. Rancangan Relasi Antar Tabel ........................................................... 69 Gambar 4.21. Rancangan Menu Utama ................................................................... 69 Gambar 5.1.

Tampilan Form “Main”...................................................................... 70

Gambar 5.2.

Tampilan Menu Master ...................................................................... 71

Gambar 5.3.

Tampilan Menu Transaksi ................................................................. 71

Gambar 5.4.

Tampilan Menu Laporan .................................................................... 72

Gambar 5.5.

Tampilan Menu Laporan Bagian Penjualan ....................................... 72

Gambar 5.6.

Tampilan Form ”Master Barang” ...................................................... 73

Gambar 5.7.

Tampilan Form ”Master Customer” .................................................. 73

Gambar 5.8.

Tampilan Form ”Master Salesman” .................................................. 74

Gambar 5.9.

Tampilan Data Kota .......................................................................... 74

Gambar 5.10. Tampilan Form “Transaksi Penjualan” ............................................. 75 Gambar 5.11. Tampilan Form “Penentuan Rute Perjalanan Salesman” .................. 75 Gambar 5.12. Tampilan Form “Hasil Rute Perjalanan Salesman” ........................... 76

ix

DAFTAR TABEL Tabel 2.1.

Perbandingan Jenis-Jenis Graf ..............................................................16

Tabel 3.1.

Jadwal Penelitian...................................................................................36

Tabel 4.1.

Tabel Barang .........................................................................................66

Tabel 4.2.

Tabel Kota .............................................................................................66

Tabel 4.3.

Tabel Customer .....................................................................................67

Tabel 4.4

Tabel Sales ...........................................................................................67

Tabel 4.5.

Tabel Penjualan .....................................................................................68

Tabel 4.6.

Tabel Detail Penjualan ..........................................................................68

x

DAFTAR LAMPIRAN Lampiran 1

: Daftar Riwayat Hidup Mahasiswa

Lampiran 2

: Surat Keputusan Dosen Pembimbing Skripsi

Lampiran 3

: Kartu Bimbingan Skripsi Dosen Pembimbing I

Lampiran 4

: Kartu Bimbingan Skripsi Dosen Pembimbing II

Lampiran 5

: Listing Program CD

xi

BAB I PENDAHULUAN

1.1.

Latar Belakang Masalah Dalam kehidupan sehari-hari, sering diperlukan efisiensi dalam pekerjaan

terutama dalam hal meningkatkan kinerja dari karyawan sehingga dapat meningkatkan bisnis perusahaan. Pembahasan dalam penelitian ini mengangkat topik mengenai bagaimana seorang salesperson atau yang biasa dikenal dengan nama salesman, melaksanakan tugasnya dengan mengunjungi semua kota hanya sekali dan mencari jarak terdekat dari satu kota ke kota-kota yang lain. Nama persoalan ini adalah Travelling Salesperson Problem (TSP) yang diilhami oleh masalah seorang pedagang yang berkeliling mengunjungi sejumlah kota. Deskripsi persoalannya adalah sebagai berikut: diberikan sejumlah kota dan jarak antar kota. Jalur yang menghubungkan dua buah kota adalah jalur dua arah. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Permasalahan yang dihadapi oleh salesperson tersebut adalah bagaimana meminimalkan jarak tempuh yang digunakan dalam mengunjungi setiap kota tersebut dengan sebuah kota sebagai tempat keberangkatannya. Dalam permasalahan TSP, kota dapat dinyatakan sebagai simpul graf sedangkan sisi menyatakan jalan yang menghubungkan antar dua buah kota. Bobot pada sisi menyatakan jarak antara dua buah kota. Graf (graph) adalah salah satu jenis struktur data yang terdiri dari kumpulan simpul dan sisi yang

1

2

menghubungkan sepasang simpul dengan persyaratan bahwa tidak boleh ada simpul yang tidak terhubung. Persoalan perjalanan pedagang adalah menentukan sirkuit Hamilton yang memiliki bobot minimum pada sebuah graf terhubung. Lintasan Hamilton adalah lintasan yang melalui tiap simpul di dalam graf tepat satu kali. Bila lintasan itu kembali ke simpul asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton adalah sirkuit yang melalui tiap simpul di dalam graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali. Berdasarkan uraian yang telah ditemukan diatas, menjadikan bahan kajian yang dituangkan dalam bentuk skripsi dengan judul “Aplikasi Penentuan Rute Perjalanan Salesman dengan Sirkuit Hamilton pada PT. Health Wealth International ”.

1.2.

Identifikasi Masalah Masalah yang ditemukan dalam penyusunan skripsi ini adalah:

1. Bagaimana

menentukan

menggunakan bantuan

rute

perjalanan

seorang

salesman

dengan

sirkuit Hamilton sehingga dapat memilih waktu

menjadi minimum ? 2. Bagaimana merancang aplikasi penentuan rute perjalanan salesman dengan menggunakan sirkuit Hamilton ?

1.3.

Batasan Masalah Peneliti membuat batasan yang meliputi:

1

Data input meliputi data customer dan jarak antara tempat customer.

3

2

Output yang akan dihasilkan dari sistem ini berupa rute perjalanan dari seorang salesman.

3

Dalam perancangan sistem, penulis menggunakan Integrated Development Environment (IDE) dari bahasa pemrograman Microsoft Visual Basic 2010 sebagai rancangan tampilan input-nya.

4

Perancangan database menggunakan Microsoft Access 2007 dan tampilan laporan dirancang dengan menggunakan Crystal Report 10.

1.4. Tujuan dan Manfaat Penelitian Adapun tujuan dalam penelitian ini adalah untuk menentukan rute perjalanan salesman sehingga dapat meminimalkan waktu yang digunakan dalam mengunjungi setiap kota tersebut dengan sebuah kota sebagai tempat keberangkatannya. Manfaat dari penelitian ini adalah blue print (rancangan) yang dapat dikembangkan menjadi sebuah aplikasi terkomputerisasi, untuk menentukan rute perjalanan salesman yang dapat meminimalkan waktu tempuh yang harus dilalui.

1.5.

Sistematika Penulisan Agar pembahasan lebih sistematis, maka skripsi ini dibuat dalam enam

bab, yaitu: BAB I

: PENDAHULUAN Berisi tentang latar belakang, identifikasi masalah, batasan masalah, tujuan dan manfaat penelitian dan sistematika penulisan.

4

BAB II

: LANDASAN TEORI Berisi tentang penjelasan singkat mengenai sistem informasi, graf, travelling salesperson problem (TSP), sirkuit Hamilton, metode pengembangan sistem, Data Flow Diagram (DFD), kamus data, basis data, normalisasi, Microsoft Visual Basic 2010, Microsoft Access 2007 dan Crystal Report 10.

BAB III

: METODE PENELITIAN Berisi tentang metode pengumpulan data yang digunakan dalam penyusunan skripsi.

BAB IV

: ANALISA DAN PERANCANGAN Berisi tentang analisis dokumen masukan dan keluaran dari sistem yang digunakan pada sistem berjalan dan perancangan terhadap sistem usulan.

BAB V

: HASIL DAN PEMBAHASAN Berisi tentang tampilan output sistem dan penjabaran singkat mengenai kelebihan dan kelemahan sistem.

BAB VI

: KESIMPULAN DAN SARAN Berisi tentang kesimpulan yang dapat ditarik setelah menyelesaikan skripsi ini dan saran-saran.

BAB  LANDASAN TEORI

2.1

Travelling Salesperson Problem (TSP) Asal usul dari masalah Travelling Salesperson ( TSP ) tidak dapat

diketahui secara pasti. Sebuah handbook untuk Travelling Salesperson pada tahun 1832 menjelaskan problema tersebut dan memberikan contoh perjalanan menelusuri Jerman dan Swiss, tetapi tidak memberikan detail rumusan matematis. Problema Travelling Salesperson pertama kali diformulasikan secara matematis pada tahun 1800 oleh ahli matematika Irlandia, W.R. Hamilton dan ahli matematika Inggris, Thomas Kirkman. Permainan Icosian dari Hamilton merupakan sebuah puzzle rekreasi yang berdasarkan pada penemuan Hamilton cycle. Bentuk umum dari TSP pertama kali dipelajari oleh ahli matematika selama tahun 1930 pada Vienna dan Harvard, terutama oleh Karl Menger, yang mendefinisikan problema ini, dengan menggunakan algoritma brute-force. Deskripsi persoalannya adalah sebagai berikut yaitu diberikan sejumlah kota dan jarak antar kota. Jalur yang menghubungkan dua buah kota adalah jalur dua arah. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Permasalahan yang dihadapi oleh salesperson tersebut adalah bagaimana meminimalkan jarak tempuh yang digunakan dalam mengunjungi setiap kota tersebut dengan sebuah kota sebagai tempat keberangkatannya. ( David L. Applegate, Robert E. Bixby, Vasek Chvátal, William J. Cook , 2006 : 1-2 )

5

6

Meskipun

persoalan

ini

bernama

perjalanan

pedagang,

namun

penerapannya tidak hanya pada kasus yang berhubungan dengan pedagang. Banyak terapan TSP yang muncul dalam kehidupan sehari-hari maupun dalam bidang teknik, antara lain: 1. Misalkan sebuah mobil pos ditugaskan mengambil surat dari kotak pos yang tersebar pada n buah lokasi di berbagai sudut kota. Graf dengan n + 1 simpul dapat digunakan untuk menyajikan persoalan. Sisi (i, j) diberi bobot yang sama dengan jarak dari kotak pos i ke kotak pos j. Rute yang dilalui mobil pos adalah sebuah perjalanan (tour) yang mengunjungi setiap kotak pos hanya satu kali dan kembali lagi ke kantor pos asal. Kita harus menentukan rute perjalanan yang mempunyai total jarak terpendek. 2. Misalkan kita ingin menggunakan lengan robot untuk mengencangkan mur pada beberapa buah peralatan mesin dalam sebuah jalur perakitan. Lengan robot mulai berada dari posisi awalnya (yaitu di atas mur pertama, kemudian mengencangkannya), lalu berturut-turut pindah ke mur-mur berikutnya dan kembali lagi ke posisi awalnya. Siklus yang dibentuk jelaslah perjalanan mengunjungi simpul-simpul sebuah Graf. Tiap simpul menyatakan mur, sisi menyatakan perpindahan dan bobot setiap sisi menyatakan waktu yang diperlukan lengan robot untuk berpindah di antara dua simpul. Perjalanan dengan biaya minimum berarti meminimumkan waktu yang dibutuhkan robot untuk menyelesaikan tugasnya (yaitu total waktu perpindahan dari sebuah mur ke mur lainnya, sedangkan waktu pengencangan mur tidak dimasukkan dalam perhitungan).

7

3. Dalam lingkungan produksi terdapat beberapa komoditi yang dihasilkan oleh sekumpulan mesin. Proses fabrikasi merupakan sebuah siklus. Tiap-tiap siklus produksi menghasilkan n komoditi berbeda. Bila pekerjaan mesin diubah dari produksi komoditas i ke komoditas j, perubahan tersebut mendatangkan biaya sebesar cij. Diinginkan untuk menemukan runtunan produksi yang menghasilkan n komoditas ini. Runtunan tersebut harus meminimumkan total biaya akibat perubahan urutan produksi (biaya lainnya tidak bergantung pada runtunan). Karena komoditas diproses secara siklus, adalah perlu memasukkan biaya untuk memulai siklus berikutnya. Ini adalah biaya akibat perubahan produksi komoditi terakhir ke komoditi pertama. Masalah ini dapat dianggap sebagai TSP pada Graf n simpul dengan sisi yang bobotnya cij. Pada persoalan TSP ini, jika setiap simpul mempunyai sisi ke simpul yang lain, maka Graf yang merepresentasikannya adalah Graf lengkap berbobot. Pada sembarang Graf lengkap dengan n buah simpul (n > 2), jumlah sirkuit Hamilton yang berbeda adalah (n – 1)!/2. Rumus ini dihasilkan dari kenyataan bahwa dimulai dari sembarang simpul kita mempunyai n – 1 buah sisi untuk dipilih dari simpul pertama, n – 2 sisi dari simpul kedua, n – 3 dari simpul ketiga, dan seterusnya. Ini adalah pilihan yang independen, sehingga kita memperoleh (n – 1)! pilihan. Jumlah itu harus dibagi dengan 2, karena tiap sirkuit Hamilton terhitung dua kali, sehingga semuanya ada (n – 1)!/2 buah sirkuit Hamilton. (Munir, 2010) TSP merupakan masalah yang unik. Tujuan dari TSP adalah mencari rute/jalur terpendek untuk dijadikan sebagai jalur penjelajahannya. TSP merupakan permasalahan dimana seorang salesperson mengunjungi semua kota hanya sekali dan mencari mana jarak yang terdekat dari satu kota ke kota-kota

8

yang lain. Karena TSP ini merupakan suatu masalah yang bersifat polynomial worst-case time complexity dan tidak ada algoritma yang cocok untuk menyelesaikan masalah TSP secara optimal. Dalam algoritma ini, diasumsikan bahwa biaya perjalanan antar kota adalah berbeda.

2.2

Aplikasi Aplikasi adalah suatu perangkat lunak komputer yang memanfaatkan

kemampuan komputer langsung untuk melakukan suatu tugas yang diinginkan pengguna. Biasanya dibandingkan dengan perangkat lunak sistem yang mengintegrasikan berbagai kemampuan komputer, tapi tidak secara langsung menerapkan kemampuan tersebut untuk mengerjakan suatu tugas yang menguntungkan pengguna. Contoh utama perangkat lunak adalah pengolah kata, lembar kerja dan pemutar media. Beberapa aplikasi yang digabung bersama menjadi suatu paket kadang disebut sebagai application suite. Contohnya adalah Microsoft Office dan OpenOffice.org, yang menggabungkan suatu apliaksi pengolah kata, lembar kerja, serta beberapa aplikasi lainnya. Aplikasi-aplikasi dalam suatu paket biasanya memiliki antarmuka pengguna yang memiliki kesamaan sehingga memudahkan pengguna untuk mempelajari dan menggunakan tiap aplikasi. Sering kali, mereka memiliki kemampuan untuk saling berinteraksi satu sama lain sehingga menguntungkan pengguna. Contohnya, suatu lembar kerja dapat dimasukkan dalam suatu dokumen pengolah kata walaupun dibuat pada aplikasi lembar kerja yang terpisah.

9

Definisi aplikasi menurut para ahli: 1. Menurut Hengky W. Pramana Aplikasi adalah suatu unit perangkat lunak yang dibuat untuk melayani kebutuhan akan beberapa aktivitas seperti sistem perniagaan, game pelayanan masyarakat, periklanan, atau semua proses yang hampir dilakukan manusia. ( Sumber : http://www.lepank.com/2012/08/pengertian-aplikasi-menurutbeberapa.html ) 2. Menurut Hendrayudi Aplikasi adalah kumpulan perintah program yang dibuat untuk melakukan pekerjaan-pekerjaan tertentu. ( Sumber : http://dilihatya.com/1810/pengertian-program-aplikasi-menurutpara-ahli ) 3. Menurut Ibisa Aplikasi adalah alat bantu untuk mempermudah dan mempercepat proses pekerjaan dan bukan merupakan beban bagi penggunanya. ( Sumber : http://dilihatya.com/1810/pengertian-program-aplikasi-menurutpara-ahli )

2.3

Graf Teori Graf merupakan pokok bahasan yang sudah tua usianya namun

memiliki

banyak

terapan

sampai

saat

ini.

Graf

digunakan

untuk

merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari Graf adalah dengan menyatakan objek sebagai noktah, bulatan atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.

10

Sebagai contoh, peta jaringan jalan kereta api yang menghubungkan sejumlah kota di pulau Sumatera. Sesungguhnya peta tersebut adalah sebuah Graf, yang dalam ini kota dinyatakan sebagai bulatan sedangkan jalan dinyatakan sebagai garis. Dengan diberikannya peta tersebut, maka dapat diketahui apakah ada lintasan jalan antara dua buah kota. Selain itu, bila panjang jalan kereta api antara dua buah kota bertetangga diketahui, maka juga dapat ditentukan rute perjalanan tersingkat dari kota A ke kota B. Secara matematis, Graf G dapat didefinisikan sebagai pasangan himpunan (V, E), ditulis dengan notasi G = (V, E), yang dalam hal ini V adalah himpunan tidak kosong dari simpul-simpul (vertices atau nodes) dan E adalah himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul. Definisi diatas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah Graf dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan Graf trivial. Simpul pada Graf dapat dinomori dengan huruf, seperti a, b, c, …, z atau dengan bilangan asli 1, 2, 3, …, n ataupun dengan gabungan keduanya. Sedangkan sisi yang menghubungkan simpul u dengan simpul v dinyatakan dengan pasangan (u, v) atau dinyatakan dengan lambang e1, e2, …, en. Dengan kata lain, jika e adalah sisi yang menghubungkan simpul u dengan simpul v, maka e dapat ditulis sebagai: e = (u, v)

11

Secara geometri Graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dua dimensi yang dihubungkan dengan sekumpulan garis (sisi). Berikut diberikan beberapa contoh Graf : 1

1 e4

e1 2

3

3 e6

e5

e7

e4

e1

e3

e2

2

1 e3

e2

2

e6

e5

4

4

4

(a) G1

(b) G2

(c) G3

3 e7

Gambar 2.1 Tiga buah Graf (a) Graf sederhana, (b) Graf ganda, dan (c) Graf semu ( Sumber : http://slidegur.com/doc/336912/dasar-teori-graf )

G2 adalah Graf dengan himpunan simpul V dan himpunan sisi E yaitu : V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4)}  himpunan ganda = {e1, e2, e3, e4, e5, e6, e7} G3 adalah Graf dengan himpunan simpul V dan himpunan sisi E yaitu : V = {1, 2, 3, 4} E = {(1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3)}  himpunan ganda = {e1, e2, e3, e4, e5, e6, e7, e8} Pada G2, sisi e3 = {1, 3} dan sisi e4 = {1, 3} dinamakan sisi ganda (multiple edges atau paralel edges) karena kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3) dinamakan gelang atau kalang (loop) karena berawal dan berakhir pada simpul yang sama. (Munir, 2012: 356-357)

e8

12

2.4

Jenis-Jenis Graf Graf dapat dikelompokkan menjadi beberapa kategori (jenis) tergantung

pada sudut pandang pengelompokkannya. Pengelompokkan Graf dapat dipandang berdasarkan ada tidaknya sisi ganda atau sisi kalang, berdasarkan jumlah simpul atau berdasarkan orientasi arah pada sisi. Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu Graf, maka secara umum Graf dapat digolongkan menjadi dua jenis, yaitu Graf sederhana dan Graf tak sederhana. Sisi pada Graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah pada sisi, maka secara umum Graf dibedakan atas 2 jenis, yaitu Graf tak berarah dan Graf berarah.

2.4.1

Graf Sederhana (Simple Graph) Graf yang tidak mengandung gelang maupun sisi ganda dinamakan Graf

sederhana. Contoh Graf sederhana adalah Graf yang merepresentasikan jaringan komputer seperti terlihat pada gambar berikut ini: 1

2

3

4

Gambar 2.2 Contoh Graf Sederhana ( Sumber : http://slidegur.com/doc/336912/dasar-teori-graf )

13

Simpul menyatakan komputer, sedangkan sisi menyatakan saluran telepon untuk berkomunikasi. Saluran telepon dapat beroperasi pada dua arah. Pada Graf sederhana, sisi adalah pasangan tak terurut (unordered pairs). Jadi, menuliskan sisi (u, v) sama saja dengan (v, u). Atau dapat juga mendefinisikan Graf sederhana G = (V, E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak terurut yang berbeda yang disebut sisi. (Munir, 2012: 356)

2.4.2

Graf Tak Sederhana (Unsimple Graph) Graf yang mengandung sisi ganda atau gelang dinamakan Graf tak

sederhana. Ada dua macam Graf tak sederhana, yaitu Graf ganda (multigraph) dan Graf semu (pseudograph). Graf ganda adalah Graf yang mengandung sisi ganda. Sisi ganda yang menghubungkan sepasang simpul bisa lebih dari dua buah. Contoh Graf ganda dapat dilihat pada gambar berikut ini: 1 e4

e1

e3

e2

2

3 e6

e5

e7

4

Gambar 2.3 Contoh Graf Ganda ( Sumber : http://slidegur.com/doc/336912/dasar-teori-graf )

Sisi ganda dapat diasosiasikan sebagai pasangan tak terurut yang sama. Atau dapat juga mendefinisikan Graf ganda G = {V, E} terdiri dari himpunan tidak kosong simpul-simpul V dan E adalah himpunan ganda (multiset) yang mengandung sisi ganda. Pada jaringan telekomunikasi, sisi ganda pada G2 dapat

14

diandaikan sebagai saluran telepon tambahan apabila beban komunikasi data antar komputer sangat padat. Setiap Graf sederhana juga adalah Graf ganda, tetapi tidak setiap Graf ganda merupakan Graf sederhana. Graf semu adalah Graf yang mengandung gelang (loop). Contoh Graf semu dapat dilihat pada gambar berikut ini: 1 e4

e1

e3

e2

2

e6

e5

3

e8

e7

4

Gambar 2.4 Contoh Graf Semu ( Sumber : http://slidegur.com/doc/336912/dasar-teori-graf )

Sisi gelang pada G3 dapat dianggap sebagai saluran telepon tambahan yang menghubungkan komputer dengan dirinya sendiri (mungkin untuk tujuan diagnostik). Graf semu lebih umum daripada Graf ganda, karena sisi pada Graf semu dapat terhubung ke dirinya sendiri. Jumlah simpul pada Graf dapat disebut sebagai kardinalitas Graf dinyatakan dengan n = |V| dan jumlah sisi dinyatakan dengan m = |E|. Pada contoh gambar 2.1 diatas, G1 mempunyai n = 4 dan m = 4, sedangkan G2 mempunyai n = 3 dan m = 4.

2.4.3

Graf Tak Berarah (Undirected Graph) Graf yang sisinya tidak mempunyai orientasi arah disebut Graf tak

berarah. Pada Graf tak berarah, urutan pasangan simpul yang dihubungkan oleh

15

sisi tidak diperhatikan. Jadi, (u, v) = (v, u) adalah sisi yang sama. Contoh Graf tak berarah dapat dilihat pada gambar berikut ini: a

b

c

d

e

f

Gambar 2.5 Contoh Graf Tak Berarah ( Sumber : Munir, 2010: 356 )

Pada jaringan telepon, sisi pada Graf menyatakan bahwa saluran telepon dapat beroperasi pada dua arah.

2.4.4

Graf Berarah (Directed Graph atau DiGraph) Graf yang setiap sisinya diberikan orientasi arah disebut sebagai Graf

berarah. Sisi berarah dapat juga disebut sebagai busur (arc). Sebuah Grafik berarah (directed Graf) adalah sebuah himpunan berhingga yang terdiri dari elemen-elemen, {P1, P2, …, Pn}, bersama dengan sebuah kumpulan berhingga dari pasangan-pasangan berurutan (Pi, Pj) dari elemen-elemen yang berbeda pada himpunan ini, tanpa ada pasangan berurutan yang diulang. (Anton dan Rorres, 2009: 189) Pada Graf berarah (u, v) dan (v, u) menyatakan dua buah busur yang berbeda, dengan kata lain (u, v)  (v, u). Untuk busur (u, v), simpul u dinamakan simpul asal (initial vertex) dan simpul v dinamakan simpul terminal (terminal vertex). Contoh Graf berarah:

16

1

2

3

4

Gambar 2.6 Contoh Graf Berarah ( Sumber : Munir, 2010: 359 )

Definisi Graf dapat diperluas sehingga mencakup Graf ganda berarah (directed multiGraf). Pada Graf ganda berarah, gelang dan sisi ganda diperbolehkan ada. Contoh Graf ganda berarah dapat dilihat pada gambar 2.8: 1

3

2

4

Gambar 2.7 Contoh Graf Ganda Berarah ( Sumber : Munir, 2010: 359 )

Perbandingan antara jenis-jenis Graf dapat dilihat pada tabel berikut : Tabel 2.1 Perbandingan Jenis-Jenis Graf Jenis

Sisi

Sisi ganda

Sisi gelang

Graf sederhana

Tak berarah

Tidak

Tidak

Graf ganda

Tak berarah

Ya

Tidak

Graf semu

Tak berarah

Ya

Ya

Graf berarah

Berarah

Tidak

Ya

Graf ganda berarah

Berarah

Ya

Ya

( Sumber : Munir, 2010: 359 )

17

2.5

Istilah-Istilah Dasar dalam Graf Di bawah ini akan didefinisikan beberapa terminologi (istilah) yang

berkaitan dengan Graf dan sering dipakai, yakni: 1. Bertetangga (Adjacent) Dua buah simpul pada Graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah sisi. Dengan kata lain, u bertetangga dengan v jika (u, v) adalah sebuah sisi pada Graf G. Pada Graf berarah, sisi disebut busur. Jika (u, v) adalah busur, maka u dikatakan bertetangga dengan v dan v dikatakan sebagai tetangga dari u. 2. Bersisian (Incident) Untuk sembarang sisi e = (u, v), sisi e dikatakan bersisian dengan simpul u dan simpul. 3. Simpul Terpencil (Isolated Vertex) Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian dengannya. Atau, dapat juga dinyatakan bahwa simpul terpencil adalah simpul yang tidak satupun bertetangga dengan simpul-simpul lainnya. 4. Graf Kosong (Null Graph atau Empty Graph) Graf yang himpunan sisinya merupakan himpunan kosong disebut sebagai Graf kosong dan ditulis sebagai Nn, yang dalam hal ini n adalah jumlah simpul. 5. Derajat (Degree) Derajat suatu simpul pada Graf tak berarah adalah jumlah sisi yang bersisian dengan simpul tersebut. Notasi : d(v) menyatakan derajat simpul v.

18

Simpul terpencil adalah simpul dengan d(v) = 0, karena tidak ada satupun sisi yang bersisian dengan simpul tersebut. Sisi gelang (loop) dihitung berderajat dua. Simpul yang berderajat satu disebut anting-anting (pendant vertex). Dengan kata lain, anting-anting hanya bertetangga dengan sebuah simpul. Pada Graf berarah, derajat suatu simpul dibedakan menjadi dua macam untuk mencerminkan jumlah busur dengan simpul tersebut sebagai simpul asal dan jumlah busur dengan simpul tersebut sebagai simpul terminal. Sisi gelang pada Graf berarah menyumbangkan 1 untuk derajat masuk dan 1 untuk derajat keluar. 6. Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam Graf G adalah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2, …, vn – 1,en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), …, en = (vn – 1, vn) adalah sisi-sisi dari Graf G. Jika Graf yang ditinjau adalah Graf sederhana, maka cukup menuliskan lintasan sebagai barisan simpul-simpul saja : v0, v1, v2, …, vn – 1, vn, karena antara dua buah simpul berurutan di dalam lintasan tersebut hanya ada satu sisi. Pada Graf yang mengandung sisi ganda, harus ditulis lintasan sebagai barisan berselang-seling antara simpul dan sisi menghindari kerancuan sisi manan dari sisi-sisi ganda yang dilalui. Simpul dan sisi yang dilalui di dalam lintasan boleh berulang. Sebuah lintasan dikatakan lintasan sederhana (simple path) jika semua simpulnya berbeda (setiap sisi yang dilalui hanya satu kali). Lintasan yang berawal dan berakhir

19

pada simpul yang sama disebut lintasan tertutup (closed path), sedangkan lintasan yang tidak berawal dan berakhir pada simpul yang sama disebut lintasan terbuka (open path). Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. 7. Siklus (Cycle) atau Sirkuit (Circuit) Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus. Panjang sirkuit adalah jumlah sisi di dalam sirkuit tersebut. Sebuah sirkuit dikatakan sirkuit sederhana (simple circuit) jika setiap sisi yang dilalui berbeda. 8. Terhubung (Connected) Keterhubungan dua buah simpul adalah penting di dalam Graf. Dua buah simpul u dan simpul v dikatakan terhubung jika terdapat lintasan dari u ke v. Jika dua buah simpul terhubung maka pasti simpul yang pertama dapat dicapai dari simpul yang kedua. Dua simpul terminal pada jaringan komputer hanya dapat berkomuniksi bila keduanya terhubung. Jika setiap pasang simpul di dalam Graf terhubung, maka Graf tersebut dikatakan Graf terhubung. Secara formal, definisi Graf terhubung adalah sebagai berikut : “Graf tak berarah G disebut Graf terhubung (connected Graf) jika untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v (yang juga harus berarti ada lintasan dari u ke v). Jika tidak, maka G disebut Graf tak terhubung (disconnected Graf)”. Graf yang hanya terdiri atas satu simpul saja (tidak ada sisi) tetap dikatakan terhubung, karena simpul tunggalnya terhubung dengan dirinya sendiri. Pada Graf berarah, definisi Graf terhubung dirumuskan sebagai berikut :

20

“Graf berarah G dikatakan terhubung jika Graf tak berarahnya terhubung (Graf tak berarah dari G diperoleh dengan menghilangkan arahnya)”. Keterhubungan dua buah simpul pada Graf berarah dibedakan menjadi terhubung kuat dan terhubung lemah. Dua simpul, u dan v pada Graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v, dan juga sebaliknya lintasan berarah dari v ke u. Jika u dan v tidak terhubung kuat tetapi tetap terhubung pada Graf tak berarahnya, maka u dan v dikatakan terhubung lemah (weakly connected). Kedua hal tersebut (terhubung kuat dan terhubung lemah) melahirkan definisi Graf terhubung kuat berikut : “Graf berarah G disebut Graf terhubung kuat (strongly connected Graf) apabila untuk setiap pasang simpul sembarang vi dan vj di G terhubung kuat. Kalau tidak, G disebut Graf terhubung lemah. 9. SubGraf dan Komplemen SubGraf Misalkan G = (V, E) adalah sebuah Graf. G1 = (V1, E1) adalah SubGraf dari G jika V1 V dan E1 E. Komplemen dari SubGraf G1 terhadap G adalah Graf G2 = (V2, E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya. Jika Graf tidak terhubung, maka Graf tersebut terdiri atas beberapa komponen terhubung (connected component). Komponen terhubung adalah SubGraf terhubung dari Graf G yang tidak terdapat di dalam SubGraf terhubung dari G yang lebih besar. Ini berarti setiap komponen terhubung di dalam Graf G saling lepas (disjoint). Pada Graf berarah, komponen terhubung kuat adalah

21

SubGraf terhubung kuat dari Graf G yang tidak terdapat di dalam SubGraf terhubung kuat dari G yang lebih besar. 10. SubGraf Merentang (Spanning Subgraph) SubGraf G1 = (V1, E1) dari G = (V, E) dikatakan SubGraf merentang jika V1 = V yaitu G1 mengandung semua simpul dari G. 11. Cut-Set Cut-set dari Graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen terhubung. Nama lain untuk cut-set adalah jembatan (bridge). Jembatan adalah himpunan sisi yang apabila dibuang dari Graf menyebabkan Graf tersebut tidak terhubung dan menjadi dua buah komponen terhubung. Di dalam cut-set tidak boleh mengandung himpunan bagian yang juga cut-set, sehingga cut-set yang dimaksudkan adalah cut-set dasar (fundamental cut-set). 12. Graf Berbobot (Weighted Graph) Graf berbobot adalah Graf yang setiap sisinya diberi sebuah harga (bobot). Bobot pada tiap sisi dapat berbeda-beda tergantung pada masalah yang dimodelkan dengan Graf. Bobot dapat menyatakan jarak antara dua buah kota, biaya perjalanan antara dua buah kota, waktu tempuh pesan (message) dari sebuah simpul komunikasi ke simpul komunikasi lain, ongkos produksi dan sebagainya. Istilah lain yang sering dikaitkan dengan Graf berbobot adalah Graf berlabel. Namun Graf berlabel sesungguhnya lebih luas lagi definisinya. Label tidak hanya diberikan pada sisi, tetapi juga pada simpul. Sisi diberi label berupa bilangan tak negatif sedangkan simpul diberi label berupa data lain. (Munir, 2010: 364-376)

22

2.6

Representasi Graf Bila Graf akan diproses dengan program komputer, maka Graf harus

direpresentasikan di dalam memori. Terdapat beberapa representasi yang mungkin untuk Graf, yaitu: 1. Matriks Ketetanggaan (Adjacency Matrix) Matriks ketetanggaan adalah representasi Graf yang paling umum. Misalkan G = (V, E) adalah Graf dengan n simpul, n  1. Matriks ketetanggaan G adalah matriks dua dimensi yang berukuran n x n. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika simpul i dan j bertetangga, sebaliknya aij = 0, jika simpul i dan j tidak bertetangga. Karena matriks ketetanggaan hanya berisi 0 dan 1, maka matriks tersebut dinamakan juga matriks nol-satu (zero-one). Selain dengan angka 0 dan 1, elemen matriks dapat juga dinyatakan dengan nilai false (menyatakan 0) dan true (menyatakan 1). Matriks ketetanggaan didasarkan pada pengurutan nomor simpul. Matriks ketetanggaan untuk Graf sederhana dan tidak berarah selalu simetri, sedangkan untuk Graf berarah, matriks ketetanggaannya belum tentu simetri (akan simetri jika berupa Graf berarah lengkap). Selain itu, diagonal utamanya selalu nol karena tidak ada sisi gelang. Sayangnya, matriks ketetanggaan nol-satu tidak dapat digunakan untuk merepresentasikan Graf yang mempunyai sisi ganda (Graf ganda). Untuk menyiasatinya, maka elemen aij pada matriks ketetanggaan sama dengan jumlah sisi yang berasosiasi dengan (vi, vj). Matriks ketetanggaannya tentu bukan lagi matriks nol-satu. Untuk Graf semu, gelang pada simpul vi dinyatakan dengan nilai 1 pada posisi (i, i) di matriks ketetanggaannya.

23

Keuntungan representasi dengan matriks ketetanggaan adalah elemen matriksnya dapat diakses lalu melalui indeks. Selain itu, juga dapat menentukan dengan langsung apakah simpul i dan simpul j bertetangga. 2. Matriks Bersisian (Incidency Matrix) Bila matriks ketetanggaan menyatakan ketetanggaan simpul-simpul di dalam Graf, maka matriks bersisian menyatakan kebersisian simpul dengan sisi. Misalkan G = (V, E) adalah Graf dengan n simpul dan m buah sisi. Matriks bersisian G adalah matriks dua dimensi yang berukuran n x m. Baris menunjukkan label simpul, sedangkan kolom menunjukkan label sisinya. Bila matriks tersebut dinamakan A = [aij], maka aij = 1 jika simpul i bersisian dengan sisi j, sebaliknya aij = 0 jika simpul i tidak bersisian dengan sisi j. Matriks bersisian dapat digunakan untuk merepresentasikan Graf yang mengandung sisi ganda atau sisi gelang. 3. Senarai Ketetanggaan (Adjacency List) Kelemahan matriks ketetanggaan adalah bila Graf memiliki jumlah sisi relatif sedikit, karena matriksnya bersifat jarang (sparse), yaitu mengandung banyak elemen nol, sedangkan elemen yang bukan nol sedikit. Ditinjau dari implementasinya di dalam komputer, kebutuhan ruang memori untuk matriks jarang boros karena komputer menyimpan elemen 0 yang tidak perlu. Untuk mengatasi masalah ini, dapat menggunakan representasi yang ketiga yaitu senarai ketetanggaan. Senarai ketetanggaan mengenumerasi simpul-simpul yang bertetangga dengan setiap simpul di dalam Graf. (Munir, 2010: 381-385)

24

2.7

Jarak Euclidean Jarak Euclidean (euclidean distance), merupakan selisih nilai piksel antara

2 vektor tersebut. Jarak euclidean adalah akar dari jumlah selisih kuadrat antara 2 vektor, dan secara matematis dapat dirumuskan: dist (i, k ) 

 i D

i j

kj

2

j

dengan dist (i,k) adalah jarak euclidean antara vektor i dan vektor k ; ji adalah komponen ke j dari vektor i ; jk adalah komponen ke j dari vektor k ; D adalah jumlah komponen pada vektor i dan vektor k .

2.8

Lintasan dan Sirkuit Hamilton Lintasan Hamilton adalah lintasan yang melalui tiap simpul di dalam Graf

tepat satu kali. Bila lintasan itu kembali ke simpul asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Dengan kata lain, sirkuit Hamilton ialah sirkuit yang melalui tiap simpul di dalam Graf tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali. Nama sirkuit Hamilton muncul ketika Sir William Hamilton membuat permainan dodecahedron. Pada tahun 1859, Sir William Hamilton menawarkan mainan tekateki ke pabrik alat mainan Dublin. Mainan itu terdiri dari dodecahedron (yaitu benda yang disusun oleh 12 buah pentagonal dan di sini ada 20 buah titik sudut) dan tiap titik sudut diberi nama ibukota negara. Permainan yang dapat dilakukan adalah membentuk perjalanan keliling dunia, yang mengunjungi setiap ibukota

25

tepat satu kali dan kembali lagi ke kota asal. Persoalan ini dinamakan mencari sirkuit Hamilton. Penulis dapat menggambarkan alat itu dengan sebuah Graf : Verteks dari Graf melambangkan verteks dari alat tersebut dan panjangnya edges disamakan dengan alat tersebut. Untuk menentukan sebuah Graf itu adalah Siklus Hamilton atau tidak, pastinya lebih sulit daripada menentukan itu Eulerian. Dan tidak ada cara pasti yang diketahui untuk menentukan itu. Diberikan contoh dalam suatu Graf ada terdapat lima buah verteks. Di misalkan A, B, C, D, dan E. Dari siklus yang terjadi penulis dapat menentukan siklus itu Hamilton atau tidak. 1. Siklus 1: A – B – C – D – E 2. Siklus 2: A – B – C – B – D – E 3. Siklus 3: A – C – B – E – D 4. Siklus 4: A – B – E – C – B – D Dari empat siklus diatas dapat dilihat siklus 1 dan 3 adalah Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan hanya tepat satu kali. Tetapi pada siklus 2 dan 4 bukan Hamilton karena dari lima buah verteks yang ada, muncul nama dari semua verteks dan ada yang melebihi satu kali. Pada siklus 2 dan 4 muncul verteks B sebanyak dua kali. Dan itu melanggar sifat dari sebuah siklus Hamilton. Siklus Hamilton dapat ditemukan di banyak hal.

26

Gambar 2.8 Contoh Sirkuit Hamilton ( Sumber : http://kuliahmsi.blogspot.com/2010/07/lintasan-dan-sirkuithamilton.html ) Graf Di atas memiliki lintasan Hamilton dengan lintasan : b,c,d,e,f,g,a,b dan Graf di atas juga memiliki sirkuit Hamilton karena di awali di simpul b dan berakhir di simpul b

Graf disamping memiliki lintasan Hamilton dengan lintasan :a,b,c,d,e,i,f,g,h. Tapi Graf disamping tidak memiliki sirkuit Hamilton.

Gambar 2.9 Contoh Lintasan Hamilton ( Sumber : http://kuliahmsi.blogspot.com/2010/07/lintasan-dan-sirkuithamilton.html ) Perbedaan sirkuit Euler dengan Hamilton 1. Dalam sirkuit euler semua garis harus dilewati tepat satu kali,sedangkan semua titiknya boleh dikunjungi lebih dari satu kali. Sirkuit Hamilton : semua titik harus dikunjungi tepat satu kali dan tidak harus melalui semua garis nya. 2. Sirkuit Euler:dipentingkan adalah garis nya , Sirkuit Hamilton:dipentingkan kunjungan titiknya .

Teorema 1

27

Syarat cukup (jadi bukan syarat perlu) supaya Graf sederhana G dengan n 3 buah vertex adalah Graf hamilton ialah bila tiap vertex paling sedikit n/2 yaitu, d v) n/2 untuk setiap simpul v di G).

Contoh: (i) n = 3, dengan tiap vertex memiliki d(v) = 1,5 ≈2 (ii) n = 4, dengan tiap vertex memiliki d(v) = 2

Gambar 2.10 Contoh Graf Hamilton Teorema 1 ( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf )

Teorema 2 Setiap Graf lengkap adalah Graf hamilton. Ingat : Graf lengkap dengan n buah simpul dilabangkan dengan Kn. Jumlah sisi pada Graf lengkap yang terdiri dari n buah simpul adalah n(n-1)/ 2

Contoh:

Gambar 2.11 Contoh Graf Hamilton Teorema 2 ( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf )

28

Teorema 3 Di dalam Graf lengkap G dengan n buah vertex n

3), terdapat n-1 )! / 2 buah

sirkuit hamilton. Contoh :

Gambar 2.12 Contoh Graf Hamilton Teorema 3 ( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf )

(i) Graf lengkap n = 3, memiliki sirkuit hamilton 1 yaitu 1231 (ii) Graf lengkap n = 4, memiliki sirkuit hamilton 3 yaitu, ABCDA, BDCAB, dan CADBC Teorema 4 Di dalam Graf lengkap G dengan n buah simpul n

3 dan n ganjil),

terdapat (n-1) / 2 buah sirkuit hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika n genap dan n

4, maka di dalam G terdapat n-2 ) / 2 buah sirkuit Hamilton

yang saling lepas. Contoh : (persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub yang bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga

29

duduk berbeda setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan? Jumlah pengaturan tempat duduk yang berbeda adalah (9-1 ) / 2 = 4 Graf yang merepresentasikan :

Gambar 2.13 Contoh Graf Hamilton Teorema 4 ( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf ) Teorema 5 Misalkan G adalah Graf terhubung sederhana dengan n titik, dengan n v + deg w

3 dan deg

n. Untuk tiap-tiap pasangan titik yang tidak berdekatan v dan w,

maka G adalah Graf hamilton.

Contoh : Untuk Graf yang ditunjukkan pada gambar berikut deg v + deg w

5 untuk

masing-masing vertex yang tidak berdekatan v dan w. Jadi menurut teorema 5 Graf ini adalah Graf hamilton.

Gambar 2.14 Contoh Graf Hamilton Teorema 5

30

( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf )

Teorema 6 Misalkan G adalah Graf sederhana dengan n vertex. Jika jumlah dari derajat masing-masing vertex di G paling sedikit n – 1, maka ada lintasan hamilton di G.

Contoh :

Gambar 2.15 Contoh Graf Hamilton Teorema 6 ( Sumber : https://toshirominamoto.files.wordpress.com/2012/12/eulerian-Grafhamiltonian-Graf.pdf ) deg(a)+deg(b)+deg(c)+deg(d)+deg(e) = 1 + 2 + 2 + 2 + 1 = 8 jumlah derajat dari masing-masing vertex lebih dari n – 1 = 5 – 1 = 4

2.9

Lintasan dan Sirkuit Euler Definisi dari lintasan Euler adalah lintasan yang melalui masing-masing

sisi di dalam Graf tepat satu kali. Bila lintasan tersebut kembali ke simpul asal, membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Euler. Jadi, sirkuit Euler ialah sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang mempunyai sirkuit Euler disebut Graf Euler (Eulerian Graph). Graf yang mempunyai lintasan Euler dinamakan juga Graf semi-Euler (semiEulerian Graph).

31

Syarat yang harus dipenuhi oleh suatu Graf agar merupakan Graf Euler ternyata sangat sederhana. Euler menemukan syarat tersebut ketika memecahkan masalah jembatan Konigsberg. Teorema yang dikemukan Euler adalah: Suatu Graf terhubung tak berarah G adalah Graf Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul di dalam Graf tersebut berderajat genap. Jika lintasan yang dilalui tidak membentuk sirkuit, maka lintasan yang terbentuk adalah lintasan terbuka yang disebut lintasan Euler. Di sini, simpul awal tidak sama dengan simpul terakhir. Baik simpul awal maupun simpul akhir di dalam lintasan Euler berderajat ganjil. Karena itu, agar sebuah Graf mempunyai lintasan Euler (bukan sirkuit Euler), maka Graf tersebut harus memiliki tepat dua buah simpul berderajat ganjil. Graf yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya. Jika kita ingin membuat Graf yang mempunyai lintasan Euler (tanpa membentuk sirkuit), maka harus dipenuhi kondisi berikut: 1. Semua simpul dalam Graf tersebut harus terhubung. 2. Graf memiliki tepat dua buah simpul berderajat ganjil.

Memiliki lintasan euler : a,b,c,d,e,f,g,b,d,f,a,g Tetapi tidak ada sirkuit euler

Gambar 2.16 Contoh Lintasan Euler ( Sumber : http://kuliahmsi.blogspot.com/2010/07/lintasan-dan-sirkuit-euler.html )

32

Memiliki lintasan euler : a,b,c,d,e,c,h,b,f,h,e,f,g,a Dan memiliki sirkuit euler karena berawal dari simpul a dan berakhir di simpul a. Gambar 2.17 Contoh Sirkuit Euler

( Sumber : http://kuliahmsi.blogspot.com/2010/07/lintasan-dan-sirkuit-euler.html )

2.10

Microsoft Visual Basic.NET Visual Basic.NET adalah generasi selanjutnya dari Visual Basic. Visual

Basic.NET memungkinkan kita untuk membangun aplikasi database client atau server performa tinggi dan sangat cocok didampingkan dengan perangkat lunak Microsoft Access 2007. Pemilihan Visual Basic.NET sebagai

program

pengembang sistem ini adalah karena merupakan salah satu program aplikasi yang berada di bawah platform .NET framework.

Gambar 2.18 Contoh Tampilan New Project ( Sumber: Junindar, 2008: 3 )

33

Dalam dialog New Project terdapat beberapa jenis aplikasi yang akan dibuat termasuk bahasa pemrograman yang digunakan. Jenis aplikasi yang dapat dibuat adalah: 1. Windows Application, yaitu: aplikasi yang paling umum dibuat, menggunakan interface windows. Biasanya, Windows Application merupakan interface aplikasi, sedangkan logic aplikasi terdapat di dalam Class Library. Windows Application dapat berisi form, class, XML file, maupun file VB Script dan Jscript. 2. Class Library, yaitu: fondasi dasar untuk membuat komponen yang menjalankan fungsi tertentu. Class merupakan fondasi dasar untuk membentuk objek dalam pemrograman berorientasi objek. Class Library tidak memiliki interface tertentu seperti form, tetapi dapat diakses oleh aplikasi lain untuk menjalankan berbagai fungsi yang terdapat di dalamnya. Class Library dapat disamakan dengan teknologi ActiveX DLL (.dll) dan ActiveX EXE dalam pemrograman VB6. 3. Windows Control Library, yaitu: tool untuk membuat kontrol sendiri dan memasukkan berbagai fungsi yang diinginkan di dalam kontrol tersebut. Fasilitas untuk membuat kontrol tersebut adalah Windows Control Library. Kontrol ini sama dengan ActiveX Control (.ocx) dalam pemrograman VB6. 4. ASP.NET Web Application, yaitu: project yang digunakan untuk membuat aplikasi web. Teknologi yang digunakan adalah ASP.NET yang memiliki berbagai kelebihan dibandingkan ASP klasik. Perubahan utamanya adalah dapat diprogram menggunakan berbagai bahasa .NET seperti VB, C++, C#,

34

maupun J#. ASP.NET juga menyediakan berbagai kontrol yang bersifat event driven programming sehingga lebih menghemat waktu pembuatan aplikasi. 5. ASP.NET Web Service, dimana web service merupakan salah satu ide utama dalam .NET. Anda dapat membuat web service dan meletakkannya di web server untuk diakses berbagai aplikasi. Sebuah web service dapat diakses oleh aplikasi windows, web, console, maupun mobile device. Web service hampir sama dengan Class Library. Perbedaan utamanya adalah web service diletakkan di web server sehingga dapat diakses dengan lebih mudah dan tidak terbatas pada aplikasi berbasis windows saja. 6. Console Application, yaitu: aplikasi dengan tampilan text mode atau DOS (Disk Operating System). Aplikasi jenis ini biasa digunakan sebagai monitoring service atau remote application di mana sumber daya komputer dan bandwidth sangat terbatas. 7. Windows Service, yaitu: aplikasi yang berjalan sebagai di windows, yang diload bersamaan dengan proses start up windows. Aplikasi ini berjalan di background dan biasanya tidak memiliki interface. Penerapan aplikasi ini misalnya untuk pembuatan scanning antivirus, server FTP dan remote server. 8. Web Control Library, yaitu: hampir sama dengan Windows Control Library tapi digunakan untuk aplikasi web. (Junindar, 2008:3)

BAB III

METODE PENELITIAN

3.1.

Tempat dan Jadwal Penelitian Penelitian dimulai dari bulan Desember 2014 dan berakhir pada bulan

April 2015. Lokasi yang diambil penulis sebagai tempat penelitian adalah PT. Health Wealth International (HWI) yang beralamat di Jalan Irian Komplek Beringin Indah Blok IV No.42 Tanjung Morawa. Berikut ini dijabarkan jadwal penelitian yang dapat dilihat pada Tabel 3.1. Tabel 3.1 Jadwal Penelitian Waktu Kegiatan

Desember 2014 1

2

3

4

Januari 2015 1

2

3

Februari 2015 4

1

2

3

4

Maret 2015 1

2

3

April 2015 4

1

2

3

4

Identifikasi Masalah Pengumpulan Data Analisa Sistem Perancangan Sistem Pembangunan Sistem Uji Coba Sistem Penulisan Skripsi

3.2.

Kerangka Kerja Adapun tahapan dan langkah-langkah pengembangan perangkat lunak ini

dapat digambarkan dalam bentuk diagram alir seperti diperlihatkan pada Gambar 3.1.

36

37

Identifikasi Masalah

Pengumpulan Data

Analisa Sistem

Perancangan Sistem

Pembangunan Sistem

Uji Coba Sistem

Penulisan Skripsi

Gambar 3.1 Kerangka Kerja

3.2.1. Pengumpulan Data Di tahap pertama, penulis mengumpulkan data yang diperlukan dalam penyusunan skripsi. Data tersebut dikumpulkan dari buku dan sumber-sumber lainnya di internet. Gambar yang diperlukan dalam pembuatan perangkat lunak diambil dari

38

gambar themes Microsoft Power Point versi 2007 yang diubah warna latarnya dan juga beberapa gambar yang bersumber dari internet dan di-edit dengan menggunakan aplikasi Adobe Photoshop C.S versi 5.0. Selain itu, juga digunakan beberapa gambar yang diunduh dari internet.

3.2.2. Analisa Sistem Setelah dipelajari, penulis memilih dan menetapkan algoritma yang akan digunakan dalam menyelesaikan masalah TSP. Penulis juga melakukan analisa ulang terhadap data sebelumnya, untuk menyimpulkan lebih rinci masalah yang akan diselesaikan serta tujuan penelitian dari penulis.

3.2.3. Perancangan Sistem Dalam tahap desain pada siklus hidup pengembangan sistem, penganalisa sistem menggunakan informasi yang terkumpul sebelumnya untuk mencapai desain sistem yang diinginkan. Penganalisa menggunakan teknik flowchart dan perancangan layar tertentu untuk menjamin keefektifan input sistem. Perangkat lunak ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan menggunakan beberapa objek dasar seperti : 1. Label, yang digunakan untuk menampilkan keterangan. 2. ComboBox, yang digunakan untuk menyediakan pilihan node awal dan node akhir. 3. Button, yang digunakan sebagai tombol eksekusi. 4. PictureBox, yang digunakan untuk menampilkan graph hasil. 5. SaveFileDialog, yang digunakan untuk menampilkan dialog save.

39

6. OpenFileDialog, yang digunakan untuk menampilkan dialog open. 7. TextBox, yang digunakan untuk menampilkan hasil proses perhitungan.

3.2.4. Pembangunan Sistem Dalam tahap kelima pada siklus hidup pengembangan sistem, penganalisa mengembangkan suatu perangkat lunak awal yang diperlukan. Teknik terstruktur yang digunakan untuk merancang dan mendokumentasikan perangkat lunak adalah pseudocode. Penganalisa sistem menggunakan perangkat ini untuk memprogram apa yang perlu diprogram. Rancangan tampilan dari perangkat lunak ini dapat dirincikan sebagai berikut: 1. Form „Main. 2. Form „Barang‟. 3. Form „Customer‟. 4. Form „Kota‟. 5. Form „Salesman‟. 6. Form „Cari‟. 7. Form „Cetak‟. 8. Form „Filter‟. 9. Form „Penentuan Rute‟ 10. Form „Pemecahan TSP‟. 11. Form „Transaksi Penjualan‟.

40

3.2.5. Uji Coba Sistem Sebelum sistem dapat digunakan, maka harus dilakukan pengujian terlebih dulu, sehingga dapat menghemat biaya jika mengetahui adanya masalah sebelum sistem tersebut dijalankan. Sebagian besar pengujian dilakukan oleh pemrogram sendiri, selaku penganalisa sistem.

BAB IV

ANALISA DAN PERANCANGAN

3.3.

Analisa Sebelum merancang perangkat lunak, maka perlu dilakukan analisa

persyaratan terhadap perangkat lunak yang mencakup analisa dokumen keluaran, analisa dokumen masukan dan analisa proses kerja.

3.3.1. Analisa Dokumen Keluaran Dokumen keluaran yang terdapat pada sistem berjalan pada perusahaan, yaitu: 1. Laporan Penjualan. Berisi data pemesanan produk dan status pemenuhan dari setiap pemesanan pelanggan. Tampilan Laporan Penjualan dapat dilihat pada Gambar 4.1 berikut:

Gambar 4.1 Laporan Penjualan

41

42 Nama

: Laporan Penjualan.

Fungsi

: Menginformasikan rincian data pemesanan produk dan status pemenuhan dari setiap pemesanan pelanggan.

Media

: Kertas.

Distribusi

: Bagian Penjualan dan Staf Administrasi.

Frekwensi

: Setiap bulan secara periodik.

Volume

: Satu kali per bulan.

Hasil Analisa

: Laporan tidak mencantumkan total harga produk yang dipesan oleh pelanggan dan tidak terdapat laporan penjualan per produk.

3.3.2. Analisa Dokumen Masukan Masukan (input) yang terdapat pada sistem berjalan pada perusahaan, yaitu: 1. Formulir Data Pelanggan Data pelanggan akan diketik dan disimpan ke dalam suatu file Microsoft Excel. Data ini akan digunakan pada saat pelanggan melakukan pemesanan produk dan pada transaksi penjualan produk. Adapun rincian dari data pelanggan dapat dilihat pada gambar 4.2 berikut: FORMULIR DATA PELANGGAN Kode

Nama

Alamat

Kota

Contact Person

Gambar 4.2 Formulir Data Pelanggan

No. Telp

No. HP

43 Nama

: Formulir Data Pelanggan.

Fungsi

: Menginformasikan rincian data pelanggan.

Media

: Kertas.

Distribusi

: Salesman.

Frekwensi

: Setiap terjadi penambahan pelanggan baru.

Volume

: Satu kali per penambahan pelanggan.

Hasil Analisa

: Data rincian telah cukup lengkap, karena telah mencakup semua informasi yang diperlukan.

2. Formulir Data Salesman Data sales akan diketik dan disimpan ke dalam suatu file Microsoft Excel. Data ini akan digunakan pada saat terjadi pemesanan produk dari pelanggan melalui sales. Adapun rincian dari data sales dapat dilihat pada gambar 4.3 berikut: FORMULIR DATA SALESMAN Kode

Nama

Alamat

Kota

Gambar 4.3 Formulir Data Salesman Nama

: Formulir Data Salesman.

Fungsi

: Menginformasikan rincian data sales.

Media

: Kertas.

Distribusi

: Administrasi.

Frekwensi

: Setiap terjadi penambahan sales baru.

Volume

: Satu kali per penambahan sales.

No. Telp

No. HP

44 Hasil Analisa

: Data rincian telah cukup lengkap, karena telah mencakup semua informasi yang diperlukan.

3. Formulir Data Produk Data ini merupakan kumpulan produk yang dijual oleh perusahaan. Adapun format rincian data produk dapat dilihat pada gambar 4.4 berikut: FORMULIR DATA PRODUK

Kode Produk

Nama Produk

Harga

Gambar 4.4 Formulir Data Produk Nama

: Formulir Data Produk.

Fungsi

: Menginformasikan rincian data produk yang dijual oleh perusahaan.

Media

: Kertas.

Distribusi

: Sales.

Frekwensi

: Setiap terjadi penambahan produk baru.

Volume

: Satu kali per penambahan produk.

Hasil Analisa

: Data rincian telah cukup lengkap, karena telah mencakup semua informasi yang diperlukan.

45 4.1.3. Analisa Data Berdasarkan analisa proses, masukan dan keluaran di atas, maka penulis memperoleh data berikut: 1. Nama Data Store

: Sales

Deskripsi

: Kumpulan data rincian sales.

Kaitan dengan data masukan

: Merupakan data rincian mengenai sales.

Kaitan dengan data keluaran

: Digunakan sebagai data dalam perhitungan insentif sales.

2. Nama Data Store Deskripsi

: Produk : Kumpulan data produk yang dijual oleh perusahaan.

Kaitan dengan data masukan

: Merupakan data rincian produk yang akan dijual kepada pelanggan.

Kaitan dengan data keluaran

: Digunakan sebagai data dalam pembuatan laporan stock dan laporan penjualan.

3. Nama Data Store

: Pelanggan

Deskripsi

: Kumpulan data rincian pelanggan.

Kaitan dengan data masukan

: Merupakan data rincian mengenai pelanggan.

Kaitan dengan data keluaran

: Digunakan sebagai data dalam pembuatan laporan penjualan.

46

4. Nama Data Store Deskripsi

: Penjualan : Kumpulan data penjualan produk kepada pelanggan.

Kaitan dengan data masukan

: Merupakan data pemesanan produk dari pelanggan.

Kaitan dengan data keluaran

: Digunakan sebagai data dalam pembuatan laporan stock dan surat tagihan.

4.1.4 Analisa Cara Kerja Proses pencarian sirkuit Hamilton dapat dicari dengan menggunakan metode Breadth First Search (BFS) dan Depth First Search (DFS). 1. Metode Breadth First Search Proses kerja dari sistem akan dimulai dari penentuan data nama dan posisi node ( keadaan ). Proses ini akan dilakukan secara acak oleh komputer. Pencarian dengan metode BFS atau disebut juga pencarian melebar pertama dimulai dari node akar (keadaan awal) terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya. Demikian seterusnya hingga ditemukannya solusi. Setiap node dalam pohon pencarian adalah berupa simpul yang sedang ditempati pada keadaan itu dan sisi-sisi yang telah ditelusuri sebelumnya. Agar lebih jelas, perhatikan gambar 4.5 berikut ini.

47

Simpul „A‟

Simpul „B‟

Simpul „C‟

Pergerakan awal dimulai dari simpul „D‟

Simpul „E‟

Gambar 4.5 Contoh Lintasan yang akan dicari solusinya Sesuai dengan gambar 4.5, maka hubungan antar simpul yang terdapat dalam lintasan tersebut adalah (A – B), (A – C), (B – C), (B – D), (B – E), (C – E), (C – D) dan (D – E). Prosedur pencarian BFS akan dimulai dari simpul ‟D‟ sebagai node akar atau keadaan awal. Kemudian, dari node akar dikembangkan semua node anak yang menghubungkan simpul ‟D‟ dengan simpul yang lain. Dalam hal ini adalah hubungan (B – D), (C – D) dan (D – E), sehingga node anak pada level-2 menempati simpul B, C dan E. Demikian seterusnya, hingga semua sisi dalam graf dilewati. Pencarian tidak akan melewati sisi yang telah dilewati sebelumnya. Prosedur pencarian BFS dapat dilihat pada gambar 4.6 berikut.

48 Level-1

Level-2

Level-3

Simpul = „B‟ Sisi yang dilewati = „D-B‟

Simpul = „A‟ Sisi yang dilewati = „D-C-A‟

Simpul = „D‟ Sisi yang dilewati = „D‟

Simpul = „C‟ Sisi yang dilewati = „D-C‟

Simpul = „E‟ Sisi yang dilewati = „D-E‟

Simpul = „B‟ Sisi yang dilewati = „D-C-B‟

Simpul = „E‟ Sisi yang dilewati = „D-C-E‟

Gambar 4.6 Prosedur Pencarian BFS Pencarian akan terus berlanjut hingga ditemukan suatu keadaan yang telah melewati semua sisi dalam graf.

2. Metode Depth First Search Pencarian dengan metode DFS atau disebut juga pencarian mendalam pertama dimulai dari node akar. Pada metode ini, proses pencarian akan dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Dari node akar (level-1), dikembangkan satu node anak (level-2), kemudian dari node baru pada level-2 dikembangkan lagi node anak pada level berikutnya (level-3). Demikian seterusnya hingga ditemukannya solusi. Jika tidak ada langkah yang dapat ditempuh pada node yang sedang diperiksa, maka pencarian akan kembali ke node induk untuk dikembangkan lagi node anak lainnya. Setiap node dalam pohon pencarian adalah berupa simpul yang sedang ditempati pada keadaan itu dan sisi-sisi yang telah ditelusuri sebelumnya. Agar lebih jelas, prosedur pencarian DFS untuk menyelesaikan graf dapat dilihat pada gambar 4.7 berikut.

49 Level-1

Level-2

Level-3

Level-4

Simpul = „D‟ Sisi yang dilewati = „D‟

Simpul = „B‟ Sisi yang dilewati = „D-B‟

Simpul = „A‟ Sisi yang dilewati = „D-B-A‟

Simpul = „C‟ Sisi yang dilewati = „D-B-A-C‟ dan seterusnya

Gambar 4.7 Prosedur Pencarian DFS Tidak seperti pencarian BFS, pencarian DFS tidak akan mengembangkan semua node anak yang mungkin dari suatu node. Pencarian DFS hanya akan mengembangkan satu node anak dan pencarian berlanjut ke node anak yang baru terbentuk. Sesuai gambar 4.6, prosedur pencarian DFS akan dimulai dari simpul ‟D‟ sebagai node akar atau keadaan awal. Kemudian, dari node akar dikembangkan satu node anak yang menghubungkan simpul ‟D‟ dengan simpul ‟B‟, kemudian dari node baru tersebut dikembangkan lagi node anak yang menghubungkan simpul ‟B‟ dengan simpul ‟A‟. Demikian seterusnya, hingga semua sisi dalam graf dilewati. Bila tidak ada sisi yang dapat dilewati lagi dan solusi belum ditemukan, maka pencarian mundur satu langkah ke node induk. Pencarian tidak akan melewati sisi yang telah dilewati sebelumnya. Pada skripsi ini, akan digunakan metode BFS untuk melakukan pencarian sirkuit Hamilton dari sebuah graph. Hal ini dikarenakan proses pencarian dengan menggunakan metode DFS akan memerlukan waktu yang lebih lama jika

50 dibandingkan dengan metode BFS. Berikut dijabarkan algoritma yang digunakan untuk mencari sirkuit Hamilton dengan metode BFS: Algoritma BFS ini digunakan untuk mencari solusi atau penyelesaian dari sirkuit atau lintasan dengan metode BFS. Metode BFS akan memeriksa dan mengembangkan setiap node pada setiap level. Pencarian dimulai dari node akar (keadaan(1)), kembangkan anak dari node tersebut, ke level berikutnya, periksa dan kembangkan node anak dari kiri ke kanan, ke level berikutnya, dari kiri ke kanan dan seterusnya hingga ditemukan solusi. Solusi dalam permasalahan ini adalah suatu keadaan dimana setiap sisi di dalam graf telah dilewati satu kali. Algoritma pencarian BFS adalah sebagai berikut 1. Set N =1, IndeksGoal = 0 dan Selesai = False. 2. Selama Selesai = False dan bStop = False, lakukan prosedur di bawah ini: a. Untuk i = 1 sampai jumlah array dari variabel „Hubungan‟, i. A = Split(Hubungan(i), “,”). ii. Jika Keadaan(N).Titik = A(0) maka periksa jika sisi belum pernah ditelusuri (InStr(1, Keadaan(n).Sisi, "," & Keadaan(n).Titik & "," & A(1) & ",") = 0 dan InStr(1, Keadaan(n).Sisi, "," & A(1) & "," & Keadaan(n).Titik & ",") = 0), maka: 1). Set j = UBound(Keadaan) + 1. 2). ReDim Preserve Keadaan(j). 3). Set Keadaan(i).Titik = A(1), .Sisi = Keadaan(n).Sisi & A(1) & ",", .Induk = n, .Level = Keadaan(n).Level + 1 dan ReDim .Anak(0). 4). k = UBound(Keadaan(n).Anak) + 1.

51 5). ReDim Preserve Keadaan(n).Anak(k). 6). Keadaan(n).Anak(k) = j. 7). Periksa

apakah

telah

mencapai

goal

State.

Set

S

=

Split(Keadaan(j).Sisi, ","). Periksa jika UBound(S) - 2 = UBound(Hubungan) maka set Selesai = True, IndeksGoal = j dan keluar dari perulangan. iii. Jika Keadaan(N).Titik = A(1) maka periksa jika sisi belum pernah ditelusuri (InStr(1, Keadaan(n).Sisi, "," & Keadaan(n).Titik & "," & A(0) & ",") = 0 dan InStr(1, Keadaan(n).Sisi, "," & A(0) & "," & Keadaan(n).Titik & ",") = 0), maka: 1). Set j = UBound(Keadaan) + 1. 2). ReDim Preserve Keadaan(j). 3). Set Keadaan(i).Titik = A(0), .Sisi = Keadaan(n).Sisi & A(0) & ",", .Induk = n, .Level = Keadaan(n).Level + 1 dan ReDim .Anak(0). 4). k = UBound(Keadaan(n).Anak) + 1. 5). ReDim Preserve Keadaan(n).Anak(k). 6). Keadaan(n).Anak(k) = j. 7). Periksa

apakah

telah

mencapai

goal

State.

Set

S

=

Split(Keadaan(j).Sisi, ","). Periksa jika UBound(S) - 2 = UBound(Hubungan) maka set Selesai = True, IndeksGoal = j dan keluar dari perulangan. b. Periksa dan kembangkan keadaan berikutnya, set N = N +1. 3. Jika bStop = False (user tidak menekan tombol „Stop‟), maka:

52 a. ReDim Temp(0). b. Set j = IndeksGoal. c. Telusuri dari node solusi ke node akar. Selamat Keadaan(j).Induk > = 0, maka set i = UBound(temp) + 1, ReDim Preserve Temp(i), temp(i) = j dan j = Keadaan(j).Induk. d. Redim Solusi(UBound(temp)). e. Untuk i = UBound(temp) sampai 1, step -1 maka set Solusi(i) = temp(UBound(temp) - i + 1). f. Munculkan pesan “Solusi berhasil ditemukan !” 4. Jika bStop = True (user menekan tombol „Stop‟), maka munculkan pesan “Pencarian dihentikan !”.

3.4.

Perancangan Perancangan sistem usulan yang dilakukan mencakup data flow diagram

(DFD), kamus data, rancangan input dan output serta rancangan basis data.

3.4.1. Data Flow Diagram (DFD) Berdasarkan analisa sistem berjalan yang dilakukan maka dapat digambarkan diagram konteks dari sistem usulan seperti terlihat pada gambar 4.8:

53 0

Data Penjualan

SALESMAN

Informasi Rute Perjalanan

Data Pelanggan

Aplikasi Penentuan Rute Perjalanan Salesman dengan Sirkuit Hamilton pada PT.Health Wealth International

Data Salesman

Data Pemesanan Produk

PELANGGAN

Informasi Produk Laporan Pelanggan Data Daerah

STAF ADMINISTRASI

Laporan Penjualan Laporan Produk Laporan Salesman

Gambar 4.8 Diagram Konteks Logika dari Sistem Usulan Dari diagram konteks pada gambar 4.6 diatas, terlihat bahwa dalam sistem informasi penjualan pada perusahaan terdapat tiga buah entitas yaitu sales, pelanggan dan manajer operasional. Dari diagram konteks tersebut, dapat dirincikan lebih lanjut proses-proses yang terlibat dalam sistem seperti terlihat pada DFD Level 0 pada gambar 4.9 berikut ini:

Salesman

Pelanggan

Record Salesman Data Penjualan

SALESMAN

Informasi Rute Perjalanan Data Salesman

Record Pelanggan

2.0

Record Penjualan

1.0 Penjualan

PENENTUAN RUTE PERJALANAN SALESMAN

Record Penjualan

PENCATATAN PENJUALAN

Record Penjualan Record Penjualan

Record Produk

Produk 3.0

Data Pelanggan Data Pemesanan Produk Informasi Produk

Record Produk

Record Produk Record Pelanggan

Record Salesman

PEMBUATAN LAPORAN Laporan Pelanggan

Laporan Salesman

Laporan Penjualan

STAF ADMINISTRASI

Laporan Produk Data Kota

Gambar 4.9 DFD Logika Level 0 dari Sistem Usulan

PELANGGAN

54 Dari gambar 4.9 di atas, terlihat bahwa terdapat tiga proses yang terdapat dalam DFD level 0 sistem informasi operasional pada perusahaan yang sedang berjalan, yaitu Penjualan, Pengaturan Rute Perjalanan Sales dan Pembuatan Laporan. Agar dapat memperoleh informasi mengenai semua proses transaksi yang terjadi, maka data transaksi tersebut akan diolah dan dibuat menjadi bentuk laporan.

3.4.2. Kamus Data Dari analisa sistem berjalan yang telah dilakukan, dapat disimpulkan bahwa dibutuhkan suatu database untuk menyimpan data pada sistem pembelian, penjualan dan persediaan perusahaan. Berikut adalah kamus data yang diperlukan. 1.

Data Produk

= KodeProduk + NamaProduk + Jenis + (Keterangan)

2.

Data Sales

= KodeSales + NamaSales + Alamat + Kota + NoTelp + NoHP + (Keterangan)

3.

Data Pelanggan

= KodeCust + NamaCust + Alamat + Kota + ContactP + NoTelp + NoHP + (Keterangan)

4.

Data Penjualan

= NoFaktur + TglFaktur + KodeCust + KodeSales + (Keterangan) + {Item Data Produk Jual}

5.

Item Data Produk Jual = KodeStock + NamaStock + Qty + Harga

55 3.4.3. Rancangan Output Rancangan output dari sistem informasi dapat dirincikan sebagai berikut: 1.

Daftar Customer. Rancangan daftar customer akan menampilkan data Pelanggan yang melakukan transaksi penjualan dengan perusahaan. Rancangan daftar Pelanggan ini dapat dilihat pada gambar 4.10:

Gambar 4.10 Rancangan Daftar Customer Nama Keluaran

: Daftar Customer

Fungsi

: Menampilkan daftar rincian pelanggan

Media

: Kertas

Distribusi

: Kabag Penjualan

Frekwensi

: Setiap terjadi penambahan pelanggan baru

Volume

: Satu kali per transaksi penambahan pelanggan baru

Keterangan

:

a. Daftar customer diurutkan berdasarkan kode cust. b. Data dari laporan diambil dari tabel “Cust” c. Laporan ini dapat ditampilkan dengan cara mengklik tombol “Laporan” pada form Main lalu pilih “Daftar Customer”.

56 2.

Daftar Salesman. Rancangan daftar sales akan menampilkan data sales yang melakukan transaksi penjualan dengan perusahaan. Rancangan Daftar Sales ini dapat dilihat pada gambar 4.11:

Gambar 4.11 Rancangan Daftar Salesman Nama Keluaran

: Daftar Salesman

Fungsi

: Menampilkan daftar rincian sales

Media

: Kertas

Distribusi

: Kabag Penjualan

Frekwensi

: Setiap terjadi penambahan sales baru

Volume

: Satu kali per transaksi penambahan sales baru

Keterangan

:

a. Daftar salesman diurutkan berdasarkan kode sales. b. Data dari laporan diambil dari tabel “Sales”. c. Laporan ini dapat ditampilkan dengan cara mengklik tombol “Laporan” pada form Main lalu pilih “Daftar Salesman”.

57 3.

Daftar Barang. Rancangan daftar produk akan menampilkan data barang yang ditawarkan oleh perusahaan. Rancangan daftar produk ini dapat dilihat pada gambar 4.12:

Gambar 4.12 Rancangan Daftar Barang Nama Keluaran

: Daftar Barang

Fungsi

: Menampilkan daftar rincian barang

Media

: Kertas

Distribusi

: Sales

Rangkap

: Satu

Frekwensi

: Setiap terjadi penambahan tipe barang baru

Volume

: Satu kali per transaksi penambahan tipe barang baru

Keterangan

:

a. Daftar produk diurutkan berdasarkan kode barang. b. Data dari laporan diambil dari tabel “Barang”. c. Laporan ini dapat ditampilkan dengan cara mengklik tombol “Laporan” pada form Main lalu pilih “Daftar Barang”.

58 4.

Laporan Penjualan Rancangan laporan penjualan per tanggal akan menampilkan data rincian penjualan barang kepada Pelanggan dengan pengelompokan berdasarkan tanggal transaksi. Rancangan laporan penjualan ini dapat dilihat pada gambar 4.13:

Gambar 4.13 Rancangan Laporan Penjualan Nama Keluaran

: Laporan Penjualan

Fungsi

: Menampilkan laporan penjualan produk kepada customer

Media

: Kertas

Distribusi

: Staf Administrasi

Frekwensi

: Setiap akhir bulan

Volume

: Satu kali per bulan

59 Keterangan

:

a. Daftar barang dikelompokkan berdasarkan kode customer dan diurutkan berdasarkan tanggal transaksi. b. Data dari laporan diambil dari tabel “Penjualan”, “Detail Penjualan”, “Customer “dan “Barang”. c. Laporan ini dapat ditampilkan dengan cara mengakses menu ”Laporan” >> ”Penjualan”.

3.4.4. Rancangan Input Perangkat lunak untuk memecahkan TSP dengan sirkuit Hamilton ini dirancang dengan menggunakan bahasa pemrograman Microsoft Visual Basic 2010 dengan menggunakan beberapa objek dasar seperti : 8. Label, yang digunakan untuk menampilkan keterangan. 9. ComboBox, yang digunakan untuk menyediakan pilihan node awal dan node akhir. 10. Button, yang digunakan sebagai tombol eksekusi. 11. PictureBox, yang digunakan untuk menampilkan graph hasil. 12. SaveFileDialog, yang digunakan untuk menampilkan dialog save. 13. OpenFileDialog, yang digunakan untuk menampilkan dialog open. 14. TextBox, yang digunakan untuk menampilkan hasil proses perhitungan. Rancangan tampilan dari perangkat lunak untuk memecahkan TSP dengan sirkuit Hamilton ini dapat dirincikan sebagai berikut:

60 1. Rancangan Form “Master Barang” Rancangan form ini dibuat untuk melakukan penambahan atau penghapusan atas data yang berhubungan dengan barang. Rancangan form “Master Barang” dapat dilihat pada Gambar 4.14.

Master Barang Nama Barang

Kode Barang Keterangan Satuan Harga Jual

Gambar 4.14 Rancangan Form “Master Barang” Nama Masukan

: Form “Master Barang”

Fungsi

: Melakukan proses penyimpanan, pengubahan dan penghapusan data barang

Keterangan

:

a. Kode barang merupakan primary key dalam tabel “Barang”, yang berarti bahwa kode barang bersifat unik dan tidak boleh ada data yang sama. b. Data input disimpan dalam tabel “Barang”. c. Data Barang tidak dapat diedit dan dihapus apabila data barang tersebut telah digunakan pada transaksi penjualan.

61 2. Rancangan Form “Master Kota” Rancangan form ini dibuat untuk melakukan penambahan atau penghapusan atas data yang berhubungan dengan kota sebagai tempat domisili dari customer. Rancangan form ”Master Kota” dapat dilihat pada Gambar 4.15. Master Kota Kota x

y ,

Posisi

Daerah penentuan lokasi kota

Simpan

Hapus

Daftar kota

Keluar

Gambar 4.15. Rancangan Form “Master Kota” Nama Masukan

: Form “Master Kota”

Fungsi

: Melakukan proses penyimpanan, pengubahan dan penghapusan data kota

Keterangan

:

a. Kode Kota merupakan primary key dalam tabel “Kota”, yang berarti bahwa kode Kota bersifat unik dan tidak boleh ada data yang sama. b. Data input disimpan dalam tabel “Kota”.

62 3. Rancangan Form “Master Customer” Rancangan form ini dibuat untuk melakukan penambahan atau penghapusan atas data yang berhubungan dengan customer. Rancangan form “Master Customer” dapat dilihat pada Gambar 4.16.

Master Customer Nama Customer

Kode Customer Contact Person Alamat Kota

Kode Pos

Keterangan Telp

Fax

Gambar 4.16 Rancangan Form “Master Customer” Nama Masukan

: Form “Master Customer”

Fungsi

: Melakukan proses penyimpanan, pengubahan dan penghapusan data customer

Keterangan

:

a. Kode customer merupakan primary key dalam tabel “Customer”, yang berarti bahwa kode customer bersifat unik dan tidak boleh ada data yang sama. b. Data input disimpan dalam tabel “Customer”. c. Data Customer tidak dapat diedit dan dihapus apabila data customer tersebut telah digunakan pada transaksi penjualan.

63 4. Rancangan Form “Master Salesman” Rancangan form ini dibuat untuk melakukan penambahan atau penghapusan atas data yang berhubungan dengan Sales. Rancangan form “Master Salesman” dapat dilihat pada Gambar 4.17.

Master Salesman Nama Salesman

Kode Salesman Alamat Kota

Kode Pos

Keterangan Telp

Gambar 4.17 Rancangan Form “Master Salesman” Nama Masukan

: Form “Master Salesman”

Fungsi

: Melakukan proses penyimpanan, pengubahan dan penghapusan data Sales

Keterangan

:

a. Kode Sales merupakan primary key dalam tabel “Sales”, yang berarti bahwa kode Sales bersifat unik dan tidak boleh ada data yang sama. b. Data input disimpan dalam tabel “Sales”. c. Data Sales tidak dapat diedit dan dihapus apabila data Sales tersebut telah digunakan pada transaksi penjualan.

64 5. Rancangan Form “Transaksi Penjualan” Rancangan form ini dibuat untuk melakukan penambahan atau penghapusan atas data yang berhubungan dengan transaksi penjualan. Rancangan form “Transaksi Penjualan” dapat dilihat pada Gambar 4.18. Transaksi Penjualan Tgl Faktur

No. Faktur

Terms

Customer

Keterangan

Sales

Kode Barang

Nama Barang

Qty

Harga (Rp.)

Sub Total (Rp.)

Total Harga Disc Netto

Gambar 4.18. Rancangan Form “Transaksi Penjualan” Nama Masukan

: Form “Transaksi Penjualan”

Fungsi

: Melakukan proses penyimpanan, pengubahan dan penghapusan data penjualan

Keterangan

:

a. Nomor faktur merupakan primary key dalam tabel “FakturJual”, yang berarti bahwa nomor faktur bersifat unik dan tidak boleh ada data yang sama.

6. Rancangan Form “Penentuan Rute Perjalanan Salesman” Rancangan form ini dibuat untuk melakukan pengaturan terhadap rute perjalanan sales berdasarkan data transaksi penjualan untuk hari yang

65 bersangkutan. Rancangan form “Penentuan Rute Perjalanan Salesman” dapat dilihat pada Gambar 4.19.

sampai

Periode Kode Salesman Nama Salesman Kota

Tabel Customer

Proses

Keluar

Gambar 4.19. Rancangan Form “Penentuan Rute Perjalanan Salesman” Nama Masukan

: Form “Penentuan Rute Perjalanan Salesman”

Fungsi

: Melakukan proses pengaturan rute perjalanan sales berdasarkan data penjualan pada hari yang bersangkutan

Keterangan

:

a. Data penjualan akan diambil dari tabel “Penjualan”. b. Data customer akan diambil dari tabel “Customer”. c. Data sales akan diambil dari tabel “Sales”. d. Untuk satu hari, seorang sales maksimal dapat mengunjungi delapan kota sekaligus.

3.4.5. Rancangan Basis Data Desain database dimaksudkan untuk mendefinisikan isi atau struktur tabel. Adapun entitas yang digunakan adalah sebagai berikut.

66 Nama Tabel

: Barang

Primary Key : KodeBarang Struktur Tabel : Berisi data rincian barang yang dijual oleh perusahaan. Rincian tabel barang dapat dilihat pada tabel 4.1: Tabel 4.1 Tabel Barang Nama Field

Tipe Data

Ukuran

KodeBarang

Varchar

20

Kode barang

NamaBarang

Varchar

50

Nama barang

Satuan

Varchar

20

Satuan barang

HJual

Float

-

Varchar

50

Keterangan

Nama Tabel

Keterangan

Harga jual barang Keterangan mengenai barang

: Kota

Primary Key : KodeKota Struktur Tabel : Berisi data rincian kota sebagai tempat domisili dari customer dan sales. Rincian tabel kota dapat dilihat pada tabel 4.2: Tabel 4.2 Tabel Kota Nama Field

Tipe Data

Ukuran

KodeKota

Varchar

20

Kode kota

NamaKota

Varchar

50

Nama kota

Posisi

Varchar

20

Posisi kota

Keterangan

Varchar

50

Keterangan mengenai kota

Nama Tabel

Keterangan

: Customer

Primary Key : KodeCust Struktur Tabel : Berisi data rincian customer perusahaan. Rincian tabel customer dapat dilihat pada tabel 4.3:

67 Tabel 4.3 Tabel Customer Nama Field

Tipe Data Ukuran

Keterangan

KodeCust

Varchar

20

Kode pelanggan

NamaCust

Varchar

50

Nama pelanggan

Alamat

Varchar

50

Alamat pelanggan

Kota

Varchar

20

Kota

KodePos

Varchar

5

Kode pos

ContactP

Varchar

30

Orang yang bisa dihubungi

NoTelp

Varchar

20

Nomor telepon yang bisa dihubungi

Fax

Varchar

20

Nomor fax pelanggan

Keterangan

Varchar

50

Keterangan mengenai pelanggan

Nama Tabel

: Sales

Primary Key : KodeSales Struktur Tabel : Berisi data rincian sales perusahaan. Rincian tabel sales dapat dilihat pada tabel 4.4: Tabel 4.4 Tabel Sales Nama Field

Tipe Data Ukuran

Keterangan

KodeSales

Varchar

20

Kode sales

NamaSales

Varchar

50

Nama sales

Alamat

Varchar

50

Alamat sales

Kota

Varchar

20

Kota

KodePos

Varchar

5

Kode pos

NoTelp

Varchar

20

Nomor telepon yang bisa dihubungi

Keterangan

Varchar

50

Keterangan mengenai sales

Nama Tabel

: Penjualan

Primary Key : NoBukti

68 Struktur Tabel : Berisi data rincian penjualan produk kepada pelanggan. Rincian tabel penjualan dapat dilihat pada tabel 4.5: Tabel 4.5 Tabel Penjualan Nama Field

Tipe Data

Ukuran

NoBukti

Varchar

20

Nomor faktur penjualan

TglFaktur

SmallDateTime

Short Date

Tanggal faktur penjualan

KodeCust

Varchar

20

Kode customer

KodeSales

Varchar

20

Kode sales

Keterangan

Varchar

50

Keterangan atas penjualan

Nama Tabel

Keterangan

: Detail Penjualan

Primary Key : NoBukti Foreign Key : KodeBarang Struktur Tabel : Berisi data rincian penjualan barang kepada pelanggan. Rincian tabel detail penjualan dapat dilihat pada tabel 4.6: Tabel 4.6 Tabel Detail Penjualan Nama Field

Tipe Data

Ukuran

NoBukti

Varchar

20

Nomor faktur penjualan

KodeBarang

Varchar

20

Kode barang yang dijual

Qty

Integer

-

Kuantitas

Float

-

Harga penjualan barang

Harga

Keterangan

Rancangan relasi antar tabel dari sistem yang dibuat dapat dilihat pada gambar berikut:

69

Gambar 4.20 Rancangan Relasi Antar Tabel

3.4.6. Rancangan Site Map Perangkat lunak menggunakan komponen “Menu Strip” untuk merancang menu utama yang terdapat pada form “Main”. Menu ini digunakan sebagai penghubung (link) ke form lainnya yang terdapat pada perangkat lunak. Rancangan menu utama ini dapat dilihat pada gambar 4.21 berikut: Menu Utama

Data

Proses

Laporan

Barang

Penjualan

Daftar Barang

Kota

Penentuan Rute Perjalanan

Daftar Customer

Customer

Daftar Salesman

Salesman

Laporan Penjualan

Keluar

Per Tanggal Per Barang Per Customer

Gambar 4.21 Rancangan Menu Utama

BAB V HASIL DAN PEMBAHASAN

5.1. Tampilan Hasil Untuk menjalankan perangkat lunak sistem informasi aplikasi penentuan rute perjalanan salesman dengan sirkuit Hamilton, maka pemakai dapat mengklik file „Rute_Perjalanan.exe‟ yang terdapat pada folder bin >> debug, sehingga sistem akan menampilkan form berikut.

Gambar 5.1 Tampilan Form Main Pada form Main terdapat beberapa menu yang dapat diakses oleh pemakai, yaitu menu Master, Transaksi, Laporan dan Keluar. Proses pengaksesan dari setiap menu dapat dilihat pada perincian berikut ini. 1. Tampilan Menu Master Dari menu Master, terdapat pilihan menu Barang, Kota, Customer, Salesman yang dapat dilihat pada gambar 5.2:

70

71

Gambar 5.2 Tampilan Menu Master Sub menu Barang berfungsi untuk menampilkan form Barang, sub menu Kota berfungsi untuk menampilkan form Kota, sub menu Customer berfungsi untuk menampilkan form Customer dan sub menu Salesman berfungsi untuk menampilkan form Salesman. 2. Tampilan Menu Transaksi Dari menu Transaksi, terdapat pilihan menu Penjualan dan Penentuan Rute Perjalanan yang dapat dilihat pada gambar 5.3:

Gambar 5.3 Tampilan Menu Transaksi

72

3. Tampilan Menu Laporan Dari menu Laporan, terdapat pilihan menu Daftar Barang, Daftar Customer, Daftar Salesman dan Penjualan (Per Tanggal, Per Barang dan Per Customer). Di dalam menu Penjualan terdapat menu Penjualan Per Tanggal, Per Barang, Per Customer (Gambar 5.5) yang dapat dilihat pada gambar berikut:

Gambar 5.4 Tampilan Menu Laporan

Gambar 5.5 Tampilan Menu Laporan Bagian Penjualan

73

4. Tampilan Master Barang Master Barang, yang berfungsi sebagai tempat pengisian, pengubahan dan penghapusan data barang, seperti terlihat pada gambar berikut:

Gambar 5.6 Tampilan Form Master Barang

5. Tampilan Master Customer Master Customer, yang berfungsi sebagai tempat pengisian, pengubahan dan penghapusan data customer, seperti terlihat pada gambar berikut:

Gambar 5.7 Tampilan Form Master Customer

74

6. Tampilan Master Salesman Master Salesman, yang berfungsi sebagai tempat pengisian, pengubahan dan penghapusan data salesman, seperti terlihat pada gambar berikut:

Gambar 5.8 Tampilan Form Master Salesman

7. Tampilan Data Kota Data Kota, yang berfungsi sebagai tempat penambahan, pengubahan dan penghapusan data kota, seperti terlihat pada gambar berikut:

Gambar 5.9 Tampilan Data Kota

75

8. Tampilan Transaksi Penjualan Transaksi Penjualan, yang berfungsi sebagai tempat pengisian, pengubahan dan penghapusan data transaksi penjualan barang, seperti terlihat pada gambar berikut:

Gambar 5.10 Tampilan Form Transaksi Penjualan 9. Tampilan Penentuan Rute Perjalanan Salesman Tampilan transaksi ini berfungsi sebagai tempat pengisian dan pengaturan filter data untuk mendaftarkan semua customer yang harus dikunjungi oleh salesman yang bersangkutan, seperti terlihat pada gambar berikut:

Gambar 5.11 Tampilan Form Penentuan Rute Perjalanan Salesman

76

10. Tampilan Hasil Rute Perjalanan Salesman Tampilan ini berfungsi untuk menampilkan rute perjalanan dari salesman dalam mengunjungi setiap customer pada periode yang bersangkutan, seperti terlihat pada gambar berikut:

Gambar 5.12 Tampilan Hasil Rute Perjalanan Salesman

5.2

Pembahasan Pembahasan ini akan menguraikan keunggulan dan kelemahan sistem

usulan, serta faktor pendukung yang diperlukan untuk menjalankan sistem usulan.

5.2.1

Keunggulan dan Kelemahan Sistem Usulan Keunggulan dari sistem usulan adalah:

1. Dapat menentukan rute perjalanan salesman. 2. Proses pengolahan dan pencarian data menjadi lebih efisien.

77

3. Menghindari kesalahan manual (human error) dalam proses penentuan rute salesman. 4. Telah tersedia informasi mengenai rute perjalanan yang harus dilalui oleh salesman yang bersangkutan untuk mengunjungi setiap customer dalam periode tertentu.

Kelemahan dari sistem usulan adalah: 1. Tidak mampu untuk menentukan lokasi kota sesuai dengan keadaan sebenarnya. 2. Tidak mampu untuk

menentukan jarak minimum dari satu kota ke kota

lainnya. 3. Tidak mampu untuk menentukan rute perjalanan salesman lebih dari 3 kota. 4. Tidak mampu untuk menentukan rute perjalanan di luar wilayah medan.

5.2.2

Kebutuhan Sistem Untuk menjalankan sistem yang dirancang, diperlukan beberapa faktor

pendukung sebagai berikut : 1. Kebutuhan Perangkat Keras (Hardware) Untuk menjalankan sistem, maka hardware yang diperlukan adalah sebagai berikut: a. Satu set lengkap perangkat komputer b. Printer, sebagai perangkat untuk mencetak laporan. 2. Kebutuhan Perangkat Lunak (Software) Adapun perangkat lunak untuk menjalankan sistem ini adalah:

78

a. Sistem operasi Windows XP/Seven b. Microsoft Visual Basic 2010 untuk pembuatan program. c. Microsoft Access 2007 untuk pembuatan database. d. Aplikasi Crystal Report 10 untuk pembuatan laporan. 3. Keahlian Operator Keahlian untuk mengoperasikan komputer dan sistem yang telah dirancang.

BAB VI KESIMPULAN DAN SARAN

6.1. Kesimpulan Setelah menyelesaikan perancangan aplikasi, dapat ditarik beberapa kesimpulan sebagai berikut: 1. Sistem terkomputerisasi yang dikembangkan mampu menghasilkan laporan berdasarkan data transaksi yang dimasukkan. 2. Aplikasi yang dibuat mampu memberikan informasi mengenai rute perjalanan yang harus dilalui oleh salesman untuk periode harian. 3. Aplikasi Penentuan rute perjalanan yang di buat hanya untuk wilayah medan. 4. Setiap satu marketing maksimal pengiriman barang dalam sehari adalah 3 kota.

6.2. Saran Adapun beberapa saran yang ingin disampaikan adalah sebagai berikut: 1. Mengembangkan aplikasi sehingga mampu untuk menentukan lokasi kota sesuai dengan keadaan sebenarnya. 2. Mengembangkan aplikasi sehingga mampu untuk menentukan jarak minimal dari satu kota ke kota lainnya. 3. Sistem dapat dikembangkan lebih lanjut sehingga rute perjalanan yang di buat untuk setiap marketing lebih dari 3 kota. 4. Aplikasi rute perjalanan yang dibuat mampu untuk menentukan rute perjalanan

untuk

wilayah

79

sumatra

utara.

DAFTAR PUSTAKA Edhy Sutanta,, 2011, Basis Data dalam Tinjauan Konseptual , CV.Andi Offset, Yogyakarta Erick Kurniawan , 2011, Cepat Mahir Visual Basic 2010, Andi Publisher. Jubilee Enterprise , 2014, Buku Pintar Database dengan Ms Access, Penerbit Elex Media Komputindo, Jakarta. Herry Raditya Wibowo , Jubilee Enterprise 2014, Visual Basic Database, Penerbit Elex Media Komputindo, Jakarta. Junindar, 2008, Panduan Lengkap Menjadi Programmer Membuat Aplikasi Penjualan Menggunakan VB.Net. Cetakan ke-3. Media Kita, Jakarta. Dr. Eng. Admi Syarif , 2015, Algoritma Genetika; Teori dan Aplikasi , Edisi 2, Penerbit Graha Ilmu.

David L. Applegate, Robert E. Bixby, Vasek Chvátal, William J. Cook , 2006, The Traveling Salesman Problem: A Computational Study: A Computational Study, Princenton, New Jersey. Munir, 2010, Matematika Diskrit, Informatika, Bandung http://www.lepank.com/2012/08/pengertian-aplikasi-menurut-beberapa.html, tanggal akses 24 april 2015. http://dilihatya.com/1810/pengertian-program-aplikasi-menurut-para-ahli, tanggal akses 24 april 2015. http://slidegur.com/doc/336912/dasar-teori-graf, tanggal akses 24 april 2015.