Aplicaciones

En esta sección del trabajo vamos a ver algunas de las aplicaciones más interesantes que tiene el problema del viajante de comercio. Más allá del interés empresarial que pueda causarle a cualquier agente comercial dedicado a la venta de productos, lo cierto es que este problema se extiende a otras muchas ramas:

Problema de Scheduling

Este problema es realmente complejo de resolver. Se formula de la siguiente forma: hay T tareas que realizar y m procesadores. Se busca una planificación en m procesadores para T minimizando el tiempo. Si ahondamos un poco más en este tipo de problemas, observamos que existen una gran cantidad de variantes asociadas a si hay orden parcial en T (es decir, algunas actividades son preferentes a otras)...

En este caso las actividades pueden verse como las ciudades y los tiempos como las distancias. El objetivo es determinar una secuencia (schedule) de tal forma que se lleven a cabo en una cantidad mínima de tiempo. Para resolverlo se usa la versión asimétrica del TSP, es decir, debemos tener en cuenta que el costo de pasar de la tarea A a la B, puede ser diferente del costo de recorrer el camino inverso. Como aplicación más cercana, los problemas de scheduling los encontramos en la televisión, donde es necesario planificar un secuenciamiento óptimo de los comerciales durante un corte publicitario.

Problema de placa de circuitos impresos PCB

Ésta es sin duda una de las utilidades más ingeniosas que puede plantear el problema del viajante de comercio: la creación de placas de circuitos. Este problema se enfoca en dos suproblemas: el orden óptimo de taladrar las placas y los caminos óptimos que comunican los chips. En los problemas de perforado hemos de tomar las ciudades como las posiciones a perforar y las distancias entre ellas como el tiempo que necesita la máquina en trasladarse de una otra. El punto inicial y final será un punto adicional donde permanece la perforadora mientras descansa. Claramente si estas máquinas no son correctamente programadas el tiempo que tarde en recorrer un orificio u otro puede ser significativo con lo que la producción de placas bajaría en un período de tiempo.

En el problema de conexión de chips la idea es minimizar la cantidad de cable necesaria para unir todos los puntos de una placa sin que haya interferencias. Como los chips son de pequeño tamaño no se pueden poner más de dos cables en un único pin. Tomando las ciudades como los pins y la cantidad de cable necesaria para unirlos como la distancia, el problema es equivalente al de viajante de comercio.

Aplicaciones en internet

Supongamos que el viajante de comercio es un bit de datos, y que las ciudades son servidores de Red distribuidos por todo el planeta. Esta variante del problema del viajante de comercio es algo inherente al uso óptimo de una plataforma masiva de distribución como es Internet. No olvidemos que en cada ruta puede haber miles de ciudades en este caso. Es curiosos como para resolver esta variante algunos investigadores se han inspirado en el comportamiento de las hormigas.

Problema de la red de basuras

El problema de la recolección de residuos puede dividirse en 3 grandes tipos: domiciliaria, comercial e industrial. La recolección domiciliaria consiste en atender fundamentalmente casas particulares. La frecuencia puede variar aunque normalmente las rutas suelen repetirse una vez todos los días. La recolección comercial o industrial se encarga de las tiendas, restaurantes o edificios de cocinas. Los objetivos en este tipo de problemas pueden ser diversos: minimizar el número de camiones, la distancia recorrida... Si queremos minimizar la distancia usaremos el problema del viajante de comercio identificando los contenedores o puntos de recogida como las ciudades a visitar. Estos mismos problemas se puede generalizar a los llamados problemas de vehículos o de reparto. Se usan en las empresas de transportes, en correos...

Última modificación: sábado, 4 de julio de 2015, 10:42