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

 

 

PENGENDALIAN KUALITAS PROSES STATISTIK DATA ATRIBUT C-CHART

C Chart dalam Pengendalian Kualitas Statistik

Salah satu alat yang dapat digunakan untuk pengendaliaan kualitas adalah peta control (control chart). Di mana peta kontrol dapat digunakan untuk:

1. Mengetahui apakah telah terjadi perubahan proses produksi.
2. Mendeteksi adanya penyebab-penyebab yang mempengaruhi proses.
3. Membuat standar suatu proses.

Variasi kualitas produk sering timbul. Dalam proses produksi ada dua jenis variasi yang timbul dalam proses produksi, yaitu (Montgomery, 2001):

• Assignable cause adalah variasi yang dapat dicari sumber-sumber penyebabnya dan ini harus dihilangkan. Misalnya kualitas bahan baku tidak homogen, petunjuk kurang jelas, kondisi mesin kurang baik.
• Random (common cause) adalah variasi natural (variasi yang tak dapat dilacak sumber - sumbernya) dan variasi jenis ini tak dapat dihilangkan 100%, tetapi diminimalkan. Salah satu contoh adalah kualitas bahan baku dibuat sehomogen mungkin, tingkat ketrampilan operator diupayakan sama.

Peta kontrol dapat dibagi menjadi dua jenis, yaitu peta kontrol atribut dan peta kontrol variabel. Karakteristik kualitas yang dapat diukur dan dinyatakan secara kuantitatif dinamakan variabel, sedangkan kualitas yang dinilai sebagai sesuai atau tidak sesuai (cacat) dinamakan atribut. Peta kontrol memberikan informasi tentang kemampuan proses, nilai parameter proses yang penting, dan stabilitas terhadap waktu sehingga memberikan taksiran kemampuan proses. Informasi ini

sangat berguna bagi perancangan produk dan proses. Pengertian atribut dalam pengendalian kualitas berkaitan dengan karakteristik kualitas yang dapat digolongkan atas baik (diterima) dan cacat (ditolak). Salah satu peta kontrol atribut yaitu Peta kontrol c (c chart), yaitu peta kontrol untuk jumlah ketidaksesuaian (number of nonconformities), mempunyai kegunaan yang jauh lebih terbatas.

 Perbedaan antara barang yang Taksesuai dan Ketaksesuaian

Barang yang Taksesuai adalah barang yang dalam beberapa hal gagal memenuhi satu atau lebih spesifikasi yang ditetapkan . Setiap kejadian dari kurangnya kesesuaian barang terhadap spesifikasi adalah Ketaksesuaian.

Setiap barang yang taksesuai berisi satu atau lebih ketaksesuaian bilamana memungkikan untuk menghitung jumlah semua ketaksesuaian dalam setiap barang , atau dalam setiap kelompok dalam jumlah yang sama dari barang-barang yang sama, mungkin beralasan untuk menggunakan teknik bahkan kendali berdasarkan distribusi poisson.

Bagan c berlaku bagi sejumlah ketaksesuaian dalam subgroup berukuran konstan. Setiap subgroup untuk bagan c biasanya merupakan barang tunggal; peubah c adalah jumlah ketaksesuaian yang diamati dalam satu barang. Tetapi subgroup bagan c dapat merupakan dua atau lebih barang. Hal itu dapat berarti bila ukuran subgroup konstan dalam pengertian bahwa subgroup-subgrup yang berbeda mempunyai peluang yang sama bagi kemunculan ketaksesuaian. Bila peluang kemunculan ketaksesuaian berubah dari subgroup ke subgroup tersedia bagan y untuk ketaksesuaian per unit.

Batas-Batas Untuk Bagan c Didasarkan pada distribusi poisson

            Sebelumnya telah dijelaskan bahwa batas eksponensial, binomial poisson berguna bukan hanya sebagai batas binomial tetapi juga sebagai distribusi probabilitas itu sendiri.

            Dalam banyak jenis barang yang diproduksi di pabrik kesempatan munculnya ketaksesuaian banyak sekali, walaupun kesempatan munculnya ketaksesuaian pada satu titik adalah kecil. Jika hal ini benar menurut teori statistik adalah tepat untuk mendasari batas-batas kendali dengan asumsi bahwa distribusi poisson dapat diterapkan. Batas-batas pada bagan kendali c didasarkan pada asumsi ini.

Suatu item yang tidak memenuhi syarat atau yang cacat dalam proses pengendalian kualitas didefinisikan sebagai tidak memenuhi satu atau lebih spesifikasi standar untuk item tersebut maka item tersebut akan dikategorikan cacat atau tidak memenuhi syarat. Penggolongan produk cacat berdasarkan kriteria di atas kadang-kadang untuk jenis produk tertentu dianggap kurang representatif, karena mungkin saja suatu produk masih dapat berfungsi dengan baik walaupun satu atau lebih titik spesifikasi yang tidak memenuhi spesifikasi.

Beberapa contoh jenis ketaksesuaian dimana bagan c dapat diterapkan adalah sebagai berikut:

1. C adalah jumlah paku keeling yang tak sesuai pada pesawat terbang atau badan pesawat terbang.
2. C adalah jumlah kerusakan pada titik-titik lemah dalam isolasi pada panjang tertentu yang diisolasi bila diuji pada tegangan tertentu.
3. C adalah jumlah ketidaksempurnaan permukaan yang diamati dalam lembaran yang dilapisi seng atau yang di cat, disepuh , atau diberi lapisan email pada daerah tertentu.
4. C adalah jumlah “ biji” (kantongan udara kecil)yang diteliti dalam botol kaca.
5. C adalah jumlah ketaksempurnaan yang diteiti dalam satu gulungan kayu bahan baju.
6. C adalah jumlah ketaksempurnaan permukaan dalam segulung kertas berlais atau selembar film foto.

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.