¿Cuál es el problema del vendedor viajero (TSP)?

problema del vendedor viajero
Featured image credit: yuoak/iStockphoto.com

El problema del vendedor viajero es el problema de averiguar la ruta más corta para que los representantes de ventas puedan tomarla, a partir de una lista  de destinos específicos.

Expliquemos el problema con un breve ejemplo.

Un vendedor desea visitar unas pocas ubicaciones para vender artículos. ´Él sabe los nombres de las áreas y las distancias entre cada una.

Entonces, ¿cuál es la ruta más corta que deberá seguir el vendedor y que solo visite cada ubicación una sola vez antes de regresar al punto de partida?

El problema del vendedor viajero es una extensión del problema del ciclo hamiltoniano. Este es un antiguo problema de la informática que tiene implicaciones en la teoría de la complejidad y el problema P versus NP.

El problema del enrutamiento vehicular y el problema del comprador viajero son ambas generalizaciones del TSP o problema del vendedor viajero.

El trasfondo del problema del vendedor viajero

El problema del vendedor viajero (TSP por su siglas en inglés) se formuló en 1930. Sin embargo, es uno de los problemas más estudiados de la optimización combinatoria, incluso en la actualidad.

En 1972, Richard Karp probó que el problema del ciclo hamiltoniano era NP-completo, una clase de problemas de optimización combinatoria.

Esto se traduce en que el TSP era NP-complejo. Y la complejidad de calcular la mejor ruta aumentará factorialmente cuando se añaden más destinos al problema.

Por ejemplo, puede haber tres rutas posibles en cuatro ciudades. Mientras que pueden existir hasta 360 rutas posibles en seis ciudades.

Esto se debe a que los científicos no solo computarizan la ruta más eficiente, sino la que funciona.

Este cálculo utiliza el enfoque de fuerza bruta para resolver el problema al describir todas las posibilidades y luego elegir la mejor. En otras palabras, busca cada una de las rutas únicas que puede tomar el vendedor.

Aunque las dificultades computacionales incrementan con cada ciudad que se añade al itinerario, los informáticos han calculado la solución óptima a este problema para miles de ciudades desde principios de los 90.

Por ejemplo, muchas ciudades y pueblos en un estado de USA pueden ser parte de un área de delivery o de la logística de un gran proveedor.

Descubrir la ruta más corta entre todas las paradas que el vehículo necesita hacer en el día a día ahorraría mucho tiempo y dinero.

Route4Me

¿Quieres ver cómo Route4Me puede aumentar tus ganancias?

No importa si lo que buscas es reducir el tiempo que te toma planificar rutas para tus conductores, aumentar la cantidad de paradas que pueden hacer o mantener a tus clientes satisfechos sabiendo que tus conductores llegan siempre a tiempo… ¡Route4Me te ayudará a lograrlo todo!

Start Free 14 Day Trial

¿Por qué el problema del vendedor viajero es tan difícil?

En teoría, el TSP se puede resolver al chequear cada ruta de ida y vuelta para encontrar así la más corta.

Sin embargo, una vez que crece el número de ciudades, el número correspondiente de rutas de ida y vuelta supera las capacidades de las computadoras más rápidas.

Pueden existir  más de 300,000 permutaciones de ida y vuelta y combinaciones con solo diez ciudades.

Con 15 ciudades, las rutas posibles pueden ser más de 87 mil millones.

En los primeros días de la computación, los informáticos esperaban que alguien desarrollara un algoritmo mejorado para resolver el problema en un tiempo razonable.

Sin embargo, aunque los científicos han progresado con escenarios específicos, no se disponía de un solucionador eficiente de los problemas del vendedor viajero.

Es posible que ni siquiera se pueda lograr un algoritmo único para todos.

Aplicaciones del problema del vendedor viajero

El TSP todavía tiene aplicaciones en todas las verticales. Soluciones eficientes a través del TSP se utilizan en astronomía, informática e incluso en el enrutamiento de vehículos y la organización de rutas.

Los astronautas utilizan los conceptos de TSP para determinar el movimiento de un telescopio en la distancia más corta entre diferentes estrellas en una constelación.

Otros usos para el TSP incluyen la planificación de internet, agricultura, producción de microchips y el arte generado por computadora.

Los desafíos enfrentados por los vendedores viajeros

Casi todos los vendedores se despiertan en la mañana con la idea de aprovechar al máximo su día.

Tienen muchas citas con sus clientes confirmadas y muchas más de último minuto.

Los vendedores no siempre tienen un horario confirmado. Por lo tanto, usualmente deben retroceder y tomar rutas más largas para llegar a las direcciones de los clientes. Esto se transforma en citas y oportunidades perdidas.

El vendedor de hoy en día enfrenta problemas adicionales de congestión del tráfico, solicitudes de último minuto de los clientes y ventanas de disponibilidad de tiempo. A eso, debemos agregarle los problemas de ruta que ya enfrentaban los vendedores de antaño.

Si piensa que el TSP es un acertijo matemático difícil, ahora debe considerar esto:

Quizá necesite planificar y organizar las rutas de un equipo completo de representantes de ventas en vez de un solo vendedor

Ahora, deberá dividir las visitas y asignarlas a su equipo.

¿Qué pasaría si los vendedores tuvieran diferentes espacios para citas, y su objetivo es mantener sus rutas lo más cortas, rápidas y rentables?

Considere esto: si tiene un total de 100 direcciones de clientes y hay 8 personas en su equipo de ventas, pueden haber más de un millón de posibles combinaciones u organizaciones de rutas.

Un algoritmo básico que sopese cada combinación posible y elija la mejor le tomará días, si no meses.

Ahora, ese es un desafío del mundo real, y es aquí donde entra en acción la optimización de rutas.

Seguro se pregunta, ¿qué es la optimización de ruta?

Route optimization is all about finding the fastest, shortest, and most fuel-efficient route for a set of stops.
La optimización de rutas es todo lo relacionado a encontrar la ruta más rápida, corta y que consuma menos combustible para un conjunto de paradas.

Cómo solucionar los problemas del vendedor viajero con un planificador de rutas

A medida que su equipo crece, la planificación de rutas será inevitablemente más compleja de manejar si utiliza un lápiz y papel o herramientas básicas como Google Maps o Waze.

Sin algunas herramientas de trabajo pesado, no puede tener en cuenta de forma manual elementos como los bloqueos de calles y condiciones climáticas. Como resultado, acabará gastando demasiado tiempo en la planificación de rutas.

Las situaciones imprevistas como la congestión del tráfico hacen más difícil que los vendedores lleguen a tiempo.

Además, la distribución balanceada es muy difícil si se intenta optimizar agendas y horarios de forma manual.

También corre el riesgo de aumentar sus costos operativos. A menudo en forma de consumo de combustible y salarios desperdiciados debido a un mayor tiempo de conducción.

Además, sus clientes se molestarán si su representante de ventas se presenta tarde o sus conductores fallan en la hora pautada para las entregas.

Un software de enrutamiento de vehículos y optimización de rutas es la solución perfecta para el problema del vendedor viajero.

Un planificador de rutas u organizador de rutas potenciado por el algoritmo de Dijkstra reducirá el tiempo de conducción y el consumo de combustible al buscar la ruta más eficiente para su equipo en segundos.

Este aborda con eficacia el complejo TSP para encontrar la ruta más eficiente hacia un destino. Encontrar la ruta más eficiente es físicamente imposible. Pero sí es posible encontrar una ruta “muy eficiente” o una ruta que es “más eficiente de lo que los humanos jamás podrían hacer”. Y es ahí donde el planificador de rutas puede ayudar.

Con un planificador de rutas se garantiza entregas y citas a tiempo, ahorro de costos y seguridad para el conductor. También, un optimizador de rutas reduce el tiempo de conducción de sus representantes de ventas y tiene un impacto directo sobre los resultados. Pero aún hay más que le puede ofrecer.

Conclusión sobre el problema del vendedor viajero

Existen muchos más casos similares al TSP con personas y vehículos que se enfrentan a rutas imprecisas y retrasos.

Los científicos han estado tratando de identificar problemas como el TSP por décadas. Lo más cerca que hemos llegado, de manera imperfecta, son los algoritmos complejos a través de aplicaciones de planificador de rutas fáciles de usar.

Route4Me

¿Quieres ver cómo Route4Me puede aumentar tus ganancias?

No importa si lo que buscas es reducir el tiempo que te toma planificar rutas para tus conductores, aumentar la cantidad de paradas que pueden hacer o mantener a tus clientes satisfechos sabiendo que tus conductores llegan siempre a tiempo… ¡Route4Me te ayudará a lograrlo todo!

Start Free 14 Day Trial

About author: Rahul Dasgupta

Rahul Dasgupta is a content writer with over 20 years of work experience. He holds a master’s degree in computer science and has written thousands of blog posts on route planning and scheduling, making it easy for readers to learn about these complex topics. Rahul enjoys playing tennis in his spare time and loves cuddling with his pet labrador Shinu. Rahul is a big fan of Roger Federer, Messi, and Bill Gates - he admires their drive to be the best at what they do and their philanthropic efforts.

Route4Me

Acerca de Route4Me

El planificador de rutas Route4Me tiene más de 40,000 clientes en casi todos los continentes. Las aplicaciones móviles para Android y iPhone de Route4Me se han descargado más de 2 millones de veces desde 2009. Extremadamente fáciles de usar, las aplicaciones sincronizan rutas, permiten la comunicación bidireccional con los conductores, ofrecen indicaciones paso a paso, confirmación de entrega y más. Detrás de escena, la plataforma de optimización operativa de Route4Me combina algoritmos de alto rendimiento con ciencia de datos, aprendizaje automático y big data para planificar, optimizar y analizar rutas de casi cualquier tamaño en tiempo real.