Model 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.