PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SIMULATED ANNEALING STUDI KASUS: TECHNICAL SUPPORT BTSSOFT SKRIPSI

PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SIMULATED ANNEALING STUDI KASUS: TECHNICAL SUPPORT BTSSOFT

SKRIPSI

LEONARDO DAVINSI NAINGGOLAN 131421017

PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh ijazah Sarjana Ilmu Komputer

LEONARDO DAVINSI NAINGGOLAN 131421017

PROGRAM STUDI EKSTENSI S1 ILMU KOMPUTER FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA MEDAN 2016


ii

PERSETUJUAN

Judul

: PENYELESAIAN

TRAVELLING

SALESMAN

PROBLEM DENGAN ALGORITMA SIMULATED ANNEALING

STUDI

KASUS:

TECHNICAL

SUPPORT BTSSOFT Kategori

: SKRIPSI

Nama

: LEONARDO DAVINSI NAINGGOLAN

Nomor Induk Mahasiswa : 131421017 Program Studi

: EKSTENSI S1 ILMU KOMPUTER

Fakultas

: ILMU KOMPUTER DAN TEKNOLOGI INFORMASI UNIVERSITAS SUMATERA UTARA

Diluluskan di Medan,

Komisi Pembimbing

2016

:

Pembimbing 2

Pembimbing 1

Handrizal, S. Si, M. Comp.Sc

Drs. Marihat Situmorang, M.Kom

NIP. -

NIP. 19631214 198903 1 001

Diketahui/Disetujui oleh Program Studi S1 Ilmu Komputer Ketua,

Dr. Poltak Sihombing, M.Kom. NIP. 196203171991031001


iii

PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan,

2016

Leonardo Davinsi Nainggolan NIM. 131421017


iv

PENGHARGAAN

Segala puji dan syukur Penulis ucapkan kepada Tuhan Yang Maha Esa yang senantiasa melimpahkan rahmat dan karunia-Nya sehingga skripsi ini dapat diselesaikan.

Ucapan terima kasih Penulis sampaikan kepada semua pihak yang telah membantu Penulis dalam menyelesaikan skripsi ini baik secara langsung maupun tidak langsung, pada kesempatan ini penulis ingin mengucapkan terima kasih yang sebesarbesarnya kepada :

1. Bapak Prof. Dr. Runtung Sitepu, SH., MHum selaku Rektor Universitas Sumatera Utara. 2. Bapak Prof. Dr. Opim Salim Sitompul, M.Sc sebagai Dekan Fakultas Ilmu Komputer dan Teknologi Informasi 3.

Bapak Dr. Poltak Sihombing, M.Kom. selaku Ketua Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.

4.

Ibu Dr. Maya Silvi Lydia, M.Sc. selaku Sekretaris Program Studi S1 Ilmu Komputer Universitas Sumatera Utara.

5.

Dian Rachmawati, S.Si., M.Kom., selaku kepala lab TA Program Studi S1 Ilmu Komputer Universitas Sumatera Utara dan juga telah memberikan bimbingan dan arahan untuk penyelesaian skripsi ini.

6.

Bapak Drs. Marihat Situmorang, M.Kom selaku Dosen Pembimbing I yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini.

7.

Bapak Handrizal, S. Si, M. Comp.Sc, selaku Dosen Pembimbing II yang telah memberikan bimbingan, saran, dan masukan kepada penulis dalam pengerjaan skripsi ini

8.

Bapak Drs. Partano Siagian, M. Sc, selaku Dosen Pembanding I yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.

9.

Ibu Elviwani, ST., S.Kom., M.Kom. selaku Dosen Pembanding II yang telah memberikan kritik dan saran dalam penyempurnaan skripsi ini.


v

10. Bapak Ade Candra, ST, M.Kom, selaku Dosen mata kuliah Sistem Informasi Geografis yang membimbing dan menyediakan waktu untuk membantu menuliskan overview skripsi ini. 11. Semua dosen dan semua pegawai di Program Studi S1 Ilmu Komputer Fakultas Ilmu Komputer dan Teknologi Informasi Universitas Sumatera Utara. 12. Teristimewa untuk orangtua terkasih Drs. Bitner Nainggolan dan Lusianna Tambunan, S. Kep. untuk segala kasih sayang yang telah diberikan dan juga memberikan semangat dan tetap membimbing penulis dalam menghadapi keadaan sulit. 13. Untuk teman terdekat saya Lini Marsela, ST yang selalu mendukung saya saat keadaan sulit terlebih semangat untuk menyelesaikan skripsi ini. 14. Teman-teman seperjuangan mahasiswa S1 Ekstensi Ilmu Komputer stambuk 2013 yang telah memberikan semangat dan dorongan kepada penulis dalam menyelesaikan skripsi ini. 15. Semua pihak yang terlibat langsung ataupun tidak langsung yang tidak dapat penulis ucapkan satu per satu.

Penulis menyadari bahwa skripsi ini masih terdapat kekurangan. Oleh karena itu, kepada pembaca agar kiranya memberikan kritik dan saran yang bersifat membangun demi kesempurnaan skripsi ini.

Medan,

2016

Penulis,

Leonardo Davinsi Nainggolan


vi

ABSTRAK

Travelling Salesman Problem (TSP) merupakan permasalahan mencari jarak optimal untuk melewati sejumlah n kota dimana kota-kota harus dikunjungi tepat sekali dengan kota awal juga merupakan kota akhir atau tujuan. Salah satu algoritma heuristis penyelesaian TSP adalah dengan menggunakan algoritma Simulated Annealing. Ide dasar simulated annealing terbentuk dari pemrosesan logam yang digunakan untuk penyelesaian masalah yang mana perubahaan keadaan dari suatu kondisi ke kondisi yang lainnya. Penelitian ini membahas tentang penerapan masalah TSP dengan menggunakan algoritma Simulated Annealing pada permasalahan rute kunjungan kerja technical support, perusahaan perangkat lunak di Medan yaitu BTSSoft. Masalah ini diterapkan pada klien dan server, dimana pada klien menggunakan sistem operasi android yang dikembangkan melalui IONIC yaitu framework aplikasi pengembangan berbasis HTML5 dan javascript. Pada sisi server dikembangkan dengan pemrograman PHP dan javascript, bahasa markah dengan HTML5 dan sistem manajemen basis data MySQL, pemantauan lokasi teknisi realtime dengan layanan DbaaS (Database as a Service) Firebase. Untuk perangkat informasi lokasi dan gambar peta menggunakan fasilitas Google Maps dan memperoleh jarak antar titik yang akan dikunjungi dengan memanfaatkan fasilitas Matrix Distance Google Maps. Untuk proses optimasi akan dilakukan di server dan waktu eksekusi akan tergantung koneksi, titik dan layanan Google Maps. Dan penelitian ini menghasilkan rute suboptimum untuk membantu keputusan teknisi dalam memilih rutenya. Kata Kunci: Android, Cordova, Google Maps, Simulated Annealing, Sistem Informasi Geografis, Travelling Salesman Problem


vii

COMPLETION OF THE TRAVELING SALESMAN PROBLEM BY SIMULATED ANNEALING ALGORITHM CASE STUDYS: TECHNICAL SUPPORT OF BTSSOFT

ABSTRACT

Travelling Salesman Problem (TSP) is a matter of searching for the optimum distance for passing a number of n cities where cities must be visited exactly once at the beginning of the city is also a city end or purpose. One heuristic algorithm TSP settlement is to use the algorithm Simulated Annealing. The basic idea of simulated annealing formed from metal processing are used for solving problems where the change of state from a condition to another. This study discusses the application of the TSP using simulated annealing algorithm to the problem of the working visit of technical support of software company in BTSSoft Medan. This issue is applied on the client and server, where on the client using the android operating system developed by IONIC is an application development framework based on HTML5 and javascript. On the server side is developed with PHP and JavaScript, markup language using HTML5 and database management system using MySQL, real-time location monitoring technician with DbaaS (Database as a Service) using Firebase. For the device location information and image map using Google Maps facility and acquire the distance between the point to be visited by utilizing the Google Maps Distance Matrix. For the optimization process will be done on the server and the execution time will depend connection, point and service Google Maps. And generate suboptimum route to assist technical support in choosing the route. Keyword: Android, Cordova, Google Maps, Simulated Annealing, SIG, Travelling Salesman Problem


viii

DAFTAR ISI

Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

Halaman ii iii iv vi vii viii x xi

BAB 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Rumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian

1 3 3 4 4

BAB 2 TINJAUAN PUSTAKA 2.1 Graf 2.1.1 Defenisi Graf 2.1.2 Graf Berbobot 2.1.3 Representasi Graf Pada Komputer 2.2 Travelling Salesman Problem 2.2.1 Sejarah Travelling Salesman Problem 2.2.2 Perkembangan Travelling Salesman Problem 2.2.3 Prosedur Sederhana Pemecahan TSP 2.3 Algoritma Simulated Annealing 2.4 Simulated Annealing untuk Penyelesaian TSP 2.5 Sistem Informasi Geografis 2.6 Google Maps 2.7 Global Positioning System 2.7.1 Kemampuan GPS 2.7.2 Waypoint 2.7.3 Perhitungan Jarak Antara Dua Waypoints

5 5 7 7 9 10 10 14 15 20 23 26 27 27 28 28

BAB 3 ANALISIS DAN PERANCANGAN SISTEM 3.1 Analisis Masalah 3.2 Analisis Sistem 3.2.1 Analisis Kebutuhan Sistem 3.2.2 General Architecture 3.3 Pemodelan Sistem 3.3.1 Use Case Diagram 3.3.2 Activity Diagram

29 31 32 33 34 34 36


ix

3.3.3 Sequence Diagram 3.3.4 Perancangan Database 3.3.5 Perancangan Flowchart Sistem 3.4 Perancangan Antar Muka Sistem 3.4.1 Antar Muka Pada Mobile (Client) 3.4.2 Antar Muka Pada Server Web

37 38 41 43 43 52

BAB 4 IMPLEMENTASI DAN PENGUJIAN SISTEM 4.1 Implementasi Sistem 4.1.1 Implementasi Algoritma SA pada Masalah TSP 4.1.2 Simulasi Perhitungan dengan Algoritma SA 4.2 Implementasi Algoritma SA Pada Program 4.2.1 Implementasi Algoritma SA pada masalah TSP di Sisi Client 4.2.2 Implementasi Algoritma SA pada masalah TSP di Sisi Server 4.3 Pengujian Sistem 4.3.1 Pengujian dengan 5 titik 4.3.2 Pengujian dengan 10 titik

56 56 59 74 74 76 78 78 81

BAB 5 KESIMPULAN DAN SARAN 5.1. Kesimpulan 5.2. Saran

85 85

DAFTAR PUSTAKA

87

LAMPIRAN Listing Program

A-1


x

DAFTAR TABEL

Halaman Tabel 2.1 analogi antara annealing dalam permasalahan proses pendinginan logam

17

Tabel 3.1 Tabel Defenisi Aktor

35

Tabel 3.2 Tabel customers

38

Tabel 3.3 Tabel user

39

Tabel 3.4 Tabel kunjungan

40

Tabel 3.5 Tabel settings

40

Tabel 4.1 Daftar Istilah

56

Tabel 4.2 Rumus Algorima SA

57

Tabel 4.3 Simulasi daftar kunjungan

59

Tabel 4.4 Matriks Data Jarak Antar titik (meter)

60

Tabel 4.5 Hasil perhitungan dengan Algoritma SA

70

Tabel 4.6 Semua kemungkinan jarak antar titik (Brute Force)

71

Tabel 4.7 Data percobaan dengan 10 titik

81

Tabel 4.8 Matriks Data Pengujian 10 titik

82


xi

DAFTAR GAMBAR

Halaman Gambar 2.1 Graf G

5

Gambar 2.2 Graf Berbobot

7

Gambar 2.3 Diagram dan Matriks Keterhubungan Graf G

8

Gambar 2.4 Gambar Ilustrasi TSP

9

Gambar 2.5 Grafik Pemecahan permasalahan TSP dengan n-kota terhadap tahun Gambar 2.6 Flowchart algoritma Simulated Annealing

14

Gambar 2.6 Flowchart algoritma Simulated Annealing

20

Gambar 2.7. Flowchart Request URL Google Maps

25

Gambar 2.8 Parameter GPS

26

Gambar 3.1 Diagram Ishikawa pada Analisis masalah sistem sisi teknisi

30

Gambar 3.2 Diagram Ishikawa pada Analisis masalah sistem sisi Admin

31

Gambar 3.3 General Architecture

34

Gambar 3.4 Use-Case Diagram pada system

35

Gambar 3.5 Activity Diagram

36

Gambar 3.6 Sequence Diagram

37

Gambar 3.7 Flowchart sistem client dalam penyelesaian TSP

41

Gambar 3.8 Flowchart sistem server dalam penyelesaian TSP

42

Gambar 3.9 Login pada client

43

Gambar 3.10 Antar Muka side menu

44

Gambar 3.11 Antar muka halaman peta

45

Gambar 3.12 Antar muka halaman pelanggan

46

Gambar 3.13 Antar muka halaman kunjungan

47

Gambar 3.14 Antar Muka Halaman matriks

48

Gambar 3.15 Antar Muka halaman result

49

Gambar 3.16 Antar Muka Halaman Pengaturan

50

Gambar 3.17 Antarmuka halaman Tentang

51

Gambar 3.18 Antar muka Halaman Login Administrator

52

Gambar 3.19 Antar muka halaman utama administrator

52


xii

Gambar 3.20 Antarmuka Halaman Lihat Data

53

Gambar 3.21 Antarmuka tambah dan edit data

54

Gambar 4.1 Aplikasi dibuat pada browser dan setelah di-compile ke perangkat Android

74

Gambar 4.2 Halaman Utama pada aplikasi android

75

Gambar 4.3 Menu dan halaman pelanggan

75

Gambar 4.4 Halaman utama

76

Gambar 4.5 Lihat Tabel

77

Gambar 4.6 Tambah/Ubah Data

77

Gambar 4.7 Menu Kunjungan dan tampilan peta muncul marker setelah ditambah kunjungan

78

Gambar 4.8 Rute Optimasi setelah dihitung

79

Gambar 4.9 Halaman matriks data

79

Gambar 4.10 Hasil perhitungan dan parameter pada halaman Result

80

Gambar 4.11 Contoh perhitungan iterasi 1 dan 10 pada Temperatur 1180874

80

Gambar 4.12 Set direction pada iterasi ke-0 (2, 4, 1, 0, 3)

81

Gambar 4.13 Parameter Annealing

82

Gambar 4.14 Marker posisi yang akan dikunjungi

83

Gambar 4.15 Hasil dengan 10 titik

83


PENYELESAIAN TRAVELLING SALESMAN PROBLEM DENGAN ALGORITMA SIMULATED ANNEALING STUDI KASUS: TECHNICAL SUPPORT BTSSOFT SKRIPSI

Recommend Documents