Imagine un ajetreado centro de distribución en el que las máquinas y los trabajadores se mueven de forma óptima entre cada lugar de trabajo y almacenamiento. Hay que planificar bien las rutas para cumplir plazos estrictos y mantener bajos los costes y otros factores. Este reto es el núcleo de la históricamente llamada problema del viajante de comercio (TSP). No sólo en las aplicaciones logísticas. Este artículo explora cómo el problema del viajante de comercio puede utilizarse en la vida real y en la fabricación. Examina cómo se puede mejorar la planificación de rutas en toda la industria.
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.
En la década de 1930 se empezó a definir más claramente la TSP. Académicos de Viena y Harvard trabajaron juntos en ello. Empezaron a ver cómo podía resolver problemas reales, como mejorar las rutas de los autobuses escolares. Esto hizo que más gente se interesara por resolver la 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, to 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
|
You have read 50% of the article. The rest is for our community. Already a member? Conectarse
(and also to protect our original content from scraping bots)
Comunidad.mundial.de.la.innovación
Iniciar sesión o registrarse (100% gratis)
Vea el resto de este artículo y todos los contenidos y herramientas exclusivos para miembros.
Sólo verdaderos ingenieros, fabricantes, diseñadores, profesionales del marketing.
Ni bot, ni hater, ni spammer.
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?
TSP is used in many areas, like making delivery routes more efficient and managing supply chains. It’s also helpful in healthcare for scheduling visits and in robótica for guiding movements or in manufacturing electronics positioning or testing small components and copper routes.
¿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.
Publicaciones relacionadas
La metodología SCAMPI para la evaluación CMMI en detalle
Relación riesgo-beneficio en la evaluación de riesgos
Los mejores chistes de ingenieros (y diseñadores, creadores, marketeros…)
Los 5 niveles de integración del modelo de madurez de capacidad (CMMI)
Internet industrial de las cosas (IIoT)
Explorador de conceptos™ de Innovation.world