Der Breitbandausbau schreitet voran und in Deutschland müssen dafür noch viele Kabel verlegt werden – meist unterirdisch. Doch dies verursacht Grabungskosten. Gegeben eine Karte mit Endkundenanschlüssen, die versorgt werden müssen, sowie den Straßen, den schon vorhandenen Leitungen, der Bodenbeschaffenheit und anderen Faktoren stellt sich die Frage: Wie sind die Leitungen zu planen, um die Grabungskosten möglichst gering zu halten? Dies ist ein schwieriges Optimierungsproblem, für das wir verschiedene Lösungsmethoden untersucht haben, darunter auch bio-inspirierte Ansätze und Quantum Annealing. Dabei konnten spezialisierte Algorithmen konstruiert werden, die State of the Art Ansätze übertreffen.