Optimization of Facility Planning and Circuit Routing for Survivable Transport NetworksAn Approach Based on Genetic Algorithm and Incremental Assignment

Hajime NAKAMURA  Toshikane ODA  

IEICE TRANSACTIONS on Communications   Vol.E80-B   No.2   pp.240-251
Publication Date: 1997/02/25
Online ISSN: 
Print ISSN: 0916-8516
Type of Manuscript: Special Section PAPER (Special Issue on Telecommunications Network Planning and Design)
Category: Network planning techniques
transport network,  facility planning,  circuit routing,  restoration planning,  GA,  IA method,  

Full Text: PDF(972.2KB)>>
Buy this Article

This paper is concerned with two important planning problems for transport network planning; circuit routing problems and facility planning problems. We treated these optimization problems by taking into account survivability requirements. In the circuit routing problem tackled in this paper, therefore, optimization of circuit restoration plans, namely allocation of spare capacity for assumed failure scenarios is considered together with optimization of circuit routing in a no failure case. In the facility planning problems, failure scenarios of new facilities whose installation is yet to be determined are considered. In this paper, we present a formulation of these two optimization problems, and give 1) optimization algorithms based on the IA (Increment Assignment) method for routing problems and 2) optimization algorithms based on a combination of the GA (Genetic Algorithm) and the IA method for facility planning problems. The IA based routing algorithm can cope flexibly with various constraints on practical network operations and is applicable to large-scale complicated network models without causing a rapid increase in computation time. The GA based facility planning algorithm includes the IA based algorithm as a function for evaluating objective function values. Taking advantage of the important features of the IA based algorithm, we propose an acceleration technique for the GA based facility planning algorithm. In this paper, several numerical examples are provided and the effectiveness of the proposed algorithms is numerically evaluated.