Diferencias
Muestra las diferencias entre dos versiones de la página.
Próxima revisión | Revisión previa | ||
problema_tsp [2010/10/21 08:51] – creado admin | problema_tsp [2023/03/13 14:40] (actual) – editor externo 127.0.0.1 | ||
---|---|---|---|
Línea 10: | Línea 10: | ||
Además del reto computacional que representa este tipo de problemas, también es de los más interesantes de la teoría de grafos y de la investigación operativa por su aplicación práctica en la realidad. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de picking, de rutas, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc. | Además del reto computacional que representa este tipo de problemas, también es de los más interesantes de la teoría de grafos y de la investigación operativa por su aplicación práctica en la realidad. Su aplicación es visible y de gran importancia para la resolución de problemas reales en la Dirección de Operaciones y Logística. Por ejemplo: problemas de picking, de rutas, sistemas de navegación GPS, planificación de movimientos de robots, vehículos autoguiados (AGV), etc. | ||
- | Este problema es fácil de enunciar, aunque un poco más complicado de modelar y resolver. Se trata de un vendedor o viajante de comercio que debe visitar | + | Este problema es fácil de enunciar, aunque un poco más complicado de modelar y resolver. Se trata de un vendedor o viajante de comercio que debe visitar |
- | Sea // | + | Sea $x_{ij}$ |
- | < | + | $$ |
y está sujeto a las restricciones: | y está sujeto a las restricciones: | ||
- | < | + | $$ |
- | < | + | $$ |
- | < | + | $$ |
y con las condiciones de Miller-Tucker adicionales: | y con las condiciones de Miller-Tucker adicionales: | ||
- | < | + | $$ |
Analizando las restricciones, | Analizando las restricciones, | ||
- | Sin embargo, con estas restricciones y la condición binaria de las variables | + | Sin embargo, con estas restricciones y la condición binaria de las variables |
- | Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en la ilustración superior del modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera | + | Es por ello, por lo que es necesario añadir más restricciones que eviten la formación de subrutas. Una de las posibles formas de hacer esto (ya que existen varias), es la propuesta por Miller-Tucker y que se muestra en el modelo. Las variables de decisión introducidas por las condiciones de Miller-Tucker son reales y no tienen límites ni superior ni inferior. La propuesta de Tucker genera |
En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta. | En el caso de Grafos, este problema se aborda a través del modelo anteriormente expuesto y su resolución mediante Programación Lineal Entera Mixta. | ||
Línea 43: | Línea 43: | ||
Más información en: | Más información en: | ||
- | * Ítem de lista desordenada | ||
- | * s | ||
* [[http:// | * [[http:// | ||
* [[http:// | * [[http:// | ||
* Miller, C. and A. Tucker, R. Zemlin, Integer programming formulations and traveling salesman problems, //J. of the ACM//, 7 (1960) 326-329. | * Miller, C. and A. Tucker, R. Zemlin, Integer programming formulations and traveling salesman problems, //J. of the ACM//, 7 (1960) 326-329. | ||
- | * | + | * N. Christofides (1985). Vehicle Routing, in The Traveling Salesman Problem, Lawler, Lenstra, Rinooy Kan and Shmoys, eds., John Wiley, 431-448. |
- | + | * J.V. Potvin (1996) Genetic Algorithms for the Traveling Salesman Problem, //Annals of Operations Research// 63, 339-370. | |
---- | ---- | ||
~~NOTOC~~ | ~~NOTOC~~ | ||
- | |||
- | |||
- | |||
- | |||
- | |||