论文部分内容阅读
最短路径问题是网络优化的关键问题之一,多年来产生了大量相关领域的研究成果。在这些研究成果中,有相当一部分是针对网络弧权单一情形的。然而,在现实生活中,很多问题的弧权不是一个而是多个,而且从源节点至目标节点的最优路径对其中一个或多个弧权是有约束的,这就是有约束的最优路径问题。目前,有关QoS路由问题的多约束最优路径算法已有很多,但基于道路交通网络的多约束最优路径问题的研究成果相对较少。论文主要基于道路交通网络,对多约束最优路径问题进行研究。论文的研究成果主要包括:1)针对带约束的多弧权网络最优路径问题,建立了多约束最短路径模型;将经典的Dijkstra算法应用于多约束最短路径问题中,提出了D_MCSP算法。2)D_MCSP算法是一种盲目搜索算法,在搜索过程中会扩展许多与最短路径无关的中间节点状态,影响算法的搜索效率。为此,论文将A*算法的启发式搜索思想引入多约束最短路径问题,提出了A*_MCSP算法。3)针对D_MCSP算法和A*_MCSP算法在搜索过程中需要占用大量系统内存来存储中间节点状态的缺点,基于启发式迭代加深搜索算法IDA*,提出了IDA*_MCSP算法;针对IDA*_MCSP算法在路径搜索过程中可能出现的节点重复扩展等问题,论文又提出了一种加强存储的迭代加深启发式搜索算法(ME-IDA*_MCSP算法)。4)对IDA*_MCSP(ME-IDA*_MCSP)算法作进一步改进,提出了一种多约束边沿搜索算——Fringe_MCSP算法,克服了原有算法每次迭代都要回到起始节点重新搜索的缺陷。5)最后,基于南京市某区域道路信息,建立了多约束道路交通网络平台,并在该平台实现了上述四种多约束最优路径算法。试验表明:上述算法都是正确有效的,并且Fringe_MCSP算法是其中最优的一种算法。