Multi-period capacity expansion for a local access telecommunications network

To link to full-text access for this article, visit this link: http://dx.doi.org/10.1016/j.ejor.2004.12.006 Byline: Michel Gendreau (a)(b), Jean-Yves Potvin (a)(b), Ali Smires (a)(b), Patrick Soriano (a)(c) Keywords: Telecommunications; Local access network; Capacity expansion; Multi-period; Heuristic Abstract: In this paper, we examine a multi-period capacity expansion problem for a local access telecommunications network with a tree topology. Capacity expansion is realized through the installation of concentrators at the nodes and cables on the links of the network. Clearly, the installation of concentrators reduces the need for additional cables, and conversely. The goal is to find the least cost alternative to satisfy the demand. A heuristic approach is proposed to solve this problem, where local installation decisions at each node are propagated in the network. This information is then used to adjust prices that guide the decision process from one iteration to the next, until a fixed point is reached. Numerical results are reported on problem instances based on different cost and demand structures. Author Affiliation: (a) Centre de Recherche sur les Transports, Universite de Montreal, C.P. 6128, Succursale Centre-ville, Montreal, Que., Canada H3C 3J7 (b) Departement d'Informatique et de Recherche Operationnelle, Universite de Montreal, C.P. 6128, Succursale Centre-ville, Montreal, Que., Canada H3C 3J7 (c) Ecole des Hautes Etudes Commerciales, 3000, Chemin de la CA[acute accent]te-Sainte-Catherine, Montreal, Que., Canada H3T 2A7 Article History: Received 19 May 2004; Accepted 13 December 2004