改进的基于关系数据库技术的公交查询算法

为满足公众对出行路径的多样性需求,针对目前公交查询算法的不足,提出改进的基于关系数据库技术的公交查询算法.该算法依据"最优路径的子路径都是最优路径"理论,通过换乘次数小的最优路径逐步求取换乘次数大的最优路径,并利用关系数据库技术进行最优路径集合的生成和优化,从而实现大规模公交网络的多目标路径搜索.以北京公汽网络作为算例,分别以最短出行时间、最小换乘次数、最少出行费用为评价标准编制程序搜索最优路径,结果表明最短出行时间算法的多目标搜索结果最优,查询速度快,具有推广价值.     

最短路径子图

在大型网络中两节点之间的最短路径常常不止一条,而且在带限制条件的路径选择等应用上,常常需要找出多条最优或近优的路径.一些经典的单源最短路径算法,如Dijkstra算法,能找出一条从起始点到目的点的最短路径,但并不能求解两点之间的所有最短路径.本文给出了最短路径子图的概念,用于存储图中两节点之间所有最短路径信息,能够节约存储空间.并给出了最短路径子图构造算法SPSG,其时间复杂度为O(n e),比同类算法时间复杂度更低.随机网络模型的仿真结果表明:SPSG算法效率更高.     

城市道路最短路径的Dijkstra算法优化

在研究城市道路网络特征基础上,建立城市道路网络模型及其数据库,应用一种改进的Dijkstra算法对城市道路进行最短路径查询,该算法是从起点和终点分别用二叉树按起点到终点和终点到起点的方向进行搜索.在计算某一段最短路径时,用Dijkstra算法时间为0.23 s,改进算法时间为0.20 s.仿真结果表明,该算法不仅在时间上有所改进,其时间复杂度由传统Dijkstra算法的O（n^2）减小为O（n）,而且其所选的最优路径更符合实际,是一种寻求最优路径的有效算法.     

基于拉格朗日松弛的水灾逃生路径规划

研究了假设路段通行时间为随机变量的交通网络约束最短路径问题.建立0-1整数规划模型,求出最小期望通行时间路径.除流量平衡和路段通行能力约束外,还引入了唯一通路选择约束以保证最终只能生成最优路径.然后,提出了拉格朗日松弛法对难约束进行松弛处理,并将松弛模型分解成两个子问题.结合次梯度算法、标号修正算法和k-最短路径算法设计了一个算法框架,以最小化上下界的差距寻找近似最优解,用改进的算法框架进行求解.最后将该框架应用于龙岩市新罗区进行了计算试验.结果表明,该算法能够找到相对间隙较小的高质量解,验证了该方法的有效性.     

基于Benders分解的鲁棒最短路算法

为了研究路段行程时间不确定条件下的最短路问题,采用区间数据表示路段行程时间,介绍了鲁棒偏差和鲁棒成本的概念,并据此给出鲁棒最短路的定义,运用鲁棒优化中的min-max准则构建了鲁棒最短路问题的混合整数规划模型。通过固定路径决策变量将鲁棒最短路问题分解为子问题和主问题,同时结合对偶理论给出子问题的对偶模型。在此基础上设计出鲁棒最短路问题的Benders分解算法,采用AMPL编程实现算法并调用CPLEX进行求解。并在一个仿真网络中对本研究方法进行了验证分析。研究结果表明,相较于传统最短路Dijkstra算法,本研究方法求得的鲁棒最短路在不确定网络中具有更强的可靠性,设计的算法迭代效率较高,能迅速缩小迭代范围并找到最优解。     

基于Mapinfo的最短路径混合搜索算法

在迪杰斯特拉(Dijkstra)算法的基础上,针对有较多节点和道路的大网络在求解最短路径时计算时间慢、扩展节点多的缺点,采用基于局部最优方向和A*算法的混合算法,利用局部最优方向法的结果,对A*算法的启发函数加以改造,可以减少扩展的节点数量,快速的找到一条最短路径.通过实验仿真证实了该算法的快速有效性.     

交通网络最优安全路径选择模型与算法

针对交通网络任意路段均可能发生中断的最小损失路径选择问题,提出交通网络最优安全路径选择模型,并设计了2种不同网络结构下最优安全路径选择算法.首先用模型计算任意一条路径上每条边中断后产生的从起点到终点最短替代路径长度的最大值,然后选择一条最短替代路径长度最大值最小且自身长度最小的路径.在网络中,当最短路径删除后该网络依然连通时,最优安全路径问题转化为最短路径问题,其计算复杂度为O(n2);当最短路径删除后该网络不再连通时,最优安全路径问题转化为最小最大问题,其计算复杂度为O(mn),且仅与网络中节点和边的数量有关.最后,结合交通网络的实际情况对最优安全路径进行了算例分析.     

基于最小分支剩余容量的矿井通风网络极值流算法

为计算矿井最大通风量,针对最短增广链算法随机选取增广链,造成增广链缺失和极值流偏小的问题,提出一种基于最小分支剩余容量的矿井通风网络极值流算法。该算法在选取增广链时,选择中间分支剩余容量最小的增广链进行增广;每次增广完毕后,优先选择与增广完毕的增广链包含相同分支的增广链进行下一次增广。利用Excel Solver解算模型与BA无标度随机网络进行仿真实验,结果表明该算法比最短增广链算法解算时间短,且避免了增广链缺失。研究结论为矿井最大通风量的计算提供理论参考。     

基于城市应急指挥系统的最优路径算法

城市应急指挥系统要求在事故发生时,计算出到出事地点的最佳路线的最短时间,其核心算法仍是最短路径算法.针对实际的城市道路网特点,对道路网络模型、道路拓扑结构和数据库结构进行构建.以优化的数据存储结构为切入点,在分析了经典的Dijkstra最短路径算法的计算速度瓶颈的基础上,提出了基于方向性的空间最优路径算法,使该算法具有更高的效率.     

基于蚁群算法求解物流订单派送问题

针对物流信息平台中的订单派送问题,研究了订单派送的单向性和路径最优特性,构建了路径选择模型,对费用最少和时间最短的双目标优化函数进行了分析,将基本蚁群算法进行了改进。通过对局部信息素进行外界人为的干扰,从而影响整个网络选择,使得路径选择全局最优,解决了基本算法在求解最短路径中计算时间长的问题。模拟结果表明,计算速度提高了30%。     

应用最小费用流求解活动网络时间-费用模型

提出了利用最小费用流原理求解时间-费用优化模型的方法.应用对偶理论将费用-优化模型转换为适用于状态算法求解的最小费用流问题,采用互补松弛定理和状态算法推出了由对偶问题最优解求出原问题最优解的等式,以一个实例说明了利用上述方法求解时间-费用优化模型最优解的步骤.所提出的求解时间-费用优化模型的算法,提高了求解问题的效率,可用于大型工程网络的费用优化.     

基于带随机网络的多种群粒子群优化算法求解多资源受限柔性作业车间调度问题

多资源受限柔性作业车间调度问题(MRC-FJSP,multi-resource constrained flexible job shop scheduling problem)是一类复杂的组合优化问题。针对以最小化最大完工时间为目标的MRC-FJSP,提出了一种带随机网络的多种群粒子群优化算法(MPSO-RDnet, multi-population particle swarm optimization algorithm with random network)。首先,设计了一种半主动解码和基于启发式规则解码相结合的新型解码方式,对原有解空间进行有效裁剪。其次,提出了基于关键路径的两种邻域结构,提高算法局部搜索能力;引入了基于随机网络的多种群策略,提高算法全局搜索能力;提出了面向算法搜索停滞问题的重新初始化策略,增强算法的鲁棒性。最后,采用MRC-FJSP基准算例SFTSP进行测试,验证了算法的可行性和有效性。     

用最小费用流的允许边算法求解指派问题

构造指派问题的最小费用最大流模型,并将基于对偶原理的允许边算法用于该模型,提出了求解指派问题的一种新算法。该算法按照互补松驰条件,通过修改已标号节点的势,在容量-费用网络中逐步扩大允许网络,并在其中增广流量,直至求得容量-费用网络的最小费用最大流,此最大流中的非0流边即对应于指派问题的最优指派。在迭代过程中,后续迭代充分利用了上一迭代的信息,有效节省了计算量。对于非标准指派问题,可以直接求解,而不需要先将其转化为标准形式。     

约束最优控制问题的磨光罚函数算法

针对约束最优控制问题,分析了已有惩罚函数算法存在的缺陷,在原惩罚函数的基础上,通过引进磨光参数,对原惩罚函数进行了光滑处理,构造了带参数的连续可微惩罚函数,将原带约束的最优控制问题转化为含参数无约束光滑的最优控制问题.利用微分方程解对参数的连续依赖性,得到了无约束条件下近似的极小值原理,提出了磨光惩罚函数算法,并证明了此算法的收敛性.该方法克服了传统简单惩罚函数不可微的缺陷,简单可行,易于实现.最后给出仿真实例验证了该方法的有效性.     

基于析取图的集束型设备建模与调度方法

针对处理腔带有缓冲且能处理不同种类晶圆产品的单臂集束型设备调度问题,提出了基于析取图模型的分枝搜索调度方法.首先将问题转换为单机调度问题,建立析取图模型,采用分枝的方法获得可行解空间.然后在此基础上,提出以最小完工时间的机械手最优动作序列为目标的分枝搜索算法.最后对调度算法进行了仿真实验分析.结果表明,该算法有效可行,同时说明了处理腔带输入、输出缓冲的集束型设备对于满足不同种类晶圆的生产、提高生产能力均具有较好的效果.     

混合蚁群遗传算法在车间作业调度的应用研究

提出了一种解决车间调度最短完成时间的有效的混合算法.将遗传算法与蚂蚁算法的融合,采用遗传算法生成信息素分布,利用蚂蚁算法求精确解,优势互补.应用该算法对Job-Shop车间作业调度问题的解进行编译,通过实例表明该算法是可行有效的.     

网络分解定理

作者在本文中提出了一条分解定理。按照这条定理，可将一大型电网络分裂成两个子网络．分别对每一个子网络进行分析计算，所得结果与对原网络进行分析所得结果一样。尤其是我们还可对网络多次进行分割，使网络的分析更加容易，更省机时。此外，此定理还具有多端网络等效变换的作用。     

基于无等待约束的供应链在线调度问题

研究了供应链在线调度问题.给出了在不改变已有工件调度的情况下,最早完成临时订单的算法,该算法在寻优过程中结合了微粒群算法的局部搜索能力,计算机仿真结果表明,在大规模订单的情况下,该算法同样能很快找到最优加工方案.     

非对称不确定性越库调度算法

在正态分布的模式下,对运输时间期望值进行修正,采用修正后的期望值计算确定性情形下的最优解以及不确定性情形下的现实解和最优解并分别加以比较,提出了期望值修正算法和基于修正期望值的启发式算法.采用最小化最大完工时间作为目标函数,研究了运输时间非对称不确定性条件下的直运物流调度问题.数值实验结果表明,因考虑了非对称性,所提出的修正策略的有效性和实用性较高.     

一种改进的基于云环境的蚁群优化算法

在研究标准蚁群优化算法的基础上,提出一种旨在改善网络路由的蚁群优化算法以应用于云环境下多元化复杂的网络结构环境.新算法在原有蚁群算法智能寻优的基础上,加入网络节点在网审查机制,实时判断网络节点是否在网,选择最优解路径.仿真实验表明,改进算法能有效地改善因为网络节点在网情况的多变性而造成的部分路径失效的情况,进而缓解网络拥塞.