La grille d’horaires de 2005 pour ce réseau a été calculée par Matheon à l’institut de Mathématiques de Berlin. La clef de ce travail était de l’ordre de l’état de l’art des techniques d’optimisation combinatoire. Les transports publics de Berlin sont modélisés comme un graphe où les stations sont des nœuds reliés par des arêtes et soumis à certaines contraintes. La solution optimale pour son fonctionnement (minimisant le temps d’attente aux stations et le nombre de trains nécessaires) est cachée quelque part dans l’ensemble de toutes les solutions possibles respectant les contraintes données. Mais cet ensemble est beaucoup trop grand pour être exploré dans son ensemble, même par les plus puissants des calculateurs. Des méthodes mathématiques astucieuses produisent des algorithmes puissants permettant d’éliminer de larges pans de cet ensemble pour concentrer la recherche dans les sous-régions plus restreintes où se trouvent l’optimum.

Le film est disponible en allemand et anglais. Pour le télécharger, cliquer sur le bouton « download link » sur la droite.