Connecting the houses at FttH with respect for social costs: Solving a Steiner tree problem with timing benefits

Rolling out a Fibre to the Home (FttH) architecture is very expensive, mainly due to all the trenching that is labour extensive. In this paper we present a method for planning the last mile in FttH in a cost effective way and extend this method for incorporating and minimizing the inconvenience and social costs this work brings. To do this, we model the problem of connecting the houses with FttH in a novel way: we know already where the fibre segments have to be, but how to connect them to create a coherent network? This can be modelled as a Minimal Steiner Tree problem. Next we present a heuristic approach to solve this node and edge weighted Minimum Steiner Tree problem and introduce a method to incorporate smart co-laying opportunities in this approach, which are called the the timing benefits.