Sun, J and Zhang, Qingfu and Li, J (2010) Two-level evolutionary approach to the survivable mesh-based transport network topological design. Journal of Heuristics, 16 (5). pp. 723-744. ISSN 1381-1231
Full text not available from this repository.Abstract
The complete topology design problem of survivable mesh-based transport networks is to address simultaneously design of network topology, working path routing, and spare capacity allocation based on span-restoration. Each constituent problem in the complete design problem could be formulated as an Integer Programming (IP) and is proved to be [NP]-hard. Due to a large amount of decision variables and constraints involved in the IP formulation, to solve the problem directly by exact algorithms (e.g. branch-and-bound) would be impractical if not impossible. In this paper, we present a two-level evolutionary approach to address the complete topology design problem. In the low-level, two parameterized greedy heuristics are developed to jointly construct feasible solutions (i.e., closed graph topologies satisfying all the mesh-based network survivable constraints) of the complete problem. Unlike existing “zoom-in”-based heuristics in which subsets of the constraints are considered, the proposed heuristics take all constraints into account. An estimation of distribution algorithm works on the top of the heuristics to tune the control parameters. As a result, optimal solution to the considered problem is more likely to be constructed from the heuristics with the optimal control parameters. The proposed algorithm is evaluated experimentally in comparison with the latest heuristics based on the IP software CPLEX, and the “zoom-in”-based approach on 28 test networks problems. The experimental results demonstrate that the proposed algorithm is more effective in finding high-quality topologies than the IP-based heuristic algorithm in 21 out of 28 test instances with much less computational costs, and performs significantly better than the “zoom-in”-based approach in 19 instances with the same computational costs.
| Item Type: | Article |
|---|---|
| Uncontrolled Keywords: | Survivable mesh-based network; Network topology design; Heuristics; Evolutionary algorithm; Estimation of distribution algorithm |
| Subjects: | Q Science > QA Mathematics Q Science > QA Mathematics > QA75 Electronic computers. Computer science |
| Divisions: | Faculty of Science and Engineering > Mathematical Sciences, Department of Faculty of Science and Engineering > Computer Science and Electronic Engineering, School of |
| Depositing User: | Jim Jamieson |
| Date Deposited: | 13 Jan 2012 11:30 |
| Last Modified: | 13 Jan 2012 11:30 |
| URI: | http://repository.essex.ac.uk/id/eprint/1969 |
Actions (login required)
 |
View Item |
