## Application of Multistage Stochastic Programming in Strategic Telecommunication Network Planning

Please always quote using this URN: urn:nbn:de:0297-zib-12206

- Telecommunication is fundamental for the information society. In both, the private and the professional sector, mobile communication is nowadays taken for granted. Starting primarily as a service for speech communication, data service and mobile Internet access are now driving the evolution of network infrastructure. In the year 2009, 19 million users generated over 33 million GB of traffic using mobile data services. The 3rd generation networks (3G or UMTS) in Germany comprises over 39,000 base stations with some 120,000 cells. From 1998 to 2008, the four network operators in Germany invested over 33 billion Euros in their infrastructure. A careful allocation of the resources is thus crucial for the profitability for a network operator: a network should be dimensioned to match customers demand. As this demand evolves over time, the infrastructure has to evolve accordingly. The demand evolution is hard to predict and thus constitutes a strong source of uncertainty. Strategic network planning has to take this uncertainty into account, and the planned network evolution should adapt to changing market conditions. The application of superior planning methods under the consideration of uncertainty can improve the profitability of the network and creates a competitive advantage. Multistage stochastic programming is a suitable framework to model strategic telecommunication network planning. We present mathematical models and effective optimization procedures for strategic cellular network design. The demand evolution is modeled as a continuous stochastic process which is approximated by a discrete scenario tree. A tree-stage approach is used for the construction of non-uniform scenario trees that serve as input of the stochastic program. The model is calibrated by historical traffic observations. A realistic system model of UMTS radio cells is used that determines coverage areas and cell capacities and takes signal propagation and interferences into account. The network design problem is formulated as a multistage stochastic mixed integer linear program, which is solved using state-of-the-art commercial MIP solvers. Problem specific presolving is proposed to reduce the problem size. Computational results on realistic data is presented. Optimization for the expected profit and the conditional value at risk are performed and compared.

Author: | Jonas Schweiger |
---|---|

Document Type: | Master's Thesis |

MSC-Classification: | 90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Bxx Operations research and management science / 90B18 Communication networks [See also 68M10, 94A05] |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C15 Stochastic programming | |

90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C90 Applications of mathematical programming | |

Granting Institution: | Technische Universität Berlin |

Advisor: | Martin Grötschel, Werner Römisch |

Publishing Institution: | Zuse Institute Berlin (ZIB) |

Date of first Publication: | 2010/07/22 |

Pagenumber: | 149 |

Licence (German): | Creative Commons - Namensnennung-Nicht kommerziell-Keine Bearbeitung |