Broadband expansion is progressing, and many cables have yet to be laid in Germany – mostly underground. But that means excavation costs. Given a map with end-user connections that need to be provided, as well as the roads, the existing lines, the soil condition, not to mention other factors, the question arises: How should the lines be planned in order to keep the excavation costs as low as possible? That is a difficult optimization problem for which we have studied various solutions, including bio-inspired approaches and quantum annealing. Specialized algorithms were designed that surpass state-of-the-art approaches.