Optimising the Distribution of Modular Capacitated Services in Smart Cities. Masterthesis VU Amsterdam
master thesis
This thesis focuses on the problem of distributing services over urban areas to satisfy the demand, which is also called the Multi-Service Capacitated Facility Location Problem (MSCFLP). In the smart city context, the demand is spread out over the city. Costs savings can be obtained by combining multiple services. Three different heuristics are proposed: the Extended Pricing Heuristic (EPH), the Extended Linear Relaxation Heuristic (ELRH) and the Extended Sequential Covering Heuristic (ESCH). The heuristics consist of two phases. A feasible solution is found in the first phase, which is optimised by an exact method in the second phase. The exact method is also executed on the whole problem to benchmark the heuristics. In addition, the Multi-Service Modular Capacitated Facility Location Problem (MSMCFLP) is introduced. This problem allows modular capacities which generally leads to large costs benefits. The heuristics and the exact method are performed on nine test instances of both problems. The heuristics can be described as efficient, since good solutions are found in short computation times. Regarding the MSCFLP, the exact method has the best performance, closely followed by the ESCH, EPH and ELRH. Concerning the MSMCFLP, the ESCH even outperforms the exact method due to the stopping criteria. Finally, a lower bound analysis showed that only small improvements can be made by new heuristics in both problems.
TNO Identifier
874849
Collation
51 p.