Optimizador de Ruta TSP
Encontrar la ruta más corta visitando todas las ubicaciones y regresando al depósito. Utiliza algoritmos heurísticos (Vecino más cercano, Clarke-Wright Ahorro)…
Utiliza algoritmos heurísticos (Vecino más cercano, Clarke-Wright Ahorro) para resolver el Problema del Viajante. Ingrese coordenadas de ubicación para encontrar una ruta optimizada.
¿Qué es el Problema del Viajante (TSP)?
TSP pregunta: dada un conjunto de ubicaciones y distancias, ¿cuál es la ruta más corta que visita cada ubicación exactamente una vez y regresa al inicio? Es uno de los problemas más estudiados en optimización combinatoria.
TSP es NP-difícil. Soluciones prácticas usan heurísticas: Vecino más cercano (rápido, ~25% sobre el óptimo), Clarke-Wright y metaheurísticas.
Se aplica a entregas de última milla, servicio de campo, perforación de PCB y rutas de picking en almacén.
Formula: Objetivo: min Σ d(route[i], route[i+1]) Vecino más cercano: visitar greedily la ubicación no visitada más cercana Ahorro: s(i,j) = d(depósito,i) + d(depósito,j) − d(i,j)
Ejemplo de cálculo
Depósito (0,0), 4 paradas (3,4),(6,1),(8,5),(2,7). Vecino más cercano: total 25,1. Clarke-Wright podría encontrar 23,4.
Cuándo usar esta calculadora
- Un despachador de entregas planificando una ruta diaria para un solo conductor que visita 10-30 ubicaciones de clientes
- Un gerente de servicio de campo optimizando rutas de técnicos para minimizar el tiempo de viaje entre llamadas de servicio
- Un ingeniero de almacén diseñando una ruta óptima de recolección a través de múltiples ubicaciones de pasillo
- Un representante de ventas planificando un viaje a múltiples ciudades para visitar clientes con mínima distancia de conducción
Errores comunes a evitar
- Asumir que la solución del vecino más cercano es óptima — es una heurística voraz que puede estar 20-25% por encima de la ruta óptima; siempre pruebe múltiples algoritmos y compare
- Usar distancias en línea recta (euclidiana) para rutas por carretera — las distancias reales de conducción pueden ser 20-40% más largas debido a las redes viales; para ruteo por carretera, use distancias reales si están disponibles
- Olvidar incluir el viaje de regreso al depósito — TSP requiere regresar al punto de partida; omitir el regreso subestima la distancia total de la ruta
- Aplicar TSP a problemas que en realidad son VRP — si tiene restricciones de capacidad, ventanas de tiempo o múltiples vehículos, use la herramienta VRP para mejores resultados
Cómo interpretar los resultados
- Compare los resultados de Vecino más Cercano y Clarke-Wright: si difieren significativamente, el problema tiene margen para mayor optimización con métodos más avanzados
- El tiempo de cómputo en milisegundos ayuda a evaluar si el re-ruteo en tiempo real es factible para el tamaño de su problema
- La visualización del mapa de ruta ayuda a identificar ineficiencias obvias como rutas que se cruzan o retrocesos innecesarios que las heurísticas pueden producir
Normas y referencias relacionadas
- Vecino más cercano y ahorros de Clarke-Wright (1964) — las heurísticas constructivas comparadas en esta herramienta
- Búsqueda local de Lin-Kernighan — la heurística de referencia de facto para tours TSP de alta calidad
- TSPLIB — la biblioteca pública de referencia estándar usada para comparar la calidad de los solvers de TSP
Preguntas frecuentes
¿Qué algoritmo debo usar?
Menos de 15 paradas: Vecino más cercano. 15-50: Clarke-Wright + 2-opt. 50+: metaheurísticas o Google OR-Tools.
¿En qué difiere TSP del ruteo real de entregas?
El ruteo real añade ventanas de tiempo, capacidad vehicular, tráfico y múltiples vehículos. TSP proporciona el límite inferior de distancia como benchmark.