APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALESMAN PROBLEM SKRIPSI WIDYA MAULINA

APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALESMAN PROBLEM

SKRIPSI

WIDYA MAULINA 060823023

PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009

Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALEMAN PROBLEM SKRIPSI Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains


PROGRAM STUDI SARJANA MATEMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2009


PERSETUJUAN Judul

Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas

Komisi Pembimbing

: APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALESMAN PROBLEM : SKRIPSI : WIDYA MAULINA : 060823023 : SARJANA (S1) MATEMATIKA : MATEMATIKA : MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA Diluluskan di Medan, Maret 2009 :

Pembimbing 2

Pembimbing 1

Syahriol Sitorus, S.Si, M.IT NIP.132 174 687

Dra. Mardiningsih, M.Si NIP.130 803 344

Diketahui oleh : Departemen Matematika FMIPA USU Ketua,

Dr. Saib Suwilo,M.Sc NIP. 131 796 149


PERNYATAAN

APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALESMAN PROBLEM

SKRIPSI

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

Medan,

Maret 2009



PENGHARGAAN

Puji dan syukur penulis panjatkan kepada Allah SWT, dengan limpahan dan karuniaNya kertas kajian ini berhasil diselesaikan dalam waktu yang telah ditetapkan. Ucapan terima kasih saya sampaikan kepada Dra. Mardiningsih, M.Si dan Syahriol Sitorus, S.Si, M.IT selaku pembimbing pada penyelesaian skripsi ini yang telah memberikan panduan dan penuh kepercayaan kepada saya untuk menyempurnakan kajian ini. Panduan ringkas, padat dan professional telah diberikan kepada saya agar penulis dapat menyelesaikan tugas ini. Ucapan terima kasih juga ditujukan kepada Ketua dan Sekretaris Departemen Matematika FMIPA USU Dr. Saib Suwilo, M.Sc. dan Drs. Henry Rani Sitepu, M.Si, Dekan dan Pembantu Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, semua dosen pada Departemen Matematika FMIPA USU, pegawai di FMIPA USU, dan rekan-rekan kuliah. Akhirnya, tidak terlupakan kepada kedua orang tua dan semua ahli keluarga dan rekan terdekat saya yang selama ini memberikan bantuan dan dorongan yang diperlukan. Semoga Allah SWT memberikan balasan yang layak.


ABSTRAK

Dynamic programming adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian hingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Dalam tulisan ini membahas tentang penggunaan graph dalam dynamic programming untuk mencari solusi optimal pada Traveling Salesman Problem (TSP). Dengan memberikan sejumlah n kota, TSP dapat didefenisikan perjalanan seorang salesman dalam menemukan jalur terpendek dengan mengunjungi setiap kota yang ada hanya sekali dan kembali ke asalnya dan kemudian diimplementasikan ke dalam suatu program dengan menggunakan Visual Basic 6.0 beserta waktu komputasinya. Hasil dari analisi kota terhadap waktu adalah berbentuk non linier.


ABSTRACT

Dynamic programming is problem solving methode by elaborating solution to become a group of step or stage in such a way finite solution from problem can be looked into from with refer to decision that is each other interconnected. In this articles studies about used of graph in dynamic programming to look for optimal solution at Traveling Salesman Problem (TSP). By giving a number of n city, TSP can be definition walk of a salesman in finding shorthestpath by visiting every cities once and back to source and than implementation into a program by using Visual Basic 6.0 and the time computation. The result of analyze about the city of the time as non linier.


DAFTAR ISI

Halaman Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar

ii iii iv v vi vii viii ix

Bab 1 Pendahuluan 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Tinjauan Pustaka 1.4 Tujuan Penelitian 1.5 Kontribusi Penelitian 1.6 Metode Penelitian

1 1 2 2 4 4 5

Bab 2 Landasan Teori 2.1 Teori Graph 2.2 Graph Hamilton 2.3 Representasi Graph pada Komputer 2.4 Permasalahan Optimasi 2.5 Traveling Salesman Problem 2.5.1 Sejarah Singkat Traveling Salesman Problem 2.6 Dynamic Programming 2.6.1 Model Dynamic Programming 2.6.2 Konsep Dasar Dalam Dynamic Programming 2.6.3 Ciri-ciri Dasar dari Suatu masalah Dynamic Programming

6 6 7 8 9 10 10 12 13 14 16

Bab 3 Pembahasan 3.1 Analisa dynamic Programming 3.2 Perancangan Flowchart 3.3 Perancangan Antar Muka 3.4 Analisa Kebutuhan Perangkat Keras 3.5 Perancangan Perangkat Lunak

18 18 24 25 25 26

Bab 4 Kesimpulan dan Saran 4.1 Kesimpulan 4.2 Saran

33 33 33

Daftar Pustaka Lampiran


DAFTAR TABEL

Halaman Tabel 2.1 Daftar History dari TSP Tabel 3.1 Perhitungan Waktu Antar Kota Tabel 3.2 Hasil Pengujian dengan Black Box


11 31 32

DAFTAR GAMBAR

Halaman Gambar 2.1 Graph dengan Empat vertex Gambar 2.2 Graph Tak-Berarah Gambar 2.3 Graph Berarah Gambar 2.4 Penggambaran Graph Hamilton Gambar 3.1 Graph dengan Empat Vertex Gambar 3.2 Graph dengan Empat Vertex Gambar 3.3 Flowchart dynamic programming pada TSP Gambar 3.4 Form Utama Aplikasi Dynamic Programming Gambar 3.5 Form Utama Gambar 3.6 Form Menu Gambar 3.7 Form Entri Data Graph Gambar 3.8 Form Komputasi jalur Terpendek Gambar 3.9 Form Hasil Komputasi Jalur Terpendek Gambar 3.10 Form Hasil Graph Jalur Terpendek Gambar 3.11 Grafik Waktu Proses Komputasi


6 7 7 8 20 23 24 25 26 27 27 28 29 29 31

BAB 1 PENDAHULUAN

1.1

Latar Belakang

Traveling Salesman Problem (TSP) merupakan salah satu permasalahan penting dalam dunia matematika dan informatika. TSP dapat diilustrasikan sebagai perjalanan seorang salesman yang harus melalui semua kota yang dituju dengan jarak terpendek, dimana setiap kota hanya boleh dilalui satu kali. Solusi dari TSP ialah jalur yang dilalui oleh salesman tersebut. Tentunya solusi terbaik atau optimal dari permasalahan ini ialah jalur dengan jarak terpendek atau dapat disebut juga dengan rute perjalanan minimum.

Penggambaran yang sangat sederhana dari istilah TSP adalah seorang salesman yang harus mengunjungi n buah kota dengan aturan: ia harus mengunjungi setiap kota hanya sebanyak satu kali. Ia harus meminimalisasi total jarak perjalanan dan pada akhirnya ia harus kembali ke kota asalnya. Dengan demikian, apa yang telah ia lakukan disebut sebagai sebuah tour. Guna memudahkan permasalahan, pemetaan n kota tersebut akan digambarkan dengan sebuah graph, dimana jumlah vertex dan edge-nya terbatas (sebuah vertex akan mewakili sebuah kota dan sebuah edge akan mewakili jarak antar dua kota yang dihubungkan). Penanganan problem TSP ini ekuivalen dengan mencari sirkuit Hamilton terpendek.

Dynamic Programming merupakan sebuah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Penemu dan orang yang bertanggung jawab atas kepopuleran dynamic programming adalah Richard Bellman. Pada dynamic programming, rangkaian keputusan optimal yang dibuat dengan menggunakan prinsip optimalitas. Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. Dengan prinsip Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

Optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya. Inti dari pemrograman dinamik adalah membuang satu bagian kecil dari sebuah persoalan dalam setiap langkahnya, kemudian menyelesaikan persoalan yang lebih kecil tersebut dan menggunakan solusi hasil penyelesaian ini untk ditambahkan kembali ke bagian persoalan dalam langkah berikutnya.

Dynamic programming mencoba untuk memberikan solusi yang memiliki pemikiran terhadap konsekuensi yang ditimbulkan dari pengambilan keputusan pada suatu tahap. Dynamic programming mampu mengurangi pengenumerasian keputusan yang tidak mengarah ke solusi. Penerapan pendekatan dynamic programming telah banyak diperlihatkan mampu untuk menyelesaikan aneka masalah seperti: alokasi, muatan (knapsack), capital budgeting, pengawasan persediaan, dan lain-lain.

1.2

Perumusan Masalah

Bagaimana peranan atau pendekatan program dinamik dalam penyelesaian TSP dalam menentukan jalur yang paling optimal dengan jarak total yang paling minimum dengan pendekatan maju (forward atau up-down).

1.3

Tinjauan Pustaka

Muhammad Ghifary (2007 : 2) dalam jurnalnya menjelaskan bahwa ada dua pendekatan yang berbeda dalam dynamic programming yaitu: 1. Maju (forward atau up-down) : bergerak mulai dari tahap 1, terus maju ke tahap 2,3,…,n. urutan variabel keputusan adalah

.

2. Mundur (backward atau bottom-up) : bergerak mulai dari tahap n, terus mundur ke tahap n-1, n-2,…2,1. Urutan variabel keputusan adalah .

Dynamic programming memiliki karakteristik sebagai berikut:


1.

Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan yang optimal.

2.

Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut.

3.

Hasil keputusan yang diambil pada tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.

4.

Jarak pada suatu tahap bergantung pada jarak tahap-tahap sebelumnya dan meningkat secara teratur dengan bertambahnya jumlah tahapan.

5.

Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan tahap sebelumnya.

6.

Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk tahap sebelumnya.

7.

Prinsip optimalitas berlaku pada persoalan ini.

Mohamad Irvan Faradian (2007 : 6) berdasarkan prinsip optimalitas, diperoleh hubungan sebagai berikut: Misalkan G = (V, E) adalah graph lengkap berarah dengan edge-nya yang diberi harga cij> 0 untuk setiap i dan j, dimana i dan j adalah vertex-vertex yang berada di dalam V. Misalkan ⎢V ⎢= n dan n > 1. Setiap simpul diberi nomor 1, 2, …, n.

f (1, V − {1}) = min{c1k + f (k , V − {1, k })} 2≤ k ≤ n

(1)

dimana: f(1, V – {1}) = panjang optimal dari tour V

= himpunan berhingga tidak kosong dari vertex-vertex dari sebuah graph

V – {1}

= himpunan vertex dari suatu graph yang dikurang vertex 1 (awal)

k

= vertex yang terhubung ke vertex 1 (awal) = bobot dari vertex 1 (awal) ke k

dari persamaan (1), diperoleh rincian:


(2) (rekurens)

dimana: f(i, S)

= bobot jalur terpendek

S – {j}

= rangkaian jalur S dikurang vertex j.

i dan j

= vertex-vertex di dalam V = bobot dari vertex i ke j

Asumsikan perjalanan (tour) dimulai dan berakhir pada vertex 1. Setiap tur pasti terdiri dari sisi

untuk beberapa k

V – {1} dan sebuah jalur dari vertex k

ke vertex 1. jalur dari vertex k ke vertex 1 tersebut melalui setiap vertex di dalam V – {1,k} tepat hanya sekali. Misalkan f(i, S) adalah bobot jalur terpendek yang berawal dari vertex i, yang melalui semua vertex di dalam S dan berakhir pada vertex 1. Nilai f(1, V – {1}) adalah bobot tour terpendek.

Dari persamaan (1) dapat diperoleh persamaan (2) jika kita mengetahui f (k, V – {1, k}) untuk seluruh pilihan nilai k. Nilai f tersebut dapat diperoleh dengan menggunakan persamaan (2). Kita menggunakan persamaan (2) untuk memperoleh f(i, S) untuk

, kemudian kita dapat memperoleh f(i, S) untuk

, hingga |S|

= n- 2.

1.4

Tujuan Penelitian

Mengkaji TSP sebagai graph Hamiltonian dengan menggunakan dynamic programming untuk mendapatkan jumlah bobot yang paling minimum dan mengaplikasikannya ke dalam sebuah program.


1.5

Kontribusi Penelitian

Dengan mengaplikasikan dynamic programming pada TSP dapat bermanfaat dalam pengembangan program dinamik lebih lanjut dan diharapkan hasil dari tulisan ini dapat dikembangkan dan direpresentasikan pada lembaga atau perusahaan yang bergerak di bidang Transportasi, Alokasi, Capital Budgeting, dan lain-lain.

1.6

Metode Penelitian

Metode penelitian yang digunakan dalam penelitian ini adalah sebagai berikut: 1. Menggambarkan contoh TSP dalam bentuk graph. 2. Menerapkan dynamic programming untuk penyelesaian TSP. 3. Mengaplikasikan dynamic programming pada TSP ke dalam bahasa pemrograman.


BAB 2 LANDASAN TEORI

2.1

Teori Graph

Graph didefinisikan dengan G = (V, E), di mana V adalah himpunan berhingga tidak dan E himpunan sisi (edges atau arcs)

kosong dari vertex-vertex = yang menghubungkan sepasang vertex

. Vertex dalam graph pada

tulisan ini merupakan kota dan edge atau sisi merupakan rute atau jalan yang menghubungkan antar kota. a

b

c

d

Gambar 2.1. Graph dengan Empat Vertex

Keterangan Gambar: G adalah graph dengan: V = { a, b, c, d } E = { (a, b), (a, c), (a,d), (c, a), (c, d), (b,b), (b, d), (d, b) } = { e1, e2, e3, e4, e5, e6, e7, e8 }

Secara umum graph dapat dibedakan atas dua jenis: 1. Graph tak-berarah (undirected graph) adalah graph yang edge-ya tidak memiliki arah tertentu. Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

Gambar 2.2. Graph Tak-Berarah

2. Graph berarah (directed graph atau digraph) adalah graf yang semua edge-nya memiliki arah tertentu.

Gambar 2.3. Graph Berarah

2.2

Graph Hamilton

Lintasan Hamilton ialah lintasan yang melalui tiap vertex di dalam graph tepat satu kali. Bila lintasan itu kembali ke vertex asal membentuk lintasan tertutup (sirkuit), maka lintasan tertutup itu dinamakan sirkuit Hamilton. Jadi, sirkuit Hamilton ialah sirkuit yang melalui tiap vertex di dalam graph tepat satu kali. Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan yang memiliki lintasan Hamilton disebut graph semi-Hamilton. Teorema 2.1. Setiap graph lengkap adalah graph Hamilton. a

b

a

b

a

b

d

c

d

c

d

c

a

b

c

Gambar 2.4. Penggambaran Graph Hamilton


Keterangan gambar: (a) graph yang memiliki lintasan Hamilton (misal:c, b, a, d) (b) graph yang memiliki sirkuit Hamilton (a, b, c, d, a) (c) graph yang tidak memiliki lintasan maupun sirkuit Hamilton

2.3

Representasi Graph Pada Komputer

Untuk mengimplementasikan suatu graph dalam bahasa pemrograman komputer, dibutuhkan suatu cara untuk menterjemahkan bentuk graph ke dalam bentuk lain yang dikenal oleh komputer, sebab komputer tidak dapat mengenal graph dalam bentuk gambar graph biasa. Matriks dapat digunakan untuk menyatakan suatu graph, jika graph dinyatakan sebagai matriks maka perhitungan-perhitungan yang diperlukan dapat dilakukan dengan mudah. Representasi graph pada komputer dapat dilakukan dengan beberapa cara, yaitu:

1. Matriks Adjacency Matriks adjacency didefinisikan sebagai berikut, misalkan A matriks berordo nxn (n baris dan n kolom). Jika antara dua vertex terhubung (adjacent) maka elemen matriks bernilai 1, dan sebaliknya jika tidak terhubung bernilai 0. Contoh dari matriks adjacency: ⎛0 ⎜ ⎜1 A= ⎜ 1 ⎜ ⎜1 ⎝

1 0 1 1

1 1 0 1

1⎞ ⎟ 1⎟ 1⎟ ⎟ 0 ⎟⎠

Jika graph yang diberikan adalah graph berbobot maka elemen matriks yang terhubung antara vertex adalah bobot graph.

2. Matriks Incidency Matriks incidency atau matriks bersisian adalah matriks yang merepresentasikan hubungan antara vertex dan edge. Misalkan B adalah matriks dengan m baris untuk setiap vertex dan n kolom untuk setiap edge. Jika vertex terhubung dengan Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

edge, maka elemen matriks bernilai 1. Sebaliknya, jika vertex tidak terhubung dengan edge maka elemen matriks bernilai 0. Contoh matriks bersisian adalah: ⎛1 ⎜ ⎜1 B= ⎜ 0 ⎜ ⎜0 ⎝

0 1 1 0

1 0 1 0

1 0 1 0

0 1 0 1

0 0 1 1

0⎞ ⎟ 0⎟ 1⎟ ⎟ 1 ⎟⎠

Seperti halnya matriks kedekatan untuk matriks berbobot, untuk matriks bersisian elemen dari matriks juga merupakan bobot dari setiap edge dari graph.

2.4

Permasalahan Optimasi

Secara umum, penyelesaian masalah pencarian jalur terpendek dapat dilakukan dengan menggunakan dua metode, yaitu metode konvensional dan metode heuristik.

1. Metode Konvensional Metode konvensional adalah metode yang menggunakan perhitungan matematis biasa. Ada beberapa metode konvensional yang biasa digunakan untuk melakukan pencarian jalur terpendek, diantaranya: algoritman Djikstra, algoritma Floyd-Warshall, dan algoritma Bellman-Ford.

2. Metode Heuristik Metode Heuristik adalah sub bidang dari kecerdasan buatan yang digunakan untuk melakukan pencarian dan optimasi. Ada beberapa algoritma pada metode heuristik yang biasa digunakan dalam permasalahan optimasi, diantaranya algoritma genetika, algoritma semut, logika fuzzy, jaringan syaraf tiruan, pencarian tabu, simulated annealing, dan lain-lain.

2.5

Traveling Salesman Problem


TSP merupakan salah satu permasalahan penting dalam dunia matematika dan informatika. TSP dapat diilustrasikan sebagai perjalanan seorang salesman yang harus memulai perjalanannya dari satu kota, melalui setiap kota lainnya hanya sekali dan kembali lagi ke kota asal keberangkatan. Solusi dari TSP ialah lintasan yang dilalui oleh salesman tersebut. Tentunya solusi terbaik atau optimal dari permasalahan ini ialah lintasan dengan jarak terpendek atau dapat disebut juga dengan tour perjalanan minimum. Model TSP dinyatakan dalam bentuk graph, dengan kata lain TSP termasuk ke dalam problem menemukan lintasan atau siklus Hamilton.

Dalam tulisan ini TSP yang dibahas adalah TSP asimetris, dimana TSP asimetris adalah jarak dari kota A ke kota B adalah tidak sama dengan jarak dari kota B ke kota A (asimetris terjadi karena jalan satu arah)(Adhi,2008). Graph yang direpresentasikan sebagai permasalahannya merupakan graph yang terhubung secara penuh artinya pada setiap vertex yang ada pasti terhubung dengan vertex yang lain.

2.5.1

Sejarah Singkat Traveling Salesman Problem

Permasalahan TSP dalam ilmu matematika dilakukan pada tahun 1800 oleh ahli matematika Irlandia William Rowan Hamilton dan ahli matematika Inggris Thomas Penyngton Kirkman, dengan membuat permainan untuk menyelesaikan perjalanan melalui 20 titik dengan menggunakan koneksi yang sudah ditetapkan. Permainan yang disebut game Icosian tersebut tak lain adalah menemukan siklus Hamilton di atas suatu bidang dengan mengunjungi tiap-tiap edge-nya sekali dan akhirnya kembali ke edge awal, suatu permainan yang jelas seperti rumus TSP.

TSP kemudian dipelajari oleh ahli matematika Karl Menger di Vienna, Harvard serta Hassler Whitney and Merrill Flood di Princeton pada tahun 1930 dan menuliskan bentuk umumnya. Karena pertumbuhan algoritma yang semakin meningkat dari tahun ke tahun, mulai tahun 1950 penyelesaian TSP dipecahkan dengan komputer. Tahun 1954 pertumbuhan penting dari TSP diteliti oleh para peneliti yaitu: Dantzig, Fulkerson dan Jhonson yang terus mengembangkan metode baru untuk menyelesaikan permasalahan TSP. Berikut tabel daftar history dari TSP (TSPLIB95, 1995) Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

Tabel 2.1 Daftar History dari TSP Tahun

Tim Periset

Ukuran

1954

G. Dantzig, R. Fulkerson, dan S. Johnson

49 kota

1971

M. Held dan R.M. Karp

64 kota

1975

P.M. Camerini, L. Fratta, dan F. Maffioli

67 kota

1977

M. Grötschel

120 kota

1980

H. Crowder dan M.W. Padberg

318 kota

1987

M. Padberg dan G. Rinaldi

532 kota

1987

M. Grötschel dan O. Holldan

666 kota

1987

M. Padberg dan G. Rinaldi

2.392 kota

1994

1998

2001

2004 2.6

D. Applegate, R. Bixby, V. Chvátal, dan W. Cook D. Applegate, R. Bixby, V. Chvátal, dan W. Cook D. Applegate, R. Bixby, V. Chvátal, dan W. Cook D. Applegate, R. Bixby, V. Chvátal, W. Cook, dan K. Helsgaun

7.397 kota

13.509 kota

15.112 kota

24.978 kota

Dynamic Programming

Dynamic programming adalah teknik manajemen sains yang diaplikasikan kepada persoalan yang melibatkan keputusan yang saling berkaitan. Program ini dikembangkan oleh Richard Bellman dan G. B Dantzig pada tahun 1940 – 1950. Sebagai sebuah konsep, dynamic programming lebih luwes dibanding programprogram optimasi lainnya. Aplikasi dynamic programming telah terbukti baik pada pengelolaam persediaan, jaringan, penjadwalan kerja untuk karyawan, pengendalian produksi, perencanaan penjualan dan bidang lainnya.

Dynamic programming adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

Pada penyelesaian persoalan dengan metode dynamic programming ini terdapat sejumlah berhingga pilihan yang mungkin, solusi pada setiap tahap dibangun dari hasil solusi tahap sebelumnya, kita menggunakan persyaratan optimasi kendala untuk membatasi sejumlah pilihan yang harus dipertimbangkan pada suatu tahap.

Pada dynamic programming, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. Prinsip Optimalitas: jika solusi optimal, maka bagian solusi pada tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k+1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Ongkos pada tahap k+1 = (ongkos yang dihasilkam pada tahap k) + (ongkos dari tahap k ke tahap k+1). Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan yang benar untuk tahap-tahap selanjutnya. 2.6.1

Model Dynamic Programming

Secara umum, model dari dynamic programming dapat dituliskan sebagai berikut: f n ( S n , Dn ) = Rn + f n −1 * ( S n −1 , Dn −1 )

dengan: f ( S n , Dn )

= return pada tahap-n dari nilai status input S n dan keputusan Dn

Sn

= kondisi awal

S n −1

= kondisi akhir

Dn

= keputusan yang dibuat pada setiap tahap

Dn −1

= keputusan pada tahap akhir

Rn

= return function

f n −1 * ( S n −1 , Dn −1 ) = return optimal pada tahap- n − 1 dari nilai status input S n −1 dan keputusan Dn −1


Adapun model dari Dynamic Programming untuk TSP adalah:

f (1, V − {1}) = min{c1k + f (k , V − {1, k})} 2≤ k ≤ n

dengan: f(1, V – {1}) = panjang optimal dari tour V


V – {1}


K

= vertex yang terhubung ke vertex 1 (awal)

C1k

= bobot dari vertex 1 (awal) ke k

2.6.2

Konsep Dasar Dalam Dynamic Programming

Adapun konsep dasar dalam sebuah dynamic programming adalah: a. Dekomposisi Persoalan dynamic programming dapat dipecah-pecah menjadi sub-persoalan atau tahapan yang lebih kecil dan berurutan. Setiap tahap disebut juga sebagai titik keputusan. Setiap keputusan yang dibuat pada suatu tahap akan mempengaruhi keputusan-keputusan pada tahap berikutnya. b. Status Status adalah kondisi awal ( S n ) dan kondisi akhir ( S n −1 ) pada setiap tahap, dimana pada tahap tersebut keputusan dibuat ( Dn ). Status akhir pada sebuah tahap tergantung kepada status awal dan keputusan yang dibuat pada tahap yang bersangkutan. Status akhir pada suatu tahap merupakan input bagi tahap berikutnya.


c. Variabel Keputusan dan Hasil Keputusan yang dibuat pada setiap tahap ( Dn ) merupakan keputusan yang berorientasi kepada return yang diakibatkannya ( Rn | Dn ), tingkat maksimal atau minimal. d. Fungsi Transisi Fungsi transisi menjelaskan secara pasti bagaimana tahap-tahap saling berhubungan. Fungsi ini berbentuk fungsi hubungan antar status pada setiap tahap yang berurutan. Fungsi transisi secara umum berbentuk : S n −1 = S n − Dn Di mana S n −1 = status pada tahap n-1, atau status akhir pada tahap-n. S n adalah status awal pada tahap-n. e. Optimasi Tahap Optimasi tahap dalam dynamic programming adalah menentukan keputusan optimal pada setiap tahap dari berbagai kemungkinan nilai status inputnya. Fungsi umum dari keputusan optimal adalah : f n ( S n , Dn ) = return pada tahap-n

dari nilai status input S n , dan keputusan,

Dn . f n * ( S n ) = return optimal pada tahap-n dari nilai input status S n . f. Fungsi Rekursif Fungsi rekursif biasanya digunakan pada berbagai program komputer, di mana nilai sebuah variabel pada fungsi itu merupakan nilai kumulatif dari nilai variabel tersebut pada tahap sebelumnya. Pada DP, fungsi umum dituliskan sebagai : f n ( S n , Dn ) = Rn + f n −1 * ( S n −1 , Dn −1 ) Prosedur optimasi diawali dari tahap akhir menuju tahap awal (backward).


Karakteristik dynamic programming adalah : 1. Persoalan dapat dipisahkan menjadi beberapa tahap (stages), di mana setiap tahap membutuhkan keputusan kebijakan yang standard dan saling berhubungan.

2. Setiap tahap memiliki sejumlah status (state). Secara umum, sekumpulan status ini merupakan berbagai kemungkinan kondisi yang timbul dari sistem persoalannya. Status ini memberikan informasi yang dibutuhkan setiap keputusan dan dampaknya pada tahap berikutnya. Jumlah status pada setiap tahap bisa definit atau infinit.

3. Setiap keputusan kebijakan yang dibuat pada suatu tahap, status pada tahap tersebut ditransformasi ke dalam status yang berkaitan pada tahap berikutnya. Hubungan antar status pada tahap yang berurutan bisa bersifat deterministik atau probabilistik. Pada sebuah persoalan dengan n-tahap, ada dua input, yaitu : (1) state pada tahap-n ( S n ) dan decision variable ( X n ). Sedang outputnya adalah : (1) return atau akibat dari setiap X n yang dipilih, f n ( S , X n ) ; dan (2) status baru yang menjadi input pada tahap berikutnya ( S n −1 ). Hubungan antara X n dan f n ( S , X n ) ditentukan oleh return function. Sedang hubungan antar status pada tahap tertentu ditentukan oleh transition function.

4. Solusi pada dynamic programming berprinsip kepada optimalitas yang dikembangkan oleh Bellman.

5. Keputusan pada tahap berikutnya bersifat independen terhadap keputusan sebelumnya. Untuk menyelesaikan persoalan dynamic programming, dimulai dari solusi awal pada suatu tahap, dan secara berurutan menuju tahap berikutnya dengan proses yang terbalik (backward induction process).

6. Solusi optimal yang dihasilkan pada setiap tahap berprinsip kepada hubungan dalam bentuk fungsi rekursif (recursion relationship). Secara

umum bentuk

fungsi rekursif adalah : Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

f n * ( S n ) = max/ min{ f n ( S n , X n )} Di mana f n * ( S n ) = adalah hasil optimal dari keputusan pada tahap-n.

2.6.3

Ciri ciri dasar dari suatu masalah dynamic programming

Adapun ciri-ciri dasar dari suatu masalah dynamic programming adalah: 1. Dalam masalah dynamic programming, keputusan tentang suatu masalah ditandai dengan optimisasi pada tahap berikutnya, bukan keserentakan. Ini berarti, jika suatu masalah akan diselesaikan dengan dynamic programming, ia harus dipisahkan menjadi n sub problem. 2. Dynamic programming berkaitan dengan masalah-masalah dimana pilihan atau keputusan dibuat pada masing-masing tahap. Seluruh kemungkinan pilihan dicerminkan, di-atur, oleh sistem status atau state pada setiap tahap. 3. Berkaitan dengan setiap keputusan pada setiap tahap adalah return function yang mengevaluasi pilihan yang dibuat dalam arti sumbangan yang diberikan kepada tujuan keseluruhan (maksimisasi atau minimisasi). 4. Pada setiap tahap proses keputusan dihubungkan dengan tahap yang berdekatan melalui fungsi transisi. 5. Suatu hubungan rekursif digunakan untuk menghubungkan kebijaksanaan optimum pada tahap n dengan n-1. Ada dua macam prosedur rekursif yaitu: a. Foreward recursive equation (perhitungan dari depan ke belakang) b. Backward recursive equation (perhitungan dari belakang ke depan)

Langkah- langkah pengembangan dynamic programming adalah sebagai berikut: 1. Karakteristikkan struktur solusi optimal. 2. Defenisikan secara rekursif nilai solusi optimal. 3. Hitung nilai solusi optimal secara maju atau mundur. 4. Kontruksi solusi optimal.


BAB 3 PEMBAHASAN

3.1 Analisa Dynamic programming

Dynamic programming merupakan metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.

Diberikan sejumlah kota dan jarak antar kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang salesman, bila salesman itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Permasalahan melewati setiap kota tepat satu kali dan kembali ke kota asal adalah meliputi pencarian lintasan terpendek pada sebuah graph Hamilton. Apabila contoh kasus tersebut diubah menjadi persoalan pada graph, maka dapat dilihat bahwa kasus tersebut adalah bagaimana menentukan sirkuit Hamilton yang memiliki bobot minimum pada graph tersebut.

Dalam dynamic programming, diperlukan beberapa variabel dan langkahlangkah untuk menentukan jalur terpendek dengan bobot minimum menggunakan metode forward, yaitu: Misalkan G = (V, E) adalah graf lengkap dengan edge-edge yang diberi harga cij > 0 untuk setiap i dan j adalah vertex-vertex di dalam V. Misalkan ⎢V ⎢= n dan n > 1. Setiap vertex diberi nomor 1, 2, …, n. Asumsikan perjalanan (tour) dimulai dan berakhir pada vertex 1 dan setiap titik saling terhubung. Setiap tur pasti terdiri dari edge (1, k) untuk beberapa k ∈ V – {1} dan sebuah jalur dari vertex k ke vertex 1. Jalur dari vertex k ke vertex 1 tersebut melalui setiap vertex di dalam V – {1, k} tepat hanya sekali. Inisialisasi a. Graph lengkap berarah (G) Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

b. Himpunan berhingga tidak kosong dari vertex-vertex pada sebuah graph (V), V = {1, 2, 3,…n} c. Himpunan edge pada sebuah graph (E) d. Jarak dari i ke j (jarak antar kota) e. Rangkaian jalur (S), S

, dimana

{2, 3, …, n}

f. Bobot jalur terpendek yang berawal pada vertex i yang melalui semua vertex di dalam S dan berakhir pada vertex 1 ( f(i,S) ), i

S dan S

Adapun langkah-langkah dalam penyelesaian TSP dengan dynamic programming adalah sebagai berikut: Langkah 1: Menentukan basis dari graph Hamilton yang telah direpresentasikan menjadi sebuah matriks adjacency dengan persamaan:

f (i , ∅ ) = c

i ,1

, 2≤i≤n

Langkah 2: Hitung f(i, S) untuk ⎢S ⎢= 1, kemudian kita dapat memperoleh f(i, S) untuk ⎢S ⎢= 2, hingga |S| = n- 1. Dengan persamaan:

f (i , S ) = min{c + f ( j , S − { j})} j ∈S

ij

dengan: f(i, S)

= bobot jalur terpendek

S – {j}

= rangkaian jalur S dikurang vertex j.

i dan j

= vertex-vertex di dalam V = bobot dari vertex i ke j

Langkah 3: Setelah diperoleh hasil dari langkah 3, kemudian hitung persamaan hubungan rekursif:

f (1, V − {1}) = min{c1k + f (k , V − {1, k})} 2≤ k ≤ n


dengan: f(1, V – {1}) = panjang optimal dari tour V


V – {1}


k

= vertex yang terhubung ke vertex 1 (awal) = bobot dari vertex 1 (awal) ke k

Langkah 4: Setelah menghitung persamaan rekursif pada langkah 3,akan diperoleh bobot jalur terpendek, maka untuk memperoleh solusi optimal / panjang jalur terpendek untuk sebuah graph adalah dengan menghitung f(1, {2, 3, 4,…, n}) yang artinya adalah panjang jalur dari vertex awal (1) menuju vertex 1 setelah melewati vertex 2, 3, 4,.., n dengan urutan apapun (dicari yang minimum) kemudian cari pembentuk dari solusi optimal minimum yang telah diperoleh.

Berikut contoh penyelesaian TSP dengan menggunakan dynamic programming. Diketahui sebuah graph lengkap berarah, dengan persoalan TSP untuk n = 4. Rangkaian jalur {2, 3, 4}. Dapat dilihat pada gambar 3.1. berikut 12

1 9

8 16

4

2

15 10 11

15

11 14 17 18

3

Gambar 3.1. Graf dengan Empat Vertex

Berikut Jarak dari i ke j (jarak antar kota)

, dimana

yang dirubah

dalam bentuk matriks:


Berikut langkah-langkah penyelesaiannya: Langkah 1:

f (i , ∅ ) = c

Hitung

i ,1

, 2≤i≤n

Diperoleh:

f ( 2, ∅ ) = c 21 = 15

f (3, ∅) = c 31 = 8 f (4, ∅) = c41 = 9 Langkah 2: Untuk |S| = 1, Hitung

f (i , S ) = min{c + f ( j , S − { j})} j ∈S

ij

Diperoleh:


Untuk |S| = 2, hitung

f (i , S ) = min{c + f ( j , S − { j})} j ∈S

ij

Diperoleh:

= min{15 + 27, 10 + 25} = min{42, 35} = 35

= min{14 +19, 27 + 11} = min{33, 38} = 33

= min{11 + 22, 17 + 29} = min{33, 46} = 33 Langkah 3: Dengan menggunakan persamaan,

f (1, V − {1}) = min{c1k + f (k , V − {1, k})} 2≤ k ≤ n

diperoleh:

= min {12 + 35, 11 + 33, 16 + 33} = min {47, 44, 49} = 44 Jadi, bobot jalur terpendek yang berawal dan berakhir di vertex 1 adalah 44. Langkah 4: Untuk mengetahui jalur yang dilalui, mula-mula diketahui bahwa nilai 44 yang merupakan nilai minimum didapatkan dari 11 + 33. Berarti jalur terpendek adalah , diperoleh bahwa bagian awal dari jalur adalah 1-3. Kemudian cari tahu komponen pembentuk adalah

yang menghasilkan nilai minimum ternyata

. Maka diketahui bahwa edge 3-2 adalah bagian dari jalur


terpendek. Dengan cara yang sama, ditelusuri pembentuk adalah

yang ternyata

. Edge 2-4 ternyata juga bagian dari solusi jalur terpendek.

Langkah terakhir adalah menelusuri pembentuk

yang ternyata adalah

(berarti edge 4-1 juga bagian dari jalur terpendek). Hanya dengan merangkai edgeedge yang ditemukan (edge 1-3, 3-2, 2-4, 4-1)dari depan ke belakang. Berarti jalur terpendek adalah 1→3→2→4→1 dengan jumlah bobot minimum 44. Dapat dilihat pada gambar berikut (edge yang bercetak tebal merupakan jalur terpendek):

12

1

15

2

16 9

11 10

416

18

11 14 15 8 143

17

Gambar 3.2 Graf dengan Empat Vertex


3.2 Perancangan Flowchart

Gambaran secara umum proses yang terjadi dalam menyelesaikan permasalahan TSP dalam menentukan jalur terpendek dengan bobot minimum yaitu :

Mulai

Gambar dari node i ke j

Input nilai

tidak

Validasi matriks jarak ya Hitung

f (i , ∅ ) = c

i ,1

, 2≤i≤n

Hitung persamaan rekursif untuk |S|=1…n-1

Hitung hubungan rekursif

Identifikasi pembentuk jalur dengan bobot terpendek

Tampilkan Hasil

Selesai

Gambar 3.3 Flowchart dynamic programming pada TSP


3.3

Perancangan Antar Muka

Rancangan antar muka dari dynamic programming menggunakan visual basic. Gambar 3.4 adalah tampilan dari aplikasi dynamic programming. Aplikasi terdiri dari beberapa bagian yaitu menu, form graph dan form hasil. Dynamic Programming Graph Matriks Jarak

Editor

Graph

Hasil

Gambar 3.4 Form Utama Aplikasi Dynamic Programming

3.4

Analisa Kebutuhan Perangkat Keras

Perangkat keras yang digunakan untuk menguji implementasi dari dynamic programming ini pada TSP adalah sebagai berikut : 1. Procesor Pentium IV 1,8D GHz 2. Memory 512 MB 3. Hard Disk 40 GB 4. O/S Windows XP 5. Mouse 6. Keyboard


3.5 Perancangan Perangkat Lunak Implementasi dari dynamic programming untuk penyelesaian TSP pada tulisan ini diaplikasikan dalam bahasa pemrograman Visual Basic 6.0. Aplikasi dari dynamic programming ini dibatasi hanya pada pencarian jalur terpendek dari data graph yang diinput oleh user. Tampilannya terdiri dari beberapa form yang memiliki fungsi masing-masing yang tampil sesuai dengan urutan yang telah diprogram. 1. Halaman Utama

Pada halaman utama terdapat dua menu yaitu keluar dan graph. Tampilan halaman utama dapat dilihat pada Gambar 3.4.

Gambar 3.5. Form Utama


Gambar 3.6. Form Menu 2. Form Graph

Form graph merupakan form yang digunakan untuk menggambar graph. Data graph diinput oleh user dengan cara menentukan vertex dan edge. Data graph juga bisa disimpan dan dibuka dalam bentuk file dengan ekstension *.tzr, sehingga mempermudah ketika data graph dibutuhkan kembali. Jumlah vertex yang dapat dirun untuk n= 100. Berikut tampilan dari form graph dengan input n=10.

Gambar 3.7. Form Entri Data Graph


3. Form Matriks Jarak

Form matriks jarak merupakan form yang digunakan untuk memasukkan jarak ke dalam matriks. Data matriks diinput oleh user . Berikut tampilan dari form matriks jarak dengan input n=10.

Gambar 3.8. Form Komputasi Jalur terpendek


4.

Form Hasil

Form hasil merupakan form untuk melakukan proses komputasi mencari jalur optimal minimum sekaligus menampilkan waktu komputasi. Berikut tampilan dari form hasil.

Gambar 3.9. Form Hasil Komputasi Jalur Terpendek

Gambar 3.10. Form Hasil Graph Jalur Terpendek Widya Maulina : Aplikasi Pendekatan Dynamic Programming Pada Traveling Salesman Problem, 2009 USU Repository © 2008

5.

Coding untuk Dynamic Programming

Berikut adalah coding untuk penyelesaian TSP dengan dynamic programming yang ditulis dengan Microsoft Visual Basic 6.0.

1. Input Matriks Jarak For i = 1 To Me.flxMap.Rows - 1 For j = 1 To Me.flxMap.Cols - 1 jarak(i, j) = flxMap.TextMatrix(i, j) If jarak(i, j) = 0 Then visib(i, j) = 0 ' Else visib(i, j) = Round(1 / jarak(i, j), 2) End If Next Next

2. Penentuan Jalur Terpendek function TSP(G(),n) for k = 2 to n C(i,k),k)=d(1,k) next for s=3 to n for a= ubound(s) to lbound(s0 for b= ubound(k()) to lbound(k()) if k(b)=s(b) the C(a,b)=min(m(c(s-{k(b)),a)+d(a,b) for c = ubound(k) to lbound(k) optimal=min(c,k + d(b,a) next end if next next

end function


6. Hasil Analisis

Setelah dynamic programming diimplementasikan dalam bahasa pemrograman, kemudian diuji dengan masukan beberapa jumlah kota untuk mendapatkan jalur terpendek dengan bobot minimum. Dari pengujian yang dilakukan dapat dilihat perbandingan waktu pada proses komputasi dengan masukan kota yang berbeda. Pengujian dilakukan pada spesifikasi komputer yang penulis gunakan, hasil waktu proses algoritma tidak selalu sama pada jenis komputer yang berbeda. Tabel 3.1. Perhitungan Waktu antar Kota Jumlah Kota 5 10 15 20 25 30

Waktu Proses (Detik) 0.016 0.047 0.153 0.442 0.716 0.890

Hasil pengukuran terhadap waktu proses dari metode dynamic programming ini ditunjukkan pada grafik berikut:

Gambar 3.11 Grafik Waktu Proses Komputasi


7. Analisis Berdasarkan Regresi

Regresi adalah bagian ilmu statistik yang mempelajari data berpasangan yang terdiri atas satu variabel takbebas dan minimal satu variabel bebas. Ada dua jenis persamaan regresi, yaitu regresi linier dan regresi non linier. Persamaan regresi linier adalah persamaan matematik yang memungkinkan peramalan nilai suatu peubah takbebas (dependent variable) dari nilai peubah bebas (independent variable).

Berdasarkan data grafik waktu proses, dilakukan pengujian untuk menghitung persamaan regresi dengan menggunakan aplikasi SPSS diperoleh model non linier eksponensial. (Data tabel SPSS terdapat pada halaman lampiran). 8.

Pengujian Perangkat Lunak dengan Black Box

Pada bagian ini akan dibahas mengenai pengujian terhadap Perangkat Lunak .Pengujian perangkat lunak dilakukan dengan pengujian secara black box. Pengujian ini menggunakan beberapa kasus, seperti pada tabel di bawah ini : No

Pengujian

Hasil Pengujian

1

Graph tidak ada

Masukkan graph

2

Jika (i,j) ={ }

Kalkulasi jarak gagal

3

(i,j) = text

Kalkulasi jarak gagal

4

Nilai jarak (i,j) = jarak (j,i)

Input jarak gagal

5

Titik awal = {} (kosong)

Pencarian rute gagal


BAB 4 KESIMPULAN DAN SARAN

4.1 Kesimpulan

Berdasarkan hasil penelitian mengenai dynamic programming dalam penyelesaian kasus TSP dapat disimpulkan bahwa: 1.

Pada penyelesaian TSP dengan dynamic programming mampu menghasilkan rute optimal yaknni jalur terpendek beserta panjang rute optimal dan dynamic programming mampu mengurangi pengenumerasian keputusan yang tidak mengarah ke solusi.

2.

Dari hasil analisis ternyata untuk 5, 10, 15...30 kota, diperoleh fungsi waktu terhadap banyaknya kota berbentuk non linier.

4.2 Saran

Sebagai saran yang ditujukan kepada pembaca yang ingin menyelesaikan persoalan TSP dengan menggunakan dynamic programming, agar dapat mengembangkan metode ini lebih luas lagi. Disini penulis hanya menyelesaikan dalam cakupan kecil yang dapat dikerjakan secara manual. Untuk itu penulis berahap agar pembaca dapat menyelesaikan persoalan TSP yang lebih kompleks dalam cakupan besar.


DAFTAR PUSTAKA

Adhi, Wahyu A.2008. Studi dan Implementasi Graf Bandung: Informatika ITB.

dalam Penentuaan Rute.

Evans. J. R. dan Minieka. E. 1992. Optimization Algorithms for Network and Graph. Marcel Dekker, Inc Irfan, Mohamad Faradin. 2007. Penerapan Penggunaan Algoritma Genetika dengan Algoritma Konvensional pada Traveling Salesman Problem. Bandung: Informatika ITB Kusuma, Dian Ningtyas, Vina Evania dan Ernastusi. 2008. Evaluasi Kinerja Algoritma Traveling Salesman Problem dengan Teknik Pemrograman Dinamik. Depok: Universitas Gunadarma. Minoux, M. 1986. Mathematical Programming Theory and Algorithms. John Wiley & Sons Ltd. Munir, Rinaldi. 2001. Matematika Diskrit . Bandung: Informatika ITB. Setiadi, Robert. 2008. Algoritma itu Mudah. Jakarta: PT Prima Infosarana. Simonetti, N. 1998. Applications of a Dynamic Programming Approach to the Traveling Salesman Problem. USA. www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/tsp/All-tsp.tar.gz. diakses tanggal 12 Desember 2008


APLIKASI PENDEKATAN DYNAMIC PROGRAMMING PADA TRAVELING SALESMAN PROBLEM SKRIPSI WIDYA MAULINA

Recommend Documents