El problema del camino más rápido con restricciones

Resumen

El problema del camino más rápido ha sido introducido en la literatura para abordar la obtención de un camino que permita transmitir una determinada cantidad de items que se encuentran inicialmente en un nodo origen hasta un nodo destino en el menor tiempo posible, utilizando las conexiones existentes. La característica fundamental del problema es que los ítems precisan un tiempo para atravesar las conexiones que depende de la tasa a la que los items son transmitidos y esta tasa está limitada en cada una de las conexiones. En consecuencia, la función objetivo de este problema depende de la longitud total de las conexiones utilizadas en el camino, de la tasa a la que los items son transmitidos y de la cantidad de items que ha de ser enviada. El problema del camino más rápido está teniendo una considerable atención por parte de los investigadores en las últimas dos décadas dada su aplicación directa a problemas de tráfico de datos en el contexto de las telecomunicaciones, y la creciente importancia que estas tienen en el ámbito personal y empresarial. El objetivo de esta memoria es estudiar el problema del camino más rápido cuando se consideran distintas restricciones añadidas al problema que modelan aspectos que son de interés en los procesos de transmisión. El capítulo 1 introduce brevemente algunos conceptos básicos sobre problemas de optimización de flujo en redes y se enuncian problemas clásicos de camino óptimo que son utilizados a lo largo de la memoria. En el capítulo 2 se formula el problema del camino más rápido y se propone un nuevo método de resolución que precisa el cálculo de un único camino más corto en una red apropiadamente definida. El capítulo 3 aborda la estrategia óptima para la transmisión cuando la totalidad de items que son transmitidos se debe programar en lotes de tamaño variable aunque dentro de unos límites preestablecidos. En el capítulo 4 se considera el problema del camino más rápido en el contexto de conexiones sujetas a fallos. El problema estudiado añade una restricción que garantiza la transmisión segura, en el sentido de que puede efectuarse con éxito con probabilidad no menor que un umbral establecido. Se analizan las propiedades de la restricción impuesta y estas propiedades se utilizan para diseñar métodos de resolución que permiten evitar el cálculo de caminos innecesarios. Los capítulos 5 y 6 consideran el problema del camino más rápido en el contexto de redes con energía limitada. Estas redes modelan situaciones en las que la energía es un recurso limitado y la acción de transmitir conlleva un consumo de energía durante el tiempo que los transmisores situados en los nodos están activos. En este contexto el tiempo empleado en la transmisión influye en el consumo de energía en los nodos emisores/receptores utilizados para establecer las conexiones. En el capítulo 5 se estudia el problema de obtener el camino más rápido viable, es decir, capaz de realizar la transmisión. Se estudia, también, una variante bi-objetivo en la que los objetivos son minimizar tanto la energía total consumida como el tiempo empleado para la transmisión de los items. En el capítulo 6 se focaliza el problema en la energía residual en los transmisores tras concluir la transmisión de los items. Se estudian los problemas de maximizar la energía residual y el problema bi-objetivo de minimizar el tiempo de transmisión y maximizar la energía residual. Para todos los modelos de ambos capítulos se desarrollan procedimientos de resolución muy eficientes.