ABSTRAK
Palupi, Rizki Dinar. 2013. Permasalahan Dynamic Travelling Salesman Problem (D-TSP) dan Implementasi Programnya. Skripsi, Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang. Pembimbing (I). Dra. Sapti Wahyuningsih, MSi, (II). Lucky Tri Oktoviana, S.Si, M.Kom.
Kata Kunci: graph,Dynamic Travelling Salesman Problem (D-TSP), Algoritma Nearest Neighbor Heuristic. Nearest Insertion Heuristic Dynamic Traveling Salesman Problem (D-TSP) merupakan masalah kombinatorial yang kompleks dalam masalah optimal. Pada dasarnya D-TSP adalah pengembangan dari Traveling Salesman Problem (TSP). Bedanya adalah dalam TSP hanya mencari jarak titik tujuan sudah ditentukan dan tetap, D-TSP mencari jarak dan waktu yang sudah ditentukan kemudian titik tujuan tidak tetap sehingga terjadi penambahan titik tujuan maupun pengurangan titik tujuan. Pendeskripsian D-TSP adalah bagaimana cara menemukan penggunaan lintasan minimum dari suatu proses pengiriman barang di mana titik tujuan tersebut dapat berubah sewaktu-waktu. Setiap pelanggan harus dilayani tepat satu setiap pengiriman barang. Diperlukan suatu metode yang lebih baik dari algoritma heuristik untuk menemukan rute minimum suatu graph. Salah satunya adalah Algoritma Nearest Insertion Heuristic dan Nearest Neighbor Heuristic. Langkah pertama pada Algoritma nearest neighbor heuristic pada D-TSP adalah mencari titik awal kemudian cari titik lainnya yang terhubung langsung. Pada pertengahan langkah terdapat penambahan dan pengurangan titik. Pada akhir langkah ini, didapat hasil minimum. Algoritma nearest insertion heuristic pada D-TSP adalah mencari titik awal kemudian cari titik lainnya kemudian terdapat penyisipan titik antara titik yang terhubung langsung tersebut. Pada pertengahan langkah terdapat penambahan dan pengurangan titik. Pada akhir langkah ini didapat hasil sikel minimum. Kedua algoritma di atas bila dibandingkan dalam D-TSP yaitu proses penambahan dan pengurangan titik sedangkan TSP tidak terdapat penambahan dan pengurangan titik pada tengah proses. Untuk menyelesaikan masalah D-TSP dalam proses analisa hasil iterasi yang berbeda dibuatlah program yang menggunakan software Delphi 7. Berdasarkan perhitungan dengan menggunakan Algoritma Nearest Insertion Heuristic dan Nearest Neighbor Heuristic yang dilakukan 50, 60, 70 titik melalui implementasi program diperoleh hasil yang berbeda.
Mengetahui Pembimbing I
Penguji
Pembimbing II
Dra. Sapti Wahyuningsih, M.Si NIP 19621211 1988122001
Dra. Mimiep S. Madja, M.Kom NIP. 19530209 198303 2 001
Lucky Tri Oktoviana, S. Si, M. Kom NIP. 196810031997022001
ABSTRACT
Palupi, Rizki Dinar. 2013. Permasalahan Dynamic Travelling Salesman Problem (D-TSP) dan Implementasi Programnya . Thesis, Mathematics Department, Faculty of Mathematics and Science, State University of Malang. Advisor: (I) Dra. Sapti Wahyuningsih, M.Si, (II) Lucky Tri Oktoviana, S.Si, M.Kom.
Keywords:
graph,Dynamic Travelling Salesman Problem (D-TSP), Nearest Neighbor Heuristic algorithm. Nearest Insertion Heuristic algorithm
Dynamic Traveling Salesman Problem (D-TSP) is a complex combinatorial problems in the optimal problem. Basically D-TSP is the development of a Traveling Salesman Problem (TSP). The difference is in the TSP only find the distance the point has been determined and fixed purpose, D-TSP for distance and time specified then the destination point is not fixed so the addition of a destination point and a destination point reduction. Description of D-TSP is how do I find the use of a minimum track the delivery process in which the destination point can be changed at any time. Each customer must be served exactly one each shipment of goods. Needed a better method of heuristic algorithms to find the minimum of a graph. One is the Nearest Insertion Heuristic Algorithm and Nearest Neighbor Heuristic. The first step on the nearest neighbor heuristic algorithm on D-TSP is to find a starting point and then look for other points that are connected directly. In mid-step addition and subtraction points there. At the end of this step, the results obtained minimum. Nearest insertion heuristic algorithm on D-TSP is to find a starting point and then look for other points then there is the insertion point between the points that are connected directly. In mid-step addition and subtraction points there. At the end of this step the results obtained minimum sikel. Both of the above algorithm when compared to the D-TSP is the process of addition and subtraction while TSP point addition and subtraction there is no point in the middle of the process. To solve the problem of D-TSP in the process of analyzing the results of different iterations made software program that uses Delphi 7. Based on calculations using the Nearest Insertion Heuristic Algorithm and Nearest Neighbor Heuristic performed 50, 60, 70 points through the implementation of the program obtained different results.
Mengetahui Pembimbing I
Penguji
Pembimbing II
Dra. Sapti Wahyuningsih, M.Si NIP 19621211 1988122001
Dra. Mimiep S. Madja, M.Kom NIP. 19530209 198303 2 001
Lucky Tri Oktoviana, S. Si, M. Kom NIP. 196810031997022001
PERMASALAHAN DYNAMIC TRAVELLING SALESMAN PROBLEM IMPLEMENTASI PROGRAMNYA
(D-TSP) DAN
Rizki Dinar Palupi, Sapti Wahyuningsih, Lucky Tri Oktoviana Email.
[email protected]
ABSTRAK Dynamic Traveling Salesman Problem (D-TSP) merupakan masalah kombinatorial yang kompleks dalam masalah optimal. Pada dasarnya D-TSP adalah pengembangan dari Traveling Salesman Problem (TSP). Bedanya adalah dalam TSP hanya mencari jarak titik tujuan sudah ditentukan dan tetap, D-TSP mencari jarak dan waktu yang sudah ditentukan kemudian titik tujuan tidak tetap sehingga terjadi penambahan titik tujuan maupun pengurangan titik tujuan. Diperlukan suatu metode yang lebih baik dari algoritma heuristik untuk menemukan rute minimum suatu graph. Salah satunya adalah Algoritma Nearest Insertion Heuristic dan Nearest Neighbor Heuristic. Kedua algoritma di atas bila dibandingkan dalam D-TSP yaitu proses penambahan dan pengurangan titik sedangkan TSP tidak terdapat penambahan dan pengurangan titik pada tengah proses. Untuk menyelesaikan masalah D-TSP dalam proses analisa hasil iterasi yang berbeda dibuatlah program yang menggunakan software Delphi 7. Kata Kunci: graph,Dynamic Travelling Salesman Problem (D-TSP), Algoritma Nearest Neighbor Heuristic. Nearest Insertion Heuristic ABSTRACT Dynamic Traveling Salesman Problem (D-TSP) is a complex combinatorial problems in the optimal problem. Basically D-TSP is the development of a Traveling Salesman Problem (TSP). The difference is in the TSP only find the distance the point has been determined and fixed purpose, D-TSP for distance and time specified then the destination point is not fixed so the addition of a destination point and a destination point reduction. Needed a better method of heuristic algorithms to find the minimum of a graph. One is the Nearest Insertion Heuristic Algorithm and Nearest Neighbor Heuristic. Both of the above algorithm when compared to the D-TSP is the process of addition and subtraction while TSP point addition and subtraction there is no point in the middle of the process. To solve the problem of D-TSP in the process of analyzing the results of different iterations made software program that uses Delphi 7. Keywords: graph,Dynamic Travelling Salesman Problem (D-TSP), Nearest Neighbor Heuristic algorithm. Nearest Insertion Heuristic algorithm PENDAHULUAN Salah satu model jaringan yang dipakai untuk masalah pendistribusian barang adalah model jaringan Traveling Salesman Problem, yaitu model jaringan untuk setiap dua titik terhubung oleh tepat satu sisi. Model jaringan ini biasanya digunakan untuk menentukan sejumlah rute terpendek yang harus melayani sejumlah customer yang bertujuan untuk meminimalisasikan jarak tempuh. Model Traveling Salesman Problem ini dapat digunakan untuk menyelesaikan berbagai masalah pendistribusian barang dengan berbagai syarat.
Dalam jurnal yang ditulis Lishan Kang (2011:90), Changhe Li (2011:87), dan Farhad Soleimanian Gharechopogh (2012:17), salah satu pengembangan Traveling Salesman Problem adalah Dynamic Travelling Salesman Problem dengan menambahkan batasan waktu atau jarak dalam pendistribusian barang. Pengembangan jaringan ini biasanya dikenal dengan nama Dynamic Traveling Salesman Problem. Model jaringan Dynamic Traveling Salesman Problem ini dapat digunakan untuk mencari jalur terpendek pendistribusian barang dengan batasan waktu atau jarak yang dapat berubah-ubah. Biasanya model jaringan ini dapat diterapkan pada perusahaan-perusahaan yang mengutamakan jarak terpendek pengiriman barang demi kepuasan konsumen. Selain itu, model ini juga dapat digunakan pada perusahaan yang memiliki keterbatasan dalam jarak yang ditempuh. Rute yang diperoleh dengan menggunakan metodemetode tersebut tunggal, sehingga dalam skripsi ini akan diperkenalkan suatu algoritma untuk DTSP yang memberikan solusi tunggal. Tujuan dari artikel ilmiah ini adalah menyelesaikan permasalahan Dynamic Travelling Salesman Problem dengan menggunakan algoritma Nearest Neighbor Heuristic dan Nearest Insertion Heuristic. Menganalisa kelebihan dan kelemahan algoritma Nearest Neighbor Heuristic dan Nearest Insertion Heuristic pada TSP dan D-TSP. Implementasi dan simulasi program menggunakan Borland Delphi 7
METODE Definisi dari Dynamic Traveling Saleman Problem yaitu diberikan n buah kota dan Cij yang merupakan jarak antara kota i dan kota j, seseorang ingin membuat suatu lintasan tertutup dengan mengunjungi setiap kota satu kali. Tujuannya adalah memilih lintasan tertutup yang total jaraknya minimum diantara pilihan dari semua kemungkinan lintasan. Berikut ini adalah bentuk modelnya
Dengan batasan:
Parameter : n = jumlah kota / lokasi / pelanggan yang akan dikunjungi (n tidak termasuk tempat asal yang diindekkan dengan i = 0). Cij = biaya / jarak perjalanan dari kota i ke kota j
A = sepasang sisi (i,j) yang ada. Titik (i,j) yang dimaksud adalah sisi yang ada dari titik i ke titik j.
Definisi 1: D-TSP adalah menentukan TSP dengan perubahan bobot (jarak) dalam bentuk matriks sebagai berikut:
adalah bobot dari titik (kota) ci ke kota cj, dan t adalah waktu sebenarnya. Dalam definisi ini, banyaknya kota n(t) dan matriks bobot bergantung pada waktu. D-TSP adalah menetukan bobot rute minimum yang memuat semua titik yaitu titik n(t) Definisi 2: Diketahui setiap titik n(t) (P1, P2, P3,…,Pn(t) ) dan berkorespondensi pada matriks berbobot , menentukan bobot rute minimum yang memuat seluruh titik n(t), di mana t bergantung pada waktu tertentu; dij bergantung pada bobot antara titik objektif P1 dan titik objektif P2 dan dij(t) = dji(t) Contoh:
Di mana
, maka
,
Dalam definisi satu, terdapat perubahan bobot matriks DTSP dengan proses waktu yang kontinu. Perubahan proses akhirnya D-TSP berubah menjadi sebuah deret masalah optimasi:
k = 0, 1 ,2,…,m-1, dengan waktu [tk, tk+1] di mana
adalah barisan dari waktu yang
diambil sebagai titik sampling. HASIL YANG DIHARAPKAN Perbandingan TSP Nearest Neighbor Heuristic
D-TSP
Iterasi pendek
Iterasi panjang
Tidak dapat dilakukan penambahan
Terdapat penambahan atau pengurangan titik
atau pengurangan titik Nearest Insertion Heuristic
Tidak ada perulangan iterasi
Terjadi perulangan iterasi dari proses awal untuk menentukan rute minimum karena titik yang selalu berubah sehingga butuh waktu perhitungan lebih lama Terdapat penambahan atau pengurangan titik
Tidak dapat dilakukan penambahan atau pengurangan titik
Kelebihan dari algoritma dari Nearest Neighbor Heuristic adalah memiliki iterasi pendek sehingga memberikan hasil optimal untuk menyelesaikan permasalahan optimasi kombinatorial. Oleh karena itu beberapa perjalanan yang menggunakan metode Nearest Neighbor Heuristic dapat dijadikan sebagai rute awal yang dapat menghasilkan perbaikan bagi metode lain. Kelemahan dari algoritma dari Nearest Neighbor Heuristic adalah disaat titik tersebut mencapai titik lebih dari 20 maka proses perhitungannya cukup lama sehingga mengusahakan suatu cara untuk mencari hasil yang baik bukan yang terbaik. Namun demikian, beberapa kota yang tidak terlalu jauh dapat dilewati dan kemudian dikunjungi pada saat akhir yang akibatnya jaraknya berubah menjadi lebih jauh dan biayanya lebih mahal. Kelebihan dari algoritma Nearest Insertion Heuristic untuk proses perhitungan dengan sedikit titik memiliki tingkat hasil yang sama baiknya dengan algoritma Nearest Neighbor Heuristic. Dengan proses penyisipan titik pada dua titik yang terdekat kemungkinan jarak minimal sama dengan algoritma Nearest Neighbor Heuristic Kelemahan dari algoritma Nearest Insertion Heuristic adalah proses iterasi yang terlalu lama dikarenakan banyak titik yang harus disisipkan sehingga proses perhitungannya cukup lama sehingga mengusahakan hasil yang belum optimal. Di mana untuk banyak titik maka didapat pencarian iterasi yang lebih panjang daripada algoritma Nearest Neighbor Heuristic dan total jarak yang didapatkan tidak seoptimal algoritma Nearest Neighbor Heuristic.
PEMBAHASAN Dengan menggunakan aplikasi program Delphi 7 untuk D-TSP pada saat penambahan titik dengan bahasa pemrograman sebagai berikut: procedure TForm1.btTambahClick(Sender: TObject); var i,tNode:Integer; x:real; begin tNode:=node[nN]+1; inc(nN); node[nN]:=tNode; SG.ColCount:=nN+1; SG.RowCount:=nN+1; //tambahkan item ke CB CB1.Items.Clear; for i:=1 to nN do CB1.Items.Add(Char(64+node[i])); drawNode(Image1,Image2,10); SG.Cells[0,nN]:=' SG.Cells[nN,0]:='
'+Char(64+node[nN]); '+Char(64+node[nN]);
for i:=1 to nN do
begin SG.Cells[Nn,i]:='0'; Dengan SG.Cells[i,nN]:='0'; menggunakan aplikasi program Delphi 7 untuk D-TSP pada saat pengurangan titik end; sebagai berikut: end; procedure TForm1.btHapusClick(Sender: TObject); var i,j,idx,tNode:Integer; x:real; begin idx:=CB1.ItemIndex; if (idx
for i:=1 to nN do begin SG.Cells[0,i]:=' '+Char(64+node[i]); SG.Cells[i,0]:=' '+Char(64+node[i]); end; end
Sehingga didapatkan hasil D-TSP untuk 50 titik
SIMPULAN DAN SARAN Pada artikel ilmiah yang dapat diambil dari permasalahan dalam penerapan algoritma Nearest Neighbor Heuritic dan Nearest Insertion Heuristic pada D-TSP dan TSP ini adalah. Pada D-TSP dengan menggunakan algoritma Nearest Neighbor Heuristic ambilah titik awal kemudian saat proses penghapusan titik dipastikan titik tersebut belum terlewati kemudian jika terdapat penambahan titik, pilihlah titik yang terhubung langsung dengan jumlah graph bobot minimum.
Keunggulan Nearest Neighbor Heuristic jika diselesaikan manual menghasilkan solusi yang lebih optimal dibandingkan penyelesaian menggunakan algoritma Nearest Insertion Heuristic. Sedangkan kelemahannya algoritma Nearest Neighbor Heuristic membutuhkan waktu yang lama karena terjadi perulangan iterasi karena ada penambahan dan pengurangan titik. DAFTAR RUJUKAN
Lutfi, Ahmad. 2006. Penerapan Algoritma Cheapest Insertion Heuristic, Farthest Insertion Heuristic, Nearest Insertion Heuristic, Nearest Neighbor Heuristiv pada Travelling Salesman Problem. Skripsi tidak diterbitkan. Malang: Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Negeri Malang.
Kang, Lishan. 2013. Benchmarking Algorithms for Dynamic Travelling Salesman Problems, (online), (http://sc.snu.ac.kr/PAPERS/dynamic_TSP_3.pdf, diakses 5 Februari 2013). Gharehchopogh, Farhad Soleimanian. 2013. A New Approach In Dynamic Travelling Salesman Problem: A Hybrid Of Ant Colony Optimization And Descending Gradient, (online), (http://www.fing.edu.uy/ inco/pedeciba/bibliote/reptec/TR0411.pdf, diakses 6 Februari 2013). Li, Change. 2013. A New Approach to Solving Dynamic Travelling Salesman Problem, (online), (http://www.few.vu.nl/en/Images/werkstuk-singer_tcm39-91434.pdf, diakses 17 April 2013).
