A hybrid genetic algorithm for the point to multipoint routing problem with single split paths
P. Galiasso, Roger L. Wainwright · 2001
A hybrid evolutionary algorithm for solving the Point to Multipoint Routing Problem (PMRP) is presented. We considered an application of the PMRP called the Message Scheduling Problem. The Message Scheduling Problem is the process of scheduling a set of requests through a network where each request has a single source and multiple destinations. Our new algorithm not only treats each request as a whole, but also allows up to two paths for transmitting the request bandwidth. We call this problem the Point to Multipoint Routing Problem with Single Split Paths. Our hybrid algorithm uses a genetic algorithm and a heuristic Steiner tree algorithm for finding near-optimal solutions to this problem. We designed the chromosome to accommodate not only the option of multiple paths for a request, but how to split the bandwidth. We ran our algorithm against results from previous researchers with superior results. 1.