MULTIPLE TRIP VEHICLE ROUTING PROUBLEM (MTVRP)

Definisi: Menentukan sejumlah rute untuk sekumpulan kendaraan identik yang  
                harus melayani sejumlah customer dari depot pusat
Tujuan:    Meminimalisasi jarak tempuh dan jumlah kendaraan

Algoritma- Algoritma MTVRP

1. Algoritma Self-Developed pada MTVRP

2. Algoritma FFD (First-Fit-Decreasing)

3. Algoritma SPMU

3. Metode Insertion Heuristic

4. Metode Brandao and Merces

5. Algoritma Genetika

6. Algoritma Tabu Search

7. Algoritma Clark and Wrigh

8. Algoritma Ant Colonyc System (ACS)

9  Algoritma Nearest Insertion Heuristic

10.Algoritma Cheapest Insertion Heuristic

 

 

Travelling Salesman Problem

Traveling Salesman Problem (TSP) adalah permasalahan untuk mencari rute terpendek yang dapat dilalui untuk mengunjungi beberapa kota tanpa harus mendatangi kota yang sama lebih dari satu kali.

1.      Nearest Neightbour Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan total jarak terpendek. Metode ini sangat sederhana dan lebih banyak digunakan daripada metode lain yang dalam menyelesaikan masalah TSP. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dari lintasan.

2. Pilih titik dengan sisi yang terkait yang memiliki bobot minimum.

3. Dari titik baru, pilih titik yang belum terpilih pada lintasan dengan bobot sisi minimum. 
4. Kembali lakukan langkah 3 sampai semua titik telah termuat dalam lintasan. Selanjutnya hubungkan titik awal dengan titik akhir sehingga terbentuk sikel.
 

 2. Cheapest Insertion Heuristik

Metode ini dapat digunakan untuk menentukan sikel Hamilton dengan jumlah bobot yang minimum. Adapun langkah-langkahnya sebagai berikut :

1. Pilih sembarang titik sebagai titik awal dan siklus S hanya terdiri dari titik awal tersebut.

2. Cari titik j di luar S sehingga Cij minimum dan membentuk sikel tertutup {(i, j), (j, i)}.

3. Pemilihan. Cari titik k (bukan dalam sikel) yang terdekat ke sembarang titik di S.

4. Penyimpanan. Cari sisi (i, j) dalam sikel dengan Cik + Ckj – Cij yang memiliki nilai minimum, masukkan k di antara i dan j sehingga diperoleh (i, k) dan (k, j).

5. Jika sikel telah terisi oleh semua titik maka terbentuklah sikel Hamilton sehingga iterasi berhenti.

3. Metode Koloni Semut

Algoritma Koloni Semut terinspirasi oleh tingkah laku semut pada saat mencari makan.Intinya adalah komunikasi tak langsung antar semut. Semut memiliki zat khusus yang disebut pheromone, yang digunakan oleh semut untuk memeberikan jejak pada jalan yang dilewati,dan juga sebagai komunikasi antar semut. Semut akan memilih salah satu jalan, yaitu jalan yang terdapat banyak pheromone yang menunjukkan bahwa jalan tersebut banyak dilewati oleh semut lain, sehingga akan lebih cepat untuk mencapai sumber makanan dan kembali ke sarang. Pembahasan dari algoritma Koloni Semut untuk menyelesaikan masalah Travelling Salesman Problem (TSP), adalah sebagai berikut:

a.       bi (t) (i=1,2,3,… n) adalah banyaknya semut pada kota I dalam waktu t.

b.      m =  adalah jumlah semua semut pada semua kota dalam waktu t.

c.       di j adalah jarak lintasan yang menghubungkan antara kota i dan kota j

adalah intensitas lintasan sisi (I,j) dalam waktu t.

Masing-masing semut pada waktu t akan memilih kota berikutnya, sehingga waktunya akan menjadi t+1. Yang dimaksud 1 iterasi dari algoritma Koloni Semut ini adalah satu kali perjalanan pergi-pulang yang dilakukan oleh satu semut pada interval (t, t+1), dan intensitas lintasan akan diperbaharui dengan rumus, dengan adalah koefisien penguapan lintasan antara waktu t dan t+n, nilai (0 <1). n= 1,2,…,q, dengan q adalah banyaknya rute yang mungkin dilewati  =  , dengan adalah banyaknya pheromone yang ditinggalkan oleh k-semut pada sisi (I,j) dalam waktu t dan t+n,

Q adalah konstanta relatif banyaknya lintasan yang dilewati oleh semut, nilai Q € (0, 10, 100, 1000) dan Lk panjang sisi yang dibuat oleh k-semut. Hasil yang diharapkan adalah rute terpendek yang diperoleh dari banyaknya pheromone yang ditinggalkan oleh masing-masing semut pada setiap jalan yang dilewatinya.(Dorigo, 1996).

4. Cheapest Link

Langkah-langkah:

1.   Dalam metode ini kita tidak memilih simpul awal yang  memilih link atau sisi dengan bobot terkecil pada graph.

2.      Kita  memilih sisi dengan bobot  terkecil kedua (sisi ini tidak perlu berbagi dengan ujung simpul sebelumnya). Lakukan teruslangkah ini, kecuali kita menolak setiap sisi jika:
1) membentuk sebuah "hubungan pendek" (sirkuit yang bukan Hamilton sirkuit) , atau
2) mengakibatkan 3 pertemuan sisi di simpul yang sama.

3.      Telah terpilih n-1 sisi, yang ujung-ujungnya membentuk lintasan Hamilton.
Lalu untuk sisi terakhir kita pilih satu sisi yang menggabungkan dengan simpul  terakhir.

5.  Algoritma Brute Force 

Algoritma bruteforce menyelesaikan masalah TSP dengan cara:

-          Mengenumerasi semua Sirkuit Hamilton dari graf lengkap TSP,

-          Menghitung bobot setiap sirkuit Hamilton yang ditemukan pada langkah 1,

-          Memilih sirkuit Hamilton yang mempunyai bobot terkecil.

Karena algoritma ini menghitung bobot untuk setiap Sirkuit Hamilton yang mungkin terjadi, maka kompleksitasnya sebesar jumlah Sirkuit Hamilton untuk graf lengkap bersimpul n yang dimulai dari sebuah simpul, yakni permutasi dari n buah simpul = n1* ... * 1 = (n1)!.

Maka, kompleksitasnya adalah O(n!)

  
6.Algoritma DFS

Algoritma DFS untuk menyelesaikan TSP adalah seperti ini:

-          Bangun sebuah pohon yang cabangnya berupasimpul pada graf, Lakukan metode DFS pada tiap cabang sampai semua simpul dipilih (tidak ada yang dipilih dua kali),

-          Hitung bobotnya,

-     Lakukan langkah ke2 dan ke3 sampai seluruhsimpul asal telah dipilih. Apabila pada waktu membangkitkan simpul anak ternyata tidak lebih kecil dari minimum sementara, maka simpul tersebut dimatikan (tidak diekspansi lebih lanjut).

 

SHORTEST PATH (LINTASAN TERPENDEK)

SHORTEST PATH (LINTASAN TERPENDEK)
Jika diberikan sebuah graph berbobot, masalah lintasan terpendek adalah bagaimana kita mencari sebuah jalur pada graph yang meminimumkan jumlah bobot sisi pembentuk jalur tersebut.
Terdapat bermacam persoalan lintasan terpendek antara lain:
1. Lintasan terpendek antara dua buah simpul tertentu (a pair shortest path).
2. Lintasan terpendek antara semua   pasanggan simpul (all pairs shortest path).
3. Lintasan terpendek dari simpul tertentu ke semua simpul yang lain (single-source shortest path).
4. Lintasan terpendek antara dua buah simpul yang melalui beberapa simpul tertentu (intermediate shortest path).

Algoritma-Algoritma Shortest Path
1.Algoritma Greedy

2. Algoritma Djikstra
3.Algoritma Bellman-Ford
4.Algoritma Branch and Bound (B&B)
5.Algoritma Koloni Semut
6.Algoritma Floyd-Warshall
7.Algoritma Genetik
8.Algoritma Perkalian Matriks
9.Algoritma Label Correcting (Pengoreksian Label)
10.Algoritma A*
11.Algoritma PHA
12.Algoritma Johnson
13.Algoritma Exhaustic Search
14.Algoritma UCS ( Uniform Cost Search )

Penyelesaian Masalah Single Pair

1. Algoritma Greedy

Langkah-langkah:

a.  Menentukan  titik sebagai titik awal dan titik tujuan.

b.  Evaluasi semua sisi yang terkait dengan titik awal. 

c.  Pilih sisi dengan bobot yang paling minimum.

d.  Maka diperoleh titik baru yang terhubung langsung dengan titik awal. 

e. Dimulai dari titik yang diperoleh pada langkah 4, ulangi langkah 2 hingga sampai ke titik tujuan. 

2. Algoritma Djikstra

1.Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada

   node awal dan nilai tak hingga terhadap node lain (belum terisi)

2.Set semua node “Belum terjamah” dan set node awal sebagai “Node 

   keberangkatan”

3. Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah

    dan hitung jaraknya dari titik keberangkatan.

4. Saat kita selesai mempertimbangkan setiap jarak terhadap node     tetangga,

   tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak

   akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang

   paling minimal bobotnya.

5.Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan)

   sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3 

3. Algoritma Exhaustic Search

Mencari lintasan terpendek dengan Exhaustive Search yaitu dengan mengenumerasi setiap lintasan

yang mungkin dengan cara yang sistematis. Dari setiap kemungkinan tersebut dievaluasi satu persatu,

selanjutnya bandingkan setiap lintasan yang telah dievaluasi, lintasan yang memberikan nilai terkecil

merupakan lintasan terpendek yang kita cari.

ALGORITMA MINIMUM SPANNING TREE

MINIMUM SPANNING TREE (MST)
By: Firqin Setara(409312419800)

Definition:
Let T be a spanning tree of mimimum total weight in a connected weighted graph G. Then T is minimumspanning tree or
a minimum connector in G. (Joan and Robin 2004:183)

Minimum Spanning Tree
• Graph bagian G( graph berbobot, terhubung, tidak berarah)
• Tidak berupa cycle
• Memuat semua titik
• Graph berbobot dengan bobot minimum

Contoh Penerapan
1. Pemodelan jaringan listrik dengan bobot (panjang kabel) minimum.
2. Pemodelan jaringan pipa PDAM(Perusahaan daerah air minum)
3. Pemodelan gardu sinyal (Tower) pada perusahaan telekomunikasi
4. Pemodelan pembangunan jalan raya, digunakan untuk memilih jalur
dengan bobot terkecil., untuk meminimalkan biaya pembangunan jalan.

Algoritma Spanning Tree:
1. Algoritma Boruvka (Otakar Borůvka 1926)
2. Algoritma Prim Vojtěch Jarník 1930)
3 Algoritma Kruskal (Joseph Kruskal 1956)
4. Algoritma Sollin
5. Algoritma Edge Ecchange
6. Algoritma TCRNN(Tree Construction with Reciprocal Nearest Neighbour)
7. Algoritma Bernard Chazel Baru Bernard Chazell
8. Algoritma Waktu Linear
9. Algoritma Reverse-Delete
10.Algoritma Semut (Marco Dorigo 1996)
11. Algoritma Genetika
12 Algoritma Parallel
13. Algoritma Penyimpanan Eksternal

1. Algoritma Boruvka
Algorima pertama untuk mencari pohon merentang minimum dari sutau graf
ditemukan oleh Otakar Borůvka pada tahun 1926. Untuk menentukan pohon merentang minimum dari sebuah graf dengan
menggunakan Algoritma Boruvka maka diperlukan langkah-langkah sebagai berikut:
Untuk mencari pohon merentang minimum pada graf G
Langkah-langkah Algoritma Boruvka:
Langkah 1: Salin titik dari G ke graf baru T yang kosong.
Langkah 2: Sedangkan L tidak terhubung (artinya hutan lebih dari satu pohon)
Langkah 3: Untuk setiap pohon di L, hubungkan sebuah titik ke titik yang lain pada pohon yang lain di L dengan
menambahkan sisi yang berbobot minimum
(Chartrand dan Ortrud, 1993:67).

2.Algoritma Prim
Algoritma Prim membentuk pohon merentang minimum langkah per langkah.
Pada setiap langkah diambil sisi dari graf G yang mempunyai bobot minimum
namun terhubung dengan pohon merentang minimum T yang telah terbentuk.
Langkah-langkah Algoritma Prim:
Langkah 1: Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T
Langkah 2: Pilih sisi (u, v) yang mempunyai bobot minimum dan bersisian dengan simpul di T,
tetapi (u,v) tidak membentuk sirkuit di T. Tambahkan (u, v) ke dalamT.
Langkah 3: Ulangi langkah 2 sebanyak n - 2 kali hingga terbentuk pohon merentang minimum.

3.Algoritma Kruskal
Algoritma Kruskal adalah suatu Algoritma di dalam teori graf yang digunakan
untuk mengkonstruksi pohon merentang minimum di dalam graf berbobot terhubung
secara berurutan dari sisi yang berbobot kecil sampai berbobot besar hingga tidak
terbentuk sikel. Algoritma Kruskal dapat diasumsikan dengan memilih sisi dari Graf
secara berurutan berdasarkan bobotnya dari bobot kecil ke bobot besar.
Langkah-langkah Algoritma Kruskal: Langkah 1: Urutkan sisi-sisi graf dari kecil ke besar. T merupakan himpunan kosong.
Langkah 2: Pilih sisi e dengan bobot minimum yang tidak membentuk sirkuit di T,
tambahkan e ke dalam T
Langkah 3: Ulangi langkah 2 sebanyak n - 1 kali hingga terbentuk pohon merentang minimum.

4.Algoritma Sollin
Algoritma Sollin adalah suatu Algoritma di dalam teori graf yang digunakan untuk
menentukan pohon merentang minimum di dalam graf berbobot terhubung dengan cara
melakukan penghapusan sisi-sisi yang tidak menyebabkan graf menjadi tidak berhubung
atau membentuk sirkuit. Penghapusan tersebut dimulai dari sisi atau busur yang memiliki bobot terbesar hingga
terkecil.
Langkah-langkah Algoritma Sollin:
Langkah 1: Urutkan sisi-sisi pada graf berdasarkan bobotnya dari besar ke kecil
Langkah 2: Lakukan penghapusan setiap sisi yang tidak menyebabkan graf menjadi
tidak terhubung
Langkah 3 :Ulangi langkah 2 hingga diperoleh pohon merentang minimum.