Using Lampposts to Provide Urban Areas with Multiple Services

In this thesis the goal is to find an efficient method which is able to assign services to each of the potential lampposts in a city such that all services are distributed adequately (i.e. the coverage requirements are met), against minimal costs. A two-step approach is proposed to find a smart and cost efficient distribution. In the first step the services are distributed over the available lampposts while taking into account the required coverage and the costs for enabling a lamppost to be equipped with services. A formulation of this problem, which is termed the Multi-Service Location Set Covering Problem, is presented. Several heuristic methods are proposed to solve this problem. A heuristic method based on sequentially solving a Set Covering Problem for each of the services is shown to obtain the best results. The quality of this heuristic can in part be attributed to an efficient method which is implemented to solve Set Covering Problems. The selected locations from the first step are then taken as input to the second step, which can be seen as a cost reduction step. In this step lampposts are selected which are enabled to serve as a hub to at most a certain amount of lampposts which are within a specified range. For this problem, termed the Wireless Network Problem a formulation is presented. To solve the Wireless Network Problem several metaheuristics are proposed. It is shown that the Iterated Local Search metaheuristic is able to find the best solutions. The best solution methods are used in the two-step approach to provide cities with multiple services.