1. Routing Problem :
Suatu daerah akan dibangun jaringan distribusi tegangan menegah (20 kV) yang menelusuri titik persimpangan jalan dengan jarak dan titik-titik persimpangan seperti “peta” berikut :
Carilah jalur terpendek dari A ke X mengikuti pinggiran jalan untuk memasang kabel JTM, hitung panjang kabel yang dipilih?
Jawab :
Untuk mencari jalur terpendek dari A ke X maka perhitungan dimulai dari X ( start from the end), hasilnya dapat dilihat pada table brikut :
| N0 | Dari titik X ke... | Lewat Titik | Jarak Terpendek (m) | N0 | Dari titik X ke... | Lewat Titik | Jarak Terpendek (m) |
| 1 | X | - | 0 | 15 | I | S-N | 550 |
| 2 | S | - | 250 | 16 | J | T-O | 350 |
| 3 | Y | - | 250 | 17 | K | U-P | 450 |
| 4 | T | - | 150 | 18 | L | U-A1-V-Q | 400 |
| 5 | U | - | 50 | 19 | M | U-A1-V-Q-L | 500 |
| 6 | A1 | U | 150 | 20 | D | S-N-I | 650 |
| 7 | Z | U | 200 | 21 | E | U-P-O-J | 550 |
| 8 | W | U-A1 | 250 | 22 | F | U-P-O-J-E | 650 |
| 9 | N | S | 450 | 23 | G | U-A1-P-Q-L | 450 |
| 10 | O | U-P | 350 | 24 | H | U-A1-P-Q-L-G | 650 |
| 11 | P | U | 200 | 25 | B | S-N-I-D | 700 |
| 12 | V | U-A1 | 200 | 26 | C | U-A1-V-Q-L-G | 600 |
| 13 | Q | U-A1-V | 250 | 27 | A | U-A1-V-Q-L-G-C | 700 |
| 14 | R | U-A1-W | 300 | | | | |
☺Jalur terdekat dari A ke X adalah 700 m dengan jalur A-C-G-L-Q-V-A1-U-X (Lihat garis putus2 pada Peta no. 1), sehingga panjang kabel yang diperlukan 700 m
2. Block City Patrol Problem :
Dari jalur TM di atas akan ditempatkan satu set trafo untuk penerangan jalan yang akan disalurkan kesemua titik persimpangan, tentukan dimana letak trafo dipasang supaya kabel TTR yang dipakai sesedikit mungkin. Berapa panjang kabel total??.
Jawab :
Berdasarkan jalur terpendek (jalur TM) maka kemungkinan trafo ditempatkan pada titik G, L, Q, V, A1
| Titik | Jarak terdekat dari… | ||||
| G | L | Q | V | A1 | |
| A B C D E F G H I J K L M N 0 P Q R S T U V W X Y A1 Z | 250 450 150 500 350 250 0 200 600 450 250 50 150 700 450 350 200 300 700 600 400 250 400 750 600 300 500 | 300 500 200 550 400 300 50 250 650 400 200 0 100 650 400 300 150 250 650 550 350 200 300 400 550 250 450 | 550 700 350 650 500 450 200 400 550 300 350 150 250 500 250 150 0 100 500 400 200 50 150 250 400 100 300 | 500 700 400 650 500 600 250 450 550 300 400 200 300 500 250 150 50 150 450 350 150 0 150 200 350 50 250 | 550 650 450 600 550 550 300 500 550 350 450 250 350 550 300 200 100 150 400 300 100 50 100 150 300 0 200 |
| Jumlah | 10.150 | 9.350 | 8.750 | 8.850 | 9.000 |
Berdasarkan tabel hasil perhitungan di atas, untuk penggunaan jumlah kabel sesedikit mungkin, maka satu set trafo tersebut dipasang pada titik Q dengan total panjang kabel 8.750 m. ( letak trafo lihat pada peta no.1)
3. Travelling Salesmen Problem :
Pada tempat trafo, ditempatkan juga pos pengawas, dimana petugas setiap malam berkeliling kesemua titik persimpangan. Tentukan rute terpendek dan jarak yang harus ditempuh, start dari tempat trafo sampai kembali ke pos dengan melalui semua titik persimpangan minimal 1 kali.!
Jawab :
Penentuan jalur terpendek traveling salesman problem merupakan masalah, kombinasi factorial, dimana banyaknya kemungkinan jalur yaitu (n-1)!/2 , table berikut beberapa kombinasi :
| Jalur/Rute | Jarak(m) |
| Q-R-M-L-G-H-C-A-F-E-B-D-I-J-K-P-O-N-S-T-X-U-Y-Z-A1-W-V-Q Q-L-M-H-C-G-F-A-B-E-D-I-J-K-P-O-N-S-T-U-X-Y-Z-A1-V-W-R-Q Q-V-A1-W-R-M-L-G-H-C-A-F-E-B-D-I-N-S-X-Y-Z-U-T-O-J-K-P-Q Q-P-U-A1-V-W-Z-Y-X-S-T-O-N-I-J-K-F-E-D-B-A-C-H-G-L-M-R-Q Q-V-A1-W-R-M-L-G-H-C-A-B-D-E-F-K-J-I-N-O-T-S-X-Y-Z-U-P-Q ……………………………………………………………………….. Dan seterusnya banyak kombinasi (n-1)!/2 | 3900 4300 3800 4250 4000 |
Setelah melakukan beberapa kombinasi jalur, maka jalur terpendek untuk menelusuri semua titik persimpangan minimal satu kali yaitu jalur Q-V-A1-W-R-M-L-G-H-C-A-F-E-B-D-I-N-S-X-Y-Z-U-T-O-J-K-P-Q dengan jarak 3800 m
Kesimpulan :
1. Jalur terdekat dari A ke X adalah 700 m dengan jalur A-C-G-L-Q-V-A1-U-X
2. Berdasarkan peta, untuk penggunaan jumlah kabel sesedikit mungkin, maka satu set trafo tersebut dipasang pada titik Q dengan total panjang kabel 8.750 m
3. Jalur terpendek untuk menelusuri semua titik persimpangan minimal satu kali yaitu jalur Q-V-A1-W-R-M-L-G-H-C-A-F-E-B-D-I-N-S-X-Y-Z-U-T-O-J-K-P-Q dengan jarak 3800 m
Postingan
Comments (0)
Posting Komentar