Modelos y métodos para la optimización y eficiencia de la programación de horarios ferroviarios

Zusammenfassung

Los problemas de optimización y satisfacción de restricciones son extraordinariamente complejos y variados, Al mismo tiempo, son problemas de alto interés, tanto en el aspecto científico-técnico como en el aplicado. Por ello, poder disponer de soluciones algorítmicas eficientes y flexibles supone un alto valor añadido en muy diferentes entornos de aplicación. Entre los más típicos problemas de este tipo, se encuentran los problemas de scheduling, que implican la ejecución de acciones que requieren recursos cuya disponibilidad está limitada y por tanto deben asignarse de modo eficiente. Problemas de este tipo aparecen en numerosos contextos, entre los que se encuentran la generación optimizada de horarios. Concretamente, el problema considerado en esta tesis corresponde a la generación optimizada de horarios ferroviarios. Este problema puede asimilarse a un problema de scheduling tipo Job Shop, aunque con unas características particulares y especialmente complejas. Se han publicado muchos trabajos en relación al problema de scheduling tipo Job Shop genérico, la mayoría de ellos modelando el problema mediante programación entera mixta y resolviéndolo mediante la utilización de métodos matemáticos. En otros casos, se ha considerado la aplicación de técnicas CSPs híbridas, donde se fuerza la consistencia de las restricciones hasta un determinado nivel, combinando el procedimiento con búsqueda heurística. Sin embargo, en todos los trabajos revisados se considera un subconjunto reducido de las restricciones del problema que consideramos en esta Tesis. Esto claramente disminuye la complejidad del problema, razón por la cual en los métodos matemáticos puede utilizarse la relajación Lagrangiana o los planos de corte para disminuir el espacio de búsqueda. Sin embargo, cuando se incorporan los complejos tipos de restricciones que aparecen en los contextos reales, la programación matemática ya no es viable, pues los métodos de soluc