● 摘要
在当今的通信网络中提供可靠的QoS服务保障，在任何相关应用中都是一个具有挑战性的研究课题，QoS Routing 是其中的一个关键性问题，而多约束最优路径问题(Muli-Constrained Optimal Path，简称MCOP)就是从QoS Routing中抽象出来的更具有一般性的网络最优化模型，它是指在一个网络中，寻找一条满足一个或者多个约束条件的可行路径并且使得路径的花费或开销达到最优。由于累加型约束（如延迟、时间等）在日常生活和研究中遇到的比较多，因此本文对累加型的MCOP问题及其变形进行深入的研究。目前解决该问题的算法包括精确算法、近似算法和启发式算法，本文通过分析已有的研究方法和成果，在精确算法和启发式算法方面进行了改进和优化。遵循从特例到一般的研究思路，首先，对MCOP问题的一个特例HSP(Hop-constrained Shortest Path)问题的精确算法进行了研究，提出了一个适用于大规模网络的算法，同时对求解MCOP问题的新界提供了线索；其次，实现了MCOP问题的一个基于分支定界算法的精确算法，在优化了搜索策略，改进了下界的基础上，一定程度上提高了搜索性能；最后，通过研究了MCOP问题的非线性加权函数和相关启发式算法，在H_MCOP算法的基础上引入了禁忌搜索和邻近搜索思想，优化了解的质量。本文工作的贡献主要体现在如下几个方面：1）对MCOP问题的特例HSP进行了研究，应用了双向对立搜索策略，通过尽量减少计算过程中涉及到的顶点和边，来减少计算时间。在大规模的网络中，节点间的连接相对较少，新提出的算法能够表现出很好的性能。2）在MCOP精确算法方面，结合HSP新提出了一个更加紧的下界，设计并实现了求解MCOP问题的分支定界算法，为后面的启发式算法的评测提供了保证。3）在MCOP启发式算法方面，基于H_MCOP将禁忌搜索融入到该算法中，通过设计禁忌规则和恰当的引入时机，提出了TS_MCOP算法；另外为了进一步的提高算法返回解的质量，又以前K短路径为基础，将其作为邻居结构，把邻近搜索的思想引入到了TS_MCOP算法中，提出了KTS_MCOP算法；相比于已有的同类算法，新提出的算法在返回路径的成功率、最优性和平均Cost的偏离度上都表现出非常好的效果。