La solución del problema del vendedor viajero para empresas de entrega y servicios

Calcular la ruta más eficiente entre varias ciudades es un gran desafío. Hay cientos de opciones posibles que cambian según cientos de variables diferentes.

Por ejemplo, en solo 15 ciudades hay más de 87 mil millones de viajes redondos posibles. 

Este es el problema del vendedor viajero. 

Y es un problema increíblemente costoso para cualquier negocio de entregas, servicios o transporte.

Para resolver el problema del vendedor viajero, necesitas algoritmos robustos y un poder computacional serio.

Si no deseas invertir dinero en un equipo interno de matemáticos y ingenieros expertos, necesitas una solución de terceros.

En este artículo, exploraremos qué hace que el problema del vendedor viajero (TSP) sea tan difícil y cómo los propietarios de negocios pueden usar soluciones de software inteligentes para resolverlo, reducir el kilometraje y mejorar la eficiencia de la flota.

Para navegar a la sección que más te interese, haz clic a continuación:

• ¿Qué es el problema del vendedor viajero?
• ¿Por qué el problema del vendedor viajero sigue siendo difícil de resolver en 2020?
• Cómo The Little Posy Co. planifica rutas para 1,000 destinos en minutos

¿Qué es el problema del vendedor viajero?

El problema del vendedor viajero (TSP) es un problema que pregunta, con una lista de paradas y las distancias entre cada una de ellas, ¿cuál es el camino/ruta posible más corta que visita cada ubicación y regresa al origen?

Durante décadas, el TSP ha sido un desafío para muchas empresas que dependen de la planificación de rutas, por ejemplo, empresas de servicios de campo, envíos y entregas.

Con solo un punto de partida y algunas paradas, planificar una ruta puede parecer lo suficientemente complicado.

Pero una vez que comienzas a planificar rutas por todo el país, alcanza un nivel de complejidad casi impensable. Con infinitas permutaciones de rutas potenciales entre diferentes paradas (típicamente llamadas nodos), identificar la ruta más corta y eficiente es un gran desafío.

Así es como se vería una ruta si se planificara para cada ciudad en los EE. UU. con más de 500 habitantes:

(Fuente de la imagen)

Solo imagina la cantidad de rutas posibles que podrías tomar cuando una sola solución posible es tan compleja.

¿Por qué el problema del vendedor viajero sigue siendo difícil de resolver en 2021?

El matemático Karl Menger descubrió el TSP en 1930, hace más de 90 años.

Desde entonces, ha habido muchas soluciones y algoritmos sugeridos. Pero a menudo luchan con la magnitud, ya que el número de rutas de ventas aumenta exponencialmente con cada nueva parada.

Y la verdad es que, la planificación de rutas real en 2021 para negocios reales es más compleja que solo una lista de paradas, lo que complica aún más las cosas.

En el mundo real, no es tan fácil como simplemente encontrar la ruta más corta.

No se trata solo de destinos y distancias, hay muchos otros factores en juego

No es tan fácil como simplemente tomar una lista de direcciones y crear una ruta. 

A ventas de campo el representante, conductor de entrega o técnico también tiene que considerar muchos otros factores, como ventanas de tiempo, capacidades del vehículo y más.

Ventanas de tiempo de entrega y reuniones de ventas planificadas

¿Qué pasa si tus conductores de entrega o vendedores tienen tiempos de entrega o reuniones de ventas planificadas? Entonces no basta con considerar solo la distancia, también debes tener en cuenta cuándo deben estar en cada ubicación.

Esto añade un nivel completamente nuevo de complejidad y es un desafío que la mayoría de los planificadores de rutas simplemente no pueden manejar.

Esta instancia particular del problema también se conoce como el Problema de Enrutamiento de Vehículos con Ventanas de Tiempo (VRPTW). 

Capacidades requeridas de los vehículos o calificaciones de los técnicos

Para las entregas, cada paquete que planificas puede tener requisitos específicos en términos de envío y manejo, desde refrigeración hasta dimensiones de descarga.

También debes considerar la capacidad de carga total de cada vehículo.

Pero incluso para las empresas de mantenimiento y servicios de campo, debes considerar las calificaciones únicas de cada técnico y si coinciden con un trabajo.

Esto también se conoce como el Problema de Enrutamiento de Vehículos Capacitados (CVRP).

Planificación de rutas eficientes que incluyan tanto recogidas como entregas

Si tu negocio entrega cualquier tipo de embalaje reutilizable o materiales reciclables a tus clientes, es probable que logística inversa sea una gran prioridad.

Para maximizar la eficiencia de tu negocio, deseas integrar tanto la recogida como la entrega en todas las rutas planificadas.

Esto añade otra dimensión y un nivel de complejidad que la mayoría de las herramientas de optimización de rutas no pueden manejar.

Esto también se refiere como el Problema de Enrutamiento de Vehículos de Recogida y Entrega (PDVRP)

Considerando la prioridad de los prospectos, clientes existentes y entregas

Para operar un negocio eficientemente y mantener satisfechos a los clientes VIP, también necesitas asegurarte de que tu personal priorice las cosas de la manera correcta.

Si tus rutas no consideran la prioridad, todos los clientes serán tratados por igual. Así que corres el riesgo de alienar a los clientes leales si de repente cambias a una solución automatizada que no puede manejar eso.

Balanceando las cargas de trabajo entre múltiples conductores

Por supuesto, al planificar rutas para múltiples conductores, también debes considerar sus cargas de trabajo.

Los conductores son solo humanos y tienen una duración máxima de turno de 14 horas y descansos obligatorios.

¿De qué sirve una "ruta eficiente" si no es posible para un conductor manejarla dentro del tiempo asignado?

Las buenas herramientas de balanceo de carga de trabajo te ayudarán a reducir las horas extras y los costos de los conductores, y asegurar que todos los conductores cumplan con las HOS en todo momento.

Cómo The Little Posy Co. Planifica Rutas para 1,000 Destinos en Minutos con OptimoRoute

The Little Posy Co. es un negocio australiano de entrega de flores, con cientos de flores y ramos únicos disponibles cada día.

Como cualquier negocio de entrega de flores o floristería, enfrentan grandes fluctuaciones en la demanda en relación con diferentes festividades.

El Día de San Valentín de 2019, el volumen de pedidos explotó a más de 1,000 pedidos en un día, el mismo volumen que en una semana regular.

Normalmente, esto sería una tarea imposible para el pequeño equipo de Posy, pero el algoritmo de optimización de OptimoRoute ayudó a agilizar todo el proceso.

"OptimoRoute ha cambiado lo imposible a lo absolutamente posible en el Día de San Valentín. Alivia la presión: no podía imaginar cómo el flujo de trabajo podría funcionar tan suavemente sin este software." – Gabby Maynard, The Little Posy Co.

Importación Masiva de Pedidos y Planificación Rápida de Rutas Automáticas

Con OptimoRoute, no hay necesidad de agregar paradas o direcciones individualmente, ni de planificar rutas para un solo conductor a la vez.

Simplemente puedes importar tu lista de pedidos en una hoja de cálculo de Excel o un archivo CSV.

Desde allí, OptimoRoute planifica rutas automáticamente, ajustándose a restricciones del mundo real como horarios de entrega, áreas de servicio de los conductores, horarios de los conductores, y más.

"No podría imaginar tener que despachar 1,000 pedidos sin OptimoRoute porque literalmente son unos pocos clics del ratón y las rutas están perfectamente trazadas." Gabby Maynard, The Little Posy Co.

Datos Históricos y Análisis Ayudan a Prever la Demanda

Los datos históricos de rutas y los análisis detallados ayudaron a Maynard a prever la demanda y escalar la flota en consecuencia.

"Dependemos mucho de los datos históricos: saber cuántos conductores necesito reclutar para el día, cuántos pedidos puede tomar cada conductor, cuánto tiempo tomarían esas entregas, y cuántos conductores fueron despachados." Gabby Maynard, The Little Posy Co.

Reflexiones Finales

Como propietario de un negocio, lo último que quieres hacer es perder tiempo innecesario sentado en Google Maps tratando de planificar rutas y no obtener soluciones óptimas (la optimización de rutas de Google Maps no es para negocios).

El problema del viajante afecta a las empresas porque planificar rutas manualmente requiere mucho trabajo, aumentando las horas de trabajo y los costos totales de tu logística.

Esto a menudo puede significar departamentos de despacho y programación sobredimensionados, y una flota que responde lentamente a cancelaciones y pedidos de última hora.

Afortunadamente, no necesitas tener un título en ciencias de la computación, crear un algoritmo de aproximación, o ser matemático para encontrar la mejor solución para el problema del viajante.

OptimoRoute ofrece una experiencia de planificación de rutas sin problemas, con funciones inteligentes que ayudan a los despachadores a planificar rutas en minutos. También hace que tu flota sea más flexible, ayudando a los despachadores a ajustarse a cambios en tiempo real.

Para ver cómo OptimoRoute puede ayudar a tu empresa a superar el problema del viajante, comienza tu prueba gratuita de 30 días hoy.

Preguntas Frecuentes sobre el problema del viajante

¿Cómo se resuelve el problema del viajante? 

Matemáticos y científicos de la computación han propuesto una serie de heurísticas potenciales o soluciones aproximadas para resolver el problema del viajante. Una solución común, llamada método de ramificación y acotamiento, implica dividir el problema en una serie de subproblemas más pequeños que son más fáciles de resolver matemáticamente que intentar resolverlo todo como un solo problema.

¿Cuál es un ejemplo del problema del viajante?

Además de lo obvio (bueno, un viajante), tomemos el ejemplo de un servicio de entrega que está entregando a varios lugares diferentes en una ciudad. El despachador tiene que determinar el orden en el que se detienen (fuera de la ubicación de inicio). Podrías pensar: simplemente detente en la ubicación más cercana al punto de inicio, y luego en la más cercana a esa, etc. 

Pero, ¿qué pasa si la parada más cercana a la ubicación de inicio te lleva más lejos de todas las otras paradas? Tienes que considerar qué tan lejos están las siguientes ubicaciones de la primera parada que elijas. Así que, como puedes ver, el número de variables se multiplica rápidamente, y encontrar la ruta más corta se vuelve enormemente complejo a medida que agregas más y más variables.

¿Por qué se considera que el problema del vendedor viajero es NP-difícil?

El problema del vendedor viajero se considera un problema NP-difícil porque no existe una solución simple o directa, y la dificultad de calcular la ruta óptima con el menor tiempo de ejecución aumenta a medida que se añaden más destinos.