Optimización multiobjetivo de rutas alternativasfundamentos heurísticos y nuevas aplicaciones

Resumen

A lo largo de este texto se presentarán una serie de métodos tales que permitan alcanzar ciertos objetivos cualitativos, de enrutado alternativo, en forma económica, esto es eficiente en costes, al tiempo que se atiene a una serie de restricciones impuestas a priori. Se observarán diferentes formas del problema clásico de enrutar (esto es: “calcular las rutas para”) mercancías valiosas o peligrosas, y cómo hacerlo, con mayor eficiencia y calidad, mediante el cómputo de rutas alternativas, que optimicen varias metas u objetivos simultáneamente. Estos objetivos pueden elegirse arbitrariamente, y suelen tener relación con criterios económicos, tales como distancia, tiempo, beneficio, o riesgo, si bien se utilizan otros más variados dentro de una amplia casuística. Naturalmente, la dificultad estriba en que, a medida que se añaden objetivos, restricciones, tramos, y etapas que la ruta pueda atravesar, la dificultad del problema crece, debido al incremento combinatorio asociado. Con el fin de realizar estos cálculos, se detallarán varios métodos que facilitan la consecución de objetivos prácticos, como en la prevención y contención de accidentes, emboscadas, y colisiones, así como en el cálculo y gestión de diferentes medidas del riesgo. Se verá, asimismo, que algunos de estos métodos, y otros que de ellos se derivan, pueden aplicarse con éxito a la reducción de la congestión en redes, tanto telemáticas, como de transporte (rodado, ferroviario, marítimo, aéreo y en otras modalidades), y en otros interesantes contextos de aplicación. Además de tratar este tipo de problemas desde una perspectiva hazmat, se suministrará una fundamentación contextual axiomática, de las técnicas más novedosas de Inteligencia Artificial dedicadas al transporte logístico, desde una perspectiva lógico-filosófica de Programación Matemática, con la optimización metaheurística multiobjetivo como campo de estudio y haciendo énfasis en la gestión de la seguridad y minimización del riesgo. Finalmente se observarán otras aplicaciones de estos algoritmos de optimización multiobjetivo en campos variados de la actividad humana, en particular para los casos de prevención de embotellamientos y bloqueos, tanto en redes multimodales de transporte combinado de mercancías y pasajeros, como en redes de telecomunicaciones digitales basadas en tecnología informática o en el transporte energético. Para la consecución de estos fines, se comienza esta disertación suministrando una perspectiva histórica del problema, y una detallada argumentación teórica filosófico-lógica de las técnicas de Investigación Operativa con que se cimentan los modelos metaheurísticos de enrutado, junto con su encaje relacional con otras áreas de la ciencia. Una vez establecidas estas bases teóricas, se provee una revisión panorámica, algorítmica y funcional, del problema de enrutado alternativo de mercancías peligrosas (hazmat: “hazardous materials”). Se hará énfasis en la optimización estocástica de varios objetivos mutuamente competitivos, y en la gestión adecuada del riesgo, a fin de contextualizar el tema tratado, y profundizar en sus orígenes e implicaciones. Seguidamente, se describen una serie de fundamentos matemáticos y modelos algorítmicos de resolución eficiente para el problema, que se enraízan en la heurística, junto con varias de sus formulaciones derivadas e implicaciones. Finalmente se trata de proporcionar algunas ideas prácticas para la aplicación de estos modelos, en contextos variados, tales como el transporte, las telecomunicaciones, la reducción de la congestión, la gestión de proyectos, o el razonamiento automático, áreas todas donde resultan de utilidad. El objeto de la tesis es la exposición de la ciencia algorítmica, en línea con el paradigma expresado por Niklaus Wirth en su vademécum “Algoritmos + Estructuras de Datos = Programas”, y con la Filosofía Neopragmática. Por lo tanto, no se centrará en exhibir y detallar fragmentos de código informático específico que hayan sido diseñados para la resolución de un problema concreto. Antes bien, se centra en el estudio del contexto de los datos, las interrelaciones conceptuales y la tecnología subyacente. Estos aspectos ingenieriles permiten tratar conjuntos de datos multipropósito, a lo largo de una extensa variedad de aplicaciones prácticas del mundo real. Son, pues, pilares fundamentales de esta tesis: La Programación Matemática, la Ingeniería de Software, la Economía Aplicada, y la Gestión de Sistemas Informáticos. Por tanto, su aplicabilidad es transversal a múltiples disciplinas, siempre que ocurra un transporte, desplazamiento, o proceso, que se pueda modelar sobre un grafo de estados discretos (“nodos”), conectados por tramos (“aristas”). Esto ocurre en diversas tareas dentro del contexto de la Investigación de Operaciones, particularmente en las de navegación, transporte, comunicación, y gestión de proyectos. En cuanto a las técnicas metaheurísticas, se entienden como estrategias maestras que guían y modifican otras heurísticas, para producir soluciones, más allá de aquéllas que normalmente se generan en una búsqueda local de mejora iterativa.” Una heurística es un procedimiento que puede producir una “buena” solución para un problema, generalmente cuando éste es un problema decisional NP-difícil, es decir, “no determinista en tiempo polinómico”. Como ya se ha avanzado, las aplicaciones prácticas del problema decisional asociado se refieren a operaciones logísticas de navegación económica y segura, con riesgo calculado, sobre grafos, incluyendo: telecomunicación de datos digitales, tráfico multimodal, transporte de mercancías valiosas o peligrosas, así como prevención de piratería, emboscadas y colisiones, con base en la teoría de juegos no cooperativos de Nash. En general, se puede aplicar a todos los usos prácticos de sistemas expertos, cuando están dotados de subrutinas de inteligencia artificial, que apoyen la toma de decisiones rápidas y eficientes en situaciones complejas, frente a varios objetivos mutuamente competitivos. Dichos sistemas, se encuentran ya en funcionamiento, en el contexto de diversas organizaciones, tanto públicas, como privadas, de escala regional, nacional, e internacional, dando soporte a operaciones de gran alcance y relevancia para la economía global. Dada su complejidad e impacto social, pueden por tanto beneficiarse de cuantas mejoras se puedan aportar, en términos de eficiencia y optimización, así como de clasificación, explicación, y divulgación. Particularmente, durante el siglo XX, este campo ha experimentado un gran desarrollo, que continúa con vigor en el XXI, gracias al advenimiento de la ingeniería informática.