El estudio y la resolución de los problemas de Optimización Combinatoria con uno o más objetivos constituyen un campo de trabajo de importancia dentro de la Investigación Operativa y las Ciencias de la Computación. En este contexto, caben resaltar los problemas de Transporte y Logística, en los que se quieren determinar soluciones óptimas bajo la consideración de uno o más criterios. Para éstos y otros problemas de naturaleza similar, un número importante de autores han dedicado esfuerzos notables que han fructificado en aportaciones relevantes publicadas en libros y revistas de impacto. El proceso de planificación estratégica en el transporte público se suele dividir en tres pasos: diseño de la red, planificación de las líneas y la programación de las mismas. En todos estos pasos son necesarias herramientas de optimización en redes eficientes, debido a la enorme dimensión de estos problemas en general. En este proyecto se analizarán los fundamentos teóricos, se expondrán las líneas de trabajo desarrolladas en la literatura existente sobre el tema, se estudiarán los algoritmos ya propuestos, se construirán nuevos procedimientos y se realizará un estudio comparativo que ponga en evidencia las ventajas y desventajas de los diferentes modelos. En algunos modelos existentes para problemas de transporte, el modelo resultante consiste en variaciones del problema de flujos múltiples en una red. En general, en la resolución exacta de estos problemas se conjugan herramientas clásicas de Programación Matemática que no suelen explotar el modelo de red subyacente del problema. Sin embargo, es preferible, desde el punto de vista computacional, diseñar algoritmos ad hoc más eficientes que los existentes. Para ello, se considerarán modelos matemáticos para los que desarrollaremos esquemas enumerativos inteligentes que permitirán resolver estos problemas de manera exacta, aún cuando las dimensiones del problema sean grandes. Las herramientas enumerativas propuestas se basan en los algoritmos eficientes que ha desarrollado nuestro grupo de investigación para la enumeración de soluciones de problemas de Optimización Combinatoria clásicos. Estas herramientas posibilitan la resolución de problemas de Transporte, ya que estos son problemas de Optimización Combinatoria clásicos con restricciones adicionales. La metodología propuesta permitirá además iniciar una línea de investigación que denominamos algoritmos evolutivos con genealogía y mecanismos duros de extinción que surge de la consideración de las herramientas a desarrollar en este proyecto y que se aplicarán a problemas en el ámbito del transporte y la planificación. Parte de esta esta nueva línea será la tesis doctoral de un doctorando supervisado por el investigador principal de este proyecto.
One of the research fields in Operations Research and in Computer Science with a great importance is the study of Combinatorial Optimization problems with one objective or several objectives and the development of approaches to solve them. In this framework, it is possible to emphasize several problems as Transport and Logisitics wherein it is required to find optimal solutions considering one or several criteria. An important number of authors have dedicated a noteworthy effort for these problems and other problems with similar nature. Their work has yielded in relevant contributions published in scientific books and journals with a great impact. Part of our work is devoted to study these problems. The strategic planning process in public transport is usually divided into three steps : network design , planning and programming lines. In all these steps are necessary efficient tools from network optimization, because of the huge data in these problems. In this project, we will analyze the theoretical, we will describe the lines developed in the literature on the subject. Moreover, we will study the existing algorithms and propose new procedures . Then, we will compare the performance of these methods in order to shows the advantages and disadvantages of the different models. In some existing transportation problems, the corresponding models are variations of the multy-commodity flow problem. In general, the exact resolution of these problems combine classical mathematical programming tools that do not usually exploit the underlying network model of the problem. However, from a computational point of view, it is preferable to design «»ad hoc»» algorithms that be more efficient than the existing ones. For this, we will consider the mathematical models that allow developing smart enumerative schemes to solve these problems in an exact way, even when the dimensions of the problem are large. The proposed enumerative tools are based on efficient algorithms developed by our research group for the enumeration of solutions of classical Combinatorial Optimization problems. These tools enable troubleshooting of Transportation, since these are classic combinatorial optimization problems with additional constraints. In addition, the proposed methodology will allow starting a new investigation line denominated as Evolutive algorithms with genealogy and hard extinction mechanisms. This new line emanates from the consideration of the approaches studied in this project and the results in this new line will be apply to combinatorial optimization problems with a single objective and with various objectives and, additionally, to some problems that lies in the scope of the transport and logistics problems. This new line will be the doctoral thesis of one investigator under the supervision of the main investigator of this project.