¿Cuáles son las aplicaciones prácticas del problema del vendedor ambulante?

Hace unos diez años, diseñé un algoritmo para ordenar contenido publicitario en vallas publicitarias digitales. Puede que no parezca un problema estándar de vendedor ambulante, pero tiene muchas similitudes y la referencia se hizo varias veces durante el recorrido.

Se determinó que cada pantalla tenía una longitud de bucle basada en el tiempo de permanencia típico. Si era probable que las personas se posicionaran a la vista de la pantalla durante un promedio de cinco minutos, los operadores de pantalla querían vender cinco minutos de espacio y recorrerlo continuamente durante el día.

El problema es que cierto contenido no querría estar adyacente a otro contenido; BMW podría no querer que su anuncio se reproduzca inmediatamente después de un anuncio de Audi, por ejemplo. Por lo tanto, el modelo de datos de soporte tenía grupos de contenido con atractores y repulsores definidos para crear relaciones positivas o negativas entre diferentes tipos de contenido. De esta manera, los anuncios de dos automóviles podrían tener relaciones negativas entre sí y con los anuncios de cerveza, pero los anuncios de salsas y condimentos podrían tener una relación positiva con los anuncios de alimentos congelados. Luego, el algoritmo encontraría el diseño de bucle óptimo que maximizaría los puntajes positivos y minimizaría los negativos colocando anuncios de salsa de tomate al lado de los anuncios de hamburguesas y manteniendo a Porsche alejado de Heineken. Es un desafío más complejo de lo que parece al principio.

Programación de la tripulación de la aerolínea

Los vuelos de las aerolíneas consisten en múltiples piernas. Un tramo de vuelo es una unidad de vuelo que consta de un despegue y un aterrizaje. Cada tramo de vuelo es único con su origen, destino, hora de llegada y salida.
Luego tienen tripulación estacionada en diferentes ciudades. Deben asignar a la tripulación a los vuelos de modo que al final de su deber (idealmente), cada miembro de la tripulación esté de regreso en su aeropuerto de origen.
Por lo tanto, la asignación de la tripulación a los vuelos se puede asignar completamente al problema del vendedor que viaja.

Sé esto porque mi proyecto de último año en la universidad implicó encontrar algoritmos que pudieran resolver mejor el problema.

El problema del vendedor ambulante se puede aplicar para encontrar la ruta óptima para perforar múltiples agujeros.
Tenga en cuenta que debe perforar múltiples orificios en una hoja determinada y que la máquina de perforación CNC correspondiente también se identifica, luego solo tiene que hacer un programa que guíe la herramienta de un lugar a otro que puede encontrar a través del problema del vendedor ambulante.

El problema del vendedor ambulante es NP-completo, y por lo tanto, cualquier otra instancia de un problema en NP puede reducirse eficientemente (en el sentido del tiempo polinómico) a una instancia equivalente del problema del vendedor ambulante. Por lo tanto, las aplicaciones prácticas del problema del vendedor ambulante, en cierto sentido, equivalen a las aplicaciones prácticas de los problemas de NP en general, que son innumerables.

Escanear costuras. Las estructuras utilizadas para probar los circuitos digitales recién fabricados implican unir los elementos de memoria en largas “cadenas de exploración”. Estos permiten que todo el sistema se establezca en cualquier estado conocido con relativamente poca sobrecarga física. Hay poca o ninguna razón lógica para colocar un registro en una ubicación particular de la cadena, principalmente queremos limitar la longitud del cable utilizado para hacer las cadenas. Entonces, el problema del vendedor viajero es

El ferrocarril puede analizar la mejor ruta disponible para un tren de larga distancia con muchas paradas. Pueden encontrar la mejor ruta que tenga más viajeros y tome un tiempo y distancia mínimos entre el primer y el último destino.