El problema de la tecnología de transporte de ventas (TSP) es uno de los retos más duraderos en la optimización combinatoria. En su núcleo, la TSP hace una pregunta engañosamente simple: dada un conjunto de ciudades y las distancias entre cada par, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y regresa al punto de origen? Este rompecabezas aparentemente sencillo ha cautivado a los matemáticos, los científicos de la computadora y las operaciones de los investigadores de la serie de la

Los orígenes y la evolución del problema de los vendedores itinerantes

El TSP fue formulado por primera vez en los años 1800 por matemáticos como William Rowan Hamilton y Thomas Kirkman, pero adquirió una atención generalizada a mediados del siglo XX, ya que el poder de cálculo comenzó a aumentar. En 1954, un equipo de RAND Corporation publicó la primera solución TSP "grande" para 49 ciudades, utilizando técnicas de programación lineal de vanguardia.

Los enlaces externos pueden proporcionar un contexto más profundo en la historia y complejidad de TSP. Por ejemplo, el ] Documento VIGRE de la Universidad de Chicago sobre el TSP ofrece una introducción rigurosa, mientras que La entrada TSP de la Guía de NOS explica su estado computacional.

Mapping the TSP to Modern Logistics Operations

En una operación de entrega típica, un vehículo comienza desde un depósito, debe visitar un conjunto de ubicaciones de clientes, y luego volver al depósito. Esto refleja el TSP simétrico clásico. Sin embargo, la logística del mundo real rara vez encuentra la forma pura del problema. Varias diferencias clave complican las cosas:

  • Ventas temporales: Los clientes esperan que las entregas se realicen dentro de horas específicas, convirtiendo el TSP en el problema de los vendedores itinerantes con el tiempo Windows (TSPTW).
  • Capacidad de vehículos: Múltiples vehículos, cada uno con espacio de carga finito, dan lugar al problema de la rotación del vehículo (VRP), una generalización de la TSP.
  • Actualizaciones sínmicas: Los nuevos pedidos llegan durante todo el día, requiriendo un cambio en tiempo real en lugar de un plan estático.
  • Redes comerciales y de carreteras: Las distancias euclidianas se sustituyen por los tiempos de viaje reales que varían con congestión, cierres de carreteras y clima.

A pesar de estas complejidades, la lógica central de TSP permanece incrustada en los solvers de VRP. La mayoría de los motores modernos de optimización de rutas descomponen el problema multi-vehículo, multi-constructor en una serie de subproblemas tipo TSP para rutas individuales.

El TSP en entrega de última hora

El suministro de última hora, la etapa final de un centro de distribución a la puerta del cliente, representa la parte más costosa de muchas cadenas de suministro. Según estimaciones de la industria, el transporte de última millas representa un 30% al 50% de los costes logísticos totales. Aquí, los algoritmos TSP reducen directamente la distancia impulsada por la parada, cortando los gastos de combustible y permitiendo a los conductores manejar más entregas por turno.

Técnicas Algorítmicas Avanzadas para TSP en Logística

Mientras que los solvers exactos (por ejemplo, ram-and-bound o branch-and-cut) pueden manejar problemas pequeños a medianos, las empresas logísticas suelen enfrentar instancias con cientos o miles de paradas por ruta. Para mantener los tiempos de computación manejable, se basan en un toolkit de algoritmos:

  • algoritmos genéticos: Mimiendo la selección natural, estos evolucionan una población de rutas a lo largo de muchas generaciones, cruzando y mutando las buenas soluciones para converger en caminos casi óptimos.
  • Asistencia simulada: Inspirada en la metalurgia, esta técnica probabilística acepta ocasionalmente peores soluciones a la hora de la búsqueda de escapar del optima local, luego reduce gradualmente la “temperatura” para ajustar la mejor ruta.
  • Optimización de la colonia ant: Simulando el comportamiento de las hormigas que transmiten feromonas, este método construye rutas incrementalmente y refuerza segmentos de trayectoria que aparecen en recorridos más cortos.
  • Nearest vecino y algoritmos de ahorro: Heurísticas de construcción rápida que proporcionan una ruta inicial decente, que puede ser mejorado por la búsqueda local.

El software moderno a menudo combina estos métodos. Por ejemplo, un algoritmo genético puede producir un conjunto de rutas candidatas, que luego se pulían mediante búsqueda local de 3 puntos y validados contra datos de tráfico en tiempo real de API como Google Maps o AQUÍ. El resultado es una recomendación dinámica de enrutamiento que puede adaptarse cuando un cliente cancela un pedido o surge una nueva gota.

Datos en tiempo real y el TSP

El TSP estático asume distancias fijas y un conjunto conocido de destinos. En logística, la realidad es fluida. Los anillos GPS de los vehículos de entrega, los alimentamientos de tráfico en vivo y las cancelaciones de pedidos en constante. Los sistemas modernos basados en TSP tratan el problema como un horizonte de rodadura: un plan se genera para las próximas paradas N, ejecutadas parcialmente, y luego se re-optimula a medida que llegan nuevas informaciones.

Para un análisis profundo de cómo las empresas utilizan datos en tiempo real para mejorar las soluciones de TSP, vea la ] seguridad sobre la enrutación dinámica de vehículos por Pillac et al. (2019).

Estudios de casos: TSP en acción en las principales empresas logísticas

Amazon Prime's Route Optimization Ecosystem

Amazon opera una de las redes de entrega más complejas del mundo, con millones de paquetes que se mueven a través de docenas de centros de clasificación y estaciones de entrega cada día. La empresa utiliza algoritmos patentados que resuelven las variantes de TSP y VRP a gran escala a través de múltiples olas. Su sistema debe tener en cuenta las ventanas de tiempo de entrega (por ejemplo, Prime Now ranuras de una hora), tamaños de paquetes variables, y la capacidad de los pilotos de búsqueda de Amazonas.

UPS y el sistema ORION

ORION (On-Road Integrated Optimization and Navigation) es quizás el mayor despliegue de optimización basada en TSP. Elaborado durante varios años a más de 55.000 rutas en América del Norte, ORION utiliza una combinación de metaheurística avanzada y datos patentados para planificar la secuencia de paradas de escala de CO de cada conductor.

Optimización de la cadena de suministro global de DHL

DHL aplica conceptos TSP no sólo a la entrega local sino también a sus redes internacionales de carga. Para servicios de correo expreso, DHL utiliza un modelo de enrutamiento multiéchelon donde se consolidan paquetes en centros, fluidos entre continentes y luego distribuidos localmente.El paso de distribución local es esencialmente un gran TSP con ventanas de tiempo y limitaciones de capacidad.

Más allá de la TSP clásica: Variantes que resuelven problemas modernos

Como la logística ha crecido más sofisticada, los investigadores han propuesto docenas de variantes TSP adaptadas a limitaciones operativas específicas:

  • Prize‐collecting TSP: El mensajero puede saltar algunos destinos pero paga una penalidad, útil cuando no todos los parados son obligatorios.
  • Multiple travelling salesmen (mTSP): Varios conductores comienzan y terminan en un depósito, cada uno visitando un subconjunto de clientes, un modelo directo para la fuga de enrutamiento.
  • TSP con backhauls: Algunos parados requieren recoger bienes (por ejemplo, retornos) en lugar de entregar, alterando la secuencia de carga de la ruta.
  • TSP asimétrico: Los costes de viaje difieren según la dirección (por ejemplo, debido a calles de una sola dirección o a diversos peajes), reflejando redes urbanas reales.

Cada variante exige ajustes algoritmos especializados, pero la lógica subyacente de TSP —encontrada el ciclo más corto de Hamilton— sigue siendo un poderoso ancla conceptual. Para los administradores de logística, entender qué mapas variantes de sus operaciones diarias es el primer paso hacia la optimización efectiva de la ruta.

Futuros Direcciones: Vehículos autónomos, Drones y AI

Los vehículos de entrega autónoma y los drones están preparados para transformar la logística de última millas, pero también presentan nuevos retos relacionados con TSP. Una furgoneta auto-aprendizaje podría tener que resolver un TSP no sólo por su propia ruta sino también coordinar con un pequeño drone que se lanza desde la furgoneta para hacer entregas en cul-de-sacs mientras la furgoneta continúa en una carretera principal.

Para un vistazo a un enfoque de vanguardia, lea sobre aprendizaje para resolver TSP con redes neuronales gráficas].

Pasos prácticos para los administradores de logística

Para las organizaciones que buscan aplicar los principios de la TSP a sus propias operaciones de entrega, el camino normalmente implica cuatro fases:

  1. Agregar datos: Recopilar direcciones exactas, tiempos de viaje (utilizando una API de enrutamiento), pronósticos de demanda y limitaciones de controlador.
  2. Selección Algorithm: Elige entre los solvers de código abierto (por ejemplo, OR‐Herramientas de Google, LKH) o plataformas comerciales (por ejemplo, Routific, Route4Me, OptimoRoute) que incrustan la heurística TSP.
  3. Integración con sistemas de despacho: Conecte el optimizador a una aplicación de controlador móvil y un sistema de gestión de pedidos de backend para impulsar rutas y recibir actualizaciones de estado en tiempo real.
  4. Mejora continua: Medir los indicadores de rendimiento clave (paradas por hora, millas por parada, porcentaje a tiempo) y ajustar los parámetros o limitaciones del solucionador a medida que evolucionan las operaciones.

Incluso las pequeñas empresas con diez o menos rutas pueden realizar ahorros sustanciales —a menudo 10-20% de reducción en distancia impulsada— mediante la adopción de una herramienta de enrutamiento basada en TSP. La inversión en software y capacitación normalmente paga en el plazo de meses a través de la reducción de combustible, mantenimiento y los costos de horas extraordinarias.

Conclusión: La relevancia de un problema clásico

El problema de viaje del salesman surgió por primera vez en las salas tranquilas de matemáticas del siglo XIX, pero ahora impulsa los algoritmos que entregan paquetes a las puertas alrededor del mundo. Desde los centros de clasificación de Amazon a una panadería de un solo trecho en una ciudad rural, la optimización de la ruta inspirada por TSP reduce los residuos, ahorra dinero y reduce el impacto ambiental.