Evolutionary design of oriented-tree networks using Cayley-type encodings

This paper introduces the oriented-tree network design problem (OTNDP), a general problem of tree network design with several applications in different fields. We also present several adaptations needed by evolutionary algorithms with Cayley-type encodings to tackle the OTNDP. In particular, we present these adaptations in two Cayley-encodings known as Prufer and Dandelion codes. We include changes in Cayley-encodings to consider rooted trees. We also show how to use a fixed-length encoding for Cayley codes in evolutionary algorithms, and how to guarantee that the optimal solution is included in the search space. Finally, we present several adaptations of the evolutionary algorithm's operators to deal with Cayley-encodings for the OTNDP. In the experimental part of the paper, we compare the performance of an evolutionary algorithm (implementing the two Cayley-encodings considered) in several OTNDP instances: first, we test the proposed techniques in randomly generated instances, and second, we tackle a real application of the OTNDP: the optimal design of an interactive voice response system (IVR) in a call center. (C) 2009 Elsevier Inc. All rights reserved.