基于0-1线性规划的多点路由规划模型研究

Multicast Routing Model based on 0-1 Linear Programming

针对传统路由算法只适用于两点之间的路由规划而不适用于对多点路由规划的问题,讨论了基于0-1线性规划的多点路由规划模型。该模型以邻接矩阵、0-1矩阵为基础,利用辅助变量记录路径中节点顺序,以路径总权重最小为目标函数,提出一种适用于起点、终点以及若干必经点之间的路由规划模型,并利用线性求解器进行了仿真实验。仿真结果表明,求解该问题所提出的路由算法能有效地解决多点之间的路由规划问题,在中小规模的网络规划中具有较大的应用价值。

Aiming at the problem that traditional routing algorithms are only suitable for routing of between two points, but not for multi-point routing planning, a multi linear routing programming model based on 0-1 linear programming is discussed. The model, based on adjacent matrix and 0-1 matrix and with secondary variables to record the order of nodes in the path and minimum total path weight as the objective function, the routing planning model suitable for starting point, and destination point and several necessary points, is proposed, and the simulation experiment with linear solver also done. Simulation results indicate that the proposed routing algorithm can effectively solve the routing problem of between multiple points, and has great application value in small-and medium-scale network planning.