import streamlit as st import folium from geopy.geocoders import Nominatim import numpy as np import requests import polyline import time from functools import lru_cache from concurrent.futures import ThreadPoolExecutor def held_karp_tsp(dist_matrix: np.ndarray) -> tuple: """ Held-Karp algorithm for solving TSP Returns: (minimum cost, optimal route) """ if len(dist_matrix) < 2: return 0, [] n = len(dist_matrix) inf = float('inf') # Use numpy arrays for better performance dp = np.full((1 << n, n), inf) parent = np.full((1 << n, n), -1, dtype=int) # Base cases for i in range(1, n): dp[1 << i][i] = dist_matrix[0][i] # Main DP loop for mask in range(1, 1 << n): if bin(mask).count('1') <= 1: continue for curr in range(n): if not (mask & (1 << curr)): continue prev_mask = mask ^ (1 << curr) for prev in range(n): if not (prev_mask & (1 << prev)): continue candidate = dp[prev_mask][prev] + dist_matrix[prev][curr] if candidate < dp[mask][curr]: dp[mask][curr] = candidate parent[mask][curr] = prev # Reconstruct path mask = (1 << n) - 1 curr = min(range(n), key=lambda x: dp[mask][x] + dist_matrix[x][0]) path = [] while curr != -1: path.append(curr) new_mask = mask ^ (1 << curr) curr = parent[mask][curr] mask = new_mask path.append(0) path.reverse() return dp[(1 << n) - 1][path[-2]] + dist_matrix[path[-2]][0], path @st.cache_data def get_route_osrm(start_coords: tuple, end_coords: tuple) -> tuple: """ Get route using OSRM public API Returns: (distance in km, encoded polyline of the route) """ try: # Format coordinates for OSRM (lon,lat format) coords = f"{start_coords[1]},{start_coords[0]};{end_coords[1]},{end_coords[0]}" # OSRM public API endpoint url = f"http://router.project-osrm.org/route/v1/driving/{coords}" params = { "overview": "full", "geometries": "polyline", "annotations": "distance" } response = requests.get(url, params=params) if response.status_code == 200: data = response.json() if data["code"] == "Ok" and len(data["routes"]) > 0: route = data["routes"][0] distance = route["distance"] / 1000 # Convert to km geometry = route["geometry"] # Already encoded polyline return distance, geometry else: st.warning("No route found") return None, None else: st.warning(f"OSRM API error: {response.status_code}") return None, None except Exception as e: st.error(f"Error getting route: {str(e)}") return None, None @st.cache_data def cached_geocoding(city_name: str) -> tuple: """Cache geocoding results""" try: geolocator = Nominatim(user_agent="tsp_app") location = geolocator.geocode(city_name, timeout=10) if location: return (location.latitude, location.longitude) return None except Exception as e: st.error(f"Error geocoding {city_name}: {str(e)}") return None def create_distance_matrix_with_routes(coordinates: list) -> tuple: """ Create distance matrix and store routes between all points using OSRM """ valid_coordinates = [c for c in coordinates if c is not None] n = len(valid_coordinates) if n < 2: return np.array([]), valid_coordinates, {} dist_matrix = np.zeros((n, n)) routes_dict = {} # Store encoded polylines for routes def calculate_route(i, j): if i != j: # Add delay to avoid hitting rate limits time.sleep(0.1) distance, route = get_route_osrm(valid_coordinates[i], valid_coordinates[j]) if distance is not None: return i, j, distance, route return i, j, 0, None with ThreadPoolExecutor(max_workers=5) as executor: # Limit concurrent requests futures = [] for i in range(n): for j in range(i + 1, n): futures.append(executor.submit(calculate_route, i, j)) with st.spinner("Calculating routes..."): for future in futures: i, j, distance, route = future.result() if route is not None: dist_matrix[i][j] = distance dist_matrix[j][i] = distance routes_dict[f"{i}-{j}"] = route routes_dict[f"{j}-{i}"] = route return dist_matrix, valid_coordinates, routes_dict def plot_route_with_roads(map_obj: folium.Map, coordinates: list, route: list, city_names: list, routes_dict: dict) -> folium.Map: """ Plot route using actual road paths from OSRM """ route_group = folium.FeatureGroup(name="Route") # Plot road segments between consecutive points total_distance = 0 for i in range(len(route)-1): start_idx = route[i] end_idx = route[i+1] route_key = f"{start_idx}-{end_idx}" if route_key in routes_dict: # Decode and plot the polyline decoded_path = polyline.decode(routes_dict[route_key]) folium.PolyLine( decoded_path, color="blue", weight=3, opacity=0.8, tooltip=f"Segment {i+1}: {city_names[start_idx]} → {city_names[end_idx]}" ).add_to(route_group) # Add markers with custom icons for i, point_idx in enumerate(route): icon_color = "green" if i == 0 else "red" if i == len(route)-1 else "blue" popup_text = f"""
City: {city_names[point_idx]}
Stop: {i + 1} of {len(route)}
""" folium.Marker( location=coordinates[point_idx], popup=folium.Popup(popup_text, max_width=200), tooltip=f'Stop {i + 1}: {city_names[point_idx]}', icon=folium.Icon(color=icon_color, icon='info-sign') ).add_to(route_group) route_group.add_to(map_obj) # Add OpenStreetMap tile layer folium.TileLayer( tiles='https://{s}.tile.openstreetmap.org/{z}/{x}/{y}.png', attr='© OpenStreetMap contributors' ).add_to(map_obj) return map_obj def main(): st.set_page_config(page_title="TSP Route Optimizer", layout="wide") st.title("🌍 Route Optimizer") st.markdown(""" Temukan rute optimal berkendara antar lokasi. Masukkan nama lokasi dibawah dan klik 'Optimize Route' untuk melihat hasilnya. """) col1, col2 = st.columns([1, 2]) with col1: st.subheader("📍 Masukkan Lokasi") city_count = st.number_input("Jumlah lokasi", min_value=2, max_value=10, value=3, step=1, help="Maksimum 10 lokasi direkomendasikan karena batasan API") if 'city_inputs' not in st.session_state: st.session_state.city_inputs = [''] * city_count if len(st.session_state.city_inputs) != city_count: st.session_state.city_inputs = st.session_state.city_inputs[:city_count] + [''] * max(0, city_count - len(st.session_state.city_inputs)) city_names = [] city_coords = [] for i in range(city_count): city_name = st.text_input( f"Kota {i+1}", value=st.session_state.city_inputs[i], key=f"city_{i}" ) st.session_state.city_inputs[i] = city_name if city_name: coords = cached_geocoding(city_name) if coords: city_names.append(city_name) city_coords.append(coords) else: st.warning(f"⚠️ Tidak dapat menemukan koordinat untuk '{city_name}'") with col2: if not city_coords: map_center = [-2.548926, 118.014863] # Center of Indonesia zoom_start = 5 else: map_center = city_coords[0] zoom_start = 5 map_obj = folium.Map(location=map_center, zoom_start=zoom_start) if st.button("🔄 Optimize Route", key="optimize"): if len(city_coords) < 2: st.error("❌ Masukkan minimal 2 lokasi yang valid") else: with st.spinner("Menghitung rute optimal..."): start_time = time.time() # Get distance matrix and routes dist_matrix, valid_coordinates, routes_dict = create_distance_matrix_with_routes(city_coords) # Calculate optimal route min_cost, optimal_route = held_karp_tsp(dist_matrix) end_time = time.time() if min_cost == float('inf'): st.error("❌ Tidak dapat menemukan rute yang valid") else: # Display results st.success(f"✅ Rute dihitung dalam {end_time - start_time:.2f} detik") st.write(f"🛣️ Total jarak berkendara: {min_cost:.2f} km") st.write("📍 Rute optimal:") route_text = " → ".join([city_names[i] for i in optimal_route]) st.code(route_text) # Update map with route map_obj = plot_route_with_roads(map_obj, valid_coordinates, optimal_route, city_names, routes_dict) # Display map st.components.v1.html(folium.Map._repr_html_(map_obj), height=600) if __name__ == "__main__": main()