Network design through forests with degree- and role-constrained minimum spanning trees

详细信息    查看全文

• 作者：Laura Anton-Sanchez ; Concha Bielza ; Pedro Larrañaga
• 关键词：Degree ; and role ; constrained minimum spanning tree ; Forest ; Network design ; Permutation problems ; Evolutionary computation
• 刊名：Journal of Heuristics
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：23
• 期：1
• 页码：31-51
• 全文大小：
• 刊物类别：Mathematics and Statistics
• 刊物主题：Operations Research, Management Science; Operation Research/Decision Theory; Artificial Intelligence (incl. Robotics); Calculus of Variations and Optimal Control; Optimization;
• 出版者：Springer US
• ISSN：1572-9397
• 卷排序：23

文摘

Finding the degree-constrained minimum spanning tree (DCMST) of a graph is a widely studied NP-hard problem. One of its most important applications is network design. Here we deal with a new variant of the DCMST problem, which consists of finding not only the degree- but also the role-constrained minimum spanning tree (DRCMST), i.e., we add constraints to restrict the role of the nodes in the tree to root, intermediate or leaf node. Furthermore, we do not limit the number of root nodes to one, thereby, generally, building a forest of DRCMSTs. The modeling of network design problems can benefit from the possibility of generating more than one tree and determining the role of the nodes in the network. We propose a novel permutation-based representation to encode these forests. In this new representation, one permutation simultaneously encodes all the trees to be built. We simulate a wide variety of DRCMST problem instances which we optimize using different evolutionary computation algorithms encoding individuals of the population using the proposed representation. To illustrate the applicability of our approach, we formulate the trans-European transport network as a DRCMST problem. In this network design, we simultaneously optimize nine transport corridors and show that it is straightforward using the proposed representation to add constraints depending on the specific characteristics of the network.