论文部分内容阅读
最短路径问题是网络中的基本问题之一，它已应用于智能交通系统、地理信息系统、路径规划问题、计算机网络通信等领域。在最短路径问题最新研究成果的基础上，针对动态网络最短路径问题、旅行商问题和多旅行商问题展开了深入的研究，具体工作如下：1、动态网络中最短路径树的拓扑变化是一个随机过程，使用静态最短路径树算法更新网络拓扑计算开销大、耗时多。Ball-and-String模型是一种广泛应用的动态更新算法，但仍存在冗余计算。针对Ball-and-String模型对网络中受影响区域的边的操作进行了改进，减少了冗余操作，同时增加了处理网络中动态加入节点和删除节点的模块。实验表明新算法提高了动态更新的效率，能有效应对网络拓扑的变化。2、为了解决旅行商问题，结合了2-OPT和分枝定界法，对给定的初始解进行迭代优化。2-OPT对给定的解进行局部优化，而分支定界法用来重构全局环的拓扑结构。新算法使用两个参数分别限制分枝定界法的规模和算法的收敛条件。实验结果表明，新算法较2-OPT的优化效果更好。3、为了解决多旅行商问题的（MTSP）各个子分支问题，构造了一个简化初始网络的模型（SModel）。SModel对初始网络进行删边处理，使其转化为一个边的数量与节点数量之比小于1.2的连通网络。在SModel的基础上，提出了新算法求解多旅行商问题（MTSP）的三个分支问题，分别为单源点闭环的MTSP、单源点开环的MTSP和多源点闭环的MTSP。使用SModel求解MTSP的过程包括简化初始网络、调整模型中的路径、生成符合要求的路径集三个阶段。实验表明，使用SModel可以有效解决MTSP的各个分支问题，与之前的工作对比，新算法稳定性好、收敛快，在更少的时间开销上得到相同甚至更好的优化效果。