Un vehículo, sin capacidad, retorno al origen: hallar la ruta cerrada de mínima distancia que visita cada uno de los N nodos exactamente una vez. El problema fundacional de la optimización combinatoria — todas las variantes VRP heredan su columna vertebral (nombre académico: TSP).
En pocas palabras
¿Te suena?
- Tenemos una operación de servicio de campo con un solo vehículo — un técnico visita 8-15 clientes al día y la secuencia la decide él por intuición.
- En nuestra mediana empresa de fabricación, un comercial hace una ruta regional un día a la semana (15-40 visitas a proveedores o clientes); un vehículo, sin capacidad limitante, el orden no es óptimo.
- Operamos una taladradora PCB o una insertadora automática — el cabezal de taladro o de colocación visita 500-5.000 puntos, la secuencia la fija el programador de máquina.
- Planificamos una traza subterránea de cable o una secuencia de tendido de tubería — un equipo, una ruta, sin capacidad limitante.
- Un robot de almacén (AS/RS de pick simple) compone rutas por estanterías — el robot no tiene capacidad limitante o transporta un solo objeto.
- Ruta urbana de proveedor en cadena de frío (un vehículo, carga pequeña); el orden lo decide la rutina del conductor.
- Nuestro número de nodos está entre 50 y 500 — escala manejable por un MIP exacto, pero la intuición 'TSP es NP-difícil, hay que usar heurística' nos mantiene solo en heurística.
Por qué importa
Cómo se resuelve
Profundidad técnica
Cómo se resuelve
Profundidad técnicaEn una frase: Construye primero la matriz de distancias por pares (distancia real por carretera, simétrica o asimétrica), luego según la escala — menos de 1.000 nodos: solver MIP exacto; por encima: búsqueda local k-opt (familia Lin-Kernighan) — y obtienes la ruta en minutos.
En la literatura de Investigación de Operaciones (disciplina que usa matemáticas e informática para resolver decisiones de negocio) este problema se llama Travelling Salesman Problem (TSP — problema del viajante), estudiado durante más de 70 años y problema fundacional de la optimización combinatoria moderna. Enunciado canónico: dados N nodos (ciudades, clientes, puntos de taladro, nodos de cable) y una matriz de distancias por pares (o tiempo, o coste), hallar la ruta hamiltoniana (ruta cerrada que visita cada nodo una vez) de coste total mínimo que visita cada nodo exactamente una vez y regresa al inicio. Un vehículo, sin capacidad, sin ventanas horarias, el depósito es siempre el nodo de inicio. Solución en tres etapas:
1. Modelado. Entradas: lista de nodos (por nodo, posición o etiqueta de identificación), matriz de distancias por pares (euclídea, distancia real por carretera, o tiempo — basada en red vial para ruta urbana, Manhattan para un cabezal), simetría (si distancia A→B = B→A, TSP simétrico; si no — p. ej. calles de un sentido — TSP asimétrico / ATSP), propiedad métrica (si se cumple la desigualdad triangular, TSP métrico y aplica una heurística de 3/2-aproximación con garantía). Objetivo: coste total mínimo de la ruta. Restricciones: cada nodo se visita exactamente una vez + una única ruta cerrada (subtours prohibidos).
2. Decisión por solver. Tres enfoques académicos principales: (i) Branch-and-cut MIP exacto (ramificación-y-corte — búsqueda en árbol con planos de corte) — el método de planos de corte se introdujo en los años 1950; solvers maduros han resuelto instancias TSP de hasta 85K+ nodos exactamente. Para escala de campo (50-500 nodos), solvers MIP comerciales o open-source maduros (Mixed-Integer Linear Programming — optimización con algunas variables 0/1 y otras continuas) terminan en minutos. (ii) Programación dinámica (Held-Karp) — la formulación DP O(n²·2^n) de los años 1960; práctica para n < 25, referencia docente. (iii) Heurística — familia Lin-Kernighan — búsqueda local k-opt (quita k aristas de la ruta y reconecta de forma óptima); la implementación moderna LKH (Lin-Kernighan-Helsgaun) se mantiene dentro de 0,1-1% del óptimo hasta escala de millones de nodos y es la referencia heurística para instancias de campo desde 1.000 nodos. Heurísticas de ladrillo: vecino más cercano, Christofides 3/2 (TSP métrico), algoritmo de savings, búsqueda local 2-opt y 3-opt.
3. Integración en campo. Salida en tres capas según uso: (a) servicio de campo — lista ordenada de paradas + navegación en la app móvil del conductor, asignada al inicio de la jornada, normalmente no se reoptimiza durante el día; (b) programación de máquina — secuencia de taladro o colocación incrustada en el programa NC de una taladradora PCB o insertadora, calculada una vez por lote de piezas; (c) ruta de cable o tubería — el plan de ruta del ingeniero, decisión única antes del ensayo. El módulo TSP suele estar embebido en una software de rutas o en un paquete de programación de línea — rara vez se vende como producto independiente. Comité trimestral de operaciones: distancia real de ruta vs plan, desviación de tiempo de conductor, número de rutas extra.
Alternativas
Secuenciación intuitiva + spreadsheet
GratisSin licencia
Para quién: Muy pequeña escala (menos de 10 paradas/día), lo que el planificador retiene en la cabeza
- + Sin coste de software
- + Cuenta el conocimiento de campo del planificador
- + Respuesta telefónica a cambios de ETA
- − Más allá de 20 paradas la mente humana se desvía 20-40% del óptimo
- − Inconsistente — la secuencia varía cada día
- − Sin medición — distancias no quedan registradas
- − Colapsa rápido si aparece multi-vehículo o capacidad (pasa a VRP)
Software general de rutas / servicio de campo (módulo TSP embebido)
Empresarial100-400 TRY/vehículo/mes suscripción o 200K-800K TRY licencia única
Para quién: Operación de servicio de campo (10-50 vehículos), ruta de un solo vehículo, sin capacidad
- + Motor de ordenación de ruta listo — vecino más cercano + mejora local es típico
- + App móvil para conductor, navegación, info de cliente integrada
- + Mapas y datos de tráfico locales
- − Transparencia algorítmica baja — 'qué método se usa' rara vez se responde con claridad
- − Un solver con garantía de óptimo suele estar ausente, sólo aproximación rápida
- − Más allá de 500 paradas la brecha a la mejor ruta crece
Solver open-source + módulo TSP a medida
Código abiertoLicencia gratuita; desarrollo interno 8-16 semanas o 200K-800K TRY de consultoría
Para quién: Operación con equipo técnico, programación de máquina (PCB, CNC), ruta de campo especializada
- + Solvers con garantía de óptimo disponibles en open source
- + Herramientas heurísticas estándar de la industria que se mantienen cerca del óptimo hasta escala de millones de paradas son open source
- + Variantes como rutas con calles de un sentido o con beneficios pueden adaptarse
- − Requiere especialista en optimización interno + equipo de integración
- − Del primer prototipo al sistema de campo 3-6 meses
- − Mantenimiento queda en la casa
Paquete de programación de máquina específico de industria (PCB / CNC)
Empresarial500K-3M TRY embebido en el paquete de software de la máquina
Para quién: Taladrado automático PCB, insertadora, corte láser — paquete del fabricante de máquina
- + Secuencia de cabezal de taladro / inserción calibrada por el fabricante
- + Salida del programa de máquina carga directamente al equipo
- + Formación del operador la entrega el fabricante
- − Atado al fabricante — recompra para otra máquina
- − Algoritmo opaco, brecha a la mejor ruta no medible
- − Personalización (p. ej. penalización por cambio de broca) difícil
Recomendación
Pregunta en la reunión
- ¿Qué enfoque usa el motor de ordenación de ruta — solver con garantía de óptimo, vecino más cercano + mejora local, heurística estándar de la industria, o sólo vecino más cercano?
- ¿La matriz de distancias soporta calles de un solo sentido y tiempo dependiente de dirección, o siempre se asume A→B = B→A?
- ¿Cómo se genera la matriz de distancias — línea recta, basada en carretera real, o matriz de tiempo dependiente del tráfico? ¿Cadencia de actualización?
- ¿Cuál es el tiempo de resolución para tamaños típicos de instancia — 100, 500, 1.000 paradas?
- ¿El módulo reporta el porcentaje de desviación respecto a la mejor ruta posible?
- Cuando el problema crece de un solo vehículo a multi-vehículo con capacidad (capacidad, varias rutas, retorno a depósito), ¿se puede reutilizar la misma infraestructura o es un módulo aparte?
- Si termina el contrato, ¿en qué formato podemos exportar los datos de ruta (posiciones de paradas, rutas generadas, matrices de distancias)?
Detalles técnicos
Nota editorial
Este problema se conoce en el día a día como “planificación de ruta”, “orden de visita” o “secuencia de ruta”. Su nombre académico es claro: Travelling Salesman Problem (TSP). TSP es el problema fundacional de la investigación de operaciones — VRP (#002), PDPTW (#046), Berth Allocation (#026) y decenas de otros problemas de rutas / programación son extensiones estructurales del TSP. La distinción estructural es nítida: TSP es un solo vehículo, una ruta cerrada, sin capacidad, retorno al inicio, sin ventanas horarias. VRP añade multi-vehículo + depósito + capacidad; VRPTW añade ventanas; PDPTW añade emparejamiento origen-destino y precedencia. Comprar el “módulo de rutas” de un proveedor sin probar cuál de estas estructuras resuelve significa enterarse meses después — cuando surge la necesidad multi-vehículo — de que la infraestructura no estira.
Punto más omitido en el sector: el umbral práctico de aplicabilidad de los solvers exactos modernos. La intuición práctica suele ser “TSP es NP-difícil (clase de problemas cuyo tiempo de cómputo explota con el tamaño), lo exacto es imposible, hay que usar heurística”. La realidad: solvers branch-and-cut maduros han resuelto instancias de 85K+ nodos de forma exacta; una instancia de campo de 100-500 nodos llega al óptimo en minutos sobre un MIP moderno. Las heurísticas (vecino más cercano + 2-opt) son el defecto en la mayoría de productos — se desvían 15-30% del óptimo sobre datos reales. Regla práctica: por debajo de 1.000 nodos el TSP operacional es exacto-MIP; en el rango 1.000-100K la heurística LKH se mantiene dentro de 0,1-1% del óptimo. La intuición “hay que usar heurística” no es correcta; no se puede decidir sin conocer el tamaño.
Segundo punto omitido: distinción simétrico vs asimétrico. Las rutas urbanas con calles de un solo sentido, accesos a autovía, o tiempos de viaje dependientes de dirección producen una matriz asimétrica — A→B difiere de B→A. La mayoría de módulos TSP de productos asume simetría; alimentados con datos asimétricos producen un óptimo erróneo. El TSP asimétrico (ATSP) requiere otra formulación.
Paso a paso — para la pyme
Etapa 1 — Medir primero, planear después. Al menos 8-12 semanas de datos de ruta: por ruta — número de paradas, ubicaciones de paradas, distancia real (cuentakilómetros), duración, identidad del conductor, si la secuencia se cambió durante el día, si se respetaron las ventanas de visita. Matriz de distancias: distancia y tiempo típicos entre cada par de nodos visitados (tráfico fluido vs hora punta). Sin este inventario no se sabe qué software entregará qué resultado.
Etapa 2 — Extraer el capital de conocimiento. Estimar la brecha de la secuencia intuitiva actual respecto al óptimo: sobre un conjunto de 30-50 nodos de una jornada, calcular la ruta exacta con un solver MIP open-source y compararla con la ruta real del conductor. Brecha típica 15-30%. Esta brecha es la piedra angular del caso de negocio. Si el número de nodos varía día a día, separar promedios para días típicos vs punta.
Etapa 3 — Piloto. 6-10 semanas. Para un vehículo o una máquina, ejecutar el módulo TSP en paralelo con la secuencia intuitiva actual. La decisión sigue siendo del conductor / operador; el sistema aconseja. Criterios de éxito escritos antes del piloto: distancia media de ruta -10% mínimo, duración -8%, satisfacción de conductor neutra o positiva.
Etapa 4 — Despliegue. 4-9 meses para toda la flota o el parque de máquinas. Comité trimestral de operaciones: distancia real vs plan, desviación de tiempo de conductor, informe de impacto en ventanas de cliente, informe de tiempo de cabezal.
Riesgos — qué puede salir mal
- Tiempo de viaje supuesto estático. Una matriz de distancias construida con tiempos medios de un solo punto se desvía 50-100% del tiempo real en hora punta. Es necesaria una matriz de tiempos por bandas horarias (p. ej., perfil de tiempo de arco a 30 minutos); durante el piloto deben compararse tiempos planificados vs reales.
- ¿Está el tiempo de servicio dentro del modelo? Un técnico de campo pasa 30-90 minutos en cada parada; si este tiempo de servicio no está en el plan, la secuencia es matemáticamente óptima pero operativamente inviable. El tiempo de servicio por nodo debe modelarse como valor fijo o probabilístico.
- El número de nodos crece, la heurística se aleja del óptimo. Con 50 nodos vecino más cercano + 2-opt queda 5-10% del óptimo; con 500 nodos 15-25%; con 5.000 nodos 30%+. Conforme crece la escala, se requiere transición a LKH o MIP exacto; congelar la heurística acumula pérdidas con el crecimiento.
- Lock-in con un único proveedor de software de rutas. Sin cláusula contractual de “exportación anual de datos de ruta, matrices de distancias e historial de soluciones en formato estándar”, abandonar el sistema implica perder la memoria de rutas del negocio. Las ubicaciones de clientes y las ventanas de visita son el núcleo de esa memoria.
Visión técnica del método de solución
| Enfoque | Escala típica | Tiempo de cálculo | ¿Óptimo garantizado? |
|---|---|---|---|
| Secuenciación intuitiva (planificador + cabeza) | <20 nodos | instantáneo | No, 60-80% óptimo |
| Vecino más cercano + 2-opt | 20-200 nodos | segundos | No, 85-95% óptimo |
| Christofides 3/2 (TSP métrico) | 50-500 nodos | segundos | Garantía 3/2 |
| Programación dinámica (Held-Karp) | <25 nodos | minutos | Sí (exacto) |
| Branch-and-cut MIP (grupo Princeton-Georgia Tech) | 50-100K nodos | minutos-horas | Sí (dentro de cota) |
| Lin-Kernighan / LKH | 1K-1M+ nodos | minutos-horas | No, 0,1-1% del óptimo |
| Metaheurística (tabú, genético, ant colony) | flexible | flexible | No, buena calidad práctica |
Variantes TSP — elegir según el campo:
- TSP simétrico: distancia A→B = B→A. Carretera interurbana, distancia aérea, taladrado PCB. La variante más estudiada.
- TSP asimétrico (ATSP): distancia dependiente de dirección. Calles urbanas de un sentido, tiempo dependiente de dirección. Modelado un poco más complejo, sigue aplicando branch-and-cut.
- TSP euclídeo: nodos en el plano, distancia recta. Taladrado PCB, operaciones en línea.
- TSP métrico: se cumple la desigualdad triangular (A→C ≤ A→B + B→C). Aplica la garantía de Christofides 3/2.
- TSP con beneficios / OP: los nodos tienen un valor (beneficio); no es obligatorio visitar cada nodo. La variante de “cliente prioritario” para servicio de campo.
Función objetivo — elección:
- Objetivo 1 — Distancia / combustible mínimos: Enfoque combustible + tiempo de conductor.
- Objetivo 2 — Tiempo total mínimo: Enfoque tiempo de conductor / ciclo de máquina.
- Objetivo 3 — Tiempo máximo de parada mínimo (min-max TSP): Reparto justo o seguridad.
Referencias académicas
Listadas en el bloque sources del frontmatter de esta página.
Fuentes
- Dantzig, G., Fulkerson, R. y Johnson, S. (1954). Solution of a large-scale traveling-salesman problem. Operations Research, 2(4), 393-410. El trabajo fundacional de los planos de corte.
- Lin, S. y Kernighan, B. W. (1973). An effective heuristic algorithm for the traveling-salesman problem. Operations Research, 21(2), 498-516. Base de la familia heurística moderna.
- Applegate, D., Bixby, R., Chvátal, V. y Cook, W. (2006). The Traveling Salesman Problem: A Computational Study. Princeton University Press. Libro canónico del solver exacto branch-and-cut del grupo Princeton-Georgia Tech.
- Held, M. y Karp, R. M. (1962). A dynamic programming approach to sequencing problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196-210. La formulación DP O(n²·2^n).
- Helsgaun, K. (2000). An effective implementation of the Lin-Kernighan traveling salesman heuristic. European Journal of Operational Research, 126(1), 106-130. LKH — dentro de 0,1-1% del óptimo hasta escala de millones.
- YÖK Tez Merkezi — palabra clave: ‘gezgin satıcı’ o ‘TSP’ o ‘optimización de rutas’ — 30+ tesis de la academia turca. tez.yok.gov.tr
Glosario
- Travelling Salesman Problem
- El problema fundacional de la optimización combinatoria: hallar la ruta hamiltoniana de coste mínimo que visita cada nodo de un grafo exactamente una vez y regresa al inicio.
- Branch-and-Cut
- El marco de resolución MIP exacto que combina branch-and-bound con métodos de planos de corte — en cada nodo del árbol de búsqueda, desigualdades válidas (cortes) ajustan la relajación LP antes de ramificar.
- MIP
- Modelo de optimización donde parte de las variables de decisión deben ser números enteros (p. ej. número de camiones o de turnos).
- VRP
- La decisión de qué vehículos, partiendo de uno o varios almacenes, visitan a qué clientes y en qué orden.
Problemas relacionados
¿Dónde Abro el Nuevo Almacén?
Un distribuidor, un operador de comercio electrónico o un fabricante pyme prevé abrir 1–5 nuevos almacenes, sucursales o centros de distribución en los próximos 2–5 años. La decisión: en qué ciudad o región, cuántas instalaciones, de qué tamaño y qué almacenes existentes transfieren qué volumen de pedido o cliente a la nueva instalación. Una mala localización implica 5–10 años de alto coste de transporte, entregas tardías y pérdida de clientes; una buena localización supone 300.000–1,5 M EUR de ahorro anual en el mismo periodo. Cuando la decisión se toma por intuición (por ejemplo 'al lado de la fábrica, los empleados viven cerca') rara vez se acierta — porque coste de transporte, alquiler, impuestos, mano de obra y tiempo de servicio son restricciones que deben equilibrarse a la vez.
¿Qué cabe en un camión o contenedor, y en qué orden se carga?
Dado un camión, contenedor o vehículo de carga de dimensiones fijas, ¿qué disposición de cajas (o pallets) con tamaños, pesos y reglas de apilado distintos da la mayor tasa de utilización? El nombre matemático de esta pregunta es Three-Dimensional Bin Packing Problem (3D-BPP) o Container Loading Problem (CLP). Métodos que resuelven al mismo tiempo volumen, límites de peso, reglas de apilado, distribución del peso (balance) y orden de entrega (multi-drop) se estudian desde los 1990. Incluso un 5% de mejora en utilización aumenta entregas por vehículo de forma material para una pyme.
¿Qué Furgoneta a Qué Cliente, a Qué Hora?
Una flota local de reparto de 5–30 furgonetas planifica sus rutas diarias. Cada cliente tiene una ventana horaria (una tienda recibe entre 09:00 y 12:00; un restaurante solo antes de las 14:00). La decisión: a qué furgoneta asignar cada cliente, en qué orden visitarlos, de modo que todas las ventanas se cumplan, las horas de combustible y conductor sean mínimas, y ninguna furgoneta supere su capacidad. Un repartidor puede planificar a mano 30–50 paradas; por encima, la calidad cae — kilómetros vacíos, entregas tardías, segundas rutas y horas extra del conductor.