File size: 10,427 Bytes
5f7ad27 436d6f9 5f7ad27 436d6f9 2bd212c 436d6f9 2bd212c 436d6f9 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 | import streamlit as st
import osmnx as ox
import matplotlib.pyplot as plt
import tempfile
import os
import folium
from streamlit_folium import st_folium
import random
import networkx as nx
from folium.plugins import PolyLineTextPath
# Konfigurasi osmnx agar tidak menyimpan cache permanen
ox.settings.use_cache = False
ox.settings.cache_folder = tempfile.gettempdir()
ox.settings.logs_folder = tempfile.gettempdir()
@st.cache_resource
def ambil_graf_keputih():
# Ambil graf awal dari OSM
G = ox.graph_from_place("Keputih, Sukolilo, Surabaya, Indonesia", network_type="drive", simplify=True)
# Ubah ke undirected agar bisa cari komponen terhubung
G_undirected = G.to_undirected()
# Ambil komponen terbesar
largest_cc = max(nx.connected_components(G_undirected), key=len)
G_connected = G.subgraph(largest_cc).copy()
# Ambil data node dan edge
gdf_nodes, gdf_edges = ox.graph_to_gdfs(G_connected)
return G_connected, gdf_nodes, gdf_edges
def buat_rute_polyline(G, rute_node_ids):
garis_rute = []
for i in range(len(rute_node_ids) - 1):
asal = rute_node_ids[i]
tujuan = rute_node_ids[i + 1]
try:
# Ambil semua shortest path
semua_path = list(nx.all_shortest_paths(G, asal, tujuan, weight="length"))
# Pilih hanya satu (misalnya yang pertama)
path = semua_path[0]
titik = [(G.nodes[n]['y'], G.nodes[n]['x']) for n in path]
garis_rute.extend(titik)
except:
continue # Lewati jika tidak ada path
return garis_rute
def buat_peta_folium(gdf_nodes, kantor_id=None, rumah_ids=None, garis_rute=None, tampilkan_hanya_yang_dipilih=False):
pusat = gdf_nodes.geometry.unary_union.centroid
m = folium.Map(location=[pusat.y, pusat.x], zoom_start=16)
for i, (node_id, row) in enumerate(gdf_nodes.iterrows(), 1):
if tampilkan_hanya_yang_dipilih:
if kantor_id != node_id and (not rumah_ids or node_id not in rumah_ids):
continue # Skip marker jika bukan kantor dan bukan rumah yang dipilih
nama = f"Rumah ke-{i}"
if kantor_id == node_id:
warna = "red"
ikon = "building"
label = "Kantor"
elif rumah_ids and node_id in rumah_ids:
warna = "green"
ikon = "home"
label = nama
else:
warna = "blue"
ikon = "home"
label = nama
folium.Marker(
location=[row.y, row.x],
popup=f"{label}<br>ID: {node_id}",
icon=folium.Icon(color=warna, icon=ikon)
).add_to(m)
if garis_rute:
# Buat garis utama
garis = folium.PolyLine(garis_rute, color="purple", weight=5, opacity=0.8)
garis.add_to(m)
# Tambahkan panah arah (text path dengan panah)
panah = PolyLineTextPath(
garis,
' ➤ ', # Simbol panah (spasi untuk jeda antar panah)
repeat=True,
offset=7, # posisi offset dari garis
attributes={'fill': 'orange', 'font-weight': 'bold', 'font-size': '16'}
)
panah.add_to(m)
return m
# Inisialisasi sesi
if "halaman" not in st.session_state:
st.session_state["halaman"] = "pilih_kantor"
G, gdf_nodes, gdf_edges = ambil_graf_keputih()
# Buat label node
list_label = [f"Rumah ke-{i} (node {node_id})" for i, node_id in enumerate(gdf_nodes.index, 1)]
id_mapping = dict(zip(list_label, gdf_nodes.index.to_list()))
# SIDEBAR
with st.sidebar:
st.title("Input Lokasi")
if st.session_state["halaman"] == "pilih_kantor":
st.subheader("1. Pilih Kantor")
kantor_label = st.selectbox("Node Kantor:", list_label)
kantor_id = id_mapping[kantor_label]
if st.button("Lanjut"):
st.session_state["kantor_id"] = kantor_id
st.session_state["halaman"] = "pilih_rumah"
st.rerun()
elif st.session_state["halaman"] == "pilih_rumah":
st.subheader("2. Pilih Rumah Tujuan")
# List rumah tidak boleh termasuk kantor
list_label_rumah = [
label for label in list_label
if id_mapping[label] != st.session_state["kantor_id"]
]
rumah_labels = st.multiselect("Node Rumah:", list_label_rumah)
rumah_ids = [id_mapping[label] for label in rumah_labels]
if st.button("Mulai Pengantaran"):
st.session_state["rumah_ids"] = rumah_ids
st.session_state["halaman"] = "hasil"
elif st.session_state["halaman"] == "hasil":
if st.button("Kembali"):
st.session_state["halaman"] = "pilih_kantor"
st.rerun()
st.markdown("---")
if st.button("🔄 Restart Aplikasi"):
for k in list(st.session_state.keys()):
del st.session_state[k]
st.rerun()
#######################################################
# Fungsi: Membuat matriks jarak (TSP) dari graf dan daftar node
def hitung_matriks_TSP(G, kantor_id, rumah_ids):
semua_ids = [kantor_id] + rumah_ids
reachable_ids = [kantor_id] # mulai dari kantor
# Cek node mana saja yang reachable dari kantor
for rumah_id in rumah_ids:
try:
nx.shortest_path_length(G, kantor_id, rumah_id, weight="length")
reachable_ids.append(rumah_id)
except nx.NetworkXNoPath:
continue # Skip rumah yang tidak reachable dari kantor
# Pastikan ada minimal 2 node (kantor + minimal 1 rumah)
if len(reachable_ids) < 2:
raise ValueError("Tidak cukup node yang saling terhubung. Harap pilih node yang lebih dekat atau tersambung.")
TSP = [[0 for _ in reachable_ids] for _ in reachable_ids]
indeks_ke_node = {i: node_id for i, node_id in enumerate(reachable_ids)}
for i in range(len(reachable_ids)):
for j in range(len(reachable_ids)):
if i != j:
try:
TSP[i][j] = nx.shortest_path_length(G, indeks_ke_node[i], indeks_ke_node[j], weight="length")
except nx.NetworkXNoPath:
TSP[i][j] = float('inf') # opsional, atau bisa raise error
return TSP, indeks_ke_node
# Kelas individu untuk algoritma genetika
class Individual:
def __init__(self, chromosome, TSP):
self.chromosome = chromosome
self.TSP = TSP
self.fitness = self.calc_fitness()
def calc_fitness(self):
distance = 0
for i in range(len(self.chromosome)):
from_city = self.chromosome[i]
to_city = self.chromosome[(i + 1) % len(self.chromosome)]
distance += self.TSP[from_city][to_city]
return distance
def mutate(self):
a = random.randint(1, len(self.chromosome) - 1)
b = random.randint(1, len(self.chromosome) - 1)
self.chromosome[a], self.chromosome[b] = self.chromosome[b], self.chromosome[a]
@staticmethod
def crossover(parent1, parent2):
size = len(parent1.chromosome)
p1 = parent1.chromosome[1:]
p2 = parent2.chromosome[1:]
start = random.randint(0, size - 2)
end = random.randint(start + 1, size - 1)
middle = p1[start:end]
child = middle + [c for c in p2 if c not in middle]
return Individual([0] + child, parent1.TSP)
# Fungsi inisialisasi populasi awal
def initial_population(TSP, size):
population = []
for _ in range(size):
chromosome = list(range(1, len(TSP)))
random.shuffle(chromosome)
chromosome = [0] + chromosome
population.append(Individual(chromosome, TSP))
return population
# Fungsi seleksi dan loop algoritma GA
def select_parent(population):
return min(random.sample(population, 5), key=lambda ind: ind.fitness)
def jalankan_GA(TSP, generations=300, pop_size=100):
population = initial_population(TSP, pop_size)
for _ in range(generations):
population.sort(key=lambda ind: ind.fitness)
next_gen = population[:10]
while len(next_gen) < pop_size:
p1 = select_parent(population)
p2 = select_parent(population)
child = Individual.crossover(p1, p2)
if random.random() < 0.2:
child.mutate()
next_gen.append(child)
population = next_gen
best = min(population, key=lambda ind: ind.fitness)
return best.chromosome + [0], best.fitness
############################################################
# HALAMAN UTAMA
if st.session_state["halaman"] == "pilih_kantor":
st.header("Pilih Kantor pada Peta")
st_folium(buat_peta_folium(gdf_nodes), width=700, height=500)
elif st.session_state["halaman"] == "pilih_rumah":
st.header("Pilih Rumah Tujuan pada Peta")
st_folium(buat_peta_folium(gdf_nodes, kantor_id=st.session_state["kantor_id"]), width=700, height=500)
elif st.session_state["halaman"] == "hasil":
st.header("Hasil Pengantaran")
rumah_ids = st.session_state.get("rumah_ids", [])
kantor_id = st.session_state.get("kantor_id")
# Jalankan GA
TSP_matrix, indeks_ke_node = hitung_matriks_TSP(G, kantor_id, rumah_ids)
best_path_indexed, best_fitness = jalankan_GA(TSP_matrix)
path_nodes = [indeks_ke_node[i] for i in best_path_indexed]
garis_rute = buat_rute_polyline(G, path_nodes)
st_folium(
buat_peta_folium(
gdf_nodes,
kantor_id=kantor_id,
rumah_ids=set(path_nodes), # hanya node yang dilewati
garis_rute=garis_rute,
tampilkan_hanya_yang_dipilih=True # aktifkan filter
),
width=700,
height=500
)
st.success(f"Kurir berangkat dari kantor dengan node {kantor_id}")
# Buat mapping dari node ke label rumah yang asli dari dropdown
node_to_label = {}
# Tambahkan label kantor
node_to_label[kantor_id] = "Kantor"
# Ambil semua label yang tersedia dari dropdown
for label, node_id in id_mapping.items():
if node_id in rumah_ids:
node_to_label[node_id] = label.split(" (")[0] # Ambil 'Rumah ke-498' saja
# Konversi path_nodes ke label
path_labels = [node_to_label.get(nid, str(nid)) for nid in path_nodes]
rute_string = " → ".join(path_labels)
st.success(f"Rute terbaik: {rute_string}")
st.success(f"Total jarak: {best_fitness:.2f} meter")
if st.button("Kembali"):
st.session_state["halaman"] = "pilih_kantor"
st.rerun() |