Research On The Multiple-Origins-Multiple-Destinations Routing Problems With Constraints On Genetic Algorithm

The multiple-origins-multiple-destinations routing (MOMD) problems with constraints is a NP-complete problem. The object of the MOMD problems with constraints is to find a optimum connection of figs including all the origins and destinations ,which meet constraints in a directionless connection network. Here every origins are correlative with many destinations. For resolving the MOMD problems with constraints, it can be divided into two-branch problems: The first one is many single-origin-multiple-destinations routing (SOMD) problems with constraints; The second one that optimal and superior solutions of each SOMD problem with constraints is combined to find the optimum solution of the MOMD problem with constraints. Then, the two problems are solved by genetic algorithm. Two aspects are following :(1)A genetic algorithm for solving the SOMD problem with degree-constraint is proposed. The coding with form of node path is adopted. The crossover operator and mutation operator retained tree-structure, and the method of modifying degree of nodes are designed. The proposed algorithm can be applied to large-scale network to solve the SOMD problems.(2) The second question belongs to combinatorial optimization. Multiple value coding is used in the algorithm. Simple point crossover operator and position mutation operator is adopted. The algorithm is simple and easy to realize.The algorithm effectively solved the MOMD problem with degree-constraint by numerical simulation results .