El problema del vendedor ambulante es bien conocido por su variedad de usos en diferentes problemas de la vida real. Aquí tengo un resumen de algunas de sus aplicaciones que están disponibles en la literatura. {Esto es de mi trabajo de tesis. Capítulo 8: Aplicaciones de TSP. Si necesita más ayuda sobre TSP, estaré disponible aquí ( https://www.facebook.com/ghostwr …).}
8.1 Perforación de placas de circuito impreso [75]
Una aplicación directa del TSP está en el problema de perforación de las placas de circuito impreso (PCB). Para conectar un conductor en una capa con un conductor en otra capa, o para colocar los pines de los circuitos integrados, los agujeros deben perforarse a través de la placa. Los agujeros pueden ser de diferentes tamaños. Para perforar dos agujeros de diferentes diámetros consecutivamente, la cabeza de la máquina tiene que moverse a una caja de herramientas y cambiar el equipo de perforación. Esto lleva bastante tiempo. Por lo tanto, está claro que uno tiene que elegir un diámetro, perforar todos los agujeros del mismo diámetro, cambiar el taladro, perforar los agujeros del siguiente diámetro, etc. Por lo tanto, este problema de perforación puede verse como una serie de TSP, uno para cada diámetro de agujero, donde las ‘ciudades’ son la posición inicial y el conjunto de todos los agujeros que se pueden perforar con el mismo taladro. La ‘distancia’ entre dos ciudades viene dada por el tiempo que lleva mover el cabezal de perforación de una posición a otra. El objetivo es minimizar el tiempo de viaje del cabezal de la máquina.
8.2 Revisión de motores de turbina de gas [76,77]
Plante informó esta aplicación en 1987. Ocurre cuando los motores de turbina de gas de los aviones tienen que ser revisados. Para garantizar un flujo uniforme de gas a través de las turbinas, hay conjuntos de paletas guía de boquilla ubicados en cada etapa de la turbina. Dicho conjunto consiste básicamente en una serie de paletas de guía de boquilla fijadas alrededor de su circunferencia. Todos estos álabes tienen características individuales y la colocación correcta de los álabes puede generar beneficios sustanciales (reducción de la vibración, aumento de la uniformidad del flujo, reducción del consumo de combustible). El problema de colocar las paletas de la mejor manera posible se puede modelar como un TSP con una función objetivo especial.
8.3 Cristalografía de rayos X [78]
El análisis de la estructura de los cristales es una aplicación importante del TSP. Aquí se utiliza un difractómetro de rayos X para obtener información sobre la estructura del material cristalino. Con este fin, un detector mide la intensidad de los reflejos de rayos X del cristal desde varias posiciones. Mientras que la medición en sí misma se puede lograr bastante rápido, hay una sobrecarga considerable en el tiempo de posicionamiento ya que se deben realizar hasta cientos de miles de posiciones para algunos experimentos. En los dos ejemplos a los que nos referimos, el posicionamiento implica mover cuatro motores. El tiempo necesario para moverse de una posición a otra se puede calcular con mucha precisión. El resultado del experimento no depende de la secuencia en la que se toman las mediciones en las distintas posiciones. Sin embargo, el tiempo total necesario para el experimento depende de la secuencia. Por lo tanto, el problema consiste en encontrar una secuencia que minimice el tiempo total de posicionamiento. Esto lleva a un problema de vendedor ambulante.
8.4 Cableado de la computadora [79]
Lenstra y Rinnooy Kan informaron un caso especial de conexión de componentes en una placa de computadora en su papel. Los módulos se encuentran en una placa de computadora y se debe conectar un subconjunto dado de pines. A diferencia del caso habitual en el que se desea una conexión de árbol Steiner, aquí el requisito es que no se conecten más de dos cables a cada pin. Por lo tanto, tenemos el problema de encontrar un camino hamiltoniano más corto con puntos de inicio y finalización no especificados. Una situación similar ocurre para el llamado cableado del bus de prueba. Para probar la placa fabricada, uno debe realizar una conexión que ingrese a la placa en algún punto específico, atraviese todos los módulos y termine en algún punto específico. Para cada módulo también tenemos un punto específico de entrada y salida para este cableado de prueba. Este problema también equivale a resolver un problema de ruta hamiltoniana con la diferencia de que las distancias no son simétricas y que se especifican los puntos de inicio y finalización.
8.5 El problema de preparación de pedidos en almacenes [80,81]
Este problema está asociado con el manejo de materiales en un almacén. Suponga que en un almacén llega un pedido para un determinado subconjunto de los artículos almacenados en el almacén. Algunos vehículos deben recoger todos los artículos de este pedido para enviarlos al cliente. La relación con el TSP se ve de inmediato. Las ubicaciones de almacenamiento de los elementos corresponden a los nodos del gráfico. La distancia entre dos nodos viene dada por el tiempo necesario para mover el vehículo de un lugar a otro. El problema de encontrar una ruta más corta para el vehículo con un tiempo mínimo de recogida ahora se puede resolver como un TSP. En casos especiales, este problema se puede resolver fácilmente para una discusión extensa y para referencias.
8.6 Enrutamiento del vehículo [82]
Suponga que en una ciudad se deben vaciar n buzones todos los días dentro de un cierto período de tiempo, digamos 1 hora. El problema es encontrar el número mínimo de camiones para hacer esto y el menor tiempo para hacer las recolecciones usando este número de camiones. Como otro ejemplo, suponga que n clientes requieren ciertas cantidades de algunos productos y que un proveedor debe satisfacer todas las demandas con una flota de camiones. El problema es encontrar una asignación de clientes a los camiones y un cronograma de entrega para cada camión, de modo que no se exceda la capacidad de cada camión y se minimice la distancia total de viaje. Varias variaciones de estos dos problemas, donde se combinan las limitaciones de tiempo y capacidad, son comunes en muchas aplicaciones del mundo real. Este problema se puede resolver como un TSP si no hay restricciones de tiempo y capacidad y si el número de camiones es fijo. En este caso obtenemos un problema de m – vendedores. Sin embargo, uno puede aplicar métodos para que el TSP encuentre buenas soluciones viables para este problema.
8.7 Trazado de máscaras en la producción de PCB
Para la producción de cada capa de una placa de circuito impreso, así como para las capas de dispositivos semiconductores integrados, se debe producir una máscara fotográfica. En nuestro caso para placas de circuito impreso, esto se hace mediante un dispositivo de trazado mecánico. El trazador mueve una lente sobre una placa de vidrio recubierta fotosensible. El obturador puede abrirse o cerrarse para exponer partes específicas de la placa. Hay diferentes aperturas disponibles para poder generar diferentes estructuras en el tablero. Se deben considerar dos tipos de estructuras. Una línea se expone en la placa moviendo el obturador cerrado a un punto final de la línea, luego abriendo el obturador y moviéndolo al otro punto final de la línea. Entonces el obturador está cerrado. Se genera una estructura de tipo de punto moviéndose (con la apertura apropiada) a la posición de ese punto, luego abriendo el obturador solo para hacer un flash corto y luego volviéndolo a cerrar. El modelado exacto del problema de control del trazador conduce a un problema más complicado que el TSP y también más complicado que el problema del cartero rural.
8.8 Aplicaciones de mTSP [83,84,85,86]
La aplicación principal de mTSP surge en un escenario real, ya que es capaz de manejar múltiples vendedores. Estas situaciones surgen principalmente en varios problemas de enrutamiento y programación. Algunas aplicaciones reportadas en la literatura se presentan a continuación.
yo.
Problema de programación de la imprenta: una de las principales y principales aplicaciones del mTSP surge en la programación de una imprenta para una publicación periódica con ediciones múltiples. Aquí, existen cinco pares de cilindros entre los cuales se imprimen simultáneamente los rollos de papel y ambos lados de una página. Existen tres tipos de formularios, a saber, formularios de 4, 6 y 8 páginas, que se utilizan para imprimir las ediciones. El problema de programación consiste en decidir qué formulario será en qué ejecución y la duración de cada ejecución. En el vocabulario mTSP, los costos de cambio de placa son los costos entre ciudades.
ii.
Problema de enrutamiento del autobús escolar: Angel investigó el problema de programar autobuses como una variación del mTSP con algunas restricciones laterales. El objetivo de la programación es obtener un patrón de carga del autobús de manera que se minimice el número de rutas, la distancia total recorrida por todos los autobuses se mantenga al mínimo, ningún autobús se sobrecargue y el tiempo requerido para atravesar cualquier ruta no exceda un máximo política permitida
iii)
Problema de programación de la tripulación: Svestka & Huckfeldt informó en 1973. Una solicitud de depósito de depósitos entre diferentes sucursales bancarias en 1973. Aquí, los depósitos deben ser recogidos en las sucursales bancarias y devueltos a la oficina central por un equipo de mensajeros. El problema es determinar las rutas que tienen un costo mínimo total. Lenstra y Rinnooy Kan describieron dos aplicaciones similares en 1975 y Zhang en 1999.
iv.
Problema de programación de entrevistas: Gilbert & Hofstra encontró la aplicación de mTSP, que tiene variaciones de múltiples períodos, en la programación de entrevistas entre agentes de turismo y vendedores de la industria del turismo. Cada corredor corresponde a un vendedor que debe visitar un conjunto específico de puestos de proveedores, que están representados por un conjunto de ciudades T.
v.
Problema de programación del laminado en caliente: en la industria del hierro y el acero, los pedidos se programan en el laminador en caliente de tal manera que el costo total de instalación durante la producción se puede minimizar. Aquí, los pedidos se tratan como ciudades y la distancia entre dos ciudades se toma como costo de penalización por el cambio de producción entre dos pedidos. La solución del modelo producirá un cronograma completo para el laminador de banda en caliente.
vi.
Problema de planificación de la misión: El problema de planificación de la misión consiste en determinar un camino óptimo para cada hombre del ejército (o planificador) para lograr los objetivos de la misión en el menor tiempo posible. El planificador de la misión utiliza una variación del mTSP donde hay n planificadores, m objetivos que deben ser visitados por algunos planificadores y una ciudad base a la que todos los planificadores eventualmente deben regresar. La aplicación del mTSP en la planificación de la misión es reportada por Brummit & Stentz en 1996; Brummit & Stentz en 1998. Del mismo modo, los problemas de enrutamiento que surgen en la planificación de aplicaciones de vehículos aéreos no tripulados, investigados por Ryan en 1998, también pueden modelarse como mTSP.
vii.
Diseño de redes topográficas del sistema mundial de navegación por satélite: una aplicación muy reciente e interesante del mTSP, según lo investigado por Saleh & Chelouah en 2004, surge en el diseño de redes topográficas del sistema global de navegación por satélite (GNSS). Un GNSS es un sistema satelital basado en el espacio que proporciona cobertura para todas las ubicaciones en todo el mundo y es bastante crucial en aplicaciones de la vida real como la alerta temprana y la gestión de desastres, monitoreo ambiental y agrícola, etc. El objetivo de la topografía es determinar la ubicación geográfica. posiciones de puntos desconocidos sobre y sobre la tierra utilizando equipos satelitales. Estos puntos, en los que se colocan los receptores, están coordinados por una serie de sesiones de observación. Cuando hay múltiples receptores o múltiples períodos de trabajo, el problema de encontrar el mejor orden de sesiones para los receptores puede formularse como un mTSP.
Además de esas aplicaciones, existen muchos otros problemas en los que podemos aplicar TSP, específicamente mTSP. Como la programación de la tripulación del Banco, la programación de la tripulación técnica, la programación del equipo de fotógrafos, la programación de la entrevista, la programación de la carga de trabajo, la programación del servicio de seguridad, la programación de la grúa, la recogida y entrega de camiones locales, la planificación de robots móviles autónomos, la planificación de vehículos aéreos no tripulados, etc.
Únase a mi misión de construir un recurso de video matemático Hugh en YouTube. https://www.youtube.com/channel/ …
