A genetic algorithm for the point to multipoint routing problem with varying number of requests

Abstract

Message scheduling or call request scheduling is the process of finding optimal routing for a set of circuit connection requests through a communications network. Each request has a single source with one or more destinations. Furthermore, different requests may have different source and different destination nodes. Finding optimal routing for a set of requests is called the point to multipoint routing problem (PMRP). The current practice in solving the PMRP is to consider each point to multipoint request as a collection of point to point requests, and then solve each paint to point request. This is very costly and generally produces poor results. The paper presents an algorithm for the point to multipoint routing problem that uses a genetic algorithm and a heuristic Steiner tree algorithm. The genetic algorithm allows the scheduler to find an optimal or near-optimal path through the network for each request. In the algorithm each request is treated as a whole and not as a collection of point to point requests. Furthermore, given a set of point to multipoint routing requests, the algorithm considers various subsets sizes of the original set of requests and produces an optimal or near-optimal ordering of the requests for the specified subset size. They run the PMRP algorithm on several test cases with excellent results.