多约束最短链路不相交路径的启发式算法

发布时间：2018-05-16 22:19

  本文选题：QoS路由 + 链路不相交路径　； 参考：《解放军理工大学学报(自然科学版)》2013年01期

【摘要】：为求解多约束最短链路不相交路径(MCSDP(k))问题,提出了一种启发式的整数规划方法:FHABIP,并给出了算法搜索方案。根据问题的整数线性约束集合具有的结构特点,利用拉格朗日乘子把整数线性约束集合中的复杂约束引入到目标函数中,导出具有约束系数矩阵是全幺模矩阵特点的整数线性规划问题,从而使这类问题能用单纯形法容易求解。MCSDP(k)在求解线性规划问题的迭代过程中很容易地被求出。算法实验结果表明该算法快速有效。
[Abstract]:In order to solve the multi-constraint shortest link disjoint path problem, a heuristic integer programming method named: FHABIPP is proposed, and the algorithm search scheme is given. According to the structural characteristics of the integer linear constraint set of the problem, the Lagrange multiplier is used to introduce the complex constraints in the integer linear constraint set into the objective function. An integer linear programming problem with the characteristic of a constrained coefficient matrix is derived, so that the problem can be easily solved by the simplex method in the iterative process of solving the linear programming problem. Experimental results show that the algorithm is fast and effective.
【作者单位】： 解放军理工大学通信工程学院;总参信息化部;
【基金】：国家自然科学基金资助项目(70971136)
【分类号】：TP393.09;O221.4

【参考文献】

相关期刊论文 前3条

1 刘千里,汪泽焱,倪明放,戴浩;一种基于多条件约束的QoS路由选择优化算法[J];计算机研究与发展;2001年03期

2 熊轲;裘正定;郭宇春;张宏科;秦雅娟;;多约束最短链路分离路径精确算法[J];软件学报;2010年07期

3 张品;章坚武;李乐民;王晟;;QoS约束下的链路分离路径问题研究[J];通信学报;2006年06期

【共引文献】

相关期刊论文 前10条

1 吴传信;倪明放;陈鸣;;路由选择的一种新遗传算法[J];电子科技大学学报;2006年05期

2 冯杰;夏尊铨;;基于多目标规划和业务区分的多QoS约束路由算法[J];大连理工大学学报;2006年04期

3 吕亚娟;王帅;李莹;;移动无线网络的安全QoS路由[J];电脑知识与技术;2008年29期

4 汪泽焱;一种基于多目标优化的QoS路由交互式算法[J];国防科技大学学报;2002年04期

5 纪洪明;郭平;蒋银华;;QoS约束下的分离路径算法研究[J];后勤工程学院学报;2007年03期

6 吴传信,倪明放;时延约束的最小费用路由选择算法[J];解放军理工大学学报(自然科学版);2004年06期

7 汪泽焱,顾红芳;一种求解QoS路由算法的数学模型研究[J];计算机工程与应用;2003年08期

8 张广跃;汪泽焱;张申如;;一种链路分离路径算法的优化[J];计算机工程与应用;2008年02期

9 汪泽焱,倪明放;基于线性约束的多参数优化的QoS路由算法[J];计算机工程;2002年03期

10 曹元大,向尕;基于多目标规划的QoS路由选择的数学模型及优化算法[J];计算机工程;2003年02期

相关会议论文 前2条

1 于战科;倪明放;;基于改进遗传算法的QoS路由选择[A];计算机技术与应用进展——全国第17届计算机科学与技术应用（CACIS）学术会议论文集（下册）[C];2006年

2 汪胡青;王诚;;基于蚁群原理的QoS多约束单播路由算法研究与实现[A];中国通信学会信息通信网络技术委员会2005年年会论文集[C];2005年

相关博士学位论文 前6条

1 张冰怡;分数Alpha通信量模型的研究与应用[D];南京理工大学;2004年

2 陈骏坚;基于新型蚂蚁算法的QoSR理论及技术研究[D];武汉理工大学;2006年

3 冯杰;基于小世界和随机图理论的多QoS路由算法研究[D];大连理工大学;2007年

4 连进;基于移动预测的Ad Hoc网络路由技术的研究[D];武汉理工大学;2008年

5 郑锋;移动Ad Hoc网络QoS多播路由协议的研究[D];武汉理工大学;2008年

6 熊轲;支持QoS的可扩展可靠路由算法及转发技术研究[D];北京交通大学;2010年

相关硕士学位论文 前10条

1 周新宇;基于演化算法的QoS约束选播路由研究[D];江西理工大学;2011年

2 王雪平;时延敏感的多播路由算法研究[D];西安电子科技大学;2004年

3 张艳华;智能集成路由算法研究[D];中国农业大学;2004年

4 路冉;MPLS流量工程中的CSPF技术研究及仿真[D];河北大学;2004年

5 李峰;多路径QoS路由算法研究[D];武汉大学;2004年

6 蒋培培;WDM光网络中的路由与波长分配算法[D];西安电子科技大学;2005年

7 陈宇;软交换技术中的时延与QoS的研究[D];哈尔滨理工大学;2005年

8 张雨;软交换技术中服务阻塞问题的研究[D];哈尔滨理工大学;2005年

9 王娜娜;基于遗传粒群路径优化的网络拥塞控制方法[D];郑州大学;2007年

10 邓育林;基于NS-2的Anycast QoS路由研究与仿真[D];广西大学;2007年

【二级参考文献】

相关期刊论文 前2条

1 张品,李乐民,王晟;两约束路由问题的近似解法[J];通信学报;2003年12期

2 张品;章坚武;李乐民;王晟;;QoS约束下的链路分离路径问题研究[J];通信学报;2006年06期

【相似文献】

相关期刊论文 前10条

1 宁爱兵;熊小华;马良;;装卸工人调配问题新解法及其证明[J];上海理工大学学报;2007年02期

2 史晓艳;;租车问题的优化模型探讨[J];长春理工大学学报;2010年11期

3 吴文江;;大规模整数规划的分解方法[J];运筹学学报;1991年01期

4 唐松生,高敬振;一类推广的整数极小极大问题的求解算法[J];山东师大学报(自然科学版);1999年02期

5 万伟勋;管理科学中一个特殊的整数规划[J];数学的实践与认识;1985年02期

6 解元元;正系数整数规划的一种快速搜索求解法[J];陕西师范大学学报(自然科学版);2003年S1期

7 徐大申,邱启荣,何凤霞,彭武安;求解整数规划方法新探[J];华北电力大学学报;2004年05期

8 郭志军;;分支定界算法的MATLAB实现[J];职业圈;2007年16期

9 郭志军;;Mathematica求解整数规划研究[J];黑龙江科技信息;2007年24期

10 钟海林;叶祥企;;背包问题的若干性质及问题的简化[J];江西科学;2008年01期

相关会议论文 前10条

1 万玉成;;系数未确知的线性规划模型及其解法[A];中国运筹学会第八届学术交流会论文集[C];2006年

2 薛声家;;线性约束拟单调规划多重最优解[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

3 韩猛;;钢铁生产组板设计优化算法研究[A];中国计量协会冶金分会2009年年会论文集[C];2009年

4 梁时木;于中华;唐小棚;李娜娜;;混合遗传算法在制造元设计中的应用研究[A];2008'中国信息技术与应用学术论坛论文集（一）[C];2008年

5 张峰;;具有先后约束关系的工件加工时间可控排序问题的线性规划松弛算法[A];2006年中国运筹学会数学规划分会代表会议暨第六届学术会议论文集[C];2006年

6 郭延明;周宁;王凯悦;;危破营房翻建费合理分配系统分析[A];发展战略与系统工程——第五届系统工程学会年会论文集[C];1986年

7 熊伟清;魏平;;基于食物量分配的多种群二元蚁群优化算法[A];中国自动化学会控制理论专业委员会D卷[C];2011年

8 刘梅娇;曹炳元;;Fuzzy线性规划最优解的新探及扩展[A];中国系统工程学会模糊数学与模糊系统委员会第十一届年会论文选集[C];2002年

9 高玉波;;规划技术在关联项目选择中的应用[A];发展的信息技术对管理的挑战——99’管理科学学术会议专辑（上）[C];1999年

10 李杰;;用0—1型整数规划进行道路交通投资决策[A];湖北省公路学会第七届优秀论文集[C];1998年

相关重要报纸文章 前10条

1 龚强（作者单位：哈尔滨工业大学管理学院）;测绘运筹学初探[N];中国测绘报;2002年

2 ;起山电信:通信领域的最优解[N];中国计算机报;2003年

3 梁文斌、李连民;寻求城市通信网络的最优解[N];中国计算机报;2003年

4 本报记者　廖新军;德隆困局最优解：破产重整？[N];21世纪经济报道;2004年

5 陈春花;寻求“满意解”[N];21世纪经济报道;2007年

6 皮建才;中国的宏观调控何以找不到最优解[N];甘肃经济日报;2006年

7 PALADIN;编程沙龙[N];电脑报;2003年

8 程爱娟;旅行推销员问题（TSP）的人工智能解法及其应用[N];新疆科技报(汉);2001年

9 本报记者 申兴;“数量扩张已经远去” 基金“限售”探路规模最优解[N];经济观察报;2006年

10 本报记者 张小彩;国有银行重组 为什么要由国家主导[N];财经时报;2004年

相关博士学位论文 前10条

1 李玉英;混沌蚂蚁群优化算法及其应用研究[D];北京邮电大学;2009年

2 郑睿;钢铁生产中的批处理机作业排序问题算法研究[D];复旦大学;2009年

3 达林;切平面在混合整数非线性规划中的应用[D];北京交通大学;2009年

4 冀淑慧;基于SDP松弛的整数规划凸化方法研究[D];复旦大学;2012年

5 李和成;非线性双层规划问题的遗传算法研究[D];西安电子科技大学;2009年

6 徐云;具有交易成本的最优投资组合及极限定理[D];新疆大学;2004年

7 陈伟;0-1二次规划的全局最优性条件及算法[D];上海大学;2005年

8 王斌;集装箱空箱调运优化研究[D];上海海事大学;2005年

9 颜昕;Internet中QoS多播路由技术研究[D];武汉理工大学;2006年

10 曾绍华;支持向量回归机算法理论研究与应用[D];重庆大学;2006年

相关硕士学位论文 前10条

1 彭凤;整数规划算法效率的研究[D];中南大学;2010年

2 吴健;约束路由及动态业务量疏导算法研究与实现[D];电子科技大学;2009年

3 颜维;满意优化理论在网络优化设计中的应用[D];西南交通大学;2006年

4 熊鹰;微粒群算法的若干改进及应用[D];武汉理工大学;2006年

5 刘明芳;基于分布估计算法的整数规划研究[D];武汉理工大学;2008年

6 姜磊;关于粒子群多策略优化算法的研究[D];江南大学;2008年

7 郭仁拥;两个供应链优化模型及优化算法[D];内蒙古大学;2006年

8 王恩龙;一种特殊永磁型磁体的匀场技术研究[D];沈阳工业大学;2007年

9 秦平平;分支定界算法在运筹学模型中的应用[D];燕山大学;2009年

10 姚春玲;边覆盖对策的均衡性及其算法[D];中国海洋大学;2008年

，

本文编号：1898657