PENYELESAIAN STACKER CRANE PROBLEM DENGAN ALGORITME LARGEARCS DAN SMALLARCS

1

PENYELESAIAN STACKER CRANE PROBLEM DENGAN ALGORITME LARGEARCS DAN SMALLARCS

HARDONO

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2013

2

ABSTRAK HARDONO. Penyelesaian Stacker Crane Problem dengan Algoritme Largearcs dan Smallarcs. Dibimbing oleh FARIDA HANUM dan TONI BAKHTIAR. Rural Postman Problem (RPP) merupakan permasalahan dalam pencarian rute terpendek dengan biaya minimum dan hanya sebagian sisi atau sisi berarah diperlukan saja yang harus dilewati. Salah satu jenis RPP ialah Stacker Crane Problem (SCP), yaitu RPP pada graf campuran yang harus melewati setiap sisi berarah. SCP dapat diselesaikan menggunakan dua macam algoritme heuristik, yaitu algoritme Largearcs dan algoritme Smallarcs yang dalam langkahlangkah penyelesaian juga memerlukan beberapa algoritme lain. Penentuan path terpendek diselesaikan dengan algoritme Dijkstra, penentuan minimum bipartite matching diselesaikan dengan metode Hungaria, penentuan minimum spanning tree diselesaikan dengan algoritme Prim, dan sirkuit Euler ditentukan dengan algoritme van Aardenne-Ehrenfest & de-Bruijn dan algoritme Fleury. Untuk menyelesaikan masalah SCP perlu dipilih sirkuit Euler terpendek dari dua algoritme heuristik yang digunakan. Contoh aplikasi SCP dalam karya ilmiah ini adalah penentuan rute pengiriman katering dengan jarak minimum. Kata kunci: Stacker Crane Problem, Largearcs, Smallarcs, sirkuit Euler, jarak minimum

3

ABSTRACT HARDONO. The Solution of Stacker Crane Problem using Largearcs and Smallarcs Algorithm. Supervised by FARIDA HANUM and TONI BAKHTIAR. In graph theory, the Rural Postman Problem (RPP) aims to determine the shortest route with minimum cost, in which only certain edges or arcs are necessarily traversed. One type of RPP is Stacker Crane Problem (SCP) which deals with a mixed graph but only arcs are necessarily traversed. SCP can be solved by using two heuristic algorithms, i.e. Largearcs and Smallarcs algorithms, which include other algorithms in their steps, such as: Dijkstra algorithm to determine shortest route, Hungaria method to determine minimum bipartite matching, Prim algorithm to determine minimum spanning tree, and van Aardenne-Ehrenfest & de-Bruijn algorithm and Fleury algorithm to determine Euler circuits. The shortest Euler circuit resulted from two heuristic algorithms can be used to find a solution of SCP. The application of SCP is illustrated in establishing the minimum distance route of catering delivery. Keywords: Stacker Crane Problem, Largearcs, Smallarcs, Euler circuit, minimum distance

4

PENYELESAIAN STACKER CRANE PROBLEM DENGAN ALGORITME LARGEARCS DAN SMALLARCS

HARDONO

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR 2013

5

Judul Skripsi Nama NIM

: Penyelesaian Stacker Crane Problem dengan Algoritme Largearcs dan Smallarcs : Hardono : G54080026

Menyetujui Pembimbing I,

Pembimbing II,

Dra. Farida Hanum, M.Si. NIP: 19651019 199103 2 002

Dr. Toni Bakhtiar, M.Sc. NIP: 19720627 199702 1 002

Mengetahui: Ketua Departemen,

Dr. Berlian Setiawaty, M.S. NIP: 19650505 198903 2 004

Tanggal Lulus:

6

KATA PENGANTAR Puji syukur penulis panjatkan kepada Allah swt atas berkat, rahmat dan kasih sayang-Nya sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga banyak sekali orang yang membantu dan berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1. keluarga tercinta: Alm. Bapak dan Alm. Ibu yang pasti selalu mendoakanku, kakakku Mas Ismail dan Mbak Woro (terima kasih atas doa, dukungan, kesabaran, kasih sayang, dan motivasinya), Mbak Resti, Mas Taufan, Mbak Mulyati (terima kasih atas doa, semangat, motivasi dan dukungannya), Fenny Risnita (terima kasih atas kasih sayang, dan doanya), 2. Dra. Farida Hanum, M.Si. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, semangat dan doa, 3. Dr. Toni Bakhtiar, M.Sc. selaku dosen pembimbing II yang telah memberikan ilmu, kritik dan saran, motivasi serta doanya, 4. Drs. Siswandi, M.Si. selaku dosen penguji yang telah memberikan ilmu, saran dan doanya, 5. semua dosen Departemen Matematika, terima kasih atas semua ilmu yang telah diberikan, 6. staf Departemen Matematika: Bapak Yono, Ibu Susi, Ibu Ade, Alm. Bapak Bono, Bapak Deni, Mas Hery, Ibu Yanti atas semangat dan doanya, 7. teman-teman satu bimbingan: Nurul, Maya, Ana dan Ali Vikri yang selalu saling mengingatkan dan memberi motivasi dalam penyusunan skripsi ini, 8. teman-teman mahasiswa Matematika angkatan 45: Herlan, Arbi, Beni, Izzudin, Haryanto, Hendri, Ari, Ridwan, Isna, Santi, Laisanopaci, Regita, Primastuti, Putri, Yunda, Fitryah, Finata, Dewi, Prama, Chastro, Fuka, Ade, Tiwi, Fikri, Irwan, Dimas, Ito, Rianiko, Nova, Dini, Heru, Bram, Kunedi, Khafidz, Irma dan teman-teman lainnya atas doa, dukungan semangatnya serta kebersamaannya selama 3 tahun, 9. kakak-kakak Matematika angkatan 43, dan 44 yang menjadi cermin untuk menjadi pribadi yang lebih baik, 10. adik-adik Matematika angkatan 46 dan 47 yang terus mendukung agar berkembang, 11. Gumatika brilian yang menunjukkan sebuah hal yang baru, 12. semua pihak yang telah membantu dalam penyusunan karya ilmiah ini. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya bidang matematika dan menjadi inspirasi bagi penelitian selanjutnya. Bogor, Januari 2013

Hardono

7

RIWAYAT HIDUP Penulis dilahirkan di Tangerang pada tanggal 11 Mei 1990 dari bapak Lasimun Hadi Atmodjo (Alm) dan ibu Sri Retno Wati (Alm). Penulis merupakan putra bungsu dari tiga bersaudara. Pada tahun 1996 penulis lulus dari TK Tunas Rimba, tahun 2002 penulis lulus dari SD Negeri Kembangan Selatan 01 Pagi, tahun 2005 penulis lulus dari SMP Negeri 105 Jakarta Barat, tahun 2008 penulis lulus dari SMA Negeri 57 Jakarta Barat. Penulis diterima sebagai mahasiswa Institut Pertanian Bogor pada tahun 2008 melalui jalur Undangan Seleksi Masuk IPB (USMI), Tingkat Persiapan Bersama. Pada tahun 2009, penulis memilih mayor Matematika pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Analisis Numerik (S1) pada semester ganjil dan semester pendek tahun akademik 2011-2012 dan 2012-2013. Tahun 2009-2010 dan 2011-2012 penulis mendapatkan beasiswa BBM (Bantuan Belajar Mahasiswa) dari Institut Pertanian Bogor. Penulis aktif dalam organisasi kemahasiswaan di kampus, seperti organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai Staf Divisi Pengembangan Sumber Daya Mahasiswa (PSDM) tahun 2009-2010 dan sebagai Kepala Divisi yang sama pada tahun 2010-2011. Penulis pernah menjadi ketua Masa Perkenalan Departemen untuk angkatan 2010 atau angkatan 47. Penulis juga pernah menjadi panitia dan koordinator di berbagai acara kemahasiswaan.

8

DAFTAR ISI Halaman DAFTAR TABEL ........................................................................................................................ ix DAFTAR GAMBAR ...................................................................................................................

x

DAFTAR LAMPIRAN ................................................................................................................

x

I

PENDAHULUAN 1.1 Latar Belakang .................................................................................................................. 1.2 Tujuan Penulisan ..............................................................................................................

1 1

II LANDASAN TEORI 2.1 Graf dan Digraf ................................................................................................................. 1 2.2 Graf Euler .......................................................................................................................... 7 2.3 Penentuan Path Terpendek dengan Algoritme Dijktra ..................................................... 8 2.4 Penentuan Minimum Bipartite Matching dengan Metode Hungaria ................................. 9 2.5 Penentuan Minimum Spanning Tree dengan Algoritme Prim .......................................... 10 2.6 Penentuan Sirkuit Euler dengan Algoritme van Aardenne-Ehfrenfest - de Bruijn ........... 11 2.7 Penentuan Sirkuit Euler dengan Algoritme Fleury ........................................................... 12 III PENYELESAIAN STACKER CRANE PROBLEM 3.1 Algoritme Preprocess ....................................................................................................... 13 3.2 Algoritme Largearcs ........................................................................................................ 14 3.3 Algoritme Smallarcs ......................................................................................................... 16 IV APLIKASI MASALAH 4.1 Penyelesaian SCP dengan Algoritme Largearcs .............................................................. 20 4.2 Penyelesaian SCP dengan Algoritme Smallarcs ............................................................... 23

V SIMPULAN DAN SARAN 5.1 Simpulan ........................................................................................................................... 25 5.2 Saran ................................................................................................................................. 25 DAFTAR PUSTAKA ............................................................................................................. 26 LAMPIRAN ........................................................................................................................... 27

viii

9

DAFTAR TABEL 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

Halaman Penentuan path terpendek dimulai dari verteks 𝑢0 = 1 ....................................................... 9 Tabel biaya yang berhubungan dengan model penugasan ................................................... 10 Penjelasan setiap verteks pada graf kasus katering di Jakarta Pusat .................................... 20 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣1 ..................................................... 31 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣2 ..................................................... 31 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣3 ..................................................... 32 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣𝑓 ..................................................... 32 Penentuan path terpendek dimulai dari verteks 𝑢0 = 1 ....................................................... 33 Penentuan path terpendek dimulai dari verteks 𝑢0 = 2 ....................................................... 33 Penentuan path terpendek dimulai dari verteks 𝑢0 = 3 ....................................................... 33 Penentuan path terpendek dimulai dari verteks 𝑢0 = 4 ....................................................... 34 Penentuan path terpendek dimulai dari verteks 𝑢0 = 5 ....................................................... 34 Penentuan path terpendek dimulai dari verteks 𝑢0 = 6 ....................................................... 34 Penentuan path terpendek dimulai dari verteks 𝑢0 = 7 ....................................................... 35 Penentuan path terpendek dimulai dari verteks 𝑢0 = 8 ....................................................... 35 Bobot (𝑊𝑖𝑗 ) setiap sisi 𝑖, 𝑗 , dengan 𝑖, 𝑗 ∈ 𝑉(𝐺𝐿𝑆 ) ............................................................. 37

DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33

Halaman Graf .................................................................................................................................... 2 Digraf ................................................................................................................................. 2 Graf berbobot ..................................................................................................................... 2 Graf campuran ................................................................................................................... 2 Graf 𝐺3 ............................................................................................................................... 3 Subgraf dari 𝐺3 .................................................................................................................. 3 Spanning subgraph dari 𝐺3 ................................................................................................ 3 Multigraf ............................................................................................................................. 3 Multidigraf ......................................................................................................................... 3 Digraf balans ...................................................................................................................... 4 Graf lengkap ...................................................................................................................... 5 Graf terhubung ................................................................................................................... 5 Graf tak terhubung ............................................................................................................. 5 Komponen ke-1 dari graf pada Gambar 13 ........................................................................ 5 Komponen ke-2 dari graf pada Gambar 13 ........................................................................ 5 Graf yang terdapat bridge .................................................................................................. 6 Tree .................................................................................................................................... 6 Graf 𝐺7 ............................................................................................................................... 6 Spanning tree dari 𝐺7 ......................................................................................................... 6 Arborescence ..................................................................................................................... 6 Graf 𝐺8 ............................................................................................................................... 6 Spanning arborescence dari 𝐺8 ......................................................................................... 6 Graf bipartite ..................................................................................................................... 7 Graf dengan matching ........................................................................................................ 7 Graf dengan matching perfect ............................................................................................ 7 Graf Euler .......................................................................................................................... 8 Graf berbobot dan tidak berarah ......................................................................................... 9 Graf contoh algoritme Prim ............................................................................................... 11 Minimum spanning tree dari graf pada Gambar 28 ........................................................... 11 Graf untuk contoh algoritme van Aardenne-Ehrenfest - de Bruijn .................................... 11 Spanning arborescence dari digraf 𝐺11 ............................................................................. 11 Pelabelan pada algoritme van Aardenne-Ehrenfest - de Bruijn ......................................... 11 Graf Euler untuk contoh algoritme Fleury ......................................................................... 12

ix

10

34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69

Iterasi pertama: inisialisasi 𝑣0 ........................................................................................... Iterasi kedua: sisi {1,6} dihapus ........................................................................................ Iterasi ketiga: sisi {6,2} dihapus ........................................................................................ Graf terakhir dari algoritme Fleury .................................................................................... Graf 𝐺13 untuk ilustrasi algoritme preprocess ................................................................... Graf 𝐺 ∗ yang diperoleh dari Langkah 1 algoritme preprocess .......................................... Graf 𝐺 ′ yang memenuhi syarat 1 dan 2 ............................................................................. Skema penyelesaian SCP dengan algoritme Largearcs ..................................................... Skema penyelesaian SCP dengan algoritme Smallarcs ..................................................... Skema penyelesaian SCP ................................................................................................... Peta Katering Eco Raos di Jakarta Pusat ........................................................................... Graf kasus Katering Eco Raos di Jakarta Pusat dengan arah pendistribusian katering ...... Subgraf 𝐺𝐴𝐿 ........................................................................................................................ Graf bipartite 𝐺𝐵𝐿 .............................................................................................................. Graf 𝐺𝑀𝐿 ............................................................................................................................ Komponen 𝐾1 dan 𝐾2 ........................................................................................................ Graf 𝐺𝐾 .............................................................................................................................. Graf 𝐺𝐶𝐿 ............................................................................................................................. Graf 𝐺𝐷𝐿 ............................................................................................................................. Spanning arborescence digraf 𝐺𝐷𝐿 .................................................................................... Graf 𝐺𝐷𝐿 yang sudah dilabeli ............................................................................................. Graf kasus Katering Eco Raos di Jakarta Pusat dengan algoritme Largearcs ................... Subgraf 𝐺𝐴𝑆 ........................................................................................................................ Graf 𝐺𝐵𝑆 ............................................................................................................................. Minimum spanning tree pada graf 𝐺𝐵𝑆 .............................................................................. Graf lengkap 𝐺𝐿 ................................................................................................................ Matching perfect minimum dari graf 𝐺𝐿 ............................................................................ Graf 𝐺𝐶𝑆 ............................................................................................................................. Graf 𝐺𝐷𝑆 .............................................................................................................................. Graf 𝐺𝐸 .............................................................................................................................. Spanning arborescence digraf 𝐺𝐸 ...................................................................................... Graf 𝐺𝐸 yang sudah dilabeli .............................................................................................. Graf kasus Katering Eco Raos di Jakarta Pusat dengan algoritme Smallarcs .................... Graf 𝐺 ∗ = 𝑉, 𝐴 ∪ 𝐸 ........................................................................................................ Graf Kasus Katering Eco Raos di Jakarta Pusat ............................................................... Graf lengkap 𝐺𝐿𝑆 ................................................................................................................

12 12 12 12 13 14 14 15 17 18 19 20 20 21 21 21 21 22 22 22 22 23 23 23 23 23 24 24 24 24 25 25 25 30 31 36

DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9 10 11

Halaman Penentuan Minimum Bipartite Matching dengan metode Hungaria ................................. 28 Langkah penentuan minimum spanning tree dengan algoritme Prim ................................ 28 Langkah solusi sirkuit Euler dengan menggunakan algoritme Fleury ............................... 29 Penentuan path terpendek dengan menggunakan algoritme Dijkstra ................................ 30 Penentuan path terpendek pada kasus Katering menggunakan algoritme Dijkstra ........... 31 Penentuan Minimum Bipartite Matching dengan metode Hungaria ................................. 34 Penentuan path terpendek 𝐾1 dan 𝐾2 ................................................................................. 34 Penentuan path terpendek 𝑛𝑖 dan 𝑛𝑗 .................................................................................. 35 Langkah penentuan minimum spanning tree dengan algoritme Prim ................................ 35 Penentuan Matching yang perfect dengan bobot minimum ............................................... 36 Penentuan solusi sirkuit Euler dengan menggunakan algoritme Fleury ............................ 37

x

11

I PENDAHULUAN 1.1 Latar Belakang Teori graf merupakan topik yang banyak mendapat perhatian saat ini karena teori graf dapat diaplikasikan di berbagai bidang. Pada penerapannya, dapat dihubungkan dengan berbagai bidang ilmu dan juga kehidupan sehari-hari seperti masalah transportasi yang bertujuan menentukan jarak atau biaya optimal. Salah satu teori graf yang dikembangkan untuk menyelesaikan masalah transportasi adalah Rural Postman Problem (RPP) yang merupakan kasus khusus dari Chinese Postman Problem (CPP). Eiselt et al. (1995a) menyatakan bahwa CPP bertujuan mencari jarak minimum dalam suatu lintasan dengan kondisi setiap jalur harus dilewati paling tidak satu kali. Jika diharuskan melewati jalur yang telah ditentukan, maka permasalahannya menjadi RPP (Eiselt et al. 1995b). RPP pertama kali diperkenalkan oleh Orloff pada tahun 1974. Dalam jurnalnya (Orloff 1974), disebutkan bahwa RPP merupakan formulasi masalah untuk menentukan biaya minimum yang melintasi setiap jalur yang diperlukan pada suatu lintasan. RPP dengan graf berarah biasanya digunakan untuk lintasan yang memiliki jalur satu arah saja, sedangkan jalur yang memiliki dua arah menggunakan RPP dengan graf tidak berarah. Jika kedua jalur,

baik yang satu arah atau pun dua arah, bisa dilayani secara bersamaan, maka dapat digunakan RPP dengan graf campuran. Contoh aplikasi RPP sangat banyak, di antaranya penentuan rute terpendek penyapuan jalan, pengiriman surat atau barang dengan rute terpendek atau biaya minimumnya, penentuan rute bus sekolah, penentuan rute pengiriman bahan bakar, rute pengiriman katering, dsb. Ada beberapa tema yang dibahas dalam RPP, yaitu undirected RPP, directed RPP, Stacker Crane Problem (SCP), dan Capacitated Arc Routing Problem (CARP). Pada karya ilmiah ini akan dibahas penyelesaian Stacker Crane Problem menggunakan dua macam algoritme heuristik, yaitu Largearcs dan Smallarcs yang bersumber dari Eiselt et al. (1995b). 1.2 Tujuan Penulisan Tujuan dari karya ilmiah ini adalah: 1. menyelesaikan masalah SCP dengan dua macam algoritme heuristik, yaitu algoritme Largearcs dan algoritme Smallarcs, 2. mengaplikasikan masalah SCP ke dalam masalah penentuan rute pengiriman katering.

II LANDASAN TEORI Dalam bab ini akan dibahas beberapa landasan teori yang berkaitan dengan bahasan karya ilmiah ini. 2.1 Graf dan Digraf Teori graf merupakan salah satu dari beberapa bidang matematika yang diketahui dengan pasti awal perkembangannya. Teori ini pertama kali dikenal sejak Euler (1736) mengemukakan penelitiannya tentang masalah jembatan Königsberg. Dua abad kemudian (1936), untuk pertama kalinya dibuat buku tentang teori graf yang ditulis oleh Denes König. Dalam periode yang sangat singkat, teori graf kini mengalami perkembangan yang sangat pesat. (Chartrand & Oellermann 1993)

Definisi 1 (Graf) Suatu graf 𝐺 adalah pasangan terurut 𝑉, 𝐸 dengan 𝑉 adalah himpunan berhingga dan takkosong dari elemen-elemen graf yang disebut verteks (node, simpul) dan 𝐸 adalah himpunan pasangan yang menghubungkan dua elemen subhimpunan dari 𝑉 yang biasa disebut sisi (edge, line). 𝑉 dapat dituliskan 𝑉 𝐺 dan 𝐸 = 𝐸 𝐺 , setiap sisi 𝑢, 𝑣 pada 𝑉 dapat dinotasikan dengan 𝑢𝑣 atau 𝑣𝑢. Banyaknya verteks dari graf 𝐺 disebut order dari 𝐺 dan banyaknya sisi dari graf 𝐺 disebut size dari graf 𝐺. (Chartrand & Zhang 2009)

2

𝐺: e1

v1 e2 v3 e8

e3

e7 v5 e11

v7

v2 e4 v4 e6

e10

v6 e9 v8

e12 e14

e5

e13 v9

Gambar 1 Graf. Pada Gambar 1 diperlihatkan bahwa 𝑉 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 , 𝑣5 , 𝑣6 , 𝑣7 , 𝑣8 , 𝑣9 dan E = {e1, e2, e3, e4, e5, e6, e7, e8, e9, e10, e11, e12, e13, e14} Definsi 2 (Graf berarah/digraf) Digraf atau graf berarah (directed graph) 𝐷 adalah pasangan terurut 𝑉, 𝐴 dengan 𝑉 adalah himpunan takkosong yang hingga, dan 𝐴 adalah himpunan pasangan terurut yang menghubungkan elemen-elemen di 𝑉. Elemen-elemen dari 𝐴 disebut sisi berarah (arc). Notasi sisi berarah secara umum ialah 𝑢, 𝑣 , yaitu sisi berarah dari verteks 𝑢 ke verteks 𝑣. (Chartrand & Zhang 2009) 𝐷: v1 e1 v2

e3

e2 v3 e5

e4 v4

e6

v5

Gambar 2 Digraf. Pada Gambar 2 terdapat contoh sisi berarah, yaitu 𝑣1 , 𝑣3 , 𝑣2 , 𝑣1 , 𝑣3 , 𝑣2 , 𝑣3 , 𝑣5 , 𝑣4 , 𝑣2 , 𝑣4 , 𝑣5 . Definisi 3 (Adjacent dan incident) Misalkan 𝑢 dan 𝑣 verteks pada graf 𝐺. Verteks 𝑣 dikatakan tetangga (adjacent) dari 𝑢 jika ada sisi 𝑒 yang menghubungkan verteks 𝑢 dan 𝑣, yaitu 𝑒 = 𝑢𝑣. Himpunan semua

tetangga dari verteks 𝑣 dinotasikan dengan 𝑁 𝑣 . Jika 𝑒 = 𝑢𝑣 adalah sisi pada graf 𝐺 maka 𝑒 dikatakan incident dengan verteks 𝑢 dan 𝑣. (Chartrand & Zhang 2009) Ilustrasi adjacent dan incident diperlihatkan pada Gambar 1. Verteks 𝑣9 adjacent dengan verteks 𝑣7 dan verteks 𝑣8 , tetapi verteks 𝑣9 tidak adjacent dengan verteks 𝑣5 dan verteks 𝑣6 . Verteks 𝑣9 incident dengan sisi 𝑒13 dan sisi 𝑒14 , tetapi verteks 𝑣6 tidak incident dengan sisi 𝑒1 dan sisi 𝑒2 . Definisi 4 (Graf berbobot) Suatu graf 𝐺 = 𝑉, 𝐸 dikatakan berbobot jika terdapat sebuah fungsi 𝑤 ∶ 𝐸 → 𝑅 (dengan 𝑅 adalah himpunan bilangan real) yang disebut bobot. Setiap bobot 𝑤 𝑢𝑣 dengan 𝑢𝑣 ∈ 𝐸 dinotasikan dengan 𝑤𝑢𝑣 . (Foulds 1992) 𝐺1 : v1

5

4 v4

v2 6

2

v3

Gambar 3 Graf berbobot. Graf 𝐺1 pada Gambar 3 merupakan contoh graf berbobot dengan bobot 𝑤 𝑢𝑣 sebagai berikut: sisi 𝑣1 𝑣2 memiliki bobot 𝑤(𝑣1 𝑣2 ) = 5, sisi 𝑣1 𝑣4 memiliki bobot 𝑤 𝑣1 𝑣4 = 4, dan seterusnya. Definisi 5 (Graf campuran) Graf campuran G = (V, A ∪ E) merupakan graf yang setidaknya memiliki satu sisi berarah dan satu sisi tidak berarah. 𝐴 merupakan himpunan sisi-sisi berarah pada 𝐺 dan 𝐸 merupakan himpunan sisi-sisi tidak berarah pada 𝐺. (Balakrishnan 1997) 𝐺2 : v1

v2

v3

Gambar 4 Graf campuran.

3

Definisi 6 (Subgraf) Graf 𝐻 = (𝑊, 𝐹) adalah subgraf dari 𝐺 = 𝑉, 𝐸 jika 𝑊 𝐻  𝑉(𝐺) dan 𝐹 𝐻  𝐸(𝐺). (Chartrand & Oellermann 1993)

Definisi 8 (Multigraf dan multidigraf) Suatu graf (digraf) dikatakan multigraf (multidigraf) bila graf (digraf) tersebut memiliki lebih dari satu sisi (sisi berarah) yang incident dengan satu pasang verteks. (Foulds 1992)

𝐺3 : Ilustrasi multigraf dapat dilihat pada gambar berikut:

v1 e1

e2

v2

v3

v1

v2

v3

v4

e3 e5

e4

v4

e6 Gambar 5 Graf 𝐺3 .

v5

Gambar 8 Multigraf.

𝐻 :

v1 e1

Gambar 8 merupakan contoh multigraf karena verteks 𝑣3 dan 𝑣4 dihubungkan oleh lebih dari satu sisi. Ilustrasi multidigraf bisa dilihat pada Gambar 9 berikut.

e2 v3

v2 e3

v1

v2

v3

v4

e4 v4 Gambar 6 Subgraf dari 𝐺3 . Definisi 7 (Spanning subgraph) Suatu subgraf 𝐻 dikatakan spanning subgraph dari graf 𝐺 jika semua verteks pada graf 𝐺 terdapat pada subgraf 𝐻. (Vasudev 2006) 𝐻1 ∶

v1 e1 v2 e4

v4

Gambar 9 Multidigraf. Definisi 9 (Derajat/degree) Derajat suatu verteks 𝑣 adalah banyaknya sisi yang incident pada verteks, dan dinotasikan dengan deg G (𝑣) atau deg 𝑣 atau 𝑑(𝑣). (Vasudev 2006)

e2 v3 e5

v5

Gambar 7 Spanning subgraph dari 𝐺3 .

Pada Gambar 8 diperlihatkan bahwa 𝑑(𝑣1 ) = 2, 𝑑(𝑣2 ) = 2, 𝑑 𝑣3 = 𝑑 𝑣4 = 3. Definisi 10 (Graf genap) Suatu graf dikatakan graf genap, jika setiap verteksnya berderajat genap. (Eiselt et al. 1995) Graf 𝐺1 pada Gambar 3, merupakan graf genap karena pada Gambar 3 setiap verteks berderajat genap.

4

Definisi 11 (Derajat masuk/indegree) Pada graf berarah, indegree suatu verteks 𝑣, yang dinotasikan dengan 𝑑 − (𝑣), adalah banyaknya sisi berarah yang berakhir di verteks 𝑣. (Vasudev 2006) Pada Gambar 9 diperlihatkan derajat masuk tiap verteksnya, yaitu 𝑑 − (𝑣1 ) = 𝑑 − (𝑣2 ) = 𝑑 − (𝑣3 ) =1, 𝑑 − (𝑣4 ) = 2. Definisi 12 (Derajat keluar/outdegree) Pada graf berarah, outdegree suatu verteks 𝑣, yang dinotasikan dengan 𝑑 + (𝑣), adalah banyaknya sisi berarah yang dimulai dari verteks 𝑣. (Vasudev 2006) Pada Gambar 9 diperlihatkan derajat keluar tiap verteksnya, yaitu 𝑑 + (𝑣1 ) = 𝑑 + (𝑣2 ) = 𝑑 + (𝑣4 ) =1, 𝑑 + (𝑣3 ) = 2. Definisi 13 (Balans) Suatu digraf dikatakan balans jika setiap verteks 𝑣 pada digraf tersebut memiliki 𝛿 𝑣 = 0, dengan 𝛿 𝑣 adalah selisih dari derajat masuk dengan derajat keluar dari verteks 𝑣. (Diestel 1997) v1

v2

v4

v3

Gambar 10 Digraf balans. Digraf pada Gambar 10 merupakan digraf balans karena setiap verteks 𝑣 memiliki 𝛿 𝑣 = 0. Definisi 14 (Underlying graph) Jika suatu graf didapat dengan cara menghapus semua arah dari sisi berarah pada digraf, maka graf tersebut adalah underlying graph dari digraf. (Vasudev 2006)

dimulai dan diakhiri oleh verteks. Walk yang dimulai dari 𝑣0 dan berakhir di 𝑣𝑛 disebut walk 𝑣0 − 𝑣𝑛 dan walk 𝑊 memunyai panjang 𝑛 karena melalui 𝑛 sisi (tidak harus berbeda). Walk yang sisi-sisinya memiliki orientasi arah disebut directed walk atau walk berarah. (Chartrand & Oellermann 1993) Ilustrasi walk dapat dilihat pada Gambar 1, yaitu W = v1 e1 v2 e4 v4 e6 v6 e10 v5. Ilustrasi walk berarah dapat dilihat pada Gambar 2, yaitu 𝑊𝐵 = 𝑣1 𝑒2 𝑣3 𝑒5 𝑣5 . Definisi 16 (Walk tertutup) Suatu walk pada graf 𝐺 dikatakan tertutup (closed) jika verteks awal dan verteks akhir pada walk tersebut adalah sama. (Foulds 1992) Ilustrasi walk tertutup dapat dilihat pada Gambar 1, yaitu WT = v1 e8 v7 e11 v5 e7 v3 e2 v1 merupakan walk tertutup karena verteksnya dimulai dan diakhiri dengan verteks yang sama. Definisi 17 (Jalur/path) Path adalah walk dengan tidak ada verteks yang diulang. (Chartrand & Oellermann 1993) Ilustrasi path dapat dilihat pada Gambar 1, yaitu 𝑃 = 𝑣1 𝑒2 𝑣3 𝑒7 𝑣5 𝑒10 𝑣6 merupakan path karena tidak ada verteks yang diulang. Definisi 18 (Cycle) Cycle adalah walk tertutup, yang memuat sedikitnya tiga verteks, dan semua verteks pada walk tersebut berbeda. (Foulds 1992) Ilustrasi cycle dapat dilihat pada Gambar 1. CE = v7 e12 v8 e13 v9 e14 v7 merupakan cycle karena tidak ada verteks yang diulang dan verteksnya dimulai di 𝑣7 dan berakhir di 𝑣7 . Definisi 19 (Lintasan/trail) Trail adalah walk dengan tidak ada sisi yang diulang. (Chartrand & Oellermann 1993)

Ilustrasi underlying graph bisa dilihat dari Gambar 3 dan Gambar 10. Graf pada Gambar 3 merupakan underlying graph dari digraf pada Gambar 10.

Ilustrasi trail dapat dilihat pada Gambar 1, yaitu 𝑇𝐼 = v3 e3 v4 e6 v6 e10 v5 e7 v3 e2 v1 merupakan trail karena tidak ada sisi pada 𝑇𝐼 yang diulang.

Definisi 15 (Jalan/walk) Suatu walk W pada graf 𝐺 adalah barisan bergantian antara verteks dan sisi yang

Definisi 20 (Circuit) Circuit adalah trail yang tertutup. (Chartrand & Oellermann 1993)

5

Ilustrasi circuit dapat dilihat pada Gambar 1, yaitu 𝐶𝐼 = v6 e9 v8 e12 v7 e14 v9 e13 v8 e5 v2 e4 v4 e6 v6 merupakan circuit karena tidak ada sisi pada 𝐶𝐼 yang diulang dan merupakan walk tertutup.

v1

Definisi 21 (Graf lengkap) Graf lengkap 𝐺𝑛 adalah graf dengan 𝑛 verteks sehingga terdapat tepat satu sisi yang menghubungkan tiap pasang verteks. (Balakrishnan 1997)

v2

v3

v4

v5

v6 𝐺4 :

Gambar 13 Graf tak terhubung.

v2

v1

v3

v4

Definisi 23 (Komponen graf) Suatu subgraf terhubung yang tidak termuat pada subgraf lainnya yang juga terhubung disebut komponen graf. Banyaknya komponen dari graf 𝐺 dituliskan sebagai 𝑘 𝐺 . (Balakrishnan 1997)

Gambar 11 Graf lengkap. Definisi 22 (Terhubung/connected) Suatu graf 𝐺 = 𝑉, 𝐸 dikatakan terhubung (connected) jika untuk setiap pasang verteks 𝑢 dan 𝑣 di 𝐺, maka 𝑢 dihubungkan dengan 𝑣. Jika terdapat pasangan verteks 𝑢 − 𝑣 di 𝐺 sehingga tidak ada path 𝑢 − 𝑣, maka graf tersebut dikatakan tak terhubung (disconnected). (Chartrand & Oellermann 1993) 𝐺5 :

Graf pada Gambar 13 terdiri atas dua komponen, yaitu 𝐾1 dan 𝐾2 sebagai berikut: 𝐾1 :

v1

v2

v3

Gambar 14 Komponen ke-1 dari graf pada Gambar 13. 𝐾2 :

v1

v4

v5

v3

v2

v6 v5

v4

v6 Gambar 12 Graf terhubung.

Gambar 15 Komponen ke-2 dari graf pada Gambar 13. Definisi 24 (Bridge) Pada graf 𝐺 suatu sisi 𝑒 yang terhubung disebut bridge jika sisi 𝑒 tidak terletak pada suatu cycle di 𝐺 sehingga pada saat sisi 𝑒 tersebut dihilangkan menyebabkan graf 𝐺 menjadi tak terhubung. (Chartrand & Oellermann 1993)

6

𝐺6 : e3

v1

v2

e2

e5

e4

e1

v4 e6

v3

v6

e7

v5

Gambar 16 Graf yang terdapat bridge.

Definisi 27 (Arborescence) Suatu tree yang memiliki verteks 𝑣 yang indegree-nya bernilai 0 (nol), sementara verteks-verteks lainnya memiliki indegree 1 (satu) disebut arborescence. (Balakrishnan 1997) Verteks yang indigree-nya bernilai 0 (nol) pada arborescence disebut akar arborescence.

Pada Gambar 16, sisi 𝑒2 merupakan bridge, karena jika sisi 𝑒2 dihapus, maka graf 𝐺6 menjadi tak terhubung.

v1

Definisi 25 (Tree) Suatu graf yang bersifat connected dan tidak memunyai cycle disebut tree. (Chartrand & Zhang 2009)

v2

v3 v4 Gambar 20 Arborescence.

v1

v2

Tree pada Gambar 20 adalah arborescence dengan verteks 𝑣3 sebagai akar arborescence. Definisi 28 (Spanning arborescence) Spanning tree yang bersifat arborescence disebut spanning arborescence. (Vasudev 2006)

v3 v4

Gambar 17 Tree. Definisi 26 ( Spanning Tree) Suatu spanning tree adalah subgraf yang merupakan tree. (Vasudev 2006)

v2

v1

v3

v2

v4 v1

v5

Gambar 21 Graf 𝐺8 .

v3

v2 v4

v5

Gambar 18 Graf 𝐺7 .

v1

v3

v2

v4 v1

v3

v4

v5

Gambar 19 Spanning tree dari 𝐺7 .

v5

Gambar 22 Spanning arborescence dari 𝐺8 . Tree pada Gambar 22 merupakan spanning arborescence dari graf 𝐺8 pada Gambar 21 dengan akar arborescence di verteks 𝑣1 .

7

Definisi 29 (Graf bipartite) Graf 𝐺 dikatakan bipartite jika 𝑉 𝐺 dapat dipartisi menjadi dua subhimpunan takkosong 𝑉1 dan 𝑉2 sehingga setiap sisi di 𝐺 menghubungkan suatu verteks di 𝑉1 dengan verteks di 𝑉2 . (Chartrand & Oellermann 1993) 𝐺9 :

v1

e1

v2

e4

e2 v3

v4 e3

Gambar 25 Graf dengan matching perfect. v1

v3

v4

v5

V1

V2

v2

Gambar 23 Graf bipartite. Graf 𝐺9 pada Gambar 23 merupakan graf bipartite dengan 𝑉1 = 𝑣1 , 𝑣3 , 𝑣5 dan 𝑉2 = 𝑣2 , 𝑣4 . Definisi 30 (Graf r-regular) Sebuah graf merupakan graf 𝑟-regular, atau graf regular berderajat 𝑟, jika setiap verteks pada graf memiliki derajat 𝑟. (Chartrand & Oellermann 1993) Graf 𝐺4 pada Gambar 11, merupakan graf regular berderajat 3 karena setiap verteks memiliki derajat 3. Definisi 31 (Matching) Matching pada sebuah graf merupakan subgraf 1-regular, yaitu berupa himpunan sisisisi yang tidak adjacent. (Chartrand & Oellermann 1993) v1

e1

v2

e3

e2 v3

e4

v4

e5

v5

Gambar 24 Graf dengan matching. 𝑀 = {𝑒1 , 𝑒4 } adalah salah satu matching pada graf di Gambar 24. Definisi 32 (Matching yang perfect) Graf ber-order 𝑝 yang mempunyai matching berkardinalitas 𝑝/2, maka matching tersebut dikatakan matching yang perfect. (Chartrand & Oellermann 1993)

Graf pada Gambar 25 ber-order 4 dan 𝑀1 = {𝑒1 , 𝑒3 } merupakan matching berkardinalitas 2, sehingga 𝑀1 adalah matching yang perfect. Definisi 33 (Matching berbobot minimum) Matching berbobot minimum merupakan matching dengan jumlah bobot pada sisinya adalah minimum. (Chartrand & Oellermann 1993) Ilustrasi matching yang perfect dapat dilihat pada graf Gambar 3, yaitu 𝑀2 = 𝑣1 , 𝑣2 , 𝑣3 , 𝑣4 dengan bobot 7, 𝑀3 = 𝑣1 , 𝑣4 , 𝑣2 , 𝑣3 dengan bobot 10. Jadi, 𝑀2 adalah matching yang perfect dengan bobot minimum. 2.2 Graf Euler Leonhard Euler (1707-1783) lahir di Swiss. Ia dipandang sebagai salah satu matematikawan terbesar sepanjang masa. Euler menyumbangkan berbagai penemuan penting di berbagai bidang antara lain kalkulus dan teori graf. Graf Euler merupakan salah satu penemuan Euler yang terkenal di bidang teori graf. Berikut ini akan dijelaskan beberapa definisi yang berkaitan dengan graf Euler yang dipakai dalam karya ilmiah ini. Definisi 34 (Lintasan Euler) Lintasan Euler adalah lintasan yang melewati semua sisi pada graf 𝐺3 tepat satu kali. Karena setiap sisi hanya boleh dilewati satu kali, maka lintasan Euler sering juga disebut trail Euler. (Vasudev 2006) Pada Gambar 5 lintasan Euler dari graf 𝐺3 salah satunya ialah EL = v2 e3 v3 e2 v1 e1 v2 e4 v4 e6 v5 e5 v3. Definisi 35 (Sirkuit Euler) Sirkuit Euler adalah lintasan Euler yang tertutup. (Vasudev 2006)

8

Ilustrasi sirkuit Euler bisa dilihat pada Gambar 26. Sirkuit Euler yang diperoleh salah satunya ialah 𝑆𝐸 = v1 e1 v3 e4 v5 e3 v4 e2 v3 e5 v2 e6 v1. v1

e1

e6

e2

v4

v3

v2

e5

e3

e4

v5

Gambar 26 Graf Euler. Definisi 36 (Graf Euler) Graf yang memiliki sirkuit Euler disebut graf Euler. (Vasudev 2006) Ilustrasi graf Euler bisa dilihat pada Gambar 26. Graf pada Gambar 26 merupakan graf Euler, karena graf tersebut memiliki sirkuit Euler. Selanjutnya akan diberikan teoremateorema yang digunakan sebagai dasar pengerjaan karya ilmiah ini. Teorema 1 Suatu graf merupakan graf Euler jika dan hanya jika setiap verteks pada graf tersebut berderajat genap. (Chartrand & Oellermann 1993) Teorema 2 Suatu digraf terhubung yang takkosong adalah digraf Euler jika dan hanya jika d+(vi) = d–(vi) untuk setiap verteks 𝑣𝑖 pada digraf balans. (Chartrand & Oellermann 1993) 2.3 Penentuan Path Terpendek dengan Algoritme Dijkstra Algoritme Dijkstra dapat digunakan untuk mencari path terpendek atau jarak terpendek pada graf atau digraf atau graf campuran yang

tidak berbobot maupun yang berbobot pada graf ber-order 𝑝. Misalkan diberikan graf berbobot 𝐺 = (𝑉, 𝐸) dengan himpunan 𝑉 = {1,2,3, … . 𝑛} dan bobot pada tiap verteksnya taknegatif. Pada setiap langkah dalam algoritme didefinisikan sebuah variabel PARENT(v) yang menyatakan verteks yang mendahului verteks v pada path terpendek 𝑢𝑜 − 𝑣 yang telah diperoleh. Variabel PARENT(v) diperbaharui jika ditemukan path 𝑢𝑜 − 𝑣 yang lebih pendek. Misalkan 𝑆 adalah himpunan semua verteks dari 𝐺 yang jaraknya dengan 𝑢0 sudah diketahui. Langkah–langkah pada algoritme Dijkstra untuk menentukan jarak dari 𝑢0 ke setiap verteks di 𝐺 sebagai berikut: Langkah 1. Inisialisasikan sebuah verteks awal 𝑢0 dengan jarak 𝑙 𝑢0 = 0, (𝑖 ← 0), 𝑆 ← {𝑢0 }, 𝑆 ′ ← 𝑉 𝐺 − {𝑢0 }, dan jarak verteks lainnya 𝑙 𝑣 bernilai ∞ untuk semua 𝑣 ∈ 𝑉 𝐺 − {𝑢0 }, PARENT 𝑣 ← 𝑢0 ; jika 𝑝 = 1, maka proses dihentikan; lainnya, proses dilanjutkan. Langkah 2. Untuk setiap 𝑣 ∈ 𝑆′ sehingga 𝑢𝑖 , 𝑣 ∈ 𝐸 𝐺 , diperiksa: jika 𝑙 𝑣 ≤ 𝑙 𝑢𝑖 + 𝑤 𝑢𝑖 𝑣 , maka proses dilanjutkan; lainnya, 𝑙 𝑣 ← 𝑙 𝑢𝑖 + 𝑤 𝑢𝑖 𝑣 , dan PARENT 𝑣 ← 𝑢𝑖 . Langkah 3. Ditentukan m = min{l(v)| v ∈ 𝑆 ′ }. Jika 𝑣𝑗 ∈ 𝑆 ′ dipilih sebagai verteks dengan 𝑙 𝑣𝑗 = 𝑚, maka 𝑚 adalah jarak antara 𝑢0 dengan 𝑣𝑗 , dan 𝑢𝑖+1 ← 𝑣𝑗 . Langkah 4. Pembaharuan 𝑆 dan 𝑆 ′ , yaitu 𝑆 ← 𝑆 ∪ 𝑢𝑖+1 , dan 𝑆 ′ ← 𝑆 ′ − 𝑢𝑖+1 . Langkah 5. 𝑖 ← 𝑖 + 1. Jika 𝑖 = 𝑝 − 1, maka berhenti. Jika tidak, kembali ke Langkah 2. (Chartrand  Oellermann 1993) Contoh Penggunaan Algoritme Dijkstra Berikut ini contoh penggunaan algoritme Dijkstra pada graf berbobot dan tidak berarah.

9

𝐺10 : 3

6

7 4

7

6

5

8

9 8 10

4 6

4

3

7 7 5 1

6

7

2

9

Gambar 27 Graf berbobot dan tidak berarah. Akan ditentukan jarak terpendek dari satu verteks ke verteks lainnya. Misalkan verteks awalnya adalah verteks 𝑢0 = 1, maka dengan algoritme Dijkstra (penghitungan lebih

Iterasi

l(1)

0 1 2 3 4 5 6 7

0

lengkap dapat dilihat pada Tabel 1) akan diperoleh path terpendek dari verteks 1 menuju verteks lainnya.

Tabel 1 Penentuan path terpendek dimulai dari verteks 𝑢0 = 1 l(2) l(3) l(4) l(5) l(6) l(7) l(8) (∞,–) (9,1) (9,1) (9,1) (9,1) – – –

(∞,–) (7,1) (7,1) – – – – –

(∞,–) (5,1) – – – – – –

Dari Tabel 1, dapat diketahui beberapa path terpendek dari verteks 𝑢0 = 1 ke verteks lainnya. Contohnya path terpendek dari verteks 𝑢0 = 1 menuju verteks 6, yaitu path terpendek 𝑃1 = 1 − 4 − 6 dengan jarak 13, untuk path terpendek dari verteks 𝑢0 = 1 menuju verteks 8 ialah 𝑃2 = 1 − 2 − 8 dengan jarak 16. 2.4 Penentuan Minimum Bipartite Matching dengan Metode Hungaria Misalkan ada 𝑚 karyawan dan 𝑛 pekerjaan. Notasi 𝑖 𝑖 = 1,2, … , 𝑚 menunjukkan karyawan ke-𝑖 dan notasi 𝑗 𝑗 = 1,2, … , 𝑛 menunjukkan pekerjaan ke𝑗. Jika banyaknya karyawan sama dengan banyaknya pekerjaan, maka dengan mempertimbangkan aspek tertentu seperti pengoptimalan profit (keuntungan) yang didapat dari penempatan 𝑚 karyawan terhadap 𝑛 pekerjaan dikenal dengan masalah penugasan optimal. Masalah penugasan

(∞,–) (7,1) (7,1) (7,1) – – – –

(∞,–) (∞,–) (13,4) (13,4) (13,4) (13,4) – –

(∞,–) (∞,–) (14,4) (14,4) (13,5) (13,5) (13,5) –

(∞,–) (∞,–) (∞,–) (17,3) (17,3) (16,2) (16,2) (16,2)

Penambahan S 1 4 3 5 2 6 7 8

(assignment problem) adalah suatu masalah mengenai pengaturan objek untuk melaksanakan tugas, dengan tujuan meminimalkan biaya, waktu, jarak, dan sebagainya ataupun memaksimalkan keuntungan yang salah satu penyelesaiannya menggunakan metode Hungaria. Misalkan graf bipartite, sehingga himpunan karyawan dianggap sebagai 𝑉1 dan himpunan pekerjaan sebagai 𝑉2 . Misalkan 𝑐𝑖𝑗 adalah biaya yang diperlukan ketika karyawan 𝑖 ditugaskan untuk menyelesaikan pekerjaan 𝑗. Untuk mencari solusi dari masalah penugasan optimal yang dinyatakan sebagai graf bipartite adalah dengan menerapkan konsep matching. Tabel 2 memberikan gambaran umum dari model penugasan ini.

10

Karyawan

Tabel 2 Tabel biaya yang berhubungan dengan model penugasan Pekerjaan 2 ⋯

1 2

𝑐11 𝑐21

𝑐12 𝑐22

𝑛 𝑐1𝑛 𝑐2𝑛

⋮ 𝑚

𝑐𝑚 1

𝑐𝑚 2

𝑐𝑚𝑛

1

Metode ini dimulai dengan mengurangi setiap elemen pada baris dengan nilai minimum baris tersebut, kemudian setiap elemen kolom dari tabel yang dihasilkan dikurangi dengan nilai minimum kolom tersebut. Tabel biaya yang dihasilkan akan memuat paling sedikit satu nol pada setiap baris dan kolom. Semua elemen tabel yang dihasilkan bernilai taknegatif. Dengan elemen-elemen nol ini akan ditentukan suatu penugasan yang fisibel (yaitu pada matriks yang dihasilkan tersebut dapat dipilih tepat 1 nol pada setiap baris dan 1 nol pada setiap kolom). Jika itu mungkin maka penugasan itu optimal, karena elemen-elemen biaya adalah taknegatif dan nilai minimum fungsi tujuan lebih kecil daripada nol sehingga suatu penugasan dengan biaya nol adalah optimum. Jika penugasan yang fisibel pada elemenelemen nol tidak diperoleh, maka aturan lebih lanjut diperlukan untuk menemukan penugasan yang fisibel. Aturan tersebut diberikan sebagai berikut: 1 Sejumlah minimum garis yang melalui beberapa baris dan kolom digambarkan sedemikian sehingga menutup semua elemen nol. (Sejumlah minimum garis yang dibutuhkan adalah sama dengan jumlah maksimum pekerja yang dapat ditugaskan dengan menggunakan elemen nol). 2. Pilih elemen minimum yang tidak tertutupi garis, elemen ini dikurangi dengan setiap baris elemen yang tidak tertutupi garis dan ditambahkan ke setiap elemen yang berada di titik potong antara dua garis. Jika solusi optimum tidak ditemukan dalam langkah di atas, prosedur penggambaran garis tersebut harus diulangi sampai satu penugasan yang fisibel diperoleh. Untuk menyelesaikan masalah penugasan dengan tujuan memaksimumkan, masalah diubah ke masalah meminimumkan sebelum diaplikasikan ke metode Hungaria, yaitu dengan cara mengalikan semua elemen 𝑐𝑖𝑗 dari matriks penugasan dengan −1. (Ravindran et al. 1987).

Contoh Penggunaan Metode Hungaria Diberikan tabel biaya sebagai berikut: 1

2

3

1

3

6

8

2

6

4

3

3

1

5

4

Dengan metode Hungaria (Lampiran 1) didapatkan Minimum Bipartite Matching pada tabel berikut.

1

1

2

0

0

3

5

0

0

0

1

1

2 3

3

Tabel terakhir memberikan biaya minimum yang ditunjukkan dengan elemen nol yang diberi kotak, yaitu elemen (1,2), (2,3), (3,1) sehingga diperoleh minimum dari bipartite matching, yaitu himpunan sisi {{1,2}, {2,3}, {3,1}} dengan total biayanya adalah 6 + 3 + 1 = 10. 2.5 Penentuan Minimum Spanning Tree dengan Algoritme Prim Minimum spanning tree adalah spanning tree T yang memiliki bobot atau nilai minimum. Salah satu cara untuk menentukan minimum spanning tree dari suatu graf/digraf adalah dengan menggunakan algoritme Prim. Algoritme Prim membentuk minimum spanning tree dengan langkah per langkah. Pada setiap langkah diambil sisi graf yang memiliki bobot minimum namun yang terhubung dengan spanning tree T yang telah terbentuk. Misalkan diberikan graf dengan banyaknya verteks adalah 𝑛, maka: Langkah 1. Ambil sisi dari graf yang berbobot minimum, masukkan ke dalam T. Langkah 2. Pilih sisi 𝑢, 𝑣 di graf yang memiliki bobot minimum dan adjacent dengan sisi di T. Jika 𝑢, 𝑣 tidak membentuk cycle, maka 𝑢, 𝑣 ditambahkan ke dalam T dan lanjut ke langkah 3. Sebaliknya, jika penambahan sisi 𝑢, 𝑣 membentuk cycle, maka sisi tersebut tidak dipilih dan kembali ke langkah kedua.

11

Langkah 3. Proses memiliki 𝑛 − 1 sisi.

berhenti

jika

T

(Balakrishnan 1997) Contoh Penggunaan Algoritme Prim Diberikan graf berbobot tak berarah sebagai berikut:

Contoh Penggunaan Algoritme van Aardenne-Ehrenfest - de Bruijn Misalkan diberikan digraf balans sebagai berikut: 𝐺11 :

2

1 1

1

2

1 5

2 6

3

5

8

4

3 2

3 3

3 4

2 4

3 3

4 2

6

4

5

Gambar 30 Graf untuk contoh algoritme van Aardenne-Ehrenfest - de Bruijn.

Gambar 28 Graf contoh algoritme Prim. Dengan algoritme Prim (Lampiran 2) didapatkan minimum spanning tree dengan bobot minimum seperti pada gambar berikut:

Langkah pertama yang akan ditentukan adalah penentuan spanning arborescence dari digraf balans tersebut, misalkan diambil spanning arborescence yang berawal di verteks 1 adalah sebagai berikut:

1 1

2

5

2 2

3 3

4

3

1

4

5

6

5

Gambar 29 Minimum spanning tree dari graf pada Gambar 28.

Gambar 31 Spanning digraf 𝐺11 .

2.6 Penentuan Sirkuit Euler dengan Algoritme van Aardenne-Ehrenfest de Bruijn Misalkan 𝐺 = 𝑉, 𝐴 adalah digraf yang balans. Langkah 1. Bentuk sebuah spanning arborescence dari digraf balans yang berakar di 𝑣𝑟 . Langkah 2. Sisi berarah yang keluar dari tiap-tiap verteks diurutkan dan dilabeli, dan sisi berarah yang terakhir dilabeli adalah sisi berarah pada spanning arborescence. Langkah 3. Tentukan sirkuit Euler dengan melintasi tiap-tiap sisi berarah yang telah dilabeli, mulai dari label yang terkecil sampai dengan label terbesar. Proses berhenti jika tiap sisi berarah yang dilabeli telah dilewati. (Eiselt et al. 1995a)

Semua sisi berarah diurutkan dan dilabeli, dengan label terakhir (terbesar) adalah label untuk sisi berarah pada spanning arborescence.

L1 1

L1 L2

L2

2

6

L1

arborescence

3 L1 L1

L2

5

dari

L2 4 L1

Gambar 32 Pelabelan pada algoritme van Aardenne-Ehrenfest - de Bruijn. Sirkuit Euler yang diperoleh, misalkan mulai dari verteks 1, adalah 1-2-6-3-5-2-3-4-5-6-1 dengan total bobot 27.

12

2.7 Penentuan Sirkuit Euler dengan Algoritme Fleury Misalkan 𝐺 = 𝑉, 𝐸 adalah graf terhubung yang semua verteksnya berderajat genap. Langkah 1. Inisialisasikan i = 0. Dimulai dari verteks 𝑣0 dan didefinisikan trail 𝑇0 : 𝑣0 . Langkah 2. Misalkan Ti = v0 e1 v1 e2 v2 e3 ... ei vi sebagai trail dari 𝑣0 ke 𝑣𝑖 pada iterasi ke-𝑖, lalu dipilih sebuah sisi 𝑒𝑖+1 yang menghubungkan 𝑣𝑖 dengan 𝑣𝑖+1 yang bukan merupakan bridge dari himpunan sisi 𝐸𝑖 = 𝐸 − 𝑒1 , 𝑒2 , … 𝑒𝑖 . Jika 𝑒𝑖+1 adalah bridge pada subgraf yang didapat dari 𝐺 setelah menghapus sisi yang dimiliki Ei dari 𝐸, dan tidak ada pilihan lain yang bisa diambil, maka sisi tersebut dimasukkan ke dalam trail 𝑇𝑖 = 𝑣0 𝑒1 𝑣1 𝑒2 𝑣2 𝑒3 … 𝑒𝑖 𝑣𝑖 𝑒𝑖+1 . Jika tidak ada sisi lagi yang bisa dipilih maka proses berhenti. Langkah 3. Kemudian 𝑖 diganti menjadi 𝑖 + 1, lalu kembali ke Langkah 2. Trail yang terbentuk dari urutan sisi yang diambil merupakan sirkuit Euler pada graf 𝐺. (Balakrishnan 1997) Contoh Penggunaan Algoritme Fleury Misalkan diberikan graf seperti pada Gambar 33.

2 1 1

3 2

3 3

4

6

3 3

2

3

4

contoh

3 3

4

v0 3

6

4

5

4

3

6

v1

4 2

5

4

Gambar 35 Iterasi kedua: sisi {1,6} dihapus. 3. dipilih sisi {6,2} yang bukan bridge pada subgraf 𝐺, sehingga graf menjadi seperti pada Gambar 36.

2 1

2

3

3

v2 2

1

4

3

4

v0 v1

6

5

4

2

Gambar 36 Iterasi ketiga: sisi {6,2} dihapus.

v9

2

1

2

3

3

v0

v8

2

Gambar 34 Iterasi pertama: inisialisasi 𝑣0 .

3

v2

v10

3

3

2

Untuk mencari sirkuit Euler pada graf tersebut dengan algoritme Fleury, dilakukan prosedur sebagai berikut: 1. dipilih sembarang verteks, misalkan verteks 1, yang dilabeli sebagai 𝑣0 , 1

1

2

Gambar 33 Graf Euler untuk algoritme Fleury.

2

1

4

5

4

2 2

Iterasi selanjutnya diberikan secara lengkap pada Lampiran 3. Setelah semua sisi dihapus, sehingga dihasilkan graf seperti pada Gambar 37, maka sirkuit Euler sudah bisa ditemukan.

𝐺12 : 2

2. dipilih sisi yang incident dengan 𝑣0 dan bukan merupakan bridge pada graf. Misalkan sisi {1,6} dipilih, lalu sisi tersebut dihapus dan didefinisikan verteks 6 sebagai verteks 𝑣1 , sehingga graf menjadi seperti pada Gambar 35.

v4

v7

1

4

v0

v6

v5 v1

6

v3

Gambar 37 Graf terakhir Fleury.

5

dari

algoritme

Dari urutan verteks yang dipilih dan sisi yang dihapus akan diperoleh solusi sirkuit Euler yang dimulai dari verteks 1, yaitu 1-6-25-3-6-5-4-3-2-1 dengan total bobot 27.

13

III PENYELESAIAN STACKER CRANE PROBLEM Rural Postman Problem (RPP) merupakan permasalahan dalam pencarian rute terpendek dengan biaya minimum dan hanya sebagian sisi atau sisi berarah yang diperlukan saja yang harus dilewati. Misalkan diberikan graf campuran 𝐺 = 𝑉, 𝐴 ∪ 𝐸 dengan 𝐴 himpunan sisi berarah dan 𝐸 himpunan sisi tidak berarah pada graf 𝐺. Misalkan 𝑅 merupakan himpunan sisi berarah yang harus dilewati minimal satu kali (required arc) pada 𝐺, yaitu 𝑅 ⊆ 𝐴 ∪ 𝐸. Selanjutnya, diberikan bobot/nilai untuk setiap sisi berarah 𝑖, 𝑗 dan sisi tidak berarah {𝑖, 𝑗} yang dinotasikan dengan 𝑐𝑖𝑗 . RPP memiliki banyak jenis yaitu URPP (Undirected RPP)/RPP yang tidak berarah, DRPP (Directed RPP)/RPP yang berarah, SCP (Stacker Crane Problem)/RPP dengan graf campuran, dan CARP (Capacitated Arc Routing Problem)/RPP dengan graf berkapasitas. Pada karya ilmiah ini, hanya dibahas kasus SCP (Stacker Crane Problem) saja, yaitu RPP dengan himpunan sisi berarah yang harus dilewati minimal satu kali 𝑅=𝐴 . Stacker Crane Problem (SCP) dapat dinyatakan sebagai permasalahan dalam pencarian rute dengan biaya atau jarak minimum dan diharuskan melewati ruas jalan yang telah ditentukan 𝑅 paling tidak satu kali. Arah sisi berarah dari 𝑅 dapat dilihat sebagai pergerakan yang harus dilakukan oleh sebuah crane dengan arah yang telah ditentukan, masing-masing tepat satu kali. Permasalahan tersebut juga dapat dinyatakan sebagai masalah menemukan sirkuit Euler yang merepresentasikan rute terpendek yang melewati sisi yang telah ditentukan tepat satu kali pada suatu graf Euler. Frederickson et al. (1978) mengajukan dua metode heuristik untuk menyelesaikan SCP dengan ketentuan graf campuran 𝐺 = 𝑉, 𝐴 ∪ 𝐸 memenuhi syarat berikut: Syarat 1. Setiap verteks adalah incident dengan setidaknya satu sisi berarah di A. Syarat 2. Fungsi bobot pada sisi 𝑖, 𝑗 yaitu 𝑐𝑖𝑗 , memenuhi pertidaksamaan segitiga, yaitu 𝑐𝑖𝑗 ≤ 𝑐𝑖𝑘 + 𝑐𝑘𝑗 , ∀ 𝑖, 𝑗, 𝑘 ∈ 𝑉 𝐺 . Apabila graf 𝐺 tidak memenuhi kedua syarat tersebut, algoritme Preprocess akan mengubahnya menjadi graf yang memenuhi kedua syarat Frederickson tersebut.

3.1 Algoritme Preprocess Input : Graf campuran 𝐺 = 𝑉, 𝐸 ∪ 𝐴 dan fungsi bobot 𝑐. Output : Graf campuran 𝐺 ′ = 𝑉 ′ , 𝐸 ′ ∪ 𝐴 memenuhi syarat 1 dan fungsi bobot 𝑐 ′ memenuhi syarat 2. 1. Jika 𝑣𝑠 bukan endpoint (verteks awal atau verteks akhir dari sisi berarah) pada graf 𝐺, maka verteks 𝑣𝑓 dan sisi berarah 𝑣𝑓 , 𝑣𝑠 ditambahkan pada graf 𝐺 dengan bobot 0. Untuk semua 𝑣𝑖 dalam 𝑉, sisi 𝑣𝑖 , 𝑣𝑓 ditambahkan pada graf 𝐺 dengan bobot 𝑐𝑖𝑠 . 2. Pada 𝑉 ditambahkan semua verteks yang merupakan endpoint dari sisi berarah dan ditentukan path terpendek antara setiap pasang verteks 𝑣𝑖 dan 𝑣𝑗 , sisi 𝑣𝑖 , 𝑣𝑗 ditambahkan pada 𝐸, dan 𝑐𝑖𝑗 ditetapkan dari bobot path terpendek yang diperoleh. Contoh algoritme Preprocess Misalkan diberikan graf campuran 𝐺13 = 𝑉, 𝐸 ∪ 𝐴 seperti pada Gambar 38. Graf tersebut tidak memenuhi syarat 1 dan 2 karena terdapat verteks 𝑣3 yang bukan merupakan endpoint dari sisi berarah manapun dan fungsi bobot 𝑐𝑖𝑗 tidak memenuhi pertidaksamaan segitiga, karena 𝑐32 ≥ 𝑐31 + 𝑐12 . 𝐺13 ∶

2 v1

4

v2

8

v3 Gambar 38 Graf 𝐺13 untuk ilustrasi algoritme preprocess. Langkah 1. Pada graf 𝐺13 terdapat verteks 𝑣3 yang bukan merupakan endpoint dari sisi berarah manapun. Sisi berarah 𝑣𝑓 , 𝑣3 dengan bobot 0, sisi 𝑣2 , 𝑣𝑓 dengan bobot 𝑐23 = 8 dan sisi 𝑣1 , 𝑣𝑓 dengan bobot 𝑐1𝑓 = 4 ditambahkan pada graf 𝐺13 sehingga diperoleh graf 𝐺 ∗ . Dapat dilihat bahwa graf 𝐺 ∗ memenuhi syarat 1.

14

𝐺∗ : 2 v1

v2 4

4

v3

8

8

vf

0

Gambar 39 Graf 𝐺 ∗ yang diperoleh dari Langkah 1 algoritme preprocess. Langkah 2. Verteks v1, v2, v3, vf merupakan endpoint dari suatu sisi berarah. Dengan algoritme Dijkstra didapat bobot terpendek antarverteks pada graf 𝐺 ∗ (detail penghitungan dapat dilihat di Lampiran 4). Path terpendek antara verteks 𝑣𝑓 dan 𝑣2 , yaitu 𝑃3 = 𝑣𝑓 − 𝑣1 − 𝑣2 dengan bobot 𝑐𝑓2 = 6 sehingga bobot sisi 𝑣𝑓 , 𝑣2 diganti dengan bobot 𝑐𝑓2 = 6 dan path tependek antara verteks 𝑣3 dan 𝑣2 , yaitu 𝑃4 = 𝑣3 − 𝑣1 − 𝑣2 dengan bobot 𝑐32 = 6 sehingga bobot sisi 𝑣3 , 𝑣2 diganti dengan bobot 𝑐32 = 6. Graf 𝐺 ′ yang memenuhi syarat 1 dan 2 tersebut adalah: 𝐺′ ∶ 2

v1

4

v3

4

v2 6

0

6

vf

Gambar 40 Graf 𝐺 ′ yang memenuhi syarat 1 dan 2. Frederickson et al. (1978) mengajukan dua metode heuristik untuk menyelesaikan penentuan rute terpendek pada graf campuran 𝐺 = 𝑉, 𝐴 ∪ 𝐸 yang memenuhi syarat 1 dan 2. Kedua metode heuristik tersebut, yaitu Largearcs dan Smallarcs. 3.2 Algoritme Largearcs Misalkan diberikan graf campuran 𝐺 = 𝑉, 𝐴 ∪ 𝐸 , dengan 𝑅 = 𝐴 himpunan sisi berarah yang harus dilewati minimal satu kali dan bobot setiap sisi 𝑖, 𝑗 atau sisi berarah 𝑖, 𝑗 adalah 𝑐𝑖𝑗 . Langkah-langkah algoritme Largearcs adalah sebagai berikut:

Langkah 1. Subgraf 𝐺𝐴𝐿 = 𝑉, 𝐴 yang dibentuk dari graf 𝐺 dengan menghilangkan E. Himpunan verteks-awal dari sisi berarah di 𝐺𝐴𝐿 dinotasikan dengan 𝑉1 dan himpunan verteks-akhir dari sisi berarah di 𝐺𝐴𝐿 dinyatakan dengan 𝑉2 . Langkah 2. Dibentuk graf bipartite 𝐺𝐵𝐿 = 𝑉1 ∪ 𝑉2 , 𝐸 ′ dengan 𝐸 ′ = {{vi,vj}| vi ∈ V1, vj ∈ V2 dan {(vi,vj)  A}. Langkah 3. Minimum bipartite matching ditentukan dari graf 𝐺𝐵𝐿 . Selanjutnya graf 𝐺𝑀𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ) dibentuk dengan 𝐴 himpunan sisi berarah dari 𝐺𝐴𝐿 dan 𝐸𝑀𝐿 himpunan matching berbobot minimum yang diarahkan dari 𝑉2 ke 𝑉1 . Langkah 4. Komponen-komponen pada 𝐺𝑀𝐿 ditentukan dan dinotasikan dengan 𝐾1 , … , 𝐾𝐶 . Jika 𝑐 = 1, maka 𝐴 ∪ 𝐸𝑀𝐿 dijadikan sebagai hasil output dan proses selesai. Jika tidak, maka dibentuk graf lengkap yang tidak berarah 𝐺𝐾 = 𝑁𝐾 , 𝐸𝐾 dengan himpunan verteks 𝑁𝐾 = 𝐾1 , … , 𝐾𝑐 dan bobot atau nilai tiap sisi yang menghubungkan 𝐾𝑝 dan 𝐾𝑞 ialah 𝑐𝑝𝑞 = min𝑖∈𝐾𝑝 ,𝑗 ∈𝐾𝑞 𝑆𝑃 𝑖, 𝑗

1

dengan 𝑆𝑃 𝑖, 𝑗 merupakan panjang path terpendek dari verteks 𝑖 pada komponen 𝐾𝑝 dengan verteks j pada komponen 𝐾𝑞 . Langkah 5. Misalkan 𝐴𝐵𝐿 himpunan sisi tidak berarah pada 𝐺𝑀𝐿 yang terletak pada path terpendek yang berpadanan dengan sisisisi minimum spanning tree pada 𝐺𝐾 . Graf 𝐺𝐶𝐿 = 𝑉, 𝐴 ∪ 𝐸𝑀 ∪ 𝐴𝐵 dibentuk dengan menentukan minimum spanning tree pada 𝐺𝐾 . Langkah 6. Graf 𝐺𝐷𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ∪ 𝐴𝐵𝐿 ) dibentuk dengan 𝐴∗𝐵𝐿 ialah himpunan sisi berarah yang diperoleh dengan menambahkan dua sisi yang arahnya berlawanan untuk sisi dari spanning tree terpendek. Langkah 7. Ditentukan sirkuit Euler pada 𝐺𝐷𝐿 dan dijadikan sebagai solusi dari SCP. (Eiselt et al. 1995b) Pada Gambar 41 diberikan skema tahapan penyelesaian SCP dengan algoritme Largearcs.

15

Graf campuran berbobot 𝐺 = 𝑉, 𝐸 ∪ 𝐴

Diperoleh sirkuit Euler Dibentuk subgraf 𝐺𝐴𝐿 = 𝑉, 𝐴 `

Algoritme van AardenneEhrenfest - de Bruijn

Dibentuk graf bipartite 𝐺𝐵𝐿 = (𝑉, 𝐸 ′ )

Dibentuk graf baru 𝐺𝐷𝐿 = 𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ∪ 𝐴∗𝐵𝐿

Algoritme Dijkstra Pengubahan sisi tidak berarah menjadi sisi berarah

Ditentukan bobot sisi graf 𝐺𝐵𝐿

Metode Hungaria

Dibentuk graf 𝐺𝐶𝐿 = 𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ∪ 𝐴𝐵𝐿

Diperoleh minimum bipartite matching 𝐸𝑀𝐿

Ditentukan Minimum Spanning Tree (MST) di 𝐺𝐾

Dikonstruksi graf 𝐺𝑀𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 )

Algoritme Prim

Ditentukan jarak antarkomponen

Dibuat graf 𝐺𝐾 Algoritme Dijkstra

Gambar 41 Skema penyelesaian SCP dengan algoritme Largearcs.

16

3.3 Algoritme Smallarcs Misalkan diberikan graf campuran 𝐺 = 𝑉, 𝐴 ∪ 𝐸 , dengan 𝑅 = 𝐴 himpunan sisi berarah yang harus dilewati minimal satu kali dan bobot setiap sisi 𝑖, 𝑗 atau sisi berarah 𝑖, 𝑗 adalah 𝑐𝑖𝑗 . Langkah-langkah algoritme Smallarcs adalah sebagai berikut: Langkah 1. Dibentuk subgraf 𝐺𝐴𝑆 = 𝑉, 𝐴 dari graf 𝐺 dengan menghilangkan E. Langkah 2. Graf 𝐺𝐴𝑆 diubah menjadi graf tidak berarah 𝐺𝐵𝑆 = 𝑉 ′ , 𝐸 ′ dengan 𝑉 ′ ialah himpunan verteks 𝑛𝑖 yang mewakili sisi berarah 𝑡𝑖 , ℎ𝑖 pada subgraf 𝐺𝐴𝑆 . Untuk setiap verteks 𝑛𝑖 dan 𝑛𝑗 , 𝑐 ′ 𝑛𝑖 , 𝑛𝑗 ditentukan sebagai minimum dari 𝑐 𝑡𝑖 , 𝑡𝑗 , 𝑐 𝑡𝑖 , ℎ𝑗 , 𝑐 ℎ𝑖 , 𝑡𝑗 , dan 𝑐 ℎ𝑖 , ℎ𝑗 . Jarak antarverteks 𝑑 𝑛𝑖 , 𝑛𝑗 dari 𝐺𝐵𝑆 ditentukan dengan 𝑐 ′ 𝑛𝑖 , 𝑛𝑗 . Antara verteks 𝑛𝑖 dan 𝑛𝑗 dihubungkan dengan sisi yang bobotnya ialah jarak terpendek 𝑐 ′ 𝑛𝑖 , 𝑛𝑗 . Langkah 3. Minimum spanning tree 𝑇𝑆 ditentukan dari graf 𝐺𝐵𝑆 dengan algoritme Prim. Langkah 4. Diidentifikasi verteks berderajat ganjil pada spanning tree 𝑇𝑆 dari graf 𝐺𝐵𝑆 . Selanjutnya dibentuk graf lengkap 𝐺𝐿 dari verteks berderajat ganjil tersebut dengan jarak antarverteks-nya merupakan jarak terpendek yang diperoleh dari Langkah 1. Langkah 5. Matching yang perfect dan berbobot minimum, yaitu 𝐸𝑀𝑆 , ditentukan dari graf 𝐺𝐿 . Langkah 6. Setiap verteks 𝑛𝑖 dan 𝑛𝑗 diubah kembali menjadi sisi berarah seperti pada 𝐺𝐴𝑆 , sisi spanning tree graf 𝐺𝐵𝑆 dan matching yang perfect berbobot minimum graf 𝐺𝐿 diganti dengan path terpendek yang

diperoleh dari Langkah 1, sehingga menghasilkan graf 𝐺𝐶𝑆 = 𝑉, 𝐴 ∪ 𝑀𝑆 dengan 𝑀𝑆 = 𝑇𝑆 ∪ 𝐸𝑀𝑆 . Langkah 7. Jika 𝑡𝑖 dan ℎ𝑖 pada 𝐺𝐶𝑆 berderajat ganjil, maka ditambahkan sisi 𝑡𝑖 , ℎ𝑖 dan diarahkan dari ℎ𝑖 ke 𝑡𝑖 . Graf yang dihasilkan diberi nama 𝐺𝐷𝑆 = 𝑉, 𝐴 ∪ 𝑀𝑆 ∪ 𝐴𝐵𝑆 dengan 𝐴𝐵𝑆 himpunan sisi berarah 𝑡𝑖,ℎ𝑖 yang diperoleh dari penambahan sisi dari verteks berderajat ganjil pada 𝐺𝐶𝑆 dan diarahkan dari ℎ𝑖 ke 𝑡𝑖 . Langkah 8. Sirkuit Euler ditentukan pada 𝐺𝐷𝑆 dengan mengabaikan arah dari sisi berarah pada verteks berderajat genap. Arah sirkuit Euler dibalikkan jika terdapat sisi berarah pada verteks berderajat genap yang dilintasi dengan arah yang salah yang bobotnya melebihi dari setengah total bobot sisi berarah pada verteks berderajat genap dari graf 𝐺𝐶𝑆 . Langkah 9. Dibentuk graf 𝐺𝐸 = 𝑉, 𝐴 ∪ 𝑀∗ ∪ 𝐴𝐵𝑆 ∪ 𝐴∗𝐵𝑆 dengan 𝑀∗ adalah himpunan sisi spanning tree graf 𝐺𝐵𝑆 dan matching yang perfect berbobot minimum graf 𝐺𝐿 yang telah ditetapkan arahnya dari sirkuit Euler dan 𝐴∗𝐵𝑆 ialah himpunan sisi berarah yang diperoleh dengan menambahkan dua sisi berarah 𝑡𝑖 , ℎ𝑖 pada sisi berarah dari verteks berderajat genap 𝑡𝑖 , ℎ𝑖 yang dilintasi dengan arah sirkuit Euler yang salah. Langkah 10. Sirkuit Euler ditentukan pada 𝐺𝐸 dan dijadikan sebagai solusi dari SCP. (Eiselt et al. 1995b) Pada Gambar 42 diberikan skema tahapan penyelesaian SCP dengan algoritme Smallarcs dan pada Gambar 43 diberikan skema keseluruhan penyelesaian SCP.

17


Diperoleh sirkuit Euler

Dibentuk subgraf 𝐺𝐴𝑆 = 𝑉, 𝐴 Algoritme Dijkstra Dibentuk Graf 𝐺𝐵𝑆 = 𝑉 ′ , 𝐸 ′

Algoritme van AardenneEhrenfest - de Bruijn

Membentuk Graf 𝐺𝐸 = 𝑉, 𝐴 ∪ 𝑀∗ ∪ 𝐴𝐵𝑆 ∪ 𝐴∗𝐵𝑆

Algoritme Prim Ditentukan minimum spanning tree graf 𝐺𝐵𝑆

Penentuan verteks berderajat ganjil pada spanning tree 𝑇𝑆 graf 𝐺𝐵𝑆

Penambahan sisi berarah

Penentuan sebuah sirkuit Euler 𝐺𝐷𝑆 sehingga menghasilkan graf 𝐺𝐸

Algoritme Fleury Konstruksi graf lengkap 𝐺𝐿 dari verteks berderajat ganjil di 𝐺𝐵𝑆

Dibentuk graf baru 𝐺𝐷𝑆 = 𝑉, 𝐴 ∪ 𝑀𝑆 ∪ 𝐴𝐵𝑆

Algoritme Dijkstra

Penentuan bobot sisi-sisi dan matching yang perfect berbobot minimum pada graf 𝐺𝐿

Dibentuk Graf 𝐺𝐶𝑆 = (𝑉, 𝐴 ∪ 𝑀𝑆 )

Gambar 42 Skema penyelesaian SCP dengan algoritme Smallarcs.

18


Memenuhi syarat 1 dan 2 Frederickson et al. (1978)

Tidak

Ya

Algoritme Preprocess

Graf campuran 𝐺 ′ = 𝑉 ′ , 𝐸′ ∪ 𝐴

Algoritme Smallarcs

Algoritme Largearcs



Dipilih sirkuit Euler terpendek

Rute terpendek

Gambar 43 Skema penyelesaian SCP.

A L G O R I T M E C R A N E

19

IV APLIKASI MASALAH Katering adalah salah satu jasa/pelayanan untuk memenuhi pesanan makanan dari pihak yang membutuhkan makanan dalam jumlah besar untuk acara yang diadakannya. Terdapat banyak katering yang tersebar di Jakarta, misalnya Katering Eco Raos yang berlokasi di Jakarta Pusat. Katering Eco Raos adalah perusahaan katering dengan empat dapur yang masing-masing bertugas untuk menyiapkan makanan untuk satu pelanggan yang menggunakan jasanya (Gambar 44), namun hanya memiliki satu kendaraan untuk mengantarkan makanan dari dapur Katering Eco Raos ke pelanggan. Kendaraan tersebut berada di Dapur 1 yang diasumsikan memiliki

tempat penyimpanan kendaraan. Agar proses pengantaran makanan berjalan lancar dan optimal, maka pihak Katering Eco Raos harus menentukan rute atau jalan terbaik untuk proses pengantaran makanan. Pada karya ilmiah ini akan dibahas penentuan rute pengantaran makanan dari dapur-dapur Katering Eco Raos ke pelanggan yang menggunakan katering tersebut. Lokasi dapur Katering Eco Raos dan pelanggan yang menggunakan katering serta jarak tempuhnya dinyatakan dengan graf pada Gambar 45. Verteks 1, 4, 5, dan 8 menyatakan dapur Katering Eco Raos, dan lokasi pelanggan katering ialah verteks lainnya.

7

6

4

5

3

8

1 2

Gambar 44 Peta Katering Eco Raos di Jakarta Pusat. (www.googlemaps.co.id). Keterangan : :

Lokasi dapur Katering Eco Raos di Jakarta Pusat

:

Lokasi pelanggan katering

Asumsi yang digunakan dalam penentuan rute tersebut adalah sebagai berikut: 1. Semua jalur pendistribusian makanan harus dilewati tanpa kecuali. 2. Jalur pilihan boleh dilewati atau tidak. 3. Pendistribusian makanan dimulai pada Dapur 1 di pertigaan jalan Sutan Syahrir dan berakhir di tempat yang sama. 4. Mobil mengambil makanan dari dapur Katering Eco Raos untuk diantarkan ke pelanggan.

5. Waktu pengiriman diperhitungkan.

makanan

tidak

Pada Gambar 45, bobot pada setiap sisi {𝑖, 𝑗} atau sisi berarah (𝑖, 𝑗) merupakan jarak dari verteks 𝑖 ke verteks 𝑗. Jarak diperoleh dari perkiraan dengan satuan kilometer. Model di atas dapat dibuat menjadi graf sebagai berikut:

20

𝐺𝑆𝐶𝑃 : 3

6

7 4

7

6

5

8

9 8 10

4 6

4

3

7 7 5 1

7

6

9

2

Gambar 45 Graf kasus Katering Eco Raos di Jakarta Pusat dengan arah pendistribusian katering. Ket :

Arah distribusi katering yang harus dilewati Jalur pilihan

Tabel 3 Penjelasan setiap verteks pada graf kasus katering di Jakarta Pusat Verteks 1

2

3

4

5

6

7

8

Keterangan Tempat awal dan akhir mobil pengantar makanan dari dapur Katering Eco Raos. Pertigaan jalan Sutan Syahrir, jalan Teuku Umar, dan jalan RP Soeroso. Perempatan jalan Teuku Umar, jalan HOS Cokroaminoto, jalan Cut Mutia dan jalan Cut Nyakdien. Dapur Katering Eco Raos di perlimaan jalan Wahid Hasyim, jalan Kebon Kacang, jalan Jaksa, jalan Cut Nyak Dien, dan jalan Lombok. Dapur Katering Eco Raos di pertigaan jalan Kebon Kacang, jalan Kampung Bali, dan jalan Jaksa. Pertigaan jalan Kampung Bali, jalan Jaksa dan jalan Kebon Sirih. Perempatan jalan Wahid Hasyim, jalan Kebon Sirih, jalan Jaksa, dan jalan Cikini Raya. Dapur Katering Eco Raos di pertigaan jalan Cikini Raya, jalan Cut Mutia, dan jalan RP Soeroso.

Dalam bahasan berikut, graf campuran 𝐺𝑆𝐶𝑃 = 𝑉, 𝐴 ∪ 𝐸 memenuhi syarat 1 dan 2, sehingga algoritme Preprocess tidak digunakan. Ada dua metode heuristik yang digunakan, yaitu Largearcs dan Smallarcs. 4.1 Penyelesaian SCP dengan Algoritme Largearcs Langkah 1. Subgraf 𝐺𝐴𝐿 = (𝑉, 𝐴) dari graf 𝐺𝑆𝐶𝑃 adalah sebagai berikut: 𝐺𝐴𝐿 ∶ 6

7

7 5

8

9 10 4

1

9

3

2

Gambar 46 Subgraf 𝐺𝐴𝐿 . Langkah 2. Selanjutnya graf bipartite 𝐺𝐵𝐿 = 𝑉1 ∪ 𝑉2 , 𝐸 ′ dibuat dengan himpunan 𝑉1 , yaitu {1,8,4,5}, himpunan 𝑉2 , yaitu {2,3,7,6} dan himpunan 𝐸 ′ = {{1,3}, {1,7}, {1,6}, {8,2}, {8,7}, {8,6}, {4,2}, {4,3},{4,6}, {5,2}, {5,3}, {5,7}}. Dengan algoritme Dijkstra didapat path tependek graf 𝐺𝐵𝐿 dari graf 𝐺𝑆𝐶𝑃 (detail penghitungan dapat dilihat di Lampiran 5).

21

V2

Langkah 4. Pada 𝐺𝑀𝐿 terdapat 2 komponen yaitu 𝐾1 dan 𝐾2 .

2

𝐾1 ∶

𝐺𝐵𝐿 ∶ V1 1

7

9

1

13

13

2

7

7 8

7

3

4

8

7

𝐾2 ∶

12 4

3 10

6

9

4

7

7

8

8 10

6

16 5

6

5

6

6 7

Gambar 47 Graf bipartite 𝐺𝐵𝐿 .

Gambar 49 Komponen 𝐾1 dan 𝐾2 .

Langkah 3. Dengan metode Hungaria didapat solusi matching berbobot minimum pada 𝐺𝐵𝐿 , yaitu 𝐸𝑀𝐿 = 1,3 , 8,2 , 4,6 , 5,7 (Lampiran 6). Selanjutnya graf 𝐺𝑀𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ) dibentuk dari graf 𝐺𝐴𝐿 dengan menambahkan sisi dari matching 𝐸𝑀𝐿 dan arahnya dari 𝑉2 ke 𝑉1 .

Karena pada 𝐺𝑀𝐿 terdapat 2 komponen, maka dibentuklah graf lengkap 𝐺𝐾 = 𝑁𝐾 , 𝐸𝐾 dengan banyaknya verteks sesuai dengan banyaknya komponen pada 𝐺𝑀𝐿 , yaitu 2. Bobot setiap verteks dapat dicari dengan cara mencari path terpendek yang menghubungkan komponen 𝐾1 dan 𝐾2 dari tiap-tiap verteksnya. Dengan menggunakan algoritme Dijkstra (Lampiran 7), didapat panjang path terpendek antarkomponen adalah:

𝐺𝑀𝐿 : 9

1

2

𝐺𝐾 ∶

7

K1

4

K2

Gambar 50 Graf 𝐺𝐾 .

7 8

10 9

4

3

7

8 6 5

6 7

Gambar 48 Graf 𝐺𝑀𝐿 .

Jarak terpendek antara 𝐾1 dan 𝐾2 diperoleh dari panjang path terpendek, yaitu path (8,7). Langkah 5. Graf 𝐺𝐾 merupakan minimum spanning tree, agar 𝐺𝑀𝐿 terhubung maka ditentukan 𝐴𝐵𝐿 , yaitu himpunan sisi tidak berarah pada 𝐺𝑀𝐿 yang berpadanan dengan 𝐺𝐾 yang menghubungkan 𝐾1 dan 𝐾2 . Pada kasus ini dipilih path (8,7), karena path tersebut pada 𝐺𝑀𝐿 berpadanan dengan minimum spanning tree 𝐺𝐾 sehingga graf 𝐺𝐶𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ∪ 𝐴𝐵𝐿 ) dengan 𝐴𝐵𝐿 = 8,7 menjadi

22

𝐺𝐶𝐿 ∶ 9

1

Langkah 7. Penentuan sirkuit Euler pada Gambar 52 dilakukan dengan algoritme van Aardenne-Ehrenfest - de Bruijn. Spanning arborescence dari graf 𝐺𝐷𝐿 berawal dari verteks 5 adalah sebagai berikut:

2

7 7

1

8

2 9

3

10

7

4 8

3 10

9

4

7

4

8 4

7

9

6 8

5

6 7 5

Gambar 51 Graf 𝐺𝐶𝐿 . Langkah 6. Graf 𝐺𝐷𝐿 = (𝑉, 𝐴 ∪ 𝐸𝑀𝐿 ∪ 𝐴∗𝐵𝐿 ) dibentuk dan dua sisi ditambahkan dengan arah yang berlawanan untuk setiap sisi dari minimum spanning tree 𝐺𝐾 , sehingga sisi 𝐴𝐵𝐿 = 8,7 menjadi sisi berarah 𝐴𝐵𝐿 = 8,7 , 7,8 .

6

7

Gambar 53 Spanning 𝐺𝐷𝐿 .

arborescence

digraf

Hasil dari pelabelan dengan algoritme van Aardenne-Ehrenfest - de Bruijn untuk graf 𝐺𝐷𝐿 dapat dilihat pada Gambar 54. 𝐺𝐷𝐿 ∶

𝐺𝐷𝐿 ∶

L1

9

1

2

1

2

7

L1

L1

7 8

8

10 4

3

3

L2 L2

L1

4 4

9

4

7

L1

8 5

6 5

7

L1

6

L1 L1

6

Gambar 54 Graf 𝐺𝐷𝐿 yang sudah dilabeli.

7

Gambar 52 Graf 𝐺𝐷𝐿 .

Dari Gambar 54 dapat diperoleh sirkuit Euler yang dimulai dari verteks 1, yaitu 1−2−8−7−5−6−4−7−8−3−1 dengan total jarak 71.

23

Aplikasi algoritme Largearcs pada kasus Katering Eco Raos di Jakarta Pusat sebagai berikut: 𝐺𝐾𝐿 ∶ 3

6

7 4

7

6

4

5

8

9 8

𝐺𝐵𝑆 :

10

4 6

4

Penentuan path terpendek (Lampiran 8) untuk setiap verteks 𝑛𝑖 dan 𝑛𝑗 diperoleh hasil sebagai berikut: 𝑑 𝑛1 , 𝑛2 = 3 𝑑 𝑛1 , 𝑛3 = 7 𝑑 𝑛1 , 𝑛4 = 7 𝑑 𝑛2 , 𝑛3 = 4 𝑑 𝑛2 , 𝑛4 = 5 𝑑 𝑛3 , 𝑛4 = 6

3

3

n1

7

n2

7 5

7

6

7

4

7 1

5

2

9

Gambar 55 Graf kasus Katering Eco Raos di Jakarta Pusat dengan algoritme Largearcs.

n3

6

n4

Gambar 57 Graf 𝐺𝐵𝑆 . Ket :

Arah distribusi katering yang harus dilewati Jalur pilihan Jalur distribusi katering

4.2 Penyelesaian SCP dengan Algoritme Smallarcs Langkah 1. Subgraf 𝐺𝐴𝑆 = (𝑉, 𝐴) dari graf 𝐺𝑆𝐶𝑃 adalah sebagai berikut:

Langkah 3. Minimum spanning tree graf 𝐺𝐵𝑆 ditentukan dengan menggunakan algoritme Prim (Lampiran 9), sehingga didapat minimum spanning tree TS = {{n1,n2}, {n2,n3}, {n2,n4}} sebagai berikut: 𝑇𝑆 : 3 n1

𝐺𝐴𝑆 ∶

n2

5

4 6

7

7

n3

5

8

9 10 4

1

9

3

2

Gambar 56 Subgraf 𝐺𝐴𝑆 . Langkah 2. Selanjutnya graf 𝐺𝐵𝑆 = 𝑉 ′ , 𝐸 ′ dibuat dari himpunan sisi berarah 𝐺𝐴𝑆 yang diubah menjadi verteks 𝑛𝑖 , sehingga diperoleh hasil sebagai berikut: sisi berarah (5,6) menjadi verteks 𝑛1 sisi berarah (4,7) menjadi verteks 𝑛2 sisi berarah (8,3) menjadi verteks 𝑛3 sisi berarah (1,2) menjadi verteks 𝑛4

n4

Gambar 58 Minimum spanning tree pada graf 𝐺𝐵𝑆 . Langkah 4. Verteks berderajat ganjil pada minimum spanning tree dari graf 𝐺𝐵𝑆 adalah {𝑛1 , 𝑛2 , 𝑛3 , 𝑛4 }. Graf lengkap 𝐺𝐿 dibentuk dengan himpunan verteksnya adalah verteks berderajat ganjil pada minimum spanning tree dari graf 𝐺𝐵𝑆 . 𝐺𝐿 ∶ n1

n2

n3

n4

Gambar 59 Graf lengkap 𝐺𝐿 .

24

Langkah 5. Terdapat 4 verteks pada 𝐺𝐿 , maka matching yang perfect berisi 2 sisi. Dari Lampiran 10, diperoleh sisi matching yang perfect dan berbobot minimum ialah sisi 𝑛1 , 𝑛2 , dan {𝑛3 , 𝑛4 } dengan total bobot 9, sehingga diperoleh 𝐸𝑀𝑆 = 𝑛1 , 𝑛2 , 𝑛3 , 𝑛4 sebagai berikut:

𝐺𝐷𝑆 : 3 7

6

7 3

4

7 5

8

9 10 4

𝐸𝑀𝑆 ∶ 3

n1

5

n2

6

1

2

9

Gambar 62 Graf 𝐺𝐷𝑆 .

6

n3

3

n4

Gambar 60 Matching perfect minimum dari graf 𝐺𝐿 . Langkah 6. Graf 𝐺𝐶𝑆 = (𝑉, 𝐴 ∪ 𝑀𝑆 ) dibentuk dari verteks pada graf 𝐺𝐵𝑆 yang sudah diubah menjadi sisi berarah pada 𝐺𝐴𝑆 dengan MS = 𝑇𝑆 ∪ 𝐸𝑀𝑆 . TS = {{6,7},{7,8},{1,4}} yang merupakan minimum spanning tree pada graf 𝐺𝐵𝑆 dan 𝐸𝑀𝑆 = 6, 7 , 2,3 yang merupakan matching yang perfect dan berbobot minimum dari graf 𝐺𝐿 . 𝐺𝐶𝑆 : 3 6

Langkah 8. Pencarian sirkuit Euler pada Gambar 62 dilakukan dengan algoritme Fleury (Lampiran 11), sehingga diperoleh sirkuit Euler dari verteks 1, yaitu 1-4-7-6-5-67-8-3-2-1. Karena sisi berarah 1,2 dengan bobot 𝑐 1,2 = 9 tidak melebihi dari setengah total bobot sisi berarah pada verteks berderajat genap dari graf 𝐺𝐶𝑆 dengan total bobotnya 14, maka arah sirkuit Euler tetap. Langkah 9. Terdapat sisi berarah dari verteks berderajat genap 1,2 yang dilewati dengan arah sirkuit Euler yang salah sehingga ditambahkan sisi berarah 𝐴∗𝐵𝑠 = 1,2 , 2,1 . Graf yang dihasilkan dinamai 𝐺𝐸 = 𝑉, 𝐴 ∪ 𝑀∗ ∪ 𝐴𝐵𝑠 ∪ 𝐴∗𝐵𝑠 .

7 3

4

𝐺𝐸 :

7

3

5

8

9

7

6

10 4

3

7 3

4

7 5

8

9 10

5

1

6

9

4

2

Gambar 61 Graf 𝐺𝐶𝑆 . Langkah 7. Sisi berarah 5,6 pada graf 𝐺𝐶𝑆 terdiri dari verteks berderajat ganjil, maka ditambahkan sisi berarah 𝐴𝐵𝑆 = 6,5 sehingga diperoleh graf 𝐺𝐷𝑆 = (𝑉, 𝐴 ∪ 𝑀𝑆 ∪ 𝐴𝐵𝑆 ).

3

5

6 9

1

9

2

9

Gambar 63 Graf 𝐺𝐸 . Langkah 10. Pencarian sirkuit Euler pada Gambar 63 dilakukan dengan algoritme van Aardenne-Ehrenfest - de Bruijn. Spanning arborescence dari graf 𝐺𝐸 berawal dari verteks 5 adalah sebagai berikut:

25

6

𝐺𝐾𝑆 ∶

7

3

3

4

6

7

7

7 3

5

8

9

4

7 6

10 4

5

8

9

3

8 10

4

6

6

4

3

7

1

7

2

9

5

Gambar 64 Spanning arborescence digraf 𝐺𝐸 . 1

Hasil dari pelabelan dengan algoritme van Aardenne-Ehrenfest - de Bruijn untuk graf 𝐺𝐸 dapat dilihat pada Gambar 65. 𝐺𝐸 ∶ L1 L1

6

9

7

2

9 9

Gambar 66 Graf kasus Katering Eco Raos di Jakarta Pusat dengan algoritme Smallarcs. Ket :

7 L2

6

L2

Arah distribusi katering yang harus dilewati

L1 5

Jalur pilihan

8

L1 L1 4 L1

L1 L1

1

L2

Jalur distribusi katering

3

2

L2

Gambar 65 Graf 𝐺𝐸 yang sudah dilabeli. Dari Gambar 65 dapat diperoleh sirkuit Euler yang dimulai dari verteks 1, yaitu 1−4−7−6−5−6−7−8−3−2− 1 − 2 − 1 dengan total jarak 81. Aplikasi algoritme Smallarcs pada kasus Katering Eco Raos di Jakarta Pusat sebagai berikut:

Aplikasi algoritme Largearcs dalam menentukan rute optimal pengiriman makanan oleh Katering Eco Raos menghasilkan sirkuit Euler dengan total jarak 71, sedangkan algoritme Smallarcs menghasilkan sirkuit Euler dengan total jarak 81. Untuk menyelesaikan masalah SCP perlu dipilih sirkuit Euler terpendek dari dua metode Heuristik yang digunakan (Frederickson et al. 1978). Dalam kasus ini, sirkuit Euler terpendek ialah sirkuit Euler yang dihasilkan dari algoritme Largearcs sehingga rute optimal pengantaran memiliki total jarak 71.

V SIMPULAN DAN SARAN 5.1 Simpulan Stacker Crane Problem (SCP) diterapkan pada graf campuran menggunakan dua macam algoritme heuristik, yaitu algoritme Largearcs dan algoritme Smallarcs. Masalah SCP diterapkan pada pencarian rute optimal pengiriman katering di Jakarta Pusat. Hasil yang didapat dari kedua algoritme tersebut berbeda, yang antara lain disebabkan oleh adanya pencarian minimum bipartite matching terlebih dahulu pada algoritme Largearcs sedangkan pada algoritme Smallarcs ada

pengubahan sisi menjadi verteks dahulu. Rute optimal pengiriman jasa di Jakarta Pusat dihasilkan menggunakan algoritme Largearcs total jarak 71.

terlebih katering dengan dengan

5.2 Saran Jika ada yang ingin mendalami karya ilmiah ini, disarankan untuk menggunakan RPP dengan graf berkapasitas atau menggunakan metode lain.

26

DAFTAR PUSTAKA Balakrishnan VK. 1997. Schaum’s Outline of Theory and Problems of Graph Theory. New York: McGraw-Hill.

Foulds LR. 1992. Graph Theory Applications. New York: Springer Publishing.

Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York: McGraw-Hill.

Frederickson GN, Hecht MS, Kim CE. 1978. Approximation algorithms for some postman problems. Siam J. Comput 7: 178193.

Chartrand G, Zhang P. 2009. Chromatic Graph Theory. London: CRC Pr.

Orloff CS. 1974. A fundamental problem in vehicle routing. Networks 4: 35-64.

Diestel R. 1997. Graph Theory. New York: Springer-Verlag.

Ravindran A, Philips DT, Solberg JJ. 1987. Operations Research: Principles and Practices. 2nd Ed. New York: John Wiley & Sons.

Eiselt HA, Gendreau M, Laporte G. 1995a. Arc routing problem, Part I: The Chinese postman problem. Operations Research 43(2): 231-242. Eiselt HA, Gendreau M, Laporte G. 1995b. Arc routing problem, Part II: The Rural Postman Problem. Operations Research 43(3): 339-414.

Vasudev C. 2006. Graph Theory with Application. New Delhi: New Age International.

27

LAMPIRAN

28

Lampiran 1 Penentuan Minimum Bipartite Matching dengan metode Hungaria Diberikan tabel biaya sebagai berikut:

1 2 3

1

2

3

3

6

8

3

3

3

4

1

6

4

1

5

Nilai minimum baris

1

1

2

3

0

0

3

5

0

0

0

1

1

2

Kurangi setiap elemen pada baris dengan nilai minimum baris tersebut, maka diperoleh tabel berikut: 1 2 3 1

0

3

5

2

3

1

0

3

0

4

3

0

1

0

Nilai minimum kolom

Pilih elemen terkecil yang tidak dilalui garis, pada kasus ini adalah 2. Kurangkan 2 pada semua elemen yang tidak dilalui garis dan tambahkan 2 pada elemen yang berada pada titik potong 2 garis sehingga diperoleh tabel sebagai berikut:

Pada tabel baru kurangi setiap elemen dengan nilai minimum kolom tersebut, maka diperoleh tabel berikut: 1

2

3

1

0

2

5

2

3

0

0

3

0

3

3

Hanya dua pekerjaan yang dapat ditugaskan dengan menggunakan elemen nol. Karena belum ditemukan penugasan yang fisibel maka gambarkan sejumlah minimum garis yang melalui beberapa baris dan kolom yang dipilih sehingga semua elemen nol dilalui garis ini. Banyaknya garis minimum untuk matriks ini adalah dua, satu garis melalui kolom ke-1 dan satu garis melalui baris ke-2. 1

2

3

1

0

2

5

2

3

0

0

3

0

3

3

3

Tabel di atas memberikan biaya minimum yang ditunjukkan dengan elemen nol yang diberi kotak, yaitu elemen (1,2), (2,3), (3,1) sehingga diperoleh minimum dari bipartite matching, yaitu himpunan sisi {{1,2},{2,3},{3,1}} dengan total biayanya adalah 6 + 3 + 1 = 10. Lampiran 2 Langkah penentuan minimum spanning tree dengan algoritme Prim Langkah 1. Ambil sisi (1,2). 𝑇 = {(1,2)} 1 1

2

Iterasi 1: Langkah 2. Pilih sisi (2,5), karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {(1,2), (2,5)} 1 1

2 2

5

Langkah 3. 𝑇 memiliki 2 sisi, maka kembali ke Langkah 2. Iterasi 2: Langkah 2. Pilih sisi (2,4), karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di 𝑇. 𝑇 = {(1,2), (2,5), (2,4)}.

29

Iterasi 5: Sisi yang incident dengan 𝑣3 dihapus, misalkan sisi {5,3} dan didefinisikan 𝑣4 .

1 1

2 2

2

3

1

4

5

Langkah 3. T memiliki 3 sisi, maka kembali ke Langkah 2. Iterasi 3: Langkah 2. Pilih sisi (1,3), karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di T dan tidak membentuk cycle. T = {(1,2), (2,5), (2,4), (1,3)}. 1

1

3 4

4 v1

6

4 v3

2

5

Iterasi 6: Sisi yang incident dengan 𝑣4 dihapus, misalkan sisi {3,6} dan didefinisikan 𝑣5 . 2

2

2

3 v4

v2

3

1

4

v0 5

v5

2

v1

3 3

3 v4

v2

v0

1

1

2

4

6

4 v3

2

5

5

Langkah 3. T memiliki 4 sisi, maka proses berhenti. Lampiran 3 Langkah solusi sirkuit Euler dengan menggunakan algoritme Fleury Iterasi 3: Diambil sisi yang incident dengan 𝑣1 , misalkan sisi {6,2}, dihapus dan didefinisikan sebagai 𝑣2 .

Iterasi 7: Sisi yang incident dengan 𝑣5 dihapus, misalkan sisi {6,5} dan didefinisikan 𝑣6 . 2 1

2

3 v4

v2

3

1

4

v0

v6

v5 v1

6

v3

5

2

2 2

1 1

3 2

3

4

3 3

4

v0 v1

6

2

2

5

4

1

Iterasi 4: Sisi yang incident dengan 𝑣2 dihapus. Sisi {2,1} adalah bridge, karena masih ada sisi lain yang bisa diambil selain sisi tersebut, maka sisi {2,1} tidak boleh diambil. Misalkan diambil sisi {2,5} dan didefinisikan 𝑣3 . 2 1

2

3

3

v2 4

1


3

v1

4 v3

3 v7

1

4

v0

v6

v5 v1

6

v3

5

Iterasi 9: Sisi yang incident dengan 𝑣7 dihapus, misalkan sisi {4,3} dan didefinisikan 𝑣8 . v8

2 1

5

3 v4

v2

4

v0 6

2

2

2

3

v2

v4

v7

1

4

v0

v6

v5 v1

6

v3

5

30

Iterasi 10: Sisi yang incident dengan 𝑣8 dihapus, misalkan sisi {3,2} dan didefinisikan 𝑣9 . v9 1


v8

2

v9

3

v2

v4 4

v1

6

v3

v4 4

v0 v1

𝐺∗ : 2 v2 4

4

v3

8

8

vf

0

Gambar 67 Graf 𝐺 ∗ = 𝑉, 𝐴 ∪ 𝐸 . Tabel 4 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣1 Iterasi 𝑙 𝑣1 𝑙 𝑣2 𝑙 𝑣3 𝑆 𝑙 𝑣𝑓 (∞,–)

(∞,–)

(∞,–)

𝑣1

1

(2,𝑣1 )

(4,𝑣1 )

(4,𝑣𝑓 )

𝑣2

2

–

(4,𝑣1 )

(4,𝑣𝑓 )

𝑣3

0

0

3 – – (4,𝑣𝑓 ) 𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣

𝑣𝑓

Tabel 5 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣2 Iterasi 𝑙 𝑣2 𝑙 𝑣1 𝑙 𝑣3 𝑆 𝑙 𝑣𝑓 (∞,–)

(∞,–)

(∞,–)

𝑣2

1

(∞,–)

(8,𝑣2 )

(8,𝑣2 )

𝑣3

2

(12,𝑣3 )

–

(8,𝑣2 )

𝑣𝑓

(12,𝑣3 ) – – 𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣

𝑣1

0

3

0

v6

v5

5

6

Lampiran 4 Penentuan path terpendek dengan menggunakan algoritme Dijkstra

v1

v7

1

v6

v5

3

v2

v10

v7

1 v0

v8

2

v3

5

31

Tabel 6 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣3 Iterasi 𝑙 𝑣3 𝑙 𝑣1 𝑙 𝑣2 𝑆 𝑙 𝑣𝑓 (∞,–)

(∞,–)

𝑣3

1

(∞,–) (4,𝑣3 )

(8,𝑣3 )

(∞,–)

𝑣1

2

–

(6,𝑣1 )

(8,𝑣1 )

𝑣2

– – (8,𝑣1 ) 𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣

𝑣3

0

0

3

Tabel 7 Penentuan path terpendek dimulai dari verteks 𝑢0 = 𝑣𝑓 Iterasi 𝑙 𝑣1 𝑙 𝑣2 𝑙 𝑣3 𝑆 𝑙 𝑣𝑓 (∞,–)

(∞,–)

(∞,–)

𝑣𝑓

1

(4,𝑣𝑓 )

(8,𝑣𝑓 )

(0,𝑣𝑓 )

𝑣3

2

(4,𝑣𝑓 )

(8,𝑣𝑓 )

–

𝑣1

0

0

– (6,𝑣1 ) – 𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣

𝑣2

3

Lampiran 5 Penentuan path terpendek pada kasus Katering menggunakan algoritme Dijkstra 𝐺𝑆𝐶𝑃 :

3

6

7 4

7 6 5

8

8

9

4

10

6 4

7

3

5

6 7

1

9

7 2

Gambar 68 Graf kasus Katering Eco Raos di Jakarta Pusat.

32

Iterasi

l(1)

0 1 2 3 4 5 6 7

0

Tabel 8 Penentuan path terpendek dimulai dari verteks 𝑢0 = 1 l(2) l(3) l(4) l(5) l(6) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 1 (9,1) (7,1) (5,1) (7,1) (∞,–) (∞,–) (∞,–) 4 (9,1) (7,1) (7,1) (13,4) (14,4) (∞,–) 3 – (9,1) (7,1) (13,4) (14,4) (17,3) 5 – – (9,1) (13,4) (13,5) (17,3) 2 – – – (13,4) (13,5) (16,2) 6 – – – – (13,5) (16,2) 7 – – – – – (16,2) 8 – – – – – –

𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣

Iterasi

l(2)

0 1 2 3 4 5 6 7

0

Tabel 9 Penentuan path terpendek dimulai dari verteks 𝑢0 = 2 l(1) l(3) l(4) l(5) l(6) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 2 (9,2) (6,2) (∞,–) (∞,–) (∞,–) (∞,–) (7,2) 3 (9,2) (12,3) (∞,–) (∞,–) (∞,–) (7,2) 8 – (9,2) (12,3) (∞,–) (∞,–) (11,8) 1 – – (12,3) (16,1) (∞,–) (11,8) 7 – – – (12,3) (16,1) (14,7) 4 – – – – (16,1) (14,7) 6 – – – – – (16,1) 5 – – – – – –


Iterasi

l(3)

0 1 2 3 4 5 6 7

0

Tabel 10 Penentuan path terpendek dimulai dari verteks 𝑢0 = 3 l(1) l(2) l(4) l(5) l(6) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 3 (7,3) (6,3) (6,3) (∞,–) (∞,–) (∞,–) (10,3) 2 (7,3) (6,3) (∞,–) (∞,–) (∞,–) (10,3) 4 – (7,3) (10,4) (14,4) (15,4) (10,3) 1 – – (10,4) (14,4) (15,4) (10,3) 5 – – – (14,4) (15,4) (10,3) 8 – – – – (14,4) (14,8) 6 – – – – – (14,8) 7 – – – – – –


33

Iterasi

l(4)

0 1 2 3 4 5 6 7

0

Tabel 11 Penentuan path terpendek dimulai dari verteks 𝑢0 = 4 l(1) l(2) l(3) l(5) l(6) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 4 (5,4) (∞,–) (6,4) (4,4) (8,4) (9,4) (∞,–) 5 (5,4) (∞,–) (6,4) (8,4) (9,4) (∞,–) 1 – (14,1) (6,4) (8,4) (9,4) (∞,–) 3 – – (12,3) (8,4) (9,4) (16,3) 6 – – – (12,3) (9,4) (16,3) 7 – – – – (12,3) (13,7) 2 – – – – – (13,7) 8 – – – – – –


Iterasi

l(5)

0 1 2 3 4 5 6 7

0

Tabel 12 Penentuan path terpendek dimulai dari verteks 𝑢0 = 5 l(1) l(2) l(3) l(4) l(6) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 5 (7,5) (∞,–) (∞,–) (4,5) (7,5) (6,5) (∞,–) 4 (7,5) (∞,–) (10,4) (7,5) (6,5) (∞,–) 7 – (7,5) (∞,–) (10,4) (7,5) (10,7) 1 – – (16,1) (10,4) (7,5) (10,7) 6 – – – (16,1) (10,4) (10,7) 3 – – – – (16,1) (10,7) 8 – – – – – (16,1) 2 – – – – – –


Iterasi

l(6)

0 1 2 3 4 5 6 7

0

Tabel 13 Penentuan path terpendek dimulai dari verteks 𝑢0 = 6 l(1) l(2) l(3) l(4) l(5) l(7) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 6 (∞,–) (∞,–) (∞,–) (8,6) (7,6) (3,6) (∞,–) 7 (∞,–) (∞,–) (∞,–) (8,6) (7,6) (7,7) 5 – (14,5) (∞,–) (∞,–) (8,6) (7,7) 8 – – (14,5) (14,8) (17,8) (8,6) 4 – – – (13,4) (14,8) (14,4) 1 – – – – (14,8) (14,4) 2 – – – – – (14,4) 3 – – – – – –


34

Iterasi

l(7)

0 1 2 3 4 5 6 7

0

Tabel 14 Penentuan path terpendek dimulai dari verteks 𝑢0 = 7 l(1) l(2) l(3) l(4) l(5) l(6) l(8) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 7 (∞,–) (∞,–) (∞,–) (9,7) (6,7) (3,7) (4,7) 6 (∞,–) (∞,–) (∞,–) (9,7) (6,7) (4,7) 8 – (∞,–) (11,8) (14,8) (9,7) (6,7) 5 – – (13,5) (11,8) (14,8) (9,7) 4 – – – (13,5) (11,8) (14,8) 2 – – – – (13,5) (14,8) 1 – – – – – (14,8) 3 – – – – – –


Iterasi

l(8)

0 1 2 3 4 5 6 7

0

Tabel 15 Penentuan path terpendek dimulai dari verteks 𝑢0 = 8 l(1) l(2) l(3) l(4) l(5) l(6) l(7) Penambahan S (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) (∞,–) 8 (∞,–) (7,8) (10,8) (∞,–) (∞,–) (∞,–) (4,8) 7 (∞,–) (7,8) (10,8) (13,7) (10,7) (7,7) 2 – (16,2) (10,8) (13,7) (10,7) (7,7) 6 – – (16,2) (10,8) (13,7) (10,7) 3 – – – (16,2) (13,7) (10,7) 5 – – – – (16,2) (13,7) 4 – – – – – (16,2) 1 – – – – – –

𝑎, 𝑏 menyatakan 𝑎 = 𝑑 𝑢0 , 𝑣 dan 𝑏 = 𝑃𝐴𝑅𝐸𝑁𝑇 𝑣 Lampiran 6 Penentuan Minimum Bipartite Matching dengan metode Hungaria Diberikan tabel biaya sebagai berikut:

1 8

2 ∞ 7 12 16

1 8 4 5

3 7 ∞ 6 10

7 13 4 ∞ 6

6 13 7 8 ∞

Minimum Baris 7 4 6 6

Kurangi setiap elemen pada baris dengan nilai minimum baris tersebut sehingga diperoleh tabel sebagai berikut:

1 8 4 5

2 ∞ 3 6 10 3

3 0 ∞ 0 4 0

7 6 0 ∞ 0 0

6 6 3 2 ∞ 2

Minimum Kolom

Pada tabel baru kurangi setiap elemen dengan nilai minimum kolom tersebut, maka diperoleh tabel berikut:

4 5

2

3

7

6

∞

00

6

4

0

∞

0

1

3

0

∞

0

7

4

0

∞

Pada tabel di atas sudah memuat paling sedikit satu elemen nol pada setiap baris (kolom), yaitu pada elemen (1,3), (8,2), (4,6), dan (5,7) sehingga diperoleh minimum dari bipartite matching, yaitu himpunan sisi 1,3 , 8,2 , 4,6 , 5,7 dengan total jaraknya adalah 7 + 7 + 8 + 6 = 28. Lampiran 7 Penentuan path terpendek 𝑲𝟏 dan 𝑲𝟐 Menentukan path terpendek antarkomponen 𝑆𝑃 = 𝑖, 𝑗 , yaitu path terpendek antara verteks 𝑖 dan verteks 𝑗, dari persamaan 1 diperoleh panjang path antara:

35

𝑲𝟏 dan 𝑲𝟐 𝑆𝑃 (1,4) = 5 𝑆𝑃 (1,5) = 7 𝑆𝑃 (1,6) = 13 𝑆𝑃 (1,7) = 13 𝑆𝑃 (2,4) = 12 𝑆𝑃 (2,5) = 16 𝑆𝑃 (2,6) = 14 𝑆𝑃 (2,7) = 11 𝑆𝑃 (3,4) = 6 𝑆𝑃 (3,5) = 10 𝑆𝑃 (3,6) = 14 𝑆𝑃 (3,7) = 14 𝑆𝑃 (8,4) = 13 𝑆𝑃 (8,5) = 10 𝑆𝑃 (8,6) = 7 𝑺𝑷 (𝟖, 𝟕) = 𝟒 Penentuan panjang path terpendek yang dimulai dari suatu verteks dengan mengunakan algoritme Dijkstra secara lengkap dapat dilihat pada Lampiran 5. Lampiran 8 Penentuan path terpendek 𝒏𝒊 dan 𝒏𝒋 Menentukan jarak terpendek antarverteks 𝑑 𝑛𝑖 , 𝑛𝑗 menggunakan 𝑐 ′ 𝑛𝑖 , 𝑛𝑗 , yaitu jarak terpendek antara verteks 𝑛𝑖 dan verteks 𝑛𝑗 dengan minimum 𝑐 𝑡𝑖 , 𝑡𝑗 , 𝑐 𝑡𝑖 , ℎ𝑗 , 𝑐 ℎ𝑖 , 𝑡𝑗 , 𝑐 ℎ𝑖 , ℎ𝑗 . Dengan menggunakan algoritme Dijkstra pada Lampiran 5 diperoleh hasil sebagai berikut: Jarak terpendek verteks 𝑛1 (5,6) dengan verteks 𝑛2 (4,7) sebagai berikut: 𝑐 5, 4 = 4 𝑐 5, 7 = 6 𝑐 6, 4 = 8 𝒄 𝟔, 𝟕 = 𝟑 Jadi 𝑑 𝑛1 , 𝑛2 = 3 Jarak terpendek verteks 𝑛1 (5,6) dengan verteks 𝑛3 (8,3) sebagai berikut: 𝑐 5, 3 = 10 𝑐 5, 8 = 10 𝑐 6, 3 = 14 𝒄 𝟔, 𝟖 = 𝟕 Jadi 𝑑 𝑛1 , 𝑛3 = 7 Jarak terpendek verteks 𝑛1 (5,6) dengan verteks 𝑛4 (1,2) sebagai berikut: 𝑐 𝟓, 𝟏 = 𝟕 𝑐 5, 2 = 16 𝑐 6, 1 = 13 𝑐 6, 2 = 14 Jadi 𝑑 𝑛1 , 𝑛4 = 7

Jarak terpendek verteks 𝑛2 (4,7) dengan verteks 𝑛3 (8,3) sebagai berikut: 𝑐 4, 3 = 6 𝑐 4, 8 = 13 𝑐 7, 3 = 14 𝒄 𝟕, 𝟖 = 𝟒 Jadi 𝑑 𝑛2 , 𝑛3 = 4 Jarak terpendek verteks 𝑛2 (4,7) dengan verteks 𝑛4 (1,2) sebagai berikut: 𝑐 𝟒, 𝟏 = 𝟓 𝑐 4, 2 = 12 𝑐 7, 1 = 13 𝑐 7,2 = 11 Jadi 𝑑 𝑛2 , 𝑛4 = 5 Jarak terpendek verteks 𝑛3 (8,3) dengan verteks 𝑛4 (1,2) sebagai berikut: 𝑐 3,1 = 7 𝒄 𝟑, 𝟐 = 𝟔 𝑐 8, 1 = 16 𝑐 8, 2 = 7 Jadi 𝑑 𝑛3 , 𝑛4 = 6 Lampiran 9 Langkah penentuan minimum spanning tree dengan algoritme Prim Langkah 1. Ambil sisi 𝑛1 , 𝑛2 . 𝑇𝑆 = 𝑛1 , 𝑛2 3 n1

n2

Iterasi 1: Langkah 2. Pilih sisi 𝑛2 , 𝑛3 , karena merupakan sisi berbobot minimum yang adjacent dengan sisi-sisi di TS. TS = 𝑛1 , 𝑛2 , 𝑛2 , 𝑛3 3 n1

n2

4 n3

Langkah 3. TS memiliki 2 sisi, maka kembali ke Langkah 2. Iterasi 2: Langkah 2. Pilih sisi 𝑛2 , 𝑛4 karena merupakan sisi berbobot minimum yang

36

adjacent dengan sisi-sisi di TS dan tidak membentuk cyle. TS = {(n1,n2),(n2,n3),(n2,n4)}. 3 n1

n2

5

4 n3

n4

Langkah 3. TS memiliki 3 sisi, maka proses berhenti. Lampiran 10 Penentuan Matching yang perfect dengan bobot minimum 𝐺𝐿𝑆 : Tabel 16 Bobot (𝑊𝑖𝑗 ) setiap sisi 𝑖, 𝑗 , dengan 𝑖, 𝑗 ∈ 𝑉(𝐺𝐿𝑆 ) n1 Sisi {𝑖, 𝑗} Bobot (𝑤𝑖𝑗 ) 3 𝑛1 , 𝑛2 7 𝑛1 , 𝑛3 7 𝑛1 , 𝑛4 7 4 𝑛2 , 𝑛3 5 𝑛2 , 𝑛4 6 𝑛3 , 𝑛4 n3

3

n2

7

4 5

n4

6

Gambar 69 Graf lengkap 𝐺𝐿𝑆 .

Dari Gambar 69 akan ditentukan matching yang perfect dengan total bobot minimum. Tabel 16 menunjukkan bobot sisi yang terdapat pada Gambar 69. Karena pada Gambar 69 hanya terdapat 4 verteks, maka matching perfect yang dapat dibentuk sebanyak 2 sisi adalah sebagai berikut. n1

n2

7

n1

3

n2

n1

7

5

n3

n4

(𝐴)

n2

n3

6

(𝐵)

n4

4

n3

n4

(𝐶)

Pada Gambar (𝐴) matching perfect yang dapat dibentuk adalah 𝑀𝐴 = 𝑛1 , 𝑛3 , 𝑛2 , 𝑛4 dengan total bobot 12. Gambar (𝐵) matching perfect yang dapat dibentuk adalah 𝑀𝐵 = 𝑛1 , 𝑛2 , 𝑛3 , 𝑛4 dengan total bobot 9. Gambar (𝐶) matching perfect yang dapat dibentuk adalah 𝑀𝐶 = 𝑛1 , 𝑛4 , 𝑛2 , 𝑛3 dengan total bobot 11. Jika dilihat dari Gambar (𝐴) sampai dengan (𝐶), maka matching yang perfect dengan total bobot minimum adalah 𝑀𝐵 = 𝑛1 , 𝑛2 , 𝑛3 , 𝑛4 dengan total bobot 9.

37

Lampiran 11 Penentuan solusi sirkuit Euler dengan menggunakan algoritme Fleury. 1. Inisialisasikan 𝑣0 sebagai verteks 4. Sisi {7,6} dihapus dan didefinisikan 𝑣3 . v3 awalnya, misalkan diambil verteks 1 v2 7 6 7 sebagai 𝑣0 . 3 4

3

7

6

7

7 3

5

4

8

7

10

5

8

9

v1 4

10 4

3 6

3

5

v0

6

1

2

9

v0 1

2

9

Sisi {1,4} dihapus dan didefinisikan 𝑣1 .

2.


5. 7

6

v3

6 3

5

4

5

v4

8 10

8

9

4

10

v1

v0 1

2


6.

6

7

6

v3

v5

v2 5

5

2

9


3.

3 6

v0 9

v1

3 6

1

7 3

4 8 10

8

4

v1

v1

3

3

6

v0 1

v0 2

v2

v4

4

1

4

7

7

4

v2

3

3 7

7

9

2

38


7.

6

v3

7

v5 5

10. Sisi {3,2} dihapus dan didefinisikan 𝑣9 .

v2

v6

6

v3

v5

4

v4

8

5

v2

7

v6

v4

v7

8

10 4

v1

3

4

v1

3

v8

6

v0

v0

1

2

9

1


8.

6

v3

7

v5 5

v2

6

5

v7

v4

v10 2

Sisi {8,7} dihapus dan didefinisikan 𝑣8 . v3

7

v5 5

v4

v7 v1 v8 6

v0 1

v2

v6

4

9

v1 v8

v0

v0

6

v7

3

2

3

8

1

v2

v6

4

6

9.

7

8

10

9

v3

v5

v4

1

2

11. Sisi {2,1} dihapus dan didefinisikan 𝑣10 .

v6

v1 4

v9

9

v9

2

3

8

PENYELESAIAN STACKER CRANE PROBLEM DENGAN ALGORITME LARGEARCS DAN SMALLARCS

Recommend Documents