jaringan

VI. Model Jaringan (Network Models)
Banyak masalah-masalah manajemen yang berhubungan dengan desain sistem
transportasi dan komunikasi dapat dengan memuaskan diselesaikan dengan bantuan
model jaringan dan teknik analisis jaringan. Pada bagian ini akan disajikan dua macam
teknik untuk menyelesaikan masalah jalan pintas dan masalah rentang minimum
(minimal spanning tree problem).
1. Masalah Jalan Pintas (shortest route problem)
Persoalan jalan pintas menyangkut pilihan rute yang harus dilalui untuk mencapai lokasi
tujuan dengan biaya minimum. Konsep biaya tersebut dapat berupa waktu, jarak atau
ongkos perjalanan. Dengan bantuan algoritma jalan pintas akan diperoleh rute perjalanan
yang paling singkat.
Ilustrasi perusahaan METEOR
Perusahaan Meteor bergerak dalam agribisnis Jambu Mete. Saat ini perusahaan akan
memindahkan lokasi pabrik ke satu tempat yang berjarak sekitar 40 km dari pabrik yang
lama. Dengan mempertimbangkan biaya transportasi yang cukup besar untuk
mengangkut material, komponen pabrik dan personil maka perusahaan perlu menetapkan
rute transportasi yang paling singkat. Jaringan transportasi yang dihadapi perusahaan
disajikan pada gambar berikut:
Lokasi baru
Lokasi lama
9
21
16
20
10
4
3
6
8
5
1
2
3
4
5
6
7
Gambar 1.
2
Angka-angka dalam lingkaran menandakan tempat (node) sedangan angka pada garis
(arc) menunjukkan jarak (kilometer). Perusahaan ingin mengetahui rute jalan yang
tersingkat dari lokasi lama (1) ke lokasi baru (7).
Penyelesaian masalah ini dimulai dengan memberikan label, dua bilangan diantara
kurung, di atas atau di bawah lingkaran. Bilangan pertama menunjukkan jarak
sedangkan bilangan ke dua menunjukkan node dari mana jarak tersebut dihitung. Contoh
berikut adalah label pada satu node:
Proses penyelesaian dilakukan dengan pemberian label pada setiap node dimulai dari
lokasi awal (node 1). Label tersebut bersifat permanen bila jarak hingga node tersebut
merupakan yang terpendek. Dari gambar 1 di atas node 1 diberi label [0, S] yang berarti
jarak dari node ke node itu sendiri adalah 0, dan S menandakan node awal (Start) dan
label pada node 1 tersebut adalah permanen. Berikutnya adalah memberikan label pada
node yang terdekat. Node yang terdekat dengan node 1 ada dua yaitu node 2 dan node 3.
Namun demikian node 3 memiliki jarak yang terdekat sehingga diberi label [16,1] yang
berarti jarak dari node 1 ke node tersebut adalah 16 kilometer dan ini bersifat permanen
karena tidak ada lagi rute untuk mencapai node 3 yang lebih singkat. Selain node 3
adalah node 2 yang terdekat dengan node 1 dan node 2 diberi label 20 [20, 1] artinya
jarak dari node 1 adalah 20 kilometer. Namun demikian label ini tidak permanen karena
node 2 dapat dicapai dari node 3 dengan jarak yang kebih singkat yaitu 19 kilometer. oleh
karena itu node 2 diberi label lain yaitu [19, 3] dan bersifat permanen. Sampai dengan
tahap ini proses pelabelan disajikan pada gambar 3 berikut:
[18, 2]
Node
Jarak dari node 1 ke
node ini
Node terakhir setelah node 1
yang menunju node ini
Label
Gambar 2.
3
Selain node 2, node yang terdekat dengan node 3 dan belum diberi label adalah node 5.
Node ini berjarak 6 kilometer dari node 3 sehingga label untuk node 5 adalah [22, 3]
artinya berjarak 22 kilometer dari node 1 yang ditempuh melalui node 3. Sedangkan dari
node 2 terdapat 2 node yang belum berlabel yaitu node 4 dan node 7 dimana node 4
diberi label [27, 2] sedangkan node 7 diberi label [40, 2]. Anda diharapkan sudah bisa
memverifikasi label ini. Hingga tahap ini proses pelabelan disajikan pada gambar 4
berikut:
[0, S]
Lokasi baru
Lokasi lama
9
21
16
20
10
4
3
6
8
5
1
2
3
4
5
6
7
[16, 1]
[19, 3]
[20, 1]
Gambar 3.
4
Tahap berikutnya adalah memberikan label pada node yang dekat dengan node 5 yaitu
node 4 dan node 6. Node 4 diberi label [27, 5] yang berarti memiliki jarak yang sama dari
node 1 baik melalui node 2 maupun node 5. Oleh karena itu kedua label ini bersifat
permanen. Selain node 4 adalah node 6 yang diberi label [26, 5] dan bersifat permanen
karena tidak ada rute lain menuju node ini. Node 5 itu sendiri dapat dicapai melalui node
4 sehingga diberi label [32, 4] namun label tidak permanen karena node 5 berjarak lebih
singkat melalui node 3. Sampai tahap ini proses pelabelan ditunjukkan oleh gambar 5
berikut:
[40, 2]
[26, 5]
[22, 3]
[32,4]
[40, 2]
[27, 2]
[27, 5]
[27, 2]
[0, S]
[0, S]
Lokasi baru
Lokasi baru
Lokasi lama
Lokasi lama
9
9
21
21
16
16
20
20
10
10
4
4
3
3
6
6
8
8
5
5
1
1
2
2
3
3
4
4
5
5
6
6
7
7
[16, 1]
[16, 1]
[19, 3]
[20, 1]
[19, 3]
[20, 1]
[22, 3]
Gambar 5.
Gambar 4.
5
Tahap berikutnya adalah memberikan label pada node lain yang dekat dengan 4 yaitu
node 7 dengan label [37, 4]. Pelabelan juga dilakukan pada node yang dekat dengan node
6 yaitu node 7 dengan label [35, 6]. Dengan selesainya tahap ini maka proses pelabelan
telah selesai karena semua node telah berlabel dan dapat ditentukan mana yang
merupakan label permanen. Akhir proses pelabelan disajikan pada gambar 6. Dari
gambar tersebut terlihat bahwa untuk mencapai node 7 yaitu lokasi pabrik yang baru
maka rute yang memberikan total jarak yang terdekat adalah 1-3-5-6-7 dengan total jarak
yaitu 35 kilometer.
Note:
Penentuan rute tersingkat dapat saja dilakukan dengan melihat jarak antar node dan
memutuskan rute mana yang terpendek secara langsung. Namun demikian bila rute yang
harus dilalui begitu banyak hingga terkadang mencapai 15 hingga 20 maka penentuan
dengan algoritma seperti yang dilakukan di atas akan sangat membantu. Meskipun
dengan menggunakan algoritma bila kompleksitas masalahnya sangat tinggi maka
diperlukan bantuan komputer untuk menyelesaikannya. Program yang dapat digunakan
untuk masalah ini adalah The Management Scientist atau ABQM.
[35, 6]
[37, 4]
[40, 2]
[26, 5]
[22, 3]
[32,4]
[27, 5]
[27, 2]
[0, S]
Lokasi baru
Lokasi lama
9
21
16
20
10
4
3
6
8
5
1
2
3
4
5
6
7
[16, 1]
[19, 3]
[20, 1]
Gambar 6.
6
2. Masalah Rentang Minimum (The Minimal Spanning Tree Problem).
Dalam terminologi model jaringan masalah rentang minimum melibatkan garis-garis
antar node (arcs) pada jaringan yang menjangkau semua node sehingga rentang jarak
yang didapat paling sedikit (minimum).
Ilustrasi masalah perusahaan TELEPOINT
Perusahaan telepoint bergerak dalam layanan komunikasi dan berrencana memperluas
cakupan pelanggan dengan cara membangun stasiun pemancar yang dihubungkan dengan
kabel bawah tanah. Lokasi dan jarak antar stasiun maupun antara stasiun dengan pusat
pengendali disajikan pada gambar 7. Perusahaan ingin menghubungkan semua stasiun
dengan biaya termurah sebagai akibat dari penggunaan kabel yang pendek.
Algoritma model jaringan untuk menyelesaikan masalah ini sangat sederhana, yaitu:
• Dari node pengendali (atau node mana saja) hubungkan dengan node yang terdekat.
Kedua node itu disebut connected nodes dan lainnya adalah unconnected nodes.
• Identifikasi unconnected node yang terdekat dengan connected nodes. Tambahkan
node ini kedalam connected node. Lakukan hal ini hingga semua node terhubungkan
(connected)
Dengan melihat problem perusahaan Telepoint dan memulai dari node 1 maka node yang
terdekat dengannya adalah node 3. Sekarang node 1 dan node 3 disebut connected nodes.
Berikutnya adalah menghubungkan unconnected node yang terdekat dengan salah satu
Node pengendali
9
21
16
20
10
4
3
6
8
5
1
2
3
4
5
6
7
Gambar 7.
7
connected node tersebut yaitu node 2 dengan node 3. Sampai tahap ini proses
penghubungan disajikan pada gambar 8 di bawah:
Berikutnya adalah menghubungkan node 3 dengan node 5 dan selanjutnya node 5 dengan
node 6. Sampai dengan tahap ini ada 3 connected nodes yang berdekatan dengan
unconnected nodes yaitu node 2, node 5 dan node 6 seperti terlihat pada gambar 9
berikut:
Unconnected node yang terdekat adalah node 4 dari node 5 dan connected nodes yang
berdekatan dengan unconnected node (node 7) adalah node 2, node 4, dan node 6. Dari
ketiga connected nodes tersebut yang terdekat dengan node 7 adalah node 6, sehingga
koneksi dilakukan melalui node 6. Dengan telah terhubungkannya semua node yang ada
maka proses ini telah selesai (gambar 10).
Node pengendali
Node pengendali
9
9
21
21
16
16
20
20
10
10
4
4
3
3
6
6
8
8
5
5
1
1
2
2
3
3
4
4
5
5
6
6
7
7
Gambar 8.
Gambar 9.
8
Dari gambar di atas maka total panjang kabel yang diperlukan untuk menghubungkan
semua stasiun adalah:
Node mulai Node berakhir Rentang (km)
1 3 16
3 2 3
3 5 6
5 6 4
5 4 5
6 7 9
Total jarak 43
Masalah perusahaan Telepoint adalah meminimalkan total jarak rentang kabel yang
dibutuhkan, namun model jaringan ini dapat juga digunakan untuk kriteria
meminimumkan biaya atau mempersingkat waktu tempuh.
Node pengendali
9
16 4
3
6
5
1
2
3
4
5
6
7
Gambar 10.