Imagine a busy distribution center where machines and workers move optimally between each working and storage locations. Routes need to be planned well to meet strict time limits and keep costs and other factors low. This challenge is at the heart of the historically so-called traveling salesman problem (TSP). It’s not only in the logistic applications. This piece explores how the traveling salesman problem can be used in real life and manufacturing. It looks at how one can improve their route planning in all the industry.
Aunque este problema es un clásico de las matemáticas puras y los estudios algorítmicos, también estudiado en logística con un enfoque más práctico, es casi desconocido en otras industrias y ámbitos de fabricación.
Este post se centra especialmente en un algoritmo de nuestro post "los 10 principales algoritmos y metodologías que hay que conocer en ingeniería".
Conclusiones Clave
- El problema del viajante de comercio (TSP) consiste en encontrar la ruta más optimizada entre varios puntos.
- Este problema empezó a cobrar interés en los años 1930-1940
- Ayuda a las organizaciones a aumentar la eficiencia y reducir los costes de sus operaciones, limitar los recursos y mejorar la prestación de servicios.
- El problema es ampliamente aplicable a distintos sectores e industrias, no sólo a la logística y los transportes.
- En cuanto hay más de 12-20 puntos, el problema se vuelve demasiado complejo para calcular una solución perfecta
- Se han inventado varios algoritmos para encontrar buenas aproximaciones, por lo tanto no la perfecta
¿Qué es el problema del viajante de comercio?
El problema del viajante de comercio: encontrar la manera más eficaz para que un vendedor visite varias ciudades y vuelva a la salida. Debe visitar cada ciudad una sola vez, con el objetivo de acortar al máximo la distancia total.
Para entender la definición del TSP, hay que saber que el número de rutas crece a medida que se añaden más ciudades. Por ejemplo, cuatro ciudades significan que hay 24 rutas posibles. Si se añaden más ciudades, aumenta el reto, lo que conlleva demasiadas rutas potenciales a considerar.
Muchas empresas, como las de logística, telecomunicaciones y fabricación, se enfrentan a menudo a este problema. Una buena solución al problema del viajante de comercio podría ahorrar dinero y aumentar la eficiencia. Muestra cómo la investigación teórica relacionada con las matemáticas ayuda a resolver problemas de la vida real.
¿Por qué es un problema?
Si hay n ciudades, hay (n-1)!/2 recorridos únicos (el /2 viene si el recorrido es un ciclo y las direcciones no importan).
Además, ligeros cambios en los datos de entrada (por ejemplo, distancias o nuevas ciudades) alteran por completo la ruta óptima, lo que hace que el problema sea muy delicado y complejo de resolver. | Ciudades visitadas | Posibles rutas / combinaciones |
| 3 | 6 | |
| 4 | 24 | |
| 5 | 120 | |
| 6 | 720 | |
| 7 | 5040 | |
| … | … | |
| 20 | 6 × 1016 (casi 2 milenios si cada cálculo de ruta requiriera un microsegundo) | |
| 25 | más que la edad de nuestro univers si cada cálculo de ruta requiriera un microsegundo. |
Historia del problema del viajante de comercio
El problema del viajante de comercio surgió a principios del siglo XX, gracias a algunos matemáticos inteligentes. William Rowan Hamilton y Karl Menger fueron grandes nombres que nos ayudaron a entender cómo recorrer caminos complejos. Se centraron en facilitar la búsqueda de la mejor ruta.
By the 1930s, people began to define the TSP more clearly. Scholars from Vienna and Harvard worked together on this. They started to see how it could solve real problems, like making school bus routes better. This made more people interested in solving the TSP.
El TSP llegó a ser muy útil para las empresas, sobre todo las de transporte marítimo y terrestre. En las décadas de 1950 y 1960, la RAND Corporation tomó cartas en el asunto. Idearon formas inteligentes de abordar el TSP que se convirtieron en una pieza clave para que la logística funcionara mejor.
¿Por qué es un problema NP-Hard?
El Problema del Vendedor Viajero es un rompecabezas difícil en informática. Es famoso por ser un problema NP-difícil porque es realmente difícil de resolver, ya que crece exponencialmente más rápido de lo que cualquier ordenador puede manejar si hay muchas ciudades.
Qué es un problema "NP-duro": en informática y teoría de la complejidad computacional, "NP" significa Non-deterministic Polynomial time (tiempo polinomial no determinista). Un problema NP-duro es al menos tan difícil como los problemas más difíciles de NP, lo que significa que todos los problemas de NP pueden reducirse a él en tiempo polinómico. A diferencia de los problemas NP-completos, que puede verificarse en tiempo polinómico, elo se conoce ningún algoritmo que resuelva problemas NP difíciles en tiempo polinómico.
Por eso, los expertos utilizan atajos especiales y conjeturas inteligentes. Estos trucos les ayudan a encontrar caminos bastante buenos sin necesitar cantidades imposibles de potencia de cálculo para obtener una solución decente que funcione lo suficientemente bien en la vida real. Vea en el capítulo siguiente algunos de estos enfoques que les ayudan a lidiar con el enorme número de caminos posibles.
Aplicaciones industriales
El problema del viajante de comercio ayuda diferentes industrias mejorar las rutas y los procesos. Muchas áreas como la logística, el transporte y la fabricación utilizan TSP para facilitar su trabajo. Las soluciones aproximadas TSP y sus variantes se utilizan en:
TransporteLos usos más similares al problema del vendedor original:
| Enrutamiento
 Las empresas pueden configurar sus nodos de red de la mejor manera para reducir la pérdida de señal y aumentar el rendimiento en el diseño de la red. |
Fabricación y maquinaria
| Logística interna
Ayuda a planificar inteligentemente los recorridos de los equipos y las líneas. Esto significa que las máquinas y las líneas de montaje están mejor dispuestas, lo que ahorra tiempo, agiliza las cosas y ayuda a ergonomía.
|
Ciencia e investigación
|  |
Métodos para aproximar rápidamente la mejor respuesta
Aunque está fuera del alcance de este post enumerar y proporcionar todos los detalles de casi 100 años de investigación científica sobre este tema, a continuación se presentan algunos métodos utilizados actualmente.
Estos métodos no siempre encuentran la mejor solución, pero se acercan bastante sin llevar mucho tiempo.
- Heurística del vecino más próximo (NN)
- Proceso: empezar en una ciudad al azar; visitar repetidamente la ciudad no visitada más cercana hasta visitar todas.
- Pros: rápido, sencillo, pero no siempre cerca de lo óptimo.
- Algoritmo de Christofides
- Proceso: construye un recorrido utilizando árboles de expansión mínima y emparejamiento perfecto (garantiza una solución dentro de 1,5 veces el óptimo para TSP métrico).
- Pros: la garantía de rendimiento más conocida para el TSP métrico.
- Algoritmo Greedy
- Proceso: en cada paso, elige la arista más corta disponible que no forme un ciclo (excepto la arista final).
- Pros: rápido, pero no suele ser óptimo.
- Búsqueda local 2-opt y k-opt
- Proceso: sustituir iterativamente k aristas del recorrido por aristas diferentes para reducir la longitud total (2-opt, 3-opt son comunes).
- Pros: mejora significativamente la heurística inicial, muy utilizada para el postprocesamiento.
- Algoritmos genéticos (AG)
- Proceso: utilizar la búsqueda poblacional con cruce y mutación para evolucionar hacia mejores soluciones a lo largo de las generaciones.
- Pros: flexible, puede escapar de mínimos locales.
- Recocido simulado (SA)
- Proceso: acepta probabilísticamente soluciones peores de vez en cuando para evitar los óptimos locales, reduciendo gradualmente la "temperatura".
- Pros: eficaz para espacios de búsqueda complejos.
Other notable methods: ant colony optimization, Tabu Search, Lin-Kernighan heuristic.
Conclusión sobre el TSP
El problema del viajante de comercio (TSP) es crucial para muchas industrias, aunque aún desconocido para algunas. Demuestra lo importante que es para mejorar la eficiencia y ahorrar costes. Muchas organizaciones ya utilizan soluciones TSP para mejorar sus rutas y planes de trabajo.
Encontrar nuevas formas de resolver este viejo problema demuestra su valor duradero. La resolución de TSP sigue siendo un reto con posibles nuevas opciones gracias a los avances en tecnología, como los algoritmos mejorados por la inteligencia artificial y el aprendizaje automático, que abrirán nuevas vías para resolver este difícil desafío. Este progreso abrirá literalmente nuevas rutas, mejorará las estrategias de operaciones y ayudará a las organizaciones a agilizar sus procesos de forma más eficiente.
Related Readings
- Algoritmos de optimización combinatoria: métodos exactos y heurísticos como algoritmos genéticos, recocido simulado
- Teoría de grafos y análisis de redes: Hamiltoniano ciclos, algoritmos del camino más corto
- Investigación operativa: programación lineal, programación entera
- Teoría de la Complejidad Computacional: Caracterización de la dureza NP
- Metaheurística e inteligencia de enjambre: optimización por colonia de hormigas, optimización por enjambre de partículas en la resolución de TSP
Preguntas frecuentes
¿Qué es el problema del viajante de comercio?
El problema del viajante de comercio (TSP) es un rompecabezas importante. Se trata de encontrar el camino más corto que visite cada lugar sólo una vez y vuelva al principio. Esto es clave para las empresas que necesitan planificar rutas de forma eficiente. El mayor reto es el enorme número de rutas posibles, que crece con cada nueva ubicación. Además, los problemas del mundo real, como el tráfico y los plazos, dificultan aún más la planificación.
¿Por qué se considera que el TSP es un problema NP-duro?
El TSP es difícil porque el número de rutas potenciales aumenta exponencialmente con cada ciudad adicional. Esto hace que sea muy difícil encontrar rápidamente la mejor ruta, sobre todo a medida que se añaden más de 20 localidades.
¿Cuáles son las aplicaciones más comunes del TSP?
El TSP se utiliza en muchos ámbitos, como hacer más eficientes las rutas de reparto y gestionar las cadenas de suministro. También es útil en sanidad para programar visitas y en robótica para guiar movimientos o en electrónica de fabricación para posicionar o probar pequeños componentes y rutas de cobre.
¿Cómo se relacionan la teoría de grafos y los algoritmos heurísticos con el TSP?
La teoría de grafos es la base matemática del TSP. Utiliza puntos (vértices) para representar ciudades y líneas (aristas) para los caminos entre ellas. Esto ayuda a desarrollar métodos para resolver problemas TSP de forma eficaz. Los algoritmos heurísticos son atajos inteligentes para resolver el TSP. Ayudan a encontrar rutas suficientemente buenas con rapidez, aunque no sean perfectas. Métodos como los algoritmos de Vecino más cercano y Greedy son ejemplos comunes. Técnicas como el templado simulado y los algoritmos genéticos también son especialmente útiles para problemas grandes.
¿Cómo influye la TSP en la eficacia de la cadena de suministro?
La TSP aumenta la eficacia de la cadena de suministro al perfeccionar las rutas de transporte. Así se reducen los costes, se aprovechan mejor los recursos y se mejora la coordinación entre todos los implicados. En sanidad, la TSP optimiza la prestación de servicios de atención domiciliaria y de urgencias. Garantiza que los suministros médicos se entreguen puntualmente, mejorando la atención y la satisfacción general del paciente.
Glosario de términos utilizados
Deoxyribonucleic Acid (DNA): Molécula compuesta por dos hebras que forman una doble hélice, compuesta por nucleótidos que codifican información genética mediante secuencias de cuatro bases: adenina, timina, citosina y guanina. Sirve como material hereditario en la mayoría de los organismos vivos.
Printed Circuit Board (PCB): Una placa plana de material aislante que soporta y conecta componentes electrónicos mediante vías conductoras, generalmente grabadas a partir de láminas de cobre. Sirve como base para el ensamblaje de circuitos y facilita las conexiones eléctricas entre componentes.
Unmanned Aerial Vehicle (UAV): Aeronave autónoma o pilotada a distancia, diseñada para diversas aplicaciones, como vigilancia, reconocimiento y entrega, sin piloto humano a bordo. Opera mediante estaciones de control terrestre o sistemas de automatización integrados, y suele estar equipada con sensores y cámaras para la recopilación de datos.
Very-large-scale Integration (VLSI): una tecnología para crear circuitos integrados combinando miles a millones de transistores en un solo chip, lo que permite miniaturizar sistemas electrónicos complejos y mejorar el rendimiento, la eficiencia energética y la funcionalidad en dispositivos como computadoras y teléfonos inteligentes.
