¿Qué es el TSP (problema del viajante de comercio)?

¿Cómo determinar la mejor ruta para visitar a varios clientes recorriendo el menor número de kilómetros posible? Detrás de esta pregunta, que afecta a diario a los comerciales itinerantes, se esconde un problema matemático estudiado desde hace décadas: el problema del viajante de comercio, o Traveling Salesperson Problem (TSP).

Su principio es sencillo: encontrar el camino más corto que conecte varios destinos. Pero su resolución se vuelve rápidamente compleja a medida que aumenta el número de puntos a visitar.

Y en la realidad, organizar una ruta comercial no se limita a calcular distancias. También es necesario respetar los horarios de apertura de los clientes, las citas ya planificadas, la duración de las visitas y las jornadas laborales.

Entonces, ¿cómo funciona el TSP? ¿Por qué es tan difícil de resolver? ¿Y cómo permiten sus principios diseñar rutas comerciales más eficaces?

¿Qué es el problema del viajante de comercio (TSP)?

El problema del viajante de comercio, denominado Traveling Salesperson Problem (TSP) en inglés, es un problema clásico de optimización combinatoria.

Consiste en determinar el circuito más corto que permita visitar un conjunto de destinos, pasando una sola vez por cada uno de ellos, antes de regresar al punto de partida.

Veamos un ejemplo.

Un comercial debe visitar cinco tiendas distribuidas en su zona. Conoce sus direcciones, pero debe determinar en qué orden visitarlas para minimizar la distancia recorrida.

Podría empezar por la tienda A, continuar hacia la B, luego la C, la D y la E. Pero también podría visitar estas tiendas en un orden totalmente diferente.

Cada combinación genera un itinerario cuya distancia total puede variar.

El objetivo del TSP es encontrar el orden de visita que permita recorrer la distancia total más corta.

Esta problemática va mucho más allá del ámbito de los equipos comerciales. Se encuentra en la logística, el reparto, el transporte o incluso en ciertos procesos industriales.

¿Por qué el TSP es tan complejo de resolver?

Cuando el número de destinos es limitado, resulta relativamente sencillo comparar varias rutas.

Sin embargo, cada nuevo destino incrementa considerablemente el número de combinaciones posibles.

Fijando un punto de partida y considerando todos los órdenes de visita posibles:

• Con 5 destinos, existen 24 secuencias posibles.

• Con 10 destinos, existen 362 880.

• Con 15 destinos, esta cifra supera los 87 000 millones.

Estas cifras ilustran lo que se denomina una explosión combinatoria: el número de soluciones posibles aumenta de forma extremadamente rápida con el tamaño del problema.

En informática, el TSP pertenece a la familia de los problemas NP-difíciles (o NP-hard). Dicho de otro modo, ningún método general conocido permite garantizar la resolución exacta de todas las instancias en un tiempo de computación que crezca de manera polinomial con su tamaño.

Esto no significa que sea imposible encontrar la solución óptima. Existen métodos exactos que permiten resolver numerosas instancias.

En cambio, cuando el número de destinos y las restricciones aumentan, buscar sistemáticamente la solución perfecta puede requerir recursos de computación considerables.

Por esta razón, las herramientas de optimización utilizan diferentes métodos para encontrar rutas eficaces en un plazo razonable.

¿Cómo funciona un algoritmo TSP?

En su formulación clásica, el problema del viajante de comercio se basa principalmente en dos elementos:

1. Los destinos a visitar, representados por puntos geográficos.

2. La distancia o el coste de desplazamiento entre estos destinos, lo que permite comparar las rutas.

El problema también define un circuito, con un punto de partida y un regreso a ese mismo punto.

A partir de esta información, el algoritmo busca el orden de visita que minimice la distancia total.

Los diferentes métodos de resolución

Existen varios enfoques para resolver un problema TSP.

Los métodos exactos exploran las soluciones de manera estructurada para identificar y demostrar cuál es el mejor itinerario posible. Pueden resultar costosos a medida que el problema se vuelve más complejo.

Las heurísticas buscan obtener rápidamente una solución satisfactoria, sin garantizar que sea óptima. Un enfoque sencillo consiste, por ejemplo, en dirigirse en cada paso al destino no visitado más cercano.

Las metaheurísticas emplean estrategias de búsqueda más elaboradas para explorar y mejorar distintas soluciones. Resultan particularmente interesantes para problemas de gran tamaño.

La elección del método depende del número de destinos, del tiempo de cálculo disponible y del nivel de precisión requerido.

Pero en el marco de las rutas comerciales, entra en juego otro elemento: la distancia no es la única restricción que se debe respetar.

Del TSP a la optimización de rutas comerciales: por qué el trayecto más corto no es suficiente

El TSP clásico responde a una pregunta: ¿cuál es el circuito más corto para visitar todos los destinos?

Un comercial itinerante debe responder a una pregunta mucho más compleja: ¿cómo organizar mis visitas para reunirme con los clientes adecuados, en el momento oportuno, limitando mis desplazamientos y respetando mis limitaciones diarias?

La diferencia es importante.

Imaginemos a un responsable de zona que debe visitar quince tiendas en tres días.

Un algoritmo que únicamente busque reducir la distancia podría proponerle una ruta muy corta sobre el papel. Sin embargo, esa planificación podría ser imposible de llevar a cabo:

• Una tienda estaría cerrada en el momento de su paso.

• Una visita duraría más tiempo que la franja horaria disponible.

• Dos citas se solaparían.

• El comercial terminaría su jornada después de su horario de trabajo.

• Una cita ya confirmada tendría que ser aplazada o reprogramada.

Por lo tanto, el camino más corto no es necesariamente la ruta más eficiente, ni siquiera una ruta viable.

Para dar respuesta a estas problemáticas, el software de optimización de rutas utiliza modelos matemáticos más avanzados que el TSP clásico.

En concreto, se aproximan a los problemas de enrutamiento de vehículos, denominados Vehicle Routing Problems (VRP), y a sus variantes que incorporan ventanas horarias o restricciones de planificación.

Estos modelos permiten buscar no solo un orden de paso, sino también una distribución coherente de las visitas en el tiempo.

¿Qué restricciones debe tener en cuenta un optimizador de rutas comerciales?

Para diseñar una ruta adaptada a las realidades sobre el terreno, se pueden integrar múltiples parámetros.

La dirección de salida

Permite definir el punto desde el cual el comercial inicia sus desplazamientos: domicilio, oficina u otra dirección de referencia.

Los horarios de trabajo

Delimitan la franja horaria durante la cual deben organizarse los desplazamientos y las visitas. Un comercial que trabaja de 8:00 a 17:00 no dispone del mismo tiempo que uno que termina su jornada a las 19:00.

El número máximo de visitas por día

Permite limitar la cantidad de citas programadas diariamente, sobre todo para evitar sobrecargar las jornadas.

La duración de las visitas

No todas las visitas comerciales requieren el mismo tiempo. Una reunión de prospección de quince minutos no se organiza igual que una visita de cuarenta y cinco minutos en la gran distribución.

Los horarios de apertura de los establecimientos

Una farmacia, un restaurante o una tienda no se pueden visitar en cualquier momento. La optimización debe tener en cuenta sus horarios de apertura siempre que estén indicados.

La pausa para el almuerzo

Puede incorporarse a la planificación para reservar un tiempo de descanso a lo largo del día.

Los días de actividad y los días excluidos

Un comercial puede trabajar a lo largo de varios días y excluir al mismo tiempo determinadas jornadas dedicadas a otras actividades, reuniones o vacaciones.

El periodo de planificación

La optimización puede abarcar un día, una semana o un periodo más largo, según las necesidades de cobertura de la cartera.

Las citas ya programadas

Se trata de una restricción especialmente importante. Cuando un comercial tiene citas confirmadas, la optimización debe ser capaz de organizar las demás visitas en torno a estos compromisos.

El conjunto de estos parámetros transforma un simple problema de distancias en un auténtico problema de planificación comercial.

Descubra cómo ayudar a sus comerciales a planificar sus rutas comerciales.

¿Por qué una ruta optimizada puede parecer a veces ilógica?

Veamos un ejemplo concreto.

Un comercial visita una tienda en Toulouse. A tan solo 200 metros se encuentra otro punto de venta que forma parte de su cartera.

Sin embargo, el optimizador no programa esta segunda tienda para el mismo día, sino que la asigna al día siguiente.

A primera vista, esta elección parece contraria a la intuición. ¿Por qué volver a pasar por el mismo barrio cuando ambos establecimientos están tan cerca?

Diversas restricciones pueden explicar esta situación.

Es posible que la tienda esté cerrada en el momento del paso. La duración estimada de la visita podría impedir que el comercial llegue a tiempo a su siguiente cita. También podría haberse alcanzado el número máximo de visitas permitidas.

El optimizador busca una solución que respete las restricciones definidas. Por lo tanto, la proximidad geográfica no siempre es suficiente para justificar la inclusión de un establecimiento en una ruta.

Este ejemplo ilustra una diferencia fundamental entre el TSP y su aplicación comercial.

Una ruta optimizada no se corresponde necesariamente con el trayecto más corto entre los clientes, sino con una organización que busca el mejor equilibrio entre desplazamientos, tiempo disponible y restricciones de visita.

¿Cómo pasar del TSP a una ruta comercial optimizada?

El problema del viajante de comercio ayuda a comprender la dificultad matemática que implica encontrar la mejor ruta. No obstante, para organizar los desplazamientos de un comercial itinerante, un software debe ir más allá.

Debe incorporar los datos de los clientes, los horarios laborales, la duración de las visitas y las citas existentes, para luego buscar una organización coherente a partir de estas restricciones.

Esta es la función de un motor de optimización de rutas: transformar una selección de clientes y unos parámetros de planificación en una propuesta de ruta aplicable.

Con Sidely, este motor está directamente integrado en el CRM de campo. Los comerciales pueden iniciar una optimización desde su mapa o calendario, teniendo en cuenta las citas ya programadas.

Para conocer los diferentes pasos del cálculo, los métodos utilizados y la forma en que Sidely organiza las visitas, descubra nuestro artículo: ¿Cómo funciona un motor de optimización de rutas?

TSP y optimización de rutas: puntos clave

El problema del viajante de comercio es uno de los más conocidos dentro de la optimización matemática. Su finalidad es identificar el circuito más corto que permita visitar un conjunto de destinos antes de regresar al punto de partida.

Sin embargo, en el día a día de los comerciales itinerantes, la distancia solo representa una parte del problema.

Los horarios de apertura, la duración de las visitas, las citas confirmadas, las jornadas de trabajo y las prioridades comerciales también deben tenerse en cuenta.

Por este motivo, los optimizadores de rutas profesionales recurren a modelos de planificación más complejos que el TSP clásico.

Su objetivo no consiste solo en que los comerciales recorran menos kilómetros, sino en ayudarles a organizar jornadas realistas, coherentes y comercialmente útiles.

Al integrar esta lógica directamente en el CRM, Sidely permite a los equipos sobre el terreno pasar con mayor facilidad de la selección de los clientes que deben visitar a la organización concreta de sus desplazamientos.