![Makalah Seminar Matematika (K1314028) [PDF]](https://pdfs.asia/img/200x200/makalah-seminar-matematika-k1314028.jpg)
12 0 2 MB
TERAPAN
MAKALAH SEMINAR MATEMATIKA PENYELESAIAN TRAVELLING SALESMAN PROBLEM MENGGUNAKAN EXCEL SOLVER
Disusun untuk memenuhi Tugas Mata Kuliah Seminar Matematika Dosen Pengampu: Henny Ekana Chrisnawati, S.Si., M.Pd.
Disusun Oleh: HARDIYANTO K1314028
PROGRAM STUDI PENDIDIKAN MATEMATIKA FAKULTAS KEGURUAN DAN ILMU PENDIDIKAN UNIVERSITAS SEBELAS MARET SURAKARTA 2019
HALAMAN PERSETUJUAN
Makalah TRAVELLING
Seminar
Matematika
SALESMAN
dengan
PROBLEM
judul
PENYELESAIAN
MENGGUNAKAN
EXCEL
SOLVER telah disetujui oleh Dosen Pembimbing untuk diseminarkan di hadapan Penguji Seminar Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Sebelas Maret Surakarta.
Surakarta, ..................................... 2019 Dosen Pembimbing
Henny Ekana Chrisnawati, S.Si., M.Pd. NIP. 19730602 199802 2 001
ii
HALAMAN PENGESAHAN
Makalah TRAVELLING
Seminar
Matematika
SALESMAN
dengan
PROBLEM
judul
PENYELESAIAN
MENGGUNAKAN
EXCEL
SOLVER telah dipertahankan di hadapan Penguji Seminar Program Studi Pendidikan Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Sebelas Maret Surakarta dan diterima untuk memenuhi tugas Mata Kuliah Seminar Matematika pada: Hari
:
Tanggal
:
Mengetahui, Kepala Program Studi Pendidikan Matematika
Penguji Seminar,
Dr. Budi Usodo, M.Pd. NIP. 19680517 199303 1 002
Henny Ekana Chrisnawati, S.Si., M.Pd. NIP. 19730602 199802 2 001
iii
PERNYATAAN KEASLIAN TULISAN
Saya yang bertanda tangan di bawah ini: Nama
: Hardiyanto
NIM
: K1314028
Program Studi
: Pendidikan Matematika
dengan ini menyatakan bahwa Makalah Seminar Matematika dengan judul PENYELESAIAN
TRAVELLING
SALESMAN
PROBLEM
MENGGUNAKAN EXCEL SOLVER benar – benar merupakan tulisan saya sendiri. Sumber informasi yang dikutip dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam daftar pustaka. Apabila dikemudian hari terbukti hasil jiplakan, saya bersedia menerima sanksi atas perbuatan saya.
Surakarta, ....................... 2019 Yang membuat pernyataan,
Hardiyanto NIM. K1314028
iv
KATA PENGANTAR
Puji syukur penulis panjatkan kehadirat Allah SWT, karena atas rahmat dan karunia-Nya sehingga penyusunan Makalah Seminar Matematika ini dapat diselesaikan dengan baik dan meskipun dengan waktu yang terhitung mepet. Tentunya dalam penyusunan Makalah Seminar Matematika ini melibatkan banyak pihak, sehingga penyusunan tugas ini dapat terlaksana dengan baik. Maka dari itu penulis hendak mengucapkan terima kasih kepada pihak – pihak yang telah membantu dalam penyusunan tugas ini, yaitu kepada: 1.
Ibu Henny Ekana Chrisnawati, S.Si., M.Pd. selaku Dosen Pembimbing Mata Kuliah Seminar Matematika Fakultas Keguruan dan Ilmu Pendidikan Universitas Sebelas Maret Tahun Akademik 2018/2019 yang telah memberikan bimbingan, dorongan, dan saran dalam penyusunan makalah ini.
2.
Teman – teman Pendidikan Matematika angkatan 2014 Fakultas Keguruan dan Ilmu Pendidikan Universitas Sebelas Maret yang telah memberikan motivasi dan saran dalam penyusunan makalah ini.
3.
Kakak-kakak tingkat dan adik-adik tingkat Pendidikan Matematika yang selalu memberikan semangat.
4.
Bapak, Ibu, dan kakak yang telah memberikan cinta serta memberi dukungan, doa serta pengorbanan baik moril maupun materil.
5.
Pihak-pihak lain yang tidak dapat disebutkan satu persatu. Penulis menyadari bahwa Penyusunan Makalah Seminar Matematika ini
masih jauh dari kesempurnaan. Oleh karena itu penulis mengharap kritik dan saran yang sifatnya membangun dari pembaca. Akhir kata semoga Makalah Seminar Matematika ini bermanfaat bagi kita semua dan semoga Allah memberikan Rahmat-Nya kepada kita semua. Aamiin.
Surakarta, ......................... 2019 Penulis
v
DAFTAR ISI
HALAMAN JUDUL ....................................................................................... i HALAMAN PERSETUJUAN ........................................................................ ii HALAMAN PENGESAHAN ......................................................................... iii PERNYATAAN KEASLIAN TULISAN ...................................................... iv KATA PENGANTAR .................................................................................... v DAFTAR ISI ................................................................................................... vi BAB I
PENDAHULUAN A. Latar Belakang Masalah .......................................................... 1 B. Rumusan Masalah ................................................................... 3 C. Tujuan Penulisan ..................................................................... 3
BAB II
PEMBAHASAN A. Teori Pendukung ..................................................................... 4 B. Pembahasan Masalah ............................................................... 10
BAB III PENUTUP A. Kesimpulan .............................................................................. 37 B. Saran ........................................................................................ 38 DAFTAR PUSTAKA ..................................................................................... 39
vi
BAB I PENDAHULUAN A. Latar Belakang Masalah Pencarian rute terpendek merupakan suatu masalah yang paling banyak dibahas dan dipelajari sejak akhir tahun 1950. Pencarian rute terpendek ini telah diterapkan di berbagai bidang untuk mengoptimasi kinerja suatu sistem, baik untuk meminimalkan biaya atau mempercepat jalannya suatu proses (Purwananto, 2005: 1). Kesulitan menentukan rute terpendek timbul karena terdapat banyak jalur yang ada dari suatu alamat ke alamat lain. Kebutuhan untuk menemukan rute terpendek dan waktu tempuh tercepat tentunya juga diperhitungkan untuk menghindari kerugian. Contoh, bagi sebuah perusahaan penyedia jasa pengiriman barang, kebutuhan untuk segera sampai ke tempat tujuan tepat waktu bahkan diharapkan bisa lebih cepat sangatlah dibutuhkan, mengingat persaingan perusahaan penyedia jasa pengiriman barang yang mementingkan kepuasan pelanggan. Proses pendistribusian barang adalah kegiatan yang tidak pernah lepas dari kehidupan. Jarak yang jauh serta penyebaran masyarakat yang meluas menjadi salah satu alasan bagi masyarakat untuk menggunakan jasa pengiriman barang dari pada mengantar sendiri barang yang akan dikirimkan. Masalah pengiriman barang menjadi poin terpenting bagi perusahaan penyedia jasa pengiriman barang. Hal ini sangat memerlukan pertimbangan dan perhitungan yang tepat karena berkaitan dengan biaya transportasi yang harus dikeluarkan dalam proses pengiriman (Sari, Dwijanto & Sugiharti, 2013: 2). Proses pendistribusian barang merupakan proses yang sangat berpengaruh pada keberlangsungan suatu usaha. Dengan pengoptimalan biaya pengiriman, dapat menambah keuntungan bagi perusahaan. Pengoptimalan biaya pengiriman dapat dilakukan dengan mencari rute pengiriman yang paling efisien. Karena dengan diperolehnya rute yang paling efisien, dapat meminimalkan biaya pengiriman barang. Permasalahan seperti ini termasuk kasus Travelling Salesmen Problem (TSP).
1
2 Travelling Salesman Problem (TSP) adalah sebuah masalah seorang salesman yang mempunyai tugas untuk mengirimkan pesanan atau barang kepada pelanggan yang berada di sejumlah tempat yang berbeda. Salesman tersebut mempunyai masalah dalam hal menentukan tempat mana yang lebih dahulu dikunjungi sedemikian sehingga total jarak dan waktu pengiriman diperkecil, setiap tempat hanya boleh dikunjungi satu kali dalam satu perjalanan, serta perjalanan berakhir di tempat awal dimana seorang sales memulai perjalanannya. Perkembangan ilmu pengetahuan dan teknologi saat ini telah mengalami perkembangan pesat terutama dalam hal proses komputasi yang memungkinkan sebuah masalah dapat diselesaikan dengan bantuan komputer sebagai solusinya. Salah satunya adalah apa yang ditawarkan oleh Microsoft. Microsoft menawarkan Excel Solver, sebuah Add-in optimisasi numerik yang dapat digunakan untuk mencari nilai optimal (maksimum atau minimum) untuk rumus dalam satu sel (disebut sel objektif) yang memenuhi kendala (batasan), atau batas nilai pada sel rumus lain pada lembar kerja. Excel Solver mengolah sekelompok sel (disebut sel variabel keputusan) yang merupakan bagian dari rumus perhitungan dari sel tujuan dan kendala. Excel Solver menyesuaikan nilai dalam sel variabel keputusan untuk memenuhi batas pada sel kendala dan menghasilkan hasil yang diinginkan untuk sel objektif (Djamaris, 2018: 1). Dengan kata lain, fasilitas Excel Solver memungkinkan kita menghitung nilai yang dibutuhkan untuk mencapai hasil dengan cara menyesuaikan nilai yang terdapat pada satu sel atau lebih dan bisa mendefinisikan sendiri suatu fungsi kendala sehingga bisa mencari solusi optimumnya misalnya meminimumkan biaya pengiriman barang dari kantor perusahaan jasa pengiriman barang ke pelanggan. Berdasarkan uraian diatas, penulis tertarik membuat makalah untuk membahas penyelesaian Travelling Salesman Problem menggunakan Excel Solver.
B. Rumusan Masalah
3 Berdasarkan latar belakang masalah di
atas,
dapat
dirumuskan
permasalahan sebagai berikut: 1.
Bagaimanakah penyelesaian Travelling Salesman Problem menggunakan Excel Solver? C. Tujuan Penulisan Berdasarkan rumusan masalah di atas, tujuan yang ingin dicapai dari
pembahasan ini adalah sebagai berikut: 1.
Mengetahui penyelesaian Travelling Salesman Problem menggunakan Excel Solver.
BAB II PEMBAHASAN A. Teori Pendukung Pada subbab Teori Pendukung ini, akan dibahas mengenai materi yang menunjang penyelesaian masalah yang telah disebutkan pada Bab I Pendahuluan. 1. Optimisasi Optimisasi merupakan suatu upaya sistematis untuk memilih elemen terbaik dari suatu kumpulan elemen yang ada. Di dalam kontek matematika, optimisasi ini bisa dinyatakan sebagai suatu usaha sistematis untuk mencari nilai minimum atau maksimum dari suatu fungsi. Dengan kata lain, optimisasi merupakan proses mencari nilai terbaik berdasarkan fungsi tujuan dengan daerah asal yang telah didefinisikan. Fungsi ini secara sederhana dapat dinyatakan dengan: 𝑚𝑖𝑛/ max 𝑓(𝑥) Sebagai contoh adalah fungsi kuadrat 𝑓(𝑥) = 𝑥 2 , dimana 𝑥 anggota bilangan real (𝑥 ∈ 𝑅). Di dalam contoh ini, 𝑓(𝑥) = 𝑥 2 merupakan fungsi tujuannya, sedangkan 𝑥 adalah daerah asal yang didefinisikan sebagai anggota bilangan real. Optimisasi dipakai di hampir semua bidang ilmu antara lain bidang teknik, sains, ilmu sosial, ekonomi dan bisnis. Banyak permasalahan di bidang teknik, sains dan ekonomi yang dapat dinyatakan sebagai permasalahan optimisasi seperti meminimalkan biaya, waktu dan resiko atau memaksimalkan keuntungan dan kualitas. (Buana, 2016: 12) 2. Travelling Salesman Problem (TSP) Travelling
salesman
problem
(TSP) merupakan permasalahan
kombinatorial yang banyak dipelajari. TSP adalah sebuah masalah seorang salesman yang mempunyai tugas untuk mengirimkan pesanan atau barang kepada pelanggan yang berada di sejumlah tempat yang berbeda. Salesman tersebut mempunyai masalah dalam hal menentukan tempat mana yang lebih dahulu dikunjungi sedemikian sehingga total jarak dan waktu pengiriman 4
5 diperkecil, setiap tempat hanya boleh dikunjungi satu kali dalam satu perjalanan, serta perjalanan berakhir di tempat awal dimana seorang sales memulai perjalanannya. Banyak permasalahan yang dapat direpresentasikan dalam bentuk TSP. Diantara permasalahan yang dapat direpresentasikan dengan TSP adalah efisiensi pengiriman surat atau barang, pencarian rute bis sekolah untuk mengantarkan siswa, pengambilan tagihan telepon, perancangan pemasangan pipa saluran dan lain-lain. (Buana, 2016: 14) Ada dua jenis kasus TSP berdasarkan sifatnya, yaitu symmetric TSP dan asymmetric TSP. Symmetric TSP adalah kasus TSP dimana jarak antar masingmasing titik lokasinya sama dari kedua arah. Sedangkan asymmetric TSP adalah kasus TSP dimana ada jarak antar titik lokasi yang berbeda dari kedua arah. Jumlah kombinasi perjalanan yang dihasilkan untuk kasus asymmetric TSP adalah (𝑛 − 1)!. Sedangkan jumlah kombinasi perjalanan yang dihasilkan untuk kasus symmetric TSP adalah (
𝑛−1 2
)!. (Buana, 2016: 15)
3. Excel Solver Solver merupakan salah satu fasilitas tambahan/optional (Add-in) yang disediakan oleh Microsoft Excel yang berfungsi untuk mencari nilai optimal suatu formula pada satu sel saja (yang biasa disebut sebagai sel tujuan) pada worksheet/lembar kerja. Excel Solver mengkombinasikan fungsi dari suatu Graphical User Interface (GUI), suatu algebraic modeling language seperti GAMS (Brooke, Kendrick, dan Meeraus 1992) atau AMPL (Fourer, Gay, and Kernighan 1993), dan optimizers untuk linier, non-linear, dan integer program. Masing-masing fungsi ini terintegrasi ke dalam spreadsheet program. Solver merupakan bagian dari serangkaian perintah/command yang seringkali disebut what-if analysis tool. Fasilitas ini bekerja dengan sel-sel suatu grup yang saling terhubung, baik secara langsung ataupun tidak langsung (directly-indirectly) untuk formula pada sel tujuan. Solver terdiri dari tiga bagian:
6 a. Variable cells (sel keputusan) Solver mengatur perubahan nilai pada sel yang spesifik, untuk memproduksi hasil perlu spesifikasi dari formula pada sel tujuan. b. Constrained cell (sel pembatas) Constraint digunakan untuk membatasi nilai solver yang dapat digunakan pada suatu model tertentu dan constraint mengacu pada sel lain yang memengaruhi formula pada sel tujuan. c. Objective cell (sel tujuan) Merupakan
bagian
solver
sebagai
tempat
dimana
hasil
akhir
pemrosesan/eksekusi suatu formula ditempatkan. (Djamaris, 2018: 2) Menu Excel Solver menggunakan kode-kode non-linear optimisasi Generalized Reduced Gradient (GRG) yang dikembangkan oleh Leon Lasdon (Universitas Texas: Austin) dan Allen Waren (Cleveland State University). Sedangkan untuk linear dan permasalahan integer digunakan metode simplex dengan bound/batas variabel. Metode ini (branch and bound method) diimplementasikan oleh John Watson dan Dan Fylstra (Frontline Systems,Inc). (Djamaris, 2018: 3) Fitur ini diinstal secara tersendiri karena merupakan fasilitas tambahan/optional. Cara menambahkan Solver pada Microsoft Excel adalah sebagai berikut: a. Masuk aplikasi Microsoft Excel. b. Klik tab File lalu klik Options.
7
Kemudian akan muncul tampilan berikut:
c. Klik kategori Add-Ins. Akan muncul tampilan berikut:
8
d. Pada bagian Manage, pilih Excel Add-in, lalu klik Go. Akan muncul tampilan berikut:
e. Pada kotak Add-in available, pilih Solver Add-in, lalu klik OK. Hasilnya, pada tab Data akan muncul menu baru di sebelah kanan, yaitu Solver.
9
Solver digunakan untuk menentukan nilai maksimum dan minimum pada suatu sel dengan mengubah sel yang lain. Misal: mengubah rute perjalanan dan melihat pengaruh pada total jarak perjalanan. Langkah-langkah untuk mencari rute terpendek menggunakan Excel Solver adalah sebagai berikut: a. Menuliskan data awal. b. Menuliskan variabel keputusan dan fungsi tujuan. c. Klik menu Solver pada tab Data. Akan muncul tampilan Solver Parameters berikut:
Pada bagian Set Objective, masukkan sel tujuan.
Pada bagian To, pilih Min untuk meminimalkan total jarak.
Pada bagian By Changing Variable Cells, masukkan referensi sel untuk setiap rentang variabel keputusan.
10
Pada bagian Subject to the Constraints, klik Add. Akan muncul tampilan berikut:
Pada bagian Cell Reference, masukkan referensi sel untuk setiap rentang variabel keputusan. Kemudian pada kotak sebelahnya, pilih hubungan antara referensi sel. Dalam hal ini, pilih dif (different – berbeda) supaya tidak ada variabel keputusan yang bernilai sama. Dengan kata lain, pilih dif supaya masing-masing titik hanya dikunjungi sekali. Kemudian klik OK. Tampilan akan kembali ke bagian Solver Parameters.
Pada bagian Select a Solving Method, pilih Evolutionary.
Kemudian klik Solve.
d. Memeriksa hasilnya dan melakukan koreksi pada model. e. Menganalisis dan menginterpretasikan hasilnya.
B. Pembahasan Masalah Pada subbab Pembahasan Masalah ini, akan dibahas mengenai contohcontoh penyelesaian TSP menggunakan Excel Solver. Contoh 1. Kasus Symmetric TSP Seorang kurir bertugas mengirimkan barang dari Kantor JNE ke enam titik lokasi tujuan dengan keterangan sebagai berikut: V1
= Kantor JNE Alauddin
V2
= Instalasi Penyakit Kusta Dan Penyakit Infeksi Endemic
V3
= RSIA Siti Khadijah III
V4
= PT Indolok Bakti Utama
V5
= PT Dipa Jaya Sejahtera
V6
= Mall GTC Tanjung Bunga
V7
= Kantor Dinas Kelautan dan Perikanan Provinsi Sulawesi Selatan
11 Jarak tempuh (km) dari masing-masing titik lokasi dapat dilihat pada tabel berikut: Tabel 1. Jarak tempuh (km) dari masing-masing titik lokasi V1 V2 V1 0
V3
V4
V5
V6
V7
2,5 2,9 2,9 3,3 6,2 2,3
V2 2,5 0
0,9 1,3 1,9 6,7 2,9
V3 2,9 0,9 0
0,8 1,7 8,1 3
V4 2,9 1,3 0,8 0
1,2 5,4 2,4
V5 3,3 1,9 1,7 1,2 0
5,6 2,4
V6 6,2 6,7 8,1 5,4 5,6 0 V7 2,3 2,9 3
3,4
2,4 2,4 3,4 0
Tentukan rute terpendek yang bisa dilalui kurir tersebut untuk mengirimkan barang dari Kantor JNE ke enam titik lokasi tujuan kemudian kembali lagi ke Kantor JNE dengan menggunakan Excel Solver! (Data diperoleh dari skripsinya Ernawati yang berjudul “Implementasi Algoritma Semut untuk Optimasi Rute Terpendek” pada halaman 34-37). Jawab: Langkah-langkah untuk menyelesaikan masalah tersebut adalah sebagai berikut: 1. Menuliskan data awal, yaitu data jarak tempuh (km) dari masing-masing titik lokasi ke dalam lembar kerja Microsoft Excel seperti berikut:
2. Menuliskan variabel keputusan dan fungsi tujuan seperti berikut:
12
Nilai pada sel K2:K8 diperoleh dengan formula: =INDEX(array; row_num; [column_num]) Keterangan:
Nilai pada sel K3 =INDEX(B2:H8;J2;J3) = 2,5 Artinya, nilai pada sel K3 merupakan jarak dari titik 1 (V1) ke titik 2 (V2) berdasarkan data pada sel B2:H8.
Nilai pada sel K4 =INDEX(B2:H8;J3;J4) = 0,9 Artinya, nilai pada sel K4 merupakan jarak dari titik 2 (V2) ke titik 3 (V3) berdasarkan data pada sel B2:H8.
Nilai pada sel K5 =INDEX(B2:H8;J4;J5) = 0,8 Artinya, nilai pada sel K5 merupakan jarak dari titik 3 (V3) ke titik 4 (V4) berdasarkan data pada sel B2:H8.
Nilai pada sel K6 =INDEX(B2:H8;J5;J6) = 1,2 Artinya, nilai pada sel K6 merupakan jarak dari titik 4 (V4) ke titik 5 (V5) berdasarkan data pada sel B2:H8.
Nilai pada sel K7 =INDEX(B2:H8;J6;J7) = 5,6 Artinya, nilai pada sel K7 merupakan jarak dari titik 5 (V5) ke titik 6 (V6) berdasarkan data pada sel B2:H8.
Nilai pada sel K8 =INDEX(B2:H8;J7;J8) = 3,4 Artinya, nilai pada sel K8 merupakan jarak dari titik 6 (V6) ke titik 7 (V7) berdasarkan data pada sel B2:H8.
13
Nilai pada sel K2 =INDEX(B2:H8;J8;J1) = 2,3 Artinya, nilai pada sel K2 merupakan jarak dari titik 7 (V7) ke titik 1 (V1) berdasarkan data pada sel B2:H8.
Nilai pada sel K9 diperoleh dengan formula: =SUM(K2:K8) yaitu total jarak yang dilalui kurir dengan urutan perjalanan: V1-V2-V3-V4-V5-V6-V7-V1 3. Klik menu Solver pada tab Data. Akan muncul tampilan Solver Parameters seperti berikut:
Pada bagian Set Objective, masukkan sel tujuan (sel K9).
Pada bagian To, pilih Min untuk meminimalkan total jarak.
Pada bagian By Changing Variable Cells, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel J2:J8.
Pada bagian Subject to the Constraints, klik Add. Akan muncul tampilan berikut:
14
Pada bagian Cell Reference, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel J2:J8. Kemudian pada kotak kedua, pilih dif. Secara otomatis kotak ketiga akan muncul tulisan AllDifferent seperti berikut:
Kemudian klik OK. Tampilan akan kembali ke bagian Solver Parameters seperti berikut:
Pada bagian Select a Solving Method, pilih Evolutionary.
15
Kemudian klik Solve. Akan muncul tampilan berikut:
4. Memeriksa hasilnya dan melakukan koreksi pada model. Dari tampilan di atas, diperoleh informasi bahwa Solver tidak dapat meningkatkan solusi lagi dikarenakan semua kendala/batasan sudah dipenuhi. Dengan kata lain, sudah diperoleh hasil yang optimal. Pilih Keep Solver Solution, Answer dan centang bagian Outline Report untuk mendapatkan informasi dari hasil pengoperasian Excel Solver. Kemudian klik OK. Akan muncul tampilan berikut:
16 5. Menganalisis dan menginterpretasikan hasilnya. Dari tampilan di atas, terdapat 1 sheet baru pada lembar kerja, yaitu sheet dengan judul Answer Report 1 seperti berikut:
Dari tampilan tersebut bisa diambil beberapa informasi berikut: a. Waktu yang dibutuhkan untuk proses Solver adalah 119,313 detik. b. Rute terpendek adalah V1-V2-V3-V4-V5-V6-V7-V1 dengan total jarak tempuh 16,7 km. Jadi, rute terpendek yang bisa dilalui kurir tersebut untuk mengirimkan barang dari Kantor JNE ke enam titik lokasi tujuan kemudian kembali lagi ke Kantor JNE adalah berangkat dari Kantor JNE Alauddin (V1) menuju Instalasi Penyakit Kusta Dan Penyakit Infeksi Endemic (V2), kemudian ke RSIA Siti Khadijah III (V3), kemudian ke PT Indolok Bakti Utama (V4), kemudian ke PT
17 Dipa Jaya Sejahtera (V5), kemudian ke Mall GTC Tanjung Bunga (V6), kemudian ke Kantor Dinas Kelautan dan Perikanan Provinsi Sulawesi Selatan (V7), dan yang terakhir adalah kembali ke Kantor JNE Alauddin (V1) dengan total jarak tempuh 16,7 km. Karena ini merupakan kasus symmetric TSP, maka terdapat rute terpendek yang lain yang juga memiliki total jarak tempuh 16,7 km, yaitu kebalikan arah dari rute yang pertama. Rute tersebut adalah V1-V7-V6-V5-V4-V3-V2-V1. Dengan kata lain, kurir bisa berangkat dari Kantor JNE Alauddin (V1) menuju Kantor Dinas Kelautan dan Perikanan Provinsi Sulawesi Selatan (V7), kemudian ke Mall GTC Tanjung Bunga (V6), kemudian ke PT Dipa Jaya Sejahtera (V5), kemudian ke PT Indolok Bakti Utama (V4), kemudian ke RSIA Siti Khadijah III (V3), kemudian ke Instalasi Penyakit Kusta Dan Penyakit Infeksi Endemic (V2), dan yang terakhir adalah kembali ke Kantor JNE Alauddin (V1). Jawaban pembanding: Dalam kasus yang sama, Ernawati dalam skripsinya yang berjudul “Implementasi Algoritma Semut untuk Optimasi Rute Terpendek” menyelesaikan kasus ini menggunakan Algoritma Semut dan diperoleh rute terpendek sementara (berhenti pada iterasi pertama) adalah V1-V5-V3-V2-V4-V7-V6-V1 dengan total jarak tempuh 19,2 km.
Contoh 2. Kasus Asymmetric TSP Diberikan matriks jarak antar titik sebagai berikut: V1
V2 V3 V4 V5 V6 V7
V1
0
75
99
9
35
63
8
V2
51
0
86
46
88
29
20
V3 100
5
0
16
28
35
28
V4
20
45
11
0
59
53
49
V5
86
63
33
65
0
76
72
V6
36
53
89
31
21
0
52
V7
58
31
43
67
52
60
0
18 Tentukan rute terpendek yang bisa dilalui dari titik yang pertama ke enam titik yang lain kemudian kembali lagi ke titik yang pertama dengan menggunakan Excel Solver! (Data diperoleh dari skripsinya Wahyu Pradana Stya Budi yang berjudul “Optimasi Traveling Salesman Problem dengan Algoritma Genetika Menggunakan Operator Partially Matched Crossover” pada halaman 35). Jawab: Langkah-langkah untuk menyelesaikan masalah tersebut adalah sebagai berikut: 1. Menuliskan data awal, yaitu matriks jarak antar titik ke dalam lembar kerja Microsoft Excel seperti berikut:
2. Menuliskan variabel keputusan dan fungsi tujuan seperti berikut:
19 Nilai pada sel K2:K8 diperoleh dengan formula: =INDEX(array; row_num; [column_num]) Keterangan:
Nilai pada sel K3 =INDEX(B2:H8;J2;J3) = 75 Artinya, nilai pada sel K3 merupakan jarak dari titik 1 (V1) ke titik 2 (V2) berdasarkan data pada sel B2:H8.
Nilai pada sel K4 =INDEX(B2:H8;J3;J4) = 86 Artinya, nilai pada sel K4 merupakan jarak dari titik 2 (V2) ke titik 3 (V3) berdasarkan data pada sel B2:H8.
Nilai pada sel K5 =INDEX(B2:H8;J4;J5) = 16 Artinya, nilai pada sel K5 merupakan jarak dari titik 3 (V3) ke titik 4 (V4) berdasarkan data pada sel B2:H8.
Nilai pada sel K6 =INDEX(B2:H8;J5;J6) = 59 Artinya, nilai pada sel K6 merupakan jarak dari titik 4 (V4) ke titik 5 (V5) berdasarkan data pada sel B2:H8.
Nilai pada sel K7 =INDEX(B2:H8;J6;J7) = 76 Artinya, nilai pada sel K7 merupakan jarak dari titik 5 (V5) ke titik 6 (V6) berdasarkan data pada sel B2:H8.
Nilai pada sel K8 =INDEX(B2:H8;J7;J8) = 52 Artinya, nilai pada sel K8 merupakan jarak dari titik 6 (V6) ke titik 7 (V7) berdasarkan data pada sel B2:H8.
Nilai pada sel K2 =INDEX(B2:H8;J8;J1) = 58 Artinya, nilai pada sel K2 merupakan jarak dari titik 7 (V7) ke titik 1 (V1) berdasarkan data pada sel B2:H8.
Nilai pada sel K9 diperoleh dengan formula: =SUM(K2:K8) yaitu total jarak yang dilalui kurir dengan urutan perjalanan: V1-V2-V3-V4-V5-V6-V7-V1 3. Klik menu Solver pada tab Data. Akan muncul tampilan Solver Parameters seperti berikut:
20
Pada bagian Set Objective, masukkan sel tujuan (sel K9).
Pada bagian To, pilih Min untuk meminimalkan total jarak.
Pada bagian By Changing Variable Cells, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel J2:J8.
Pada bagian Subject to the Constraints, klik Add. Akan muncul tampilan berikut:
Pada bagian Cell Reference, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel J2:J8. Kemudian pada kotak kedua, pilih dif. Secara otomatis kotak ketiga akan muncul tulisan AllDifferent seperti berikut:
21
Kemudian klik OK. Tampilan akan kembali ke bagian Solver Parameters seperti berikut:
Pada bagian Select a Solving Method, pilih Evolutionary.
Kemudian klik Solve. Akan muncul tampilan berikut:
22
4. Memeriksa hasilnya dan melakukan koreksi pada model. Dari tampilan di atas, diperoleh informasi bahwa Solver tidak dapat meningkatkan solusi lagi dikarenakan semua kendala/batasan sudah dipenuhi. Dengan kata lain, sudah diperoleh hasil yang optimal. Pilih Keep Solver Solution, Answer dan centang bagian Outline Report untuk mendapatkan informasi dari hasil pengoperasian Excel Solver. Kemudian klik OK. Akan muncul tampilan berikut:
5. Menganalisis dan menginterpretasikan hasilnya.
23 Dari tampilan di atas, terlihat bahwa sel J2:J8 sudah berubah nilainya. Artinya referensi sel untuk setiap rentang variabel keputusan yang ditetapkan di awal bukan merupakan rute terbaik. Akibatnya sel J2:J8 sudah digantikan oleh rentang variabel keputusan yang baru, hasil dari proses Solver dan merupakan rute terbaik. Selain itu juga terdapat 1 sheet baru pada lembar kerja, yaitu sheet dengan judul Answer Report 1 seperti berikut:
Perubahan yang terjadi pada sel J2:J8 juga terlihat pada tampilan tersebut dimana kolom Original Value merupakan referensi sel untuk setiap rentang variabel keputusan yang ditetapkan di awal dan kolom Final Value merupakan rentang variabel keputusan yang baru, hasil dari proses Solver dan merupakan rute terbaik. Dari tampilan tersebut bisa diambil beberapa informasi berikut:
24 a. Waktu yang dibutuhkan untuk proses Solver adalah 122,297 detik. b. Karena titik awal adalah titik pertama (V1), maka rute terpendek adalah V1V7-V2-V6-V5-V3-V4-V1 dengan total jarak tempuh 158 satuan. Jadi, rute terpendek yang bisa dilalui dari titik yang pertama ke enam titik yang lain kemudian kembali lagi ke titik yang pertama adalah V1-V7-V2-V6-V5-V3V4-V1 dengan total jarak tempuh 158 satuan. Karena ini merupakan kasus asymmetric TSP, maka tidak berlaku hal sama pada arah yang berlawanan. Dengan kata lain, arah yang berlawanan bukan merupakan rute terpendek. Jawaban pembanding: Dalam kasus yang sama, Wahyu Pradana Stya Budi dalam skripsinya yang berjudul “Optimasi Traveling Salesman Problem dengan Algoritma Genetika Menggunakan Operator Partially Matched Crossover” menyelesaikan kasus ini menggunakan Algoritma Genetika dengan Operator Partially Matched Crossover dan diperoleh rute terpendek adalah V1-V7-V2-V6-V5-V3-V4-V1 dengan total jarak tempuh 158 satuan. Sama dengan hasil yang diperoleh dari Excel Solver.
Contoh 3. Kasus Symmetric TSP Seorang kurir bertugas mengirimkan barang dari Kantor JNE ke 27 pelanggan dengan keterangan sebagai berikut: Kode
Nama Penerima
Alamat
V1
JNE
Jl. Sultan Agung
V2
Zerlin
Jl. Tirto Mukti 3 No. 1022
V3
Rendy Risk
Jl. Parang Kembang X No. 30
V4
Agung
Jl. Wahyu Temurun 2 No. 15
V5
Teta
Jl. Satrio Manah II No. 2
V6
Michelle Buison
Jl. Soekarno Hatta No. 28
V7
Anjie Aristianty
Jl. Sido Asih 5 No. 15
V8
Betty Ekowati
Jl. Parang Kusuma 1
V9
Elisa Amalia
Jl. Lintang Trenggono V/ 2
V10
Nouva Alesia
Jl. Parang Kusuma VII/ 7
25 V11
Putri
Jl. Seruni 7 No. 28
V12
Ferdinad
Jl. Tlogosari Raya 2 No. 62
V13
Indah Putri
Jl. Gusti Putri No. 17
V14
Maulita
Jl. Grinsing
V15
Desy Nourma
Jl. Seruni 4 No. 1
V16
Awan Djati
Jl Parang Baris 6 No. 10
V17
Januar Wahyu
Jl. Parang Kusuma XI No. 13
V18
Ida Hanifah
Jl. Malangsari Cluster III
V19
Fresma
Jl. Bledok Kantil 1 No. 5
V20
Prasetyo Kentjono
Jl. Parang Barong Raya No. 10
V21
Toko Pro Atk
Jl. Tlogosari Raya I No. 69
V22
Vani
Jl. Parang Kesit
V23
Ningrum
Jl. Tlogosari Raya 2/ 30
V24
Yudi Ucil
Jl. Tlogosari Raya 2 Blok H2
V25
Adi
Bank BRI KCP Tlogosari
V26
Esti
Jl. Bugen
V27
Optik Audhifa
Jl. Parang Kembang Raya No. 11
V28
Elisabet Yania Adriani
Jl. Sido Asih 4/ 79
Jarak tempuh (km) dari masing-masing titik lokasi dapat dilihat pada tabel berikut: Tabel 1: Jarak tempuh (km) dari masing-masing titik lokasi V1
V2
V3
V4
V5
V6
V7
V8
V9
V10
V1
0
13,7
12,8
13
12,4
10,2
13
8,7
12,3
12,2
V2
13,7
0
0,65
0,45
1,7
2,5
2,6
0,95
0,9
1,2
V3
12,8
0,65
0
0,24
1
1,8
1,9
0,5
0,21
0,7
V4
13
0,45
0,24
0
1
2,1
1,9
0,9
0,29
1
V5
12,4
1,7
1
1
0
0,95
1,5
1
1
0,75
V6
10,2
2,5
1,8
2,1
0,95
0
2,2
1,7
1,9
1,5
V7
13
2,6
1,9
1,9
1,5
2,2
0
1,9
2
1,7
V8
8,7
0,95
0,5
0,9
1
1,7
1,9
0
0,9
0,29
V9
12,3
0,9
0,21
0,29
1
1,9
2
0,9
0
0,85
26 V10
12,2
1,2
0,7
1
0,75
1,5
1,7
0,29
0,85
0
V11
12,7
2,3
1,4
1,4
0,4
0,75
1,5
1,4
1,3
1,8
V12
9,7
1,3
0,6
0,65
0,65
1,4
1,4
0,75
0,45
1
V13
11,8
1,4
1
1,1
0,75
1,3
1,7
0,45
0,95
0,35
V14
13,2
2,1
1,7
1,7
1,6
2,3
1,2
2
1,5
2
V15
12,5
2,1
1,5
1,5
0,5
0,95
1,3
1,4
1,2
1,7
V16
12,1
1,3
0,6
0,45
0,8
1,6
1,5
1,3
0,4
0,85
V17
11,6
1,2
0,75
0,9
0,7
1,6
1,6
0,35
0,75
0,14
V18
12,4
2,1
1,3
1,3
0,45
0,6
1,9
1,2
1,1
1
V19
11,8
1,5
1,1
1,1
0,65
1,2
1,7
0,6
0,9
0,55
V20
11,9
1,5
0,7
0,75
0,35
1,2
1,2
0,7
0,55
0,5
V21
11,6
1,3
0,9
1,1
0,9
1,7
1,8
0,65
1
0,4
V22
11,7
1,3
0,8
0,85
0,5
1,5
1,5
0,4
0,6
0,21
V23
9,7
1,4
0,75
0,75
0,65
1,5
1,5
0,9
0,6
1,1
V24
12,4
2,1
1,3
1,3
1
1,8
0,7
1,5
1,2
1,7
V25
11,5
1,2
1
0,8
0,7
1,6
1,6
0,45
0,65
0,23
V26
12,8
1,3
1,3
1,7
1
2,2
1,6
1,8
1,3
1,6
V27
12,3
0,75
0,29
0,65
1
1,9
1,9
0,75
0,85
0,4
V28
13
2,6
1,9
1,8
1,4
2,2
0,1
1,9
1,7
1,6
V11
V12
V13
V14
V15
V16
V17
V18
V19
V20
V1
12,7
9,7
11,8
13,2
12,5
12,1
11,6
12,4
11,8
11,9
V2
2,3
1,3
1,4
2,1
2,1
1,3
1,2
2,1
1,5
1,5
V3
1,4
0,6
1
1,7
1,5
0,6
0,75
1,3
1,1
0,7
V4
1,4
0,65
1,1
1,7
1,5
0,45
0,9
1,3
1,1
0,75
V5
0,4
0,65
0,75
1,6
0,5
0,8
0,7
0,45
0,65
0,35
V6
0,75
1,4
1,3
2,3
0,95
1,6
1,6
0,6
1,2
1,2
V7
1,5
1,4
1,7
1,2
1,3
1,5
1,6
1,9
1,7
1,2
V8
1,4
0,75
0,45
2
1,4
1,3
0,35
1,2
0,6
0,7
V9
1,3
0,45
0,95
1,5
1,2
0,4
0,75
1,1
0,9
0,55
27 V10
1,8
1
0,35
2
1,7
0,85
0,14
1
0,55
0,5
V11
0
1
0,85
1,6
0,2
1,2
1,1
0,45
0,75
0,85
V12
1
0
0,5
2
1,3
0,9
0,29
1,1
0,55
0,6
V13
0,85
0,5
0
1,8
0,85
0,9
0,21
0,7
0,11
0,6
V14
1,6
2
1,8
0
1,4
1,3
1,7
2,1
1,8
1,3
V15
0,2
1,3
0,85
1,4
0
1,1
1,3
0,6
0,75
0,65
V16
1,2
0,9
0,9
1,3
1,1
0
0,75
1,1
0,9
0,55
V17
1,1
0,29
0,21
1,7
1,3
0,75
0
0,9
0,3
0,45
V18
0,45
1,1
0,7
2,1
0,6
1,1
0,9
0
0,55
0,7
V19
0,75
0,55
0,11
1,8
0,75
0,9
0,3
0,55
0
0,55
V20
0,85
0,6
0,6
1,3
0,65
0,55
0,45
0,7
0,55
0
V21
1,3
1
0,55
1,9
1,3
1
0,35
1,2
0,6
0,65
V22
0,95
0,28
0,24
1,6
0,9
0,65
0,12
0,85
0,26
0,35
V23
1,1
0,11
0,75
1,5
1,1
0,55
0,6
1
0,75
0,4
V24
1,1
1,3
1,3
0,6
0,9
1
1,2
1,5
1,4
0,7
V25
1,2
0,17
0,35
1,6
1,1
0,6
0,17
1
0,4
0,45
V26
1,5
1,8
1,6
0,8
1,3
0,8
1,5
1,8
1,7
1,1
V27
1,4
0,45
0,65
2,1
1,4
0,9
0,45
1,3
0,7
0,75
V28
1,5
1,7
1,7
2,1
1,3
1,5
1,6
1,9
1,8
1,2
V21
V22
V23
V24
V25
V26
V27
V28
V1
11,6
11,7
9,7
12,4
11,5
12,8
12,3
13
V2
1,3
1,3
1,4
2,1
1,2
1,3
0,75
2,6
V3
0,9
0,8
0,75
1,3
1
1,3
0,29
1,9
V4
1,1
0,85
0,75
1,3
0,8
1,7
0,65
1,8
V5
0,9
0,5
0,65
1
0,7
1
1
1,4
V6
1,7
1,5
1,5
1,8
1,6
2,2
1,9
2,2
V7
1,8
1,5
1,5
0,7
1,6
1,6
1,9
0,1
V8
0,65
0,4
0,9
1,5
0,45
1,8
0,75
1,9
V9
1
0,6
0,6
1,2
0,65
1,3
0,85
1,7
28 V10
0,4
0,21
1,1
1,7
0,23
1,6
0,4
1,6
V11
1,3
0,95
1,1
1,1
1,2
1,5
1,4
1,5
V12
1
0,28
0,11
1,3
0,17
1,8
0,45
1,7
V13
0,55
0,24
0,75
1,3
0,35
1,6
0,65
1,7
V14
1,9
1,6
1,5
0,6
1,6
0,8
2,1
2,1
V15
1,3
0,9
1,1
0,9
1,1
1,3
1,4
1,3
V16
1
0,65
0,55
1
0,6
0,8
0,9
1,5
V17
0,35
0,12
0,6
1,2
0,17
1,5
0,45
1,6
V18
1,2
0,85
1
1,5
1
1,8
1,3
1,9
V19
0,6
0,26
0,75
1,4
0,4
1,7
0,7
1,8
V20
0,65
0,35
0,4
0,7
0,45
1,1
0,75
1,2
V21
0
0,35
0,8
0,8
0,45
1,2
0,6
1,3
V22
0,35
0
0,5
1,1
0,16
1,5
0,45
1,5
V23
0,8
0,5
0
1,3 0,089
1,8
0,35
1,7
V24
0,8
1,1
1,3
0
0,9
0,9
1,2
1,1
V25
0,45
0,16 0,089
0,9
0
2,2
0,7
2,2
V26
1,2
1,5
1,8
0,9
2,2
0
2
3,6
V27
0,6
0,45
0,35
1,2
0,7
2
0
2
V28
1,3
1,5
1,7
1,1
2,2
3,6
2
0
Tentukan rute terpendek yang bisa dilalui kurir tersebut untuk mengirimkan barang dari Kantor JNE ke 27 pelanggan kemudian kembali lagi ke Kantor JNE dengan menggunakan Excel Solver! (Data diperoleh dari skripsinya Dinar Anggit Wicaksana yang berjudul “Solusi Travelling Salesman Problem Menggunakan Algoritma Fuzzy Evolusi” pada halaman 89-94). Jawab: Langkah-langkah untuk menyelesaikan masalah tersebut adalah sebagai berikut: 1. Menuliskan data awal, yaitu data jarak tempuh (km) dari masing-masing titik lokasi ke dalam lembar kerja Microsoft Excel seperti berikut:
29
2. Menuliskan variabel keputusan dan fungsi tujuan seperti berikut:
Nilai pada sel AF2:AF29 diperoleh dengan formula: =INDEX(array; row_num; [column_num])
Nilai pada sel AF30 diperoleh dengan formula: =SUM(AF2:AF29) yaitu total jarak yang dilalui kurir dengan urutan perjalanan: V1-V2-V3-V4-V5-V6-V7-V8-V9-V10-V11-V12-V13-V14-V15-V16-V17-V18-V19V20-V21-V22-V23-V24-V25-V26-V27-V28-V1
3. Klik menu Solver pada tab Data. Akan muncul tampilan Solver Parameters seperti berikut:
30
Pada bagian Set Objective, masukkan sel tujuan (sel AF30).
Pada bagian To, pilih Min untuk meminimalkan total jarak.
Pada bagian By Changing Variable Cells, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel AE2:AE29.
Pada bagian Subject to the Constraints, klik Add. Akan muncul tampilan berikut:
Pada bagian Cell Reference, masukkan referensi sel untuk setiap rentang variabel keputusan, yaitu sel AE2:AE29. Kemudian pada kotak kedua, pilih dif. Secara otomatis kotak ketiga akan muncul tulisan AllDifferent seperti berikut:
31
Kemudian klik OK. Tampilan akan kembali ke bagian Solver Parameters seperti berikut:
Pada bagian Select a Solving Method, pilih Evolutionary.
Kemudian klik Solve. Akan muncul tampilan berikut:
32
4. Memeriksa hasilnya dan melakukan koreksi pada model. Dari tampilan di atas, diperoleh informasi bahwa Solver tidak dapat meningkatkan solusi lagi dikarenakan semua kendala/batasan sudah dipenuhi. Dengan kata lain, sudah diperoleh hasil yang optimal. Pilih Keep Solver Solution, Answer dan centang bagian Outline Report untuk mendapatkan informasi dari hasil pengoperasian Excel Solver. Kemudian klik OK. Akan muncul tampilan berikut:
5. Menganalisis dan menginterpretasikan hasilnya.
33 Dari tampilan di atas, terlihat bahwa sel AE2:AE29 sudah berubah nilainya. Artinya referensi sel untuk setiap rentang variabel keputusan yang ditetapkan di awal bukan merupakan rute terbaik. Akibatnya sel AE2:AE29 sudah digantikan oleh rentang variabel keputusan yang baru, hasil dari proses Solver dan merupakan rute terbaik. Selain itu juga terdapat 1 sheet baru pada lembar kerja, yaitu sheet dengan judul Answer Report 1 seperti berikut:
34
Perubahan yang terjadi pada sel AE2:AE29 juga terlihat pada tampilan tersebut dimana kolom Original Value merupakan referensi sel untuk setiap rentang variabel keputusan yang ditetapkan di awal dan kolom Final Value merupakan rentang variabel keputusan yang baru, hasil dari proses Solver dan merupakan rute terbaik.
35 Dari tampilan tersebut bisa diambil beberapa informasi berikut: a. Waktu yang dibutuhkan untuk proses Solver adalah 171,937 detik. b. Karena titik awal adalah titik pertama (V1), maka rute terpendek adalah V1V12-V23-V25-V17-V13-V19-V22-V20-V5-V18-V6-V11-V15-V28-V7-V24-V14-V26V16-V9-V3-V4-V2-V27-V21-V10-V8-V1 dengan total jarak tempuh 29,689 km. Jadi, rute terpendek yang bisa dilalui kurir tersebut untuk mengirimkan barang dari Kantor JNE ke 27 pelanggan kemudian kembali lagi ke Kantor JNE adalah berangkat dari kantor JNE (V1) menuju tempatnya Ferdinad (V12), kemudian ke tempatnya Ningrum (V23), kemudian ke tempatnya Adi (V25), kemudian ke tempatnya Januar Wahyu (V17), kemudian ke tempatnya Indah Putri (V13), kemudian ke tempatnya Fresma (V19), kemudian ke tempatnya Vani (V22), kemudian ke tempatnya (V20), kemudian ke tempatnya Teta (V5), kemudian ke tempatnya Ida Hanifah (V18), kemudian ke tempatnya Michelle Buison (V6), kemudian ke tempatnya Putri (V11), kemudian ke tempatnya Desy Nourma (V15), kemudian ke tempatnya Elisabet Yania Adriani (V28), kemudian ke tempatnya Anjie Aristianty (V7), kemudian ke tempatnya Yudi Ucil (V24), kemudian ke tempatnya Maulita (V14), kemudian ke tempatnya Esti (V26), kemudian ke tempatnya Awan Djati (V16), kemudian ke tempatnya Elisa Amalia (V9), kemudian ke tempatnya Rendy Risk (V3), kemudian ke tempatnya Agung (V4), kemudian ke tempatnya Zerlin (V2), kemudian ke tempatnya Optik Audhifa (V27), kemudian ke tempatnya Toko Pro Atk (V21), kemudian ke tempatnya Nouva Alesia (V10), kemudian ke tempatnya Betty Ekowati (V8), dan yang terakhir adalah kembali ke kantor JNE (V1) dengan total jarak tempuh 29,689 km. Karena ini merupakan kasus symmetric TSP, maka terdapat rute terpendek yang lain yang juga memiliki total jarak tempuh 29,689 km, yaitu kebalikan arah dari rute yang pertama. Rute tersebut adalah V1-V8-V10-V21-V27-V2-V4-V3-V9-V16V26-V14-V24-V7-V28-V15-V11-V6-V18-V5-V20-V22-V19-V13-V17-V25-V23-V12-V1. Dengan kata lain, kurir bisa berangkat dari Kantor JNE (V1) menuju tempatnya Betty Ekowati (V8), kemudian ke tempatnya Nouva Alesia (V10), kemudian ke tempatnya Toko Pro Atk (V21), kemudian ke tempatnya Optik Audhifa (V27), kemudian ke tempatnya Zerlin (V2), kemudian ke tempatnya Agung (V4), kemudian
36 ke tempatnya Rendy Risk (V3), kemudian ke tempatnya Elisa Amalia (V9), kemudian ke tempatnya Awan Djati (V16), kemudian ke tempatnya Esti (V26), kemudian ke tempatnya Maulita (V14), kemudian ke tempatnya Yudi Ucil (V24), kemudian ke tempatnya Anjie Aristianty (V7), kemudian ke tempatnya Elisabet Yania Adriani (V28), kemudian ke tempatnya Desy Nourma (V15), kemudian ke tempatnya Putri (V11), kemudian ke tempatnya Michelle Buison (V6), kemudian ke tempatnya Ida Hanifah (V18), kemudian ke tempatnya Teta (V5), kemudian ke tempatnya (V20), kemudian ke tempatnya Vani (V22), kemudian ke tempatnya Fresma (V19), kemudian ke tempatnya Indah Putri (V13), kemudian ke tempatnya Januar Wahyu (V17), kemudian ke tempatnya Adi (V25), kemudian ke tempatnya Ningrum (V23), kemudian ke tempatnya Ferdinad (V12), dan yang terakhir adalah kembali ke kantor JNE (V1) dengan total jarak tempuh 29,689 km.
Jawaban pembanding: Dalam kasus yang sama, Dinar Anggit Wicaksana dalam skripsinya yang berjudul “Solusi Travelling Salesman Problem Menggunakan Algoritma Fuzzy Evolusi” menyelesaikan kasus ini menggunakan Algoritma Fuzzy Evolusi dalam bentuk program yang ia buat sendiri menggunakan bahasa pemrogaraman Matlab dan diperoleh rute terpendek dengan total jarak tempuh 35,180 km dengan waktu komputasi 635,698 detik. Hasilnya lebih buruk daripada hasil yang diperoleh dari Excel Solver. Hal ini kemungkinan besar disebabkan karena masih ada kelemahan dari program yang ia buat.
BAB III PENUTUP A. Kesimpulan Berdasarkan hasil yang diperoleh pada pembahasan, maka dapat diambil kesimpulan sebagai berikut: 1. Excel Solver bisa digunakan untuk menyelesaikan kasus Travelling Salesman Problem (TSP). 2. Langkah-langkah untuk mencari rute terpendek menggunakan Excel Solver adalah sebagai berikut: a. Menuliskan data awal. b. Menuliskan variabel keputusan dan fungsi tujuan. c. Klik menu Solver pada tab Data. Akan muncul tampilan Solver Parameters berikut:
Pada bagian Set Objective, masukkan sel tujuan.
Pada bagian To, pilih Min untuk meminimalkan total jarak.
Pada bagian By Changing Variable Cells, masukkan referensi sel untuk setiap rentang variabel keputusan. 37
38
Pada bagian Subject to the Constraints, klik Add. Akan muncul tampilan berikut:
Pada bagian Cell Reference, masukkan referensi sel untuk setiap rentang variabel keputusan. Kemudian pada kotak sebelahnya, pilih hubungan antara referensi sel. Dalam hal ini, pilih dif (different – berbeda) supaya tidak ada variabel keputusan yang bernilai sama. Dengan kata lain, pilih dif supaya masing-masing titik hanya dikunjungi sekali. Kemudian klik OK. Tampilan akan kembali ke bagian Solver Parameters.
Pada bagian Select a Solving Method, pilih Evolutionary.
Kemudian klik Solve.
d. Memeriksa hasilnya dan melakukan koreksi pada model. e. Menganalisis dan menginterpretasikan hasilnya. 3. Hasil yang diperoleh dari Excel Solver merupakan hasil terbaik. 4. Proses Solver tergolong cepat. B. Saran Dalam makalah ini, Excel Solver hanya digunakan untuk menyelesaikan kasus Travelling Salesman Problem (TSP). Bagi pembaca yang tertarik untuk mengkaji penggunaan Excel Solver, pembaca bisa mengkaji Excel Solver untuk menyelesaikan masalah transportasi, masalah penugasan (assignment), masalah aliran maksimum, atau sebagainya. Selain itu, pembaca juga bisa mengkaji varian Travelling Salesman Problem (TSP) yang lain menggunakan Excel Solver, misalnya Travelling Salesman Problem with Time Windows (TSPTW), Clustered Travelling Salesman Problem (CTSP), Multiple Travelling Salesman Problem (MTSP), Dynamic Travelling Salesman Problem (DTSP), dan Travelling Salesman Problem with Precedence Constraints (TSPPC).
DAFTAR PUSTAKA Buana, M.I. (2016). Ant Colony Optimization dalam Penyelesaian Travelling Salesman Problem Menggunakan Matlab. Skripsi Tidak Dipublikasikan. Universitas Negeri Semarang. Budi, W.P.S. (2013). Optimasi Traveling Salesman Problem dengan Algoritma Genetika Menggunakan Operator Partially Matched Crossover. Skripsi Tidak Dipublikasikan. Universitas Islam Negeri Maulana Malik Ibrahim, Malang. Djamaris, A.R.A. (2018). Pemanfaatan Excel-Solver untuk Pengambilan Keputusan. Laporan Pengabdian Kepada Masyarakat. Universitas Bakrie, Jakarta. Ernawati (2017). Implementasi Algoritma Semut untuk Optimasi Rute Terpendek. Skripsi Tidak Dipublikasikan. Universitas Islam Negeri Alauddin, Makassar. Purwananto, Y., D. Purwitasari, & A. W. Wibowo. 2005. Implementasi dan Analisis Algoritma Pencarian rute terpendek di kota Surabaya. Jurnal Penelitian dan Pengembangan TELEKOMUNIKASI, Vol 10 No.2, 94101.
Tersedia
di
http://www.researchgate.net/profile/Diana_Purwitasari/publication/26030 2626_IMPLEMENTASI_DAN_ANALISIS_ALGORITMA_PENCARI AN_RUTE_TERPENDEK_DI_KOTA_SURABAYA/links/53ebcaae0cf 250c8947c6458.pdf?inViewer=1&disableCoverPage=true&origin=publi cation_detail. Sari, F.A., Dwijanto, & Sugiharti E. (2013). Implementasi Algoritma Genetika Untuk Menyelesaikan Travelling Salesman Problem. UNNES Journal of Matematics,
Vol.
2,
No.2,
November
2013.
Tersedia
di
http://journal.unnes.ac.id/sju/ index.php/ujm/article/view/3251. Wicaksana, D.A. (2013). Solusi Travelling Salesman Problem Menggunakan Algoritma Fuzzy Evolusi. Skripsi Tidak Dipublikasikan. Universitas Negeri Semarang.
39
