pgRouting untuk Analisis Jaringan - Mencari Rute Terpendek dengan PostGIS dari Nol

Dulu saya pikir bikin aplikasi peta cuma soal nampilin marker dan polygon. Begitu klien minta fitur "cari rute terpendek dari A ke B", saya baru sadar betapa rumitnya network analysis di GIS. Untungnya PostGIS punya extension yang specifically dirancang untuk masalah ini: pgRouting. Saya sudah pakai di beberapa project WebGIS dan hasilnya keren banget.

pgRouting itu extension PostGIS yang ngasih kamu kemampuan shortest path computation langsung di database. Gak perlu library tambahan di aplikasi, cukup satu SQL query dan kamu dapet rute optimal antara dua titik. Bayangin bikin app kayak Google Maps lite, tapi semuanya jalan di PostgreSQL kamu sendiri.

Apa Itu pgRouting dan Kenapa Kamu Butuh?

pgRouting adalah extension PostgreSQL yang dibangun di atas PostGIS untuk analisis jaringan (network analysis). Jika PostGIS fokus pada geometri spasial seperti titik, garis, dan polygon, pgRouting fokus pada graf (graph) yang terdiri dari node dan edge. Setiap edge punya cost atau weight, yang bisa berupa jarak, waktu tempuh, atau biaya lainnya.

Beberapa algoritma yang tersedia di pgRouting:

• pgr_dijkstra - algoritma Dijkstra untuk shortest path, paling umum dipakai
• pgr_aStar - A* algorithm, lebih cepat dari Dijkstra karena pakai heuristik
• pgr_dijkstraVia - rute dengan multiple waypoint, kayak navigation app yang lewat beberapa titik
• pgr_drivingDistance - area yang bisa dijangkau dalam jarak/waktu tertentu (isochrone)
• pgr_ksp - K shortest paths, nemuin beberapa rute alternatif sekaligus
• pgr_tsp - Traveling Salesman Problem, rute optimal untuk kunjungi multiple titik

Saya paling sering pakai pgr_dijkstra karena stabil dan gampang dipahami. pgr_aStar cocok kalau datanya gede banget dan butuh performa lebih cepat.

Install pgRouting di PostgreSQL

Sebelum mulai, pastikan PostgreSQL dan PostGIS sudah terinstall. pgRouting adalah extension tambahan yang dipasang terpisah. Di Ubuntu/Debian:

# Install PostGIS dan pgRouting sekaligus
sudo apt update
sudo apt install postgresql-14-postgis-3 postgresql-14-pgrouting

# Masuk ke PostgreSQL
sudo -u postgres psql

# Bikin database baru (atau pakai yang sudah ada)
CREATE DATABASE webgis_db;

# Connect ke database
\c webgis_db

# Aktifkan extension yang dibutuhkan
CREATE EXTENSION postgis;
CREATE EXTENSION pgrouting;

# Verifikasi pgRouting terinstall
SELECT extname, extversion FROM pg_extension WHERE extname = 'pgrouting';

Outputnya harus nunjukin pgrouting dengan versi 3.x. Kalau gagal, kemungkinan package name beda tergantung versi PostgreSQL kamu. Cek dengan apt search pgrouting dulu.

Menyiapkan Data Jaringan Jalan

pgRouting butuh data jalan dalam format topologi graf. Setiap jalan harus punya source (node awal), target (node akhir), dan cost (biasanya panjang segmen). Saya biasanya pakai data OpenStreetMap karena gratis dan lengkap. Untuk import OSM data ke PostGIS, saya pakai osm2pgrouting.

# Install osm2pgrouting
sudo apt install osm2pgrouting

# Download data OSM area yang kamu mau
# Contoh: area Jakarta Pusat
wget -O jakarta.osm https://api.openstreetmap.org/api/0.6/map?bbox=106.76,-6.21,106.85,-6.13

# Import ke database
osm2pgrouting -f jakarta.osm -d webgis_db -U postgres -W

# Cek tabel yang dihasilkan
psql -U postgres -d webgis_db -c "\dt"

osm2pgrouting akan bikin beberapa tabel: ways (data jalan), ways_vertices_pgr (node jaringan), dan beberapa tabel config. Tabel ways punya kolom-kolom penting seperti source, target, cost, length, dan the_geom.

Kalau kamu gak mau pakai osm2pgrouting, bisa juga import shapefile jalan pakai shp2pgsql, lalu bikin topologi manual. Tapi cara manual lebih ribet karena kamu harus ngitung source/target node sendiri pakai pgr_createTopology().

Query Shortest Path dengan Dijkstra

Ini bagian serunya. Setelah data siap, mencari rute terpendek cuma butuh satu query. Saya ingat pertama kali jalan query ini, rasanya kayak sihir. Kamu kasih dua titik, dapet rute lengkap dengan geometri yang bisa langsung ditampilin di peta.

-- Cari rute terpendek antara node 100 dan node 500
SELECT * FROM pgr_dijkstra(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    100,
    500,
    directed := false
);

Hasil query ini bakal ngasih sequence path, node, edge, cost, dan agg_cost. Tapi ini cuma ngasih node dan edge ID, belum geometri. Untuk dapetin geometri rute yang bisa ditampilin di Leaflet atau OpenLayers, kamu perlu join dengan tabel ways:

-- Rute lengkap dengan geometri untuk ditampilin di peta
SELECT seq, node, edge, cost, agg_cost,
       ways.the_geom AS route_geom
FROM pgr_dijkstra(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    100,
    500,
    directed := false
) AS path
JOIN ways ON path.edge = ways.id;

Kolom route_geom berisi LineString yang bisa kamu konversi ke GeoJSON di aplikasi kamu. Saya biasanya pakai ST_AsGeoJSON() untuk langsung dapet format GeoJSON yang siap dipakai Leaflet.

-- Output GeoJSON untuk Leaflet.js
SELECT jsonb_build_object(
    'type', 'FeatureCollection',
    'features', jsonb_agg(
        jsonb_build_object(
            'type', 'Feature',
            'geometry', ST_AsGeoJSON(ways.the_geom)::jsonb,
            'properties', jsonb_build_object(
                'sequence', path.seq,
                'cost', path.cost,
                'accumulated_cost', path.agg_cost
            )
        )
    )
) AS geojson
FROM pgr_dijkstra(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    100, 500, directed := false
) AS path
JOIN ways ON path.edge = ways.id;

Menemukan Node Terdekat dari Koordinat

Dalam aplikasi nyata, user gak ngasih node ID. Mereka kasih koordinat latitude/longitude. Jadi kamu perlu nemuin node terdekat dari koordinat tersebut. Ini penting banget karena tanpa ini, user gak bisa interaksi langsung dengan peta.

-- Cari node terdekat dari koordinat tertentu
-- Contoh: koordinat Monas Jakarta (-6.1754, 106.8272)
SELECT id, the_geom,
       ST_Distance(the_geom, ST_SetSRID(ST_MakePoint(106.8272, -6.1754), 4326)) AS jarak
FROM ways_vertices_pgr
ORDER BY the_geom <-> ST_SetSRID(ST_MakePoint(106.8272, -6.1754), 4326)
LIMIT 1;

Operator <-> itu KNN (K-Nearest Neighbor) operator dari PostGIS, jauh lebih cepat dari ORDER BY ST_Distance karena pakai GiST index. Pastikan kamu sudah bikin index spasial di kolom the_geom:

CREATE INDEX ways_vertices_pgr_geom_idx
ON ways_vertices_pgr USING GIST (the_geom);

Cost Berdasarkan Waktu Tempuh, Bukan Jarak

Awalnya saya cuma pakai cost = panjang jalan. Tapi klien saya bilang, "tolong, jalan tol sama jalan kecil itu beda kecepatan." Benar juga. Rute terpendek berdasarkan jarak belum tentu rute tercepat. Kamu bisa bikin cost berdasarkan estimasi waktu tempuh dengan memperhitungkan kategori jalan.

-- Update cost berdasarkan tag class (highway type)
-- class 1 = motorway (cepat), class 5 = residential (lambat)
UPDATE ways SET cost_s = CASE
    WHEN tag_id = 1 THEN length / 1000 * 60 / 100  -- 100 km/h
    WHEN tag_id = 2 THEN length / 1000 * 60 / 80   -- 80 km/h
    WHEN tag_id = 3 THEN length / 1000 * 60 / 60   -- 60 km/h
    WHEN tag_id = 4 THEN length / 1000 * 60 / 40   -- 40 km/h
    ELSE length / 1000 * 60 / 30                     -- 30 km/h default
END;

-- Pakai cost_s (detik) sebagai cost untuk rute tercepat
SELECT * FROM pgr_dijkstra(
    'SELECT id, source, target, cost_s AS cost FROM ways WHERE cost_s > 0',
    100, 500, directed := false
);

Hasilnya, rute yang ditemukan bakal ngutamain jalan raya dan tol karena cost (waktu) lebih rendah, walaupun mungkin jaraknya lebih jauh. Inilah yang bikin pgRouting powerful untuk navigation app.

Integrasi pgRouting dengan PHP dan CodeIgniter 4

Kalau kamu bikin WebGIS dengan CI4 (seperti yang saya sering lakukan), query pgRouting bisa dipanggil langsung dari model. Berikut contoh controller dan model untuk endpoint routing API:

<?php
// app/Controllers/Routing.php
namespace App\Controllers;

use App\Models\M_Routing;
use CodeIgniter\API\ResponseTrait;

class Routing extends BaseController
{
    use ResponseTrait;

    public function findRoute()
    {
        $startLat = $this->request->getGet('start_lat');
        $startLng = $this->request->getGet('start_lng');
        $endLat   = $this->request->getGet('end_lat');
        $endLng   = $this->request->getGet('end_lng');

        $model = new M_Routing();

        // Cari node terdekat untuk start dan end
        $startNode = $model->findNearestNode($startLng, $startLat);
        $endNode   = $model->findNearestNode($endLng, $endLat);

        if (!$startNode || !$endNode) {
            return $this->failNotFound('Node tidak ditemukan');
        }

        // Hitung rute
        $route = $model->shortestPath($startNode->id, $endNode->id);

        if (empty($route)) {
            return $this->failNotFound('Rute tidak ditemukan');
        }

        return $this->respond([
            'status'  => 'success',
            'start'   => $startNode,
            'end'     => $endNode,
            'route'   => $route,
            'total_cost' => array_sum(array_column($route, 'cost'))
        ]);
    }
}

<?php
// app/Models/M_Routing.php
namespace App\Models;

use CodeIgniter\Model;

class M_Routing extends Model
{
    protected $db;

    public function __construct()
    {
        parent::__construct();
        $this->db = \Config\Database::connect();
    }

    public function findNearestNode($lng, $lat)
    {
        $sql = "SELECT id,
                       ST_X(the_geom) AS lng,
                       ST_Y(the_geom) AS lat
                FROM ways_vertices_pgr
                ORDER BY the_geom <-> ST_SetSRID(ST_MakePoint(?, ?), 4326)
                LIMIT 1";
        return $this->db->query($sql, [$lng, $lat])->getRow();
    }

    public function shortestPath($startId, $endId)
    {
        $sql = "SELECT path.seq, path.node, path.edge, path.cost,
                       path.agg_cost,
                       ST_AsGeoJSON(ways.the_geom)::json AS geom
                FROM pgr_dijkstra(
                    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
                    ?, ?, directed := false
                ) AS path
                JOIN ways ON path.edge = ways.id";

        return $this->db->query($sql, [$startId, $endId])->getResult();
    }
}

Menampilkan Rute di Leaflet.js

Setelah API jadi, kamu tinggal tampilin di Leaflet. Saya pakai Leaflet karena ringan dan gampang dipakai. Berikut kode JavaScript untuk menampilkan rute dari API:

// Init peta
const map = L.map('map').setView([-6.2, 106.8], 13);

L.tileLayer('https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', {
    attribution: 'OpenStreetMap'
}).addTo(map);

// Fungsi cari rute
async function findRoute(startLat, startLng, endLat, endLng) {
    const url = `/routing/findRoute?start_lat=${startLat}&start_lng=${startLng}` +
                `&end_lat=${endLat}&end_lng=${endLng}`;
    const res = await fetch(url);
    const data = await res.json();

    if (data.status !== 'success') {
        alert('Rute tidak ditemukan');
        return;
    }

    // Gambar rute di peta
    const latlngs = [];
    data.route.forEach(seg => {
        if (seg.geom) {
            const coords = seg.geom.coordinates;
            coords.forEach(c => latlngs.push([c[1], c[0]]));
        }
    });

    L.polyline(latlngs, {
        color: '#e74c3c',
        weight: 5,
        opacity: 0.8
    }).addTo(map);

    // Marker start dan end
    L.marker([startLat, startLng]).addTo(map).bindPopup('Start');
    L.marker([endLat, endLng]).addTo(map).bindPopup('End');

    // Fit bounds
    map.fitBounds(L.latLngBounds(latlngs), { padding: [50, 50] });
}

Tips dan Pitfalls dari Pengalaman

1. Index itu wajib. Tanpa index spasial pada kolom the_geom, query nearest node bakal full table scan dan timeout. Selalu bikin GiST index di tabel ways dan ways_vertices_pgr.

2. Cost = 0 bikin rute putus. Kadang osm2pgrouting ngasih cost = 0 untuk segmen tertentu. pgRouting gak bisa ngolah edge dengan cost 0, jadi rute bisa putus di tengah. Filter dengan WHERE cost > 0 atau set cost minimum ke 0.001.

3. Directed vs undirected. Jalan satu arah butuh directed := true. Tapi kalau data OSM kamu gak lengkap tag one_way-nya, rute bisa salah. Saya prefer directed := false untuk data OSM yang belum dibersihkan.

4. Memory query untuk data besar. Kalau area jaringan kamu gede (satu kota lengkap), query pgRouting bisa makan 2-4GB RAM. Bikin work_mem lebih gede atau partisi data per wilayah.

5. Bidirectional routing lebih cepat. Kalau pakai pgr_bdDijkstra (bidirectional Dijkstra), query jalan dari dua arah sekaligus dan bertemu di tengah. Lebih cepat 30-50% untuk jaringan besar.

6. Cache hasil routing. Kalau rute yang sama sering dicari (misalnya rute populer antar landmark), cache hasilnya di Redis atau tabel PostgreSQL sendiri. Tinggal SELECT dari cache, gak perlu hitung ulang.

Driving Distance untuk Analisis Area Jangkauan

Selain shortest path, pgRouting juga punya pgr_drivingDistance yang berguna banget untuk isochrone analysis. Misalnya kamu mau tau area mana saja yang bisa dijangkau dalam 15 menit berkendara dari sebuah lokasi.

-- Cari semua node dalam jarak 1000 meter dari node 100
SELECT * FROM pgr_drivingDistance(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    100,
    1000,
    directed := false
);

Hasilnya bisa kamu konversi jadi polygon pakai ST_ConcaveHull atau ST_Buffer untuk bikin visual area jangkauan di peta. Ini cocok untuk app yang mau nunjukin area layanan delivery, coverage tower, atau zona sekolah.

Perbandingan: pgRouting vs Alternatif Lain

Sebelum pakai pgRouting, saya juga pertimbangin beberapa alternatif. Berikut perbandingan yang saya bikin berdasarkan pengalaman:

• pgRouting (PostgreSQL): Query di DB langsung, gak perlu service tambahan. Cocok kalau kamu sudah pakai PostGIS. Performa bagus untuk data kota. Free dan open source.
• OSRM (Open Source Routing Machine): Lebih cepat untuk routing realtime karena pakai C++ dan kontraksi hierarki. Tapi butuh service terpisah dan preprocessing data. Cocok untuk high-traffic navigation app.
• GraphHopper: Java-based, mendukung multi-modal routing (mobil, sepeda, jalan kaki). Ada turn-by-turn instructions. Tapi butuh Java server dan lebih berat.
• Valhalla: Dibuat oleh Mapzen/Tesla, C++ based. Mendukung isochrone dan multi-modal. Tapi dokumentasi kurang lengkap dan komunitas lebih kecil.
• Google Maps API: Paling akurat dan lengkap. Tapi berbayar per request, dan kamu gak punya kontrol atas data jalan. Mahal untuk volume tinggi.

Untuk project WebGIS self-hosted dengan budget terbatas, pgRouting adalah pilihan terbaik. Kamu punya full control atas data, gak ada biaya per-request, dan terintegrasi langsung dengan stack PostGIS yang sudah kamu punya.

Struktur Project WebGIS dengan pgRouting

Kalau kamu mulai dari nol, berikut struktur project yang saya pakai untuk WebGIS dengan routing. Pakai CodeIgniter 4 sebagai framework backend, Leaflet.js untuk frontend, dan PostgreSQL dengan PostGIS + pgRouting untuk database:

webgis-routing/
|-- app/
|   |-- Controllers/
|   |   |-- Routing.php        # API endpoint routing
|   |   |-- Home.php           # Halaman utama peta
|   |-- Models/
|   |   |-- M_Routing.php      # Query pgRouting
|   |   |-- M_Ways.php         # CRUD data jalan
|   |-- Views/
|   |   |-- map.php            # View peta Leaflet
|   |-- Config/
|   |   |-- Database.php       # Config koneksi PostgreSQL
|-- assets/
|   |-- css/
|   |   |-- map.css            # Styling peta dan UI
|   |-- js/
|   |   |-- routing.js         # Logic routing di frontend
|   |   |-- leaflet.min.js     # Leaflet library
|-- public/
|   |-- index.php              # Entry point CI4
|-- sql/
|   |-- seed_roads.sql         # Data jalan sample
|   |-- create_topology.sql    # Script bikin topologi
|-- .env                       # Environment config

Pemisahan antara query pgRouting di model (M_Routing.php) dan controller (Routing.php) bikin kode lebih bersih. Controller cuma handle request/response, model handle SQL. File routing.js di frontend nangani interaksi peta dan fetch API. Struktur ini gampang di-scale kalau nanti mau nambah fitur kayak isochrone atau TSP.

Optimasi Performa pgRouting untuk Data Besar

Ketika data jaringan jalan kamu makin gede (provinsi atau nasional), performa query jadi penting banget. Saya pernah handle data Pulau Jawa lengkap dan query Dijkstra dasar bisa 30-60 detik. Berikut optimasi yang saya terapkan dan hasilnya lumayan drastis:

1. Kontraksi hierarki dengan pgr_contraction. pgRouting versi 3+ support contraction yang bikin graf lebih kecil dengan menghilangkan node yang gak penting. Query setelah kontraksi bisa 5-10x lebih cepat:

-- Kontraksi graf untuk optimasi query
SELECT * FROM pgr_contraction(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    array[1, 2]  -- level kontraksi
);

-- Bikin tabel hasil kontraksi
SELECT * INTO ways_contracted FROM pgr_contraction(
    'SELECT id, source, target, cost FROM ways WHERE cost > 0',
    array[1, 2, 3]
);

-- Query pakai tabel hasil kontraksi (jauh lebih cepat)
SELECT * FROM pgr_dijkstra(
    'SELECT id, source, target, cost FROM ways_contracted WHERE cost > 0',
    100, 5000, directed := false
);

2. Tingkatkan work_mem PostgreSQL. Default work_mem PostgreSQL cuma 4MB. Untuk query pgRouting yang kompleks, naikin ke 256MB atau lebih:

# Set di postgresql.conf
sudo nano /etc/postgresql/14/main/postgresql.conf

# Cari work_mem dan set ke 256MB
work_mem = 256MB

# Reload PostgreSQL
sudo systemctl reload postgresql

3. Partisi data per wilayah. Kalau kamu punya data seluruh Indonesia, partisi tabel ways per provinsi. Query pgRouting cuma scan partisi yang relevant, gak full table scan:

-- Bikin tabel partitioned per provinsi
CREATE TABLE ways_partitioned (
    id BIGSERIAL,
    source BIGINT,
    target BIGINT,
    cost DOUBLE PRECISION,
    the_geom geometry(LineString, 4326),
    provinsi TEXT
) PARTITION BY LIST (provinsi);

-- Partisi per provinsi
CREATE TABLE ways_jakarta PARTITION OF ways_partitioned FOR VALUES IN ('DKI Jakarta');
CREATE TABLE ways_jawa_barat PARTITION OF ways_partitioned FOR VALUES IN ('Jawa Barat');
CREATE TABLE ways_jawa_timur PARTITION OF ways_partitioned FOR VALUES IN ('Jawa Timur');

-- Bikin index di tiap partisi
CREATE INDEX ON ways_jakarta USING GIST (the_geom);
CREATE INDEX ON ways_jawa_barat USING GIST (the_geom);

Dengan ketiga optimasi ini, query routing untuk Pulau Jawa lengkap turun dari 30-60 detik ke 3-8 detik. Masih bukan realtime banget, tapi cukup untuk WebGIS yang gak butuh sub-second response. Kalau butuh realtime, sebaiknya pakai OSRM yang sudah optimized untuk use case itu.

FAQ: Pertanyaan yang Sering Muncul

Berapa minimal spesifikasi server untuk pgRouting? Untuk data jalan satu kota kecil (kayak Jakarta Pusat), 2GB RAM cukup. Untuk satu provinsi lengkap, minimal 4GB RAM dan 20GB storage. pgRouting itu memory-intensive saat query berjalan, jadi RAM lebih banyak = query lebih cepat.

Bisa pakai pgRouting tanpa PostGIS? Tidak. pgRouting butuh PostGIS untuk fungsi geometri. Install urutannya: PostgreSQL dulu, lalu PostGIS, baru pgRouting.

Berapa lama import data OSM satu kota? Jakarta lengkap sekitar 5-15 menit tergantung spesifikasi server. Proses osm2pgrouting bikin topologi yang cukup intensive. Untuk seluruh Pulau Jawa bisa sampai 1-2 jam.

Kesimpulan

pgRouting bikin analisis jaringan di PostgreSQL jadi straightforward. Kamu gak perlu service tambahan atau API berbayar. Cukup PostGIS + pgRouting, satu SQL query, dan kamu dapet rute optimal langsung dari database. Kalau kamu lagi bangun WebGIS dengan fitur routing, pgRouting worth banget buat dicoba.

Yang perlu diingat: siapin index spasial, filter cost > 0, dan pilih algoritma yang sesuai dengan ukuran data kamu. Untuk data kota, Dijkstra cukup. Untuk data provinsi atau nasional, pertimbangin pgr_aStar atau pgr_bdDijkstra.

Kamu sudah pernah coba pgRouting atau lebih suka OSRM/GraphHopper? Bagi pengalaman kamu di kolom komentar, saya penasaran apa approach yang dipakai developer lain untuk routing di Indonesia.