30/05/2014
Techniques of Continuous Space Location Problems – Median method » Rectilinier / Manhattan / City block distance
– Contour-Line method
PERMASALAHAN LOKASI (Model Dasar) [2]
» Constructs regions bounded by counter line which provide feasible point for new facility with the same total cost
– Gravity method » Squared Euclidean distance
– Weiszfeld method » Euclidien distance
• Jika solusi optimal tidak feasibel perlu dilakukan proses lebih lanjut untuk mencari lokasi feasible dan optimal
Types of Distance •
Rectilinear distance / Manhattan distance / City block distance / rigth-angle distance / rectangular distance – 𝑑𝑖𝑗 = 𝑥𝑖 − 𝑥𝑗 + 𝑦𝑖 − 𝑦𝑗 – Aplikasi pada overhead material handling carrier dengan rel tegak lurus
•
(𝑥𝑖 − 𝑥𝑗 )2 +(𝑦𝑖 − 𝑦𝑗 )2
– Aplikasi pada conveyor, jaringan transportasi dan distribusi
•
• Meletakkan fasilitas pada titik median • Contoh Aplikasi: – Level makro: penempatan warehouse – Level mikro: penempatan mesin
Euclidean – 𝑑𝑖𝑗 =
Median Method
Squared Eucledian – 𝑑𝑖𝑗 = (𝑥𝑖 − 𝑥𝑗 )2+(𝑦𝑖 − 𝑦𝑗 )2 – Memberikan bobot terbesar pada jarak terdekat
𝑥𝑖 : 𝑘𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡 𝑥 𝑙𝑜𝑘𝑎𝑠𝑖 𝑖 𝑦𝑖 : 𝑘𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡 𝑦 𝑙𝑜𝑘𝑎𝑠𝑖 𝑖 𝑥𝑗 : 𝑘𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡 𝑥 𝑙𝑜𝑘𝑎𝑠𝑖 𝑗 𝑦𝑗 : 𝑘𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡 𝑥 𝑙𝑜𝑘𝑎𝑠𝑖 𝑗 𝑑𝑖𝑗 : 𝑗𝑎𝑟𝑎𝑘 𝑙𝑜𝑘𝑎𝑠𝑖 𝑖 𝑑𝑎𝑛 𝑗
• Frekuensi lintasan lokasi 𝑖 (𝑓𝑖 ) dan biaya transportasi (𝑐𝑖 ) ke lokasi baru diketahui. Dan karena nilainya konstan maka dapat ditetapkan sebagai bobot lokasi 𝑖 (𝑤𝑖 ) – 𝑤𝑖 = 𝑐𝑖 ∗ 𝑓𝑖
1
30/05/2014
Median Method
Median Method
• Tujuan Median Method:
𝑚 𝑖=1 𝑐𝑖 𝑓𝑖 𝑥𝑖 − 𝑥 + » 𝑇𝐶 ∶ 𝑇𝑜𝑡𝑎𝑙 𝑏𝑖𝑎𝑦𝑎 𝑑𝑖𝑠𝑡𝑟𝑖𝑏𝑢𝑠𝑖 » 𝑥 , 𝑦 ∶ 𝑘𝑜𝑜𝑟𝑑𝑖𝑛𝑎𝑡 𝑜𝑝𝑡𝑖𝑚𝑎𝑙 𝑙𝑜𝑘𝑎𝑠𝑖 𝑏𝑎𝑟𝑢
– Meminimasi 𝑇𝐶 =
• Contoh Soal:
𝑦𝑖 − 𝑦
• Langkah-langkah Metode Median: – Langkah1. Urutkan lokasi mulai koordinat 𝑥 terkecil – Langkah2. Tentukan lokasi 𝑗 dari urutan pada langkah1 yang nilai 1 1 kumulatif bobotnya bernilai atau lebih dari untuk pertama kali. 𝑗−1
𝑚
𝑤𝑖 < 𝑖=1
𝑖=1
𝑤𝑖 𝑑𝑎𝑛 2
𝑗
2
𝑚
𝑤𝑖 ≥ 𝑖=1
𝑖=1
2
𝑤𝑖 2
– Terdapat 4 divisi di lantai 5 yang telah memiliki satu mesin fotokopi, namun karena kebutuhan yang tinggi diperlukan satu mesin fotokopi baru untuk digunakan bersama. Cari lokasi fotokopi yang optimal, jika diketahui koordinat centroid masing-masing divisi dan rata-rata trafic penggunaan ke fotokopi baru per divisi. Asumsi jarak yang ditempuh dimulai dan berakhir pada centroid lokasi.
– Langkah3. Urutkan lokasi mulai koordinat 𝑥 terkecil – Langkah4. Tentukan lokasi 𝑘 dari urutan pada langkah3 yang nilai 1 1 kumulatif bobotnya bernilai atau lebih dari untuk pertama kali. 𝑘−1
𝑚
𝑤𝑖 < 𝑖=1
𝑖=1
𝑤𝑖 𝑑𝑎𝑛 2
𝑘
2
𝑚
𝑤𝑖 ≥ 𝑖=1
𝑖=1
No. Divisi
Koordinat x
Koordinat y
1
10
2
6
2
10
10
10
3
8
6
8
4
12
5
4
2
𝑤𝑖 2
– Lokasi baru OPTIMAL adalah 𝒙: 𝒋 𝒍𝒌. 𝟐 𝒅𝒂𝒏 𝒚: 𝒌 (𝒍𝒌. 𝟒)
Median Method
Median Method
• Contoh Soal: – Langkah 1 No. Divisi
• Contoh Soal: – Langkah 3 Koordinat x
Bobot
3
8
1
10
2 4
𝑤𝑖 2
=
• 𝑗 = 10
28 2
Kumulatif Bobot
No. Divisi
Koordinat y
Bobot
Kumulatif Bobot
8
8
1
2
6
6
6
14
4
5
4
10
10
10
24
3
6
8
18
12
4
28
2
10
10
28
– Langkah 4
– Langkah 2 •
Rata2 trafic pemakaian
= 14
•
𝑤𝑖 2
=
28 2
= 14
• 𝑘=6
– Lokasi Optimal : (10, 6)
2
30/05/2014
Gravity Method • Untuk jarak yang bersifat tidak linier: fungsi kuadrat • Jenis jarak: squared Euclidean • Hasil optimal: pusat gravitasi (sering disebut Metode Pusat Gravitasi) • Tujuan: Meminimasi 𝑇𝐶 =
𝑚 𝑖=1 𝑐𝑖 𝑓𝑖
• Lokasi baru optimal:
𝜕𝑇𝐶 𝜕𝑥
𝜕𝑇𝐶 𝜕𝑦
=2
=2
𝑚 𝑖=1 𝑤𝑖 𝑥
2
• Contoh Soal: – Permasalahan yang sama dengan Metode Median: No. Divisi
𝒙𝒊
𝒚𝒊
𝒘𝒊
𝒘𝒊𝒙𝒊
1
10
2
6
60
12
2
10
10
10
100
100
3
8
6
8
64
48
4
12
5
4
48
20
28
272
180
2
(𝑥𝑖 − 𝑥) +(𝑦𝑖 − 𝑦)
𝑚 𝑖=1 𝑤𝑖 𝑥𝑖 = 𝑚 𝑤𝑖 𝑥𝑖 𝑥 = 𝑖=1 𝑚 𝑖=1 𝑤𝑖 𝑚 𝑚 𝑖=1 𝑤𝑖 𝑦 − 2 𝑖=1 𝑤𝑖 𝑦𝑖 = 𝑚 𝑤𝑖 𝑦𝑖 𝑦 = 𝑖=1 𝑚 𝑖=1 𝑤𝑖
−2
Gravity Method
0
Total
272 = 9.71 28 180 𝑦= = 6.43 28
0
𝑥=
Fungsi Tujuan Weiszfeld Method
Weiszfeld Method • Metode kuantitatif untuk menentukan posisi (dalam koordinat) fasilitas baru yang akan ditempatkan di antara beberapa fasilitas lainnya yang sudah terpasang. • Ukuran jarak yang dipergunakan dalam metode ini adalah Jarak Euclidean.
𝒘𝒊 𝒚𝒊
MINIMIZE m
TC ci . f i .( ( xi x) 2 ( yi y) 2 ) i 1
TC c f x y m w
w ci . f i
= Total Cost i = Biaya perpindahan = Frekuensi perpindahan = Koordinat fasilitas pada sumbu x = Koordinat fasilitas pada sumbu y = Banyaknya fasilitas yang telah terpasang = Bobot perpindahan
3
30/05/2014
Koordinat Fasilitas X
3 Langkah Iterasi
m wi .xi 2 2 i 1 ( xi x) ( yi y ) x m wi 2 2 i 1 ( xi x) ( yi y )
Langkah 0 : * Nyatakan k = 1
m
k
x
i 1 m
i
Langkah 1 : * Nyatakan : x
m wi . yi 2 2 i 1 ( xi x) ( yi y ) y m wi i 1 ( xi x) 2 ( yi y ) 2
k 1
k
y
w .y i 1 m
i
i
w
i
i 1
m wi .xi k k i 1 ( xi x ) 2 ( yi y ) 2 m wi k k i 1 ( xi x ) 2 ( yi y ) 2
y
k 1
i
m wi . yi k 2 k 2 i 1 ( x x ) ( y y ) i i m wi k k i 1 2 2 ( x x ) ( y y ) i i
Langkah 2 : k 1
k 1
k
k
•Jika x x dan y y , maka stop. Jika tidak maka nyatakan k = k+1 dan kembali ke langkah 1.
Iterasi 1
Contoh Soal Dua buah mesin fax yang akan dipergunakan oleh 4 departemen. Koordinat ke 4 buah mesin dan rata-rata jumlah pemakaian mesin fax dinyatakan tabel dibawah ini. Koordinat Y (Yi)
i
w i 1
Koordinat Fasilitas Y
m
w .x
Rata-rata jumlah permakaian mesin fax (Wi)
Departemen
Koordinat X (Xi)
1
10
2
6
2
10
10
20
3
8
6
8
4
12
5
4
Dept 1 2 3 4
xi 10 10 8 12
yi 2 10 6 5
wi 6 20 8 4
w i. x i 60 200 64 48
wi.yi 12 200 48 20
38
372
280
60 200 64 48 9.8 6 20 8 4 0 12 200 48 20 y 7.4 6 20 8 4 0
x
4
30/05/2014
Dept
xi
yi
wi
wi. xi [a]
wi.yi [b]
1
10
2
6
60
2
10
10
20
3
8
6
4
12
5
( xi –x0 )2 [c]
( y i – y 0 )2 [d]
[e] = Akar ([c]+[d])
[a] / [e]
[b] / [e]
wi / [e]
12
0.04
28.82
5.37
11.16
2.23
1.11
200
200
0.04
6.93
2.63
75.75
75.75
7.57
8
64
4
48
48
3.20
1.87
2.25
28.40
21.30
20
4.89
5.61
3.23
14.81
6.17
38
372
280
130.15
105.47
1
x
130.15 9.7 13.47
105.47 y 7.8 13.47 1
HASIL KESELURUHAN ITERASI
Karena nilai X dan Y tidak berubah pada iterasi ke 25 dengan koordinat (10,10) Maka posisi mesin fax akan diletakkan di kordinat (10,10)
Iterasi ke-
x
y
TC
1
9.7
7.8
113.4
2
9.7
8.2
111.9
3
9.8
8.4
110.8
4
9.8
8.7
109.9
5
9.8
8.9
109.1
6
9.9
9
108.5
7
9.9
9.2
108
8
9.9
9.3
107.6
9
9.9
9.4
107.2
10
9.9
9.5
106.9
11
9.9
9.6
106.7
12
10
9.6
106.5
…
…
…
…
20
10
9.9
105.6
…
…
…
…
25
10
10
105.5
Total Cost Iterasi 1 wi
( xi –x1 )2 [f]
( yi –x1 )2 [g]
[h]=akar ([f]+[g])
TC1=(wi.[h])
3.55
6
0.12
33.93
5.83
35.0
1.23
20
0.12
4.73
2.20
44.0
13.47
8
2.74
3.33
2.46
19.7
4
5.49
7.98
3.67
14.7
38
113.4
Karena x1 tidak sama dengan x0, dan y1 tidak sama dengan y0, maka Lakukan kembali iterasi ke-2 mulai dari langkah ke2.
Contour-Line Method • Digunakan untuk mengeliminasi kemungkinan lokasi baru berada di lokasi yang telah ada, dimana dua fasilitas yang sama tidak dapat berada di satu tempat yang sama • Meletakkan lokasi baru pada daerah terdekat dengan biaya paling minimal (feasible near optimal location) • Metode ini membentuk area geografis yang dibentuk oleh garis contour • Garis contour merupakan alternatif lokasi baru dengan nilai biaya yang sama • Kelebihan Contour-line Method: – Memberikan alternatif lokasi jika lokasi optimal infeasibel – Dapat mengakomodasi kriteria subyektif, yaitu dengan menggeser lokasi optimal awal sepanjang contour-line hingga memenuhi kriteria subyektif tersebut
5
30/05/2014
Contour-Line Method
• Langkah-langkah: 1.
Plot lokasi saat ini beserta bobotnya sesuai dengan koordinatnya
3.
Jumlahkan bobot pada titik lokasi yang dilewati oleh tiap garis. Notasikan V untuk jumlah bobot pada garis Vertikal, dan H untuk jumlah bobot pada garis Horisontal
www.aeunike.lecture.ub.ac.id
2.
Contour-Line Method
Tarik garis horisontal dan vertikal yang melintasi titik-titik lokasi saat ini
Contour-Line Method
𝐻5 : 𝐻4 : 𝐻3 : 𝐻2 : 𝐻1 :
www.aeunike.lecture.ub.ac.id
𝑉1 :
𝑉2 :
www.aeunike.lecture.ub.ac.id
𝑉3 :
𝑉4 :
𝑉5 :
6
30/05/2014
4.
Contour-Line Method
Jumlahkan bobot dan notasikan 𝑁0 = 𝐷0 = − 𝑁𝑖 = −
𝑚 𝑖=1 𝑤𝑖
+2
𝑖 𝑘=1 𝑉𝑘 ;
𝐷𝑖 = −
Contour-Line Method
𝑚 𝑖=1 𝑤𝑖
𝑚 𝑖=1 𝑤𝑖
+2
5.
Hitung gradien masing-masing area: −
𝑖 𝑘=1 𝐻𝑘
𝑁0 :
𝑁0 :
𝑁1 :
𝑁2 :
𝑁3 :
𝑁𝑠 𝐷𝑡
𝑁4 :
𝑁5 :
:𝐷5
:𝐷4 :𝐷3
:𝐷2 :𝐷1 :𝐷0
:𝐷0
www.aeunike.lecture.ub.ac.id
6.
www.aeunike.lecture.ub.ac.id
Contour-Line Method
References
Pilih titik sembarang dan gambarkan garis contour-nya sesuai dengan gradien tiap area. • • •
Heragu, S. (2008). Facilities Design (3rd Ed.). CRC Press. Tompkins, W, Tanchoco, B. (2003). Facilities Planning (3rd Ed.). John Wiley & Sons. Wignjosoebroto, S. & Rahman, A. (2011). Analisa Lokasi & Permasalahan Alokasi (PPT). Surabaya: Teknik Industri – ITS.
www.aeunike.lecture.ub.ac.id
7
