Ilustrasi Tutorial Biaya Lintasan Raster: Menghitung Rute Termurah dengan Dijkstra

Tutorial Biaya Lintasan Raster: Menghitung Rute Termurah dengan Dijkstra

Hitung biaya lintasan raster dengan contoh Dijkstra, bedakan rute termurah dari terpendek, lalu uji ketetanggaan, sel terlarang, dan hasil jalurnya.

Jarak terpendek belum tentu biaya terkecil

Perencanaan lintasan pada raster dapat memperhitungkan perbedaan hambatan antarbagian wilayah. Sebuah jalur pendek yang melewati sel berbiaya tinggi dapat lebih mahal daripada jalur memutar melalui sel berbiaya rendah. Analisis biaya lintasan membantu menelusuri konsekuensi model tersebut untuk kajian akses, koridor, atau skenario pemetaan. Hasilnya bergantung pada definisi biaya dan gerakan yang diizinkan, sehingga garis keluaran perlu dibaca sebagai hasil model, bukan langsung sebagai jalur yang tersedia di lapangan.

Tutorial ini memakai kisi kecil buatan dan algoritme Dijkstra yang dapat diikuti dengan tabel. Dokumentasi r.cost memberi konteks biaya kumulatif serta arah untuk menelusuri jalur, sementara dokumentasi SciPy menjelaskan Dijkstra dengan bobot tidak negatif dan matriks pendahulu. Aturan bobot latihan ditetapkan sendiri secara eksplisit. Contoh ini tidak mengklaim mereproduksi pengaturan bawaan suatu perangkat. Dengan menghitung beberapa langkah, pengguna dapat memeriksa arti biaya sebelum menjalankan analisis pada data wilayah yang lebih besar.

Kisi tiga kali tiga dengan hambatan pusat seratus, jalur langsung melewati pusat dan jalur minimum melalui baris atas
Pada model empat tetangga, jalur langsung panjangnya 20 m tetapi berbiaya 1.010 unit. Jalur atas atau bawah sepanjang 40 m hanya berbiaya 40 unit. — Tim editorial TechnoGIS (Original editorial illustration)

Prasyarat dan definisi kisi latihan

Prasyaratnya adalah tabel tiga baris dan tiga kolom, kalkulator, serta kemampuan menjumlahkan biaya. Setiap sel berukuran 10×10 meter dalam kerangka bidang buatan. Baris dihitung dari atas dan kolom dari kiri, mulai satu. Titik awal S berada pada pusat sel (2,1), sedangkan tujuan T pada pusat sel (2,3). Nilai hambatan c semua sel adalah 1, kecuali pusat (2,2) yang bernilai 100. Satuan c didefinisikan sebagai unit biaya per meter, tanpa menyatakan mata uang atau waktu nyata.

Gerakan dasar hanya melalui sisi: atas, bawah, kiri, dan kanan. Biaya satu langkah dari sel i menuju sel j adalah w(i,j)=((ci+cj)/2)×dij, dengan dij jarak antarpusat sel dalam meter. Untuk tetangga sisi, dij=10. Biaya dari S ke sel biasa adalah 10 unit, sedangkan dari S ke pusat mahal adalah ((1+100)/2)×10=505 unit. Sediakan kolom biaya sementara, status selesai, dan pendahulu untuk setiap sel agar jejak perhitungannya tetap dapat ditinjau.

Tabel perbandingan biaya dan panjang rute untuk empat tetangga, delapan tetangga, serta kolom tengah yang tidak dapat dilewati
Biaya minimum bergantung pada aturan gerak dan mask. Skenario delapan tetangga memberi 20√2 unit; kolom tengah terlarang membuat tujuan tidak terjangkau. — Tim editorial TechnoGIS (Original editorial illustration)

1. Bedakan biaya tinggi dari sel yang dilarang

Sel bernilai 100 masih boleh dilalui menurut model latihan; ia hanya mahal. Jika suatu wilayah memang tidak boleh dimasuki, gunakan mask larangan yang menghapus hubungan gerak menuju wilayah itu. Jangan memakai angka sangat besar sebagai pengganti larangan tanpa menyadari bahwa algoritme masih dapat memilihnya bila alternatif lain lebih mahal. Sel tanpa data juga perlu aturan tersendiri. Catatan metode harus membedakan hambatan terukur, larangan, dan kondisi yang belum diketahui.

Dokumentasi r.cost menjelaskan bahwa sel null dikecualikan secara bawaan, tetapi tersedia pilihan untuk memberinya biaya. Ini menunjukkan mengapa makna NoData perlu diperiksa pada perangkat yang dipakai. Dalam latihan utama semua sembilan sel valid dan diperbolehkan. Simpan salinan kisi awal sebelum mengubah mask atau nilainya. Dengan demikian, perbedaan hasil antarskenario dapat dikaitkan pada perubahan yang jelas, bukan pada penggantian data tanpa catatan selama proses berlangsung.

2. Tetapkan biaya awal dan buka tetangga S

Isi biaya sementara S dengan nol karena perjalanan belum dimulai. Sel lain belum mempunyai biaya terjangkau; tulis tak hingga atau status belum terjangkau, bukan nol. Pilih S sebagai sel belum selesai dengan biaya terkecil. Tetangganya adalah (1,1), (3,1), dan (2,2). Berikan biaya sementara 10, 10, dan 505, masing-masing dengan pendahulu S. Setelah tetangga diperiksa, tandai S selesai. Pendahulu menyimpan dari sel mana biaya terbaik yang diketahui itu diperoleh.

Pemilihan sel berikutnya memakai biaya kumulatif terkecil, bukan nilai hambatan sel saja. Dua sel biasa dapat mempunyai biaya perjalanan berbeda karena letaknya terhadap titik awal. Pada latihan, pecahkan biaya sama dengan urutan baris lalu kolom untuk memudahkan pengulangan. Aturan pemecah seri menentukan jalur yang disimpan ketika beberapa jalur sama baik, tanpa mengubah nilai biaya minimum. Simpan aturan tersebut agar gambar lintasan yang berbeda tidak langsung dianggap menunjukkan kegagalan perhitungan.

3. Perbarui biaya melalui tetangga yang lebih murah

Pilih (1,1) yang mempunyai biaya 10. Langkah menuju (1,2) menambah 10 sehingga kandidat biayanya 20; simpan pendahulu (1,1). Kemudian (3,1) juga berbiaya 10 dan memberi (3,2) biaya 20. Saat (1,2) dipilih, biaya menuju (1,3) menjadi 30. Kandidat menuju pusat melalui (1,2) adalah 20+505=525, lebih besar daripada 505 yang sudah tersimpan. Karena itu, jangan mengganti biaya pusat atau pendahulunya dengan kandidat yang lebih mahal.

Aturan pembaruan dapat ditulis kandidat=D(i)+w(i,j). Jika kandidat lebih kecil daripada D(j), ganti D(j) dan pendahulunya. Lanjutkan dengan (3,2), yang memberi (3,3) biaya 30. Pendekatan ini menilai total biaya yang telah ditempuh, lalu memperluas pilihan paling murah yang belum selesai. Untuk latihan dengan semua bobot tidak negatif, biaya sel yang dipilih dan diselesaikan sudah minimum. Dokumentasi Dijkstra juga menyebut bobot negatif sebagai kondisi yang tidak didukung algoritme tersebut.

4. Selesaikan tujuan dan telusuri pendahulu

Dari (1,3) dengan biaya 30, satu langkah ke T menambah 10 sehingga T mendapat biaya 40. Jalur bawah melalui (3,3) memberi nilai sama. Dengan aturan seri latihan, pertahankan pendahulu yang pertama memberi biaya tersebut. Saat T menjadi sel belum selesai dengan biaya terkecil dan kemudian diselesaikan, hasil minimum menuju T adalah 40 unit. Jangan berhenti hanya ketika tujuan pertama kali memperoleh angka sementara pada masalah lain; kandidatnya masih dapat diperbaiki sebelum giliran penyelesaiannya.

Telusuri T→(1,3)→(1,2)→(1,1)→S, lalu balik urutannya untuk mendapatkan jalur dari awal. Ada empat langkah sisi sepanjang masing-masing 10 meter, sehingga panjangnya 40 meter dan biayanya 40 unit. Jalur bawah juga minimum pada model yang sama. Periksa bahwa pendahulu setiap sel benar-benar tetangga yang diizinkan dan bahwa penelusuran berakhir pada S. Rantai yang terputus atau berputar menunjukkan masalah pada pencatatan atau definisi hubungan.

5. Bandingkan jalur langsung sebagai verifikasi

Jalur langsung S→(2,2)→T hanya mempunyai panjang 20 meter. Namun kedua langkahnya masing-masing berbiaya 505, sehingga totalnya 1.010 unit. Bandingkan dengan jalur memutar sepanjang 40 meter berbiaya 40 unit. Hasil ini memeriksa bahwa proses meminimalkan jumlah bobot, bukan jumlah langkah atau panjang saja. Dalam dokumentasi SciPy, mode tanpa bobot mempunyai arti berbeda karena menilai jumlah sisi. Pilihan semacam itu tidak boleh tertukar dengan tujuan biaya yang ditetapkan pada awal latihan.

Uji tambahan dilakukan dengan mengubah semua c menjadi 1. Dalam model empat tetangga ini, rute langsung kembali minimum dengan dua langkah, panjang 20 meter, dan biaya 20 unit. Jika hasil tidak berubah dari skenario pusat mahal, periksa apakah kisi baru benar-benar digunakan dan bobot hubungan dihitung ulang. Pengujian kecil tersebut lebih mudah ditelusuri daripada menilai garis hasil pada wilayah besar tanpa mengetahui biaya tiap langkah yang membentuknya.

6. Uji perubahan tetangga dan mask

Bila delapan tetangga diperbolehkan, jarak pusat sel diagonal adalah 10√2 meter. Dengan bobot latihan yang sama, jalur S→(1,2)→T melewati dua hubungan diagonal antar-sel biasa dan berbiaya 20√2, sekitar 28,28427 unit. Nilai itu berbeda dari 40 karena ruang geraknya berubah. Aturan lintasan diagonal di dekat sudut sel terlarang juga harus ditetapkan. Hasil delapan tetangga tidak boleh dibandingkan sebagai perubahan kondisi wilayah jika sebenarnya perbedaannya berasal dari aturan model.

Kembalikan empat tetangga, lalu larang seluruh kolom kedua sebagai skenario terpisah. S dan T tidak lagi terhubung sehingga tujuan harus berstatus tidak terjangkau. Jangan memberinya biaya nol atau menggambar garis lurus pengganti. Artikel konektivitas jaringan jalan pada blog TechnoGIS memberi konteks tentang pentingnya hubungan yang benar sebelum menghitung rute. Pada raster, pilihan tetangga, batas wilayah, serta mask sama pentingnya bagi keberadaan jalur yang dapat ditemukan.

7. Serahkan biaya, jalur, dan asumsi bersama

Simpan kisi hambatan, mask, titik awal dan tujuan, aturan bobot, ukuran sel, pilihan tetangga, biaya tujuan, pendahulu, serta jalur hasil. Pastikan jumlah biaya tiap langkah kembali 40 pada skenario utama. Pisahkan panjang meter dari unit biaya pada tabel dan legenda. Untuk penerapan nyata, sumber nilai hambatan serta alasan pembobotannya perlu diperiksa bersama pengguna data. Angka buatan pada latihan tidak menetapkan biaya ekonomi, waktu tempuh, atau akses legal suatu koridor.

Laman resmi TechnoGIS Indonesia menyediakan konteks pemetaan dan GIS dalam perencanaan analisis wilayah. Biaya lintasan dapat membantu membandingkan skenario bila input dan definisinya jelas. Perubahan resolusi, titik awal, hambatan, atau aturan gerak dapat mengubah jalur, sehingga versi parameter perlu dipertahankan. Gunakan hasil sebagai bahan kajian yang masih memerlukan pemeriksaan kondisi lapangan dan kebutuhan pekerjaan, dengan bukti hitungan yang memungkinkan tim lain mengulang serta menjelaskan pilihan rutenya.

Bacaan terkait

Pelajari informasi terkait untuk menyesuaikan langkah di atas dengan kebutuhan tim Anda:

Sumber dan referensi

0 replies

Leave a Reply

Want to join the discussion?
Feel free to contribute!

Tinggalkan Balasan

Alamat email Anda tidak akan dipublikasikan. Ruas yang wajib ditandai *