Network Analisis: Vehicle Routing System With Openstreetmap

Network Analysis: Vehicle Routing System with OpenStreetMap

Untuk memahami bagaimana sistem rute kendaraan (Vehicle Routing System / VRS) bekerja menggunakan OpenStreetMap (OSM), kita bisa membagi analisisnya dalam beberapa aspek penting:

---

🔍 1. Pengertian Dasar

Vehicle Routing System (VRS) adalah sistem yang digunakan untuk menentukan rute optimal kendaraan dalam menyelesaikan serangkaian tugas, misalnya pengantaran barang, penjemputan penumpang, atau layanan logistik.

OpenStreetMap (OSM) adalah peta digital open-source yang menyimpan data geografis seperti jalan, bangunan, dan fitur lainnya.

---

🧠 2. Komponen Kunci dalam Network Analysis

a. Graf Jalan (Road Network Graph)

• OSM menyimpan data jalan dalam bentuk node (titik) dan way (garis penghubung node).
• Data ini diubah menjadi graph berbobot, dengan simpul (nodes) sebagai persimpangan jalan dan sisi (edges) sebagai jalan antar simpul.

b. Routing Engine

Untuk melakukan rute kendaraan berbasis OSM, dibutuhkan routing engine. Contoh:

• OSRM (Open Source Routing Machine) – cepat dan cocok untuk kendaraan bermotor.
• GraphHopper – ringan dan mendukung berbagai moda transportasi.
• pgRouting – berbasis PostgreSQL/PostGIS, cocok untuk analisis jaringan kompleks.

---

🛠️ 3. Langkah Kerja Vehicle Routing dengan OSM

1. Ekstraksi Data

• Download data OSM untuk area tertentu (format .osm.pbf).
• Parsing data jalan dan atributnya (misalnya: highway=primary, maxspeed, dll).

2. Konversi ke Graph

• Jalan → edges.
• Titik persimpangan → nodes.
• Berat (cost) = jarak, waktu tempuh, atau biaya lainnya.

3. Algoritma Pencarian Rute

• Dijkstra: algoritma klasik untuk rute terpendek.
• A*: seperti Dijkstra tapi lebih cepat menggunakan heuristik.
• VRP Algorithms (Vehicle Routing Problem):
  • Clarke-Wright Savings
  • Tabu Search, Genetic Algorithm (untuk kasus kompleks)
  • Capacitated VRP, Time Window VRP, dll

4. Visualisasi dan Eksekusi

• Tampilan peta hasil rute dengan leaflet.js atau peta interaktif lain.
• Output rute bisa diubah menjadi file .gpx atau .geojson untuk navigasi.

---

📦 4. Contoh Studi Kasus Sederhana

Studi Kasus: Perusahaan pengiriman ingin mengantarkan paket ke 10 lokasi di Jakarta.

Tools:

• Data OSM Jakarta.
• GraphHopper + Java/Python.
• Algoritma VRP sederhana.

Langkah:

1. Ambil koordinat depot dan 10 titik tujuan.
2. Buat matriks jarak dari setiap titik ke titik lain.
3. Jalankan algoritma VRP untuk menghasilkan rute optimal.
4. Visualisasikan hasil dengan Leaflet atau OpenLayers.

---

⚙️ 5. Software & Library Pendukung

Tool/Library	Keterangan
OSRM	Routing cepat berbasis OSM
GraphHopper	Fleksibel, berbasis Java
pgRouting	Routing berbasis database PostGIS
OpenRouteService (ORS)	Routing berbasis API, mendukung VRP
ORTools (Google)	Menyediakan solver VRP yang kuat
Python NetworkX	Analisis graf (non-spasial)
Leaflet / Folium	Visualisasi peta dan rute

---

🧩 6. Tantangan dan Solusi

Tantangan	Solusi
Data jalan tidak lengkap di OSM	Kontribusi ke OSM, validasi manual
Keterbatasan algoritma klasik untuk VRP kompleks	Gunakan algoritma heuristik/metaheuristik
Waktu proses lambat untuk ribuan titik	Gunakan pre-processing (seperti contraction hierarchies di OSRM)

---

📈 7. Aplikasi Nyata

• Pengiriman logistik (GrabExpress, dll.)
• Distribusi makanan (GrabFood, dll.)
• Rute armada sampah, ambulans, transportasi sekolah
• Rute navigasi dinamis berdasarkan kondisi lalu lintas (real-time)

---

Kita akan buat skrip teknis dasar untuk Vehicle Routing Problem (VRP) menggunakan data dari OpenStreetMap dan memanfaatkan Google OR-Tools untuk solusi algoritmiknya. Untuk tahap awal, kita buat:

---

🎯 Studi Kasus Sederhana

Misalnya:

1 depot (gudang pusat)

5 lokasi pengantaran

2 kendaraan

Tujuan: Minimalkan jarak tempuh total

---

🧰 Teknologi & Tools

Tools Fungsi

OSM (via OpenRouteService API) Mendapatkan matriks jarak antar titik

Google OR-Tools Menyelesaikan masalah VRP

Python Bahasa pemrograman utama

Folium Visualisasi rute di peta interaktif

---

🧾 Step-by-Step: Code Python

1. Install library yang dibutuhkan

pip install openrouteservice ortools folium

---

2. Python Script: VRP dengan 2 Kendaraan

import openrouteservice

from ortools.constraint_solver import routing_enums_pb2

from ortools.constraint_solver import pywrapcp

import folium

# === 1. Lokasi (depot + titik pengantaran) ===

coords = [

    [106.827153, -6.175110], # Monas (Depot)

    [106.827201, -6.180020], # Lokasi 1

    [106.829820, -6.176780], # Lokasi 2

    [106.825020, -6.172510], # Lokasi 3

    [106.830580, -6.170310], # Lokasi 4

    [106.832110, -6.174720], # Lokasi 5

]

# === 2. Ambil matriks jarak dari OpenRouteService ===

api_key = "MASUKKAN_API_KEY_ORS_KAMU_DI_SINI"

client = openrouteservice.Client(key=api_key)

matrix = client.distance_matrix(locations=coords, profile='driving-car', metrics=['distance'])

distance_matrix = matrix['distances']

# === 3. Setup Data untuk OR-Tools ===

def create_data_model():

    data = {

        'distance_matrix': distance_matrix,

        'num_vehicles': 2,

        'depot': 0,

    }

    return data

# === 4. OR-Tools Solver ===

def solve_vrp(data):

    manager = pywrapcp.RoutingIndexManager(len(data['distance_matrix']),

                                            data['num_vehicles'], data['depot'])

    routing = pywrapcp.RoutingModel(manager)

    def distance_callback(from_index, to_index):

        return data['distance_matrix'][manager.IndexToNode(from_index)][manager.IndexToNode(to_index)]

    transit_callback_index = routing.RegisterTransitCallback(distance_callback)

    routing.SetArcCostEvaluatorOfAllVehicles(transit_callback_index)

    search_parameters = pywrapcp.DefaultRoutingSearchParameters()

    search_parameters.first_solution_strategy = (

        routing_enums_pb2.FirstSolutionStrategy.PATH_CHEAPEST_ARC)

    solution = routing.SolveWithParameters(search_parameters)

    routes = []

    if solution:

        for vehicle_id in range(data['num_vehicles']):

            index = routing.Start(vehicle_id)

            route = []

            while not routing.IsEnd(index):

                route.append(manager.IndexToNode(index))

                index = solution.Value(routing.NextVar(index))

            route.append(manager.IndexToNode(index))

            routes.append(route)

    return routes

# === 5. Visualisasi dengan Folium ===

def visualize_routes(coords, routes):

    m = folium.Map(location=[-6.175, 106.827], zoom_start=15)

    color_list = ['blue', 'green', 'red', 'purple']

    

    for i, route in enumerate(routes):

        path = [coords[idx][::-1] for idx in route] # [lat, lon]

        folium.PolyLine(path, color=color_list[i % len(color_list)], weight=5).add_to(m)

        for j, idx in enumerate(route):

            folium.Marker(location=coords[idx][::-1],

                          popup=f"Stop {j} - Node {idx}",

                          icon=folium.Icon(color=color_list[i % len(color_list)])).add_to(m)

    return m

# === 6. Jalankan semua ===

data = create_data_model()

routes = solve_vrp(data)

m = visualize_routes(coords, routes)

m.save("vrp_result.html")

print("Rute selesai dihitung dan disimpan ke vrp_result.html")

---

🔑 Keterangan

Ganti MASUKKAN_API_KEY_ORS_KAMU_DI_SINI dengan API Key dari https://openrouteservice.org/sign-up/

Output berupa file HTML vrp_result.html yang menampilkan rute pada peta interaktif.

---

📚 Studi Literatur Terkait

Berikut referensi akademik dan teknis terkait:

📘 Paper Ilmiah

1. Golden, B. L., et al. (2008)

The Vehicle Routing Problem: Latest Advances and New Challenges

→ Menjelaskan klasifikasi VRP dan pendekatan algoritma modern.

2. Geisberger, R. et al. (2012)

Routing with Contraction Hierarchies

→ Dasar algoritma cepat seperti yang digunakan di OSRM.

3. Luxen, D., & Vetter, C. (2011)

Real-time routing with OpenStreetMap data

→ Implementasi routing real-time dengan OSM.

📗 Dokumentasi Teknis

OR-Tools VRP Guide

OpenRouteService Matrix API

📚 LITERATUR TAMBAHAN

Judul Sumber

OpenStreetMap Data Extraction https://geoffboeing.com/2016/11/osmnx-python-street-networks/

Google OR-Tools Routing Guide https://developers.google.com/optimization/routing

pgRouting Docs https://pgrouting.org/docs/

Journal: Real-time Vehicle Routing with Open Data Transportation Research Part C