SIHC:一种高效的时态图上k-core查询算法

许多实体之间的关系可以建模为时态图,其中每条边都与表示其发生的时间相关联,k-core是捕获密集子图的基本模型,在近些年得到了广泛研究.给定时间区间I=[s,e]和k值,时态图G上的k-core子图查询从区间I对应的快照图GI中返回相应的k-core子图.针对时态图中的k-core子图查询问题,现有方法是基于PHC索引(Pruned Historical Core-Index)的算法.对任意可能的k值,PHC索引维护了所有可能出现在某个时间区间的k-core子图中的顶点集Sk,且为集合中每个顶点存储了一组时间区间,用于判定该点是否属于给定时间区间的k-core子图.基于PHC索引查询k-core子图时,需要访问Sk集合中的所有顶点,并判断每个顶点的可满足性.由于Sk集合对应于最大区间快照图的k-core子图里的所有顶点,且实际中用户查询区间对应的快照图往往比最大区间快照图小得多,基于PHC索引的查询算法存在许多无效判断,需要对大量不在结果集中的顶点进行检测,且无效检测次数随着查询区间的缩短而增多,从而导致算法效率较低.针对该问题,本文提出一种新的索引,即最短区间历史核索引SIHC(Shortest Interval Historical Core Index).SIHC索引的基本思想是通过维护最短k核区间到顶点的倒排表,查询处理时,可基于用户给定的时间区间定位到SIHC索引中满足条件的区间,进而直接得到满足条件的k-core子图中的顶点,从而避免了基于PHC索引进行查询时所需的大量无效判断.我们从理论上证明了基于SIHC索引处理时态图上k-core子图查询的正确性,并设计了高效的索引构建算法.最后,基于真实世界的时态图进行了实验,实验结果表明本文提出的算法比现有算法快1~2个数量级.

基于机器学习算法的卷烟营销智能客户拜访策略研究

为提高卷烟行业客户经理的工作效率和服务质量,提出一种基于机器学习算法的卷烟营销智能客户拜访策略。在构建卷烟客户价值分类模型的基础上,利用K均值聚类机器学习算法对零售客户进行分类,合理设置LKH超启发算法和Dijkstra最短路径算法的参数,对客户经理拜访路径进行最优规划和智能导航。仿真结果表明,基于机器学习算法的卷烟营销智能客户拜访策略显著提高了客户经理人均拜访户数、商户满意度,大大缩减了户均在途时间和商户拜访服务覆盖周期。文中提出的策略有助于推动卷烟营销工作质量变革、效率变革和动力变革。

基于二分法和控制信息素量的改进蚁群算法

为弥补蚁群算法易陷入局部最优、收敛速度较慢等不足,提出一种基于二分法和控制信息素量的改进蚁群算法。在每次迭代结束时,利用二分法放弃行走路程较远的半数蚁群的信息素,使收敛速度得到提高;利用3-opt局部优化方法提高解的精度;通过控制信息素量动态调整蚁群选择路径的概率,避免算法早熟;将改进的算法应用于旅行商问题。实验结果表明,该算法在寻优能力、可靠性、收敛速度以及稳定性方面均表现出明显的优越性。

基于约束聚类和粒子群算法的多路径规划

大型物流中心物流管理信息系统在进行物流配送中,必须进行多配送中心车辆路径问题研究,用尽可能少的车辆,完成货物的配送,并使得行驶总里程最小。业界已经针对多中心路径规划中k条最短路径难问题进行了深入的研究,通过采用传统的聚类算法已经能够实现多路径规划问题,但是在现实多配送中心车辆路径规划中,运输工具的运输能力和用户的需求存在特定限制,本文在聚类算法基础上引入约束机制,将多配送中心问题通过聚类算法降维为单配送中心问题,并在此基础上引入粒子群算法求解单配送中心多路径规划的最优解。通过实验验证该方法的优越性,他比传统粒子群算法的收敛速度至少提升了n(配送中心个数)倍,为路径规划提出了新的解决思路。

基于偏离路径的煤矿水灾Yen-K最优路径算法

为矿井水灾提供最佳逃生路线,提高应急救援效率,首先引入当量长度,结合水流等巷道相关因素,求解到达安全地点的时间最短路径;其次根据一般矿井具有多个逃生出口的特性,提出一种基于偏离路径的煤矿水灾Yen-K最优路径算法,分别求出从源节点到每个目标节点的前k则最优路径;最后按照长度大小排序求得的所有路径,并结合矿井具体实例选取所需的前若干条逃生路线。在MATLAB环境下,对文章算法与传统的Dijkstra算法、K最短路径(KShortestPaths,KSP)算法进行仿真对比分析,结果显示改进后的算法在求解矿井水灾逃生最优路径时更具准确性和实用性。

一种基于QoS约束的kMUPP替换服务快速查找算法

动态服务组合运行过程中,当发生服务失效时,失效恢复机制通过切换到替换路径来保证整个服务正常执行。本文提出一种WSC_KUPB算法利用k-Shortest路径问题来研究最大效用路径问题,以自定义的服务质量效用函数为依据,选取有最大总效用的优化路径作为替换路径。实验表明,该算法能够在时间和可用性上很好地折衷。

K最短路径算法综述

为了进一步推广应用K最短路径(K shortest paths,KSP)算法并为深入研究该类算法提供相关资料。根据路径限制条件,将KSP问题分为一般KSP问题和限定无环KSP问题,归纳总结了求解每类KSP问题的基本思路、研究现状和研究进展。KSP问题非常复杂,在实际应用中所需处理的数据规模非常庞大,使得算法效率成了评价KSP算法的一个重要指标。在分析各种KSP算法时尤其关注其时间复杂度,指出KSP问题未来的研究方向,将为满足多约束的最短路径等问题的研究提供有益的参考。

基于D-K算法的煤矿水灾多最优路径研究

矿井水灾时选择合理的逃生路线,需要考虑水及巷道其他因素的影响,引入当量长度来求解到达逃生地点用时最短最安全的路径。Dijkstra算法可求解从源节点到目标节点的最短路径,K则最优路径算法可求解从源节点到某一目标节点的前N条最优路径,矿井水灾时,为了避免拥挤,同一地点工作的人员可选择多个逃生井口进行逃生,但从源节点到某一目标节点的前N条最优路径并不一定是到其他逃生井口的前N条最优路径,基于这种思路,在Dijkstra算法的基础上,提出一种从源节点到其他所有逃生节点的前N条最优路径的新方法,并结合矿井具体实例,与Dijkstra算法和K则最优路径算法比较,用MATLAB仿真实现。

基于前K最短路径的输电断面搜索新算法

过载支路切除引起的潮流转移是导致连锁过载跳闸的重要原因。本文分析了过载支路切除后的潮流转移特征,引入了潮流转移系数(FTF)的概念,并给出了输电断面新的定义。根据潮流转移的路径特征,给出了一种快速搜索输电断面的新算法。该算法通过把实时的电力网络转化成拓扑图,基于动态规划理论,通过在一个以过载支路为中心的拓扑子图内快速搜索出过载支路两端点间的前K条最短路径,并最终找出受潮流转移影响较大的输电断面,把对整个系统的安全性分析缩小到一个输电断面内,极大地减少了进一步分析的工作量,有利于防止连锁过载跳闸的发生。中国电科院CEPRI36节点系统的仿真结果验证了该算法的有效性。

基于多路径的城市轨道交通网络客流分布模型及算法研究

城市轨道交通网络形成之后,为实施"一票换乘"需建立轨道交通自动售检票清算管理中心,进行客流信息统计和票务收入清分,而清分的核心在于解决客流在网络上的分布问题。本文结合城市轨道交通系统的基本特性,提出一种考虑乘客多路径出行选择的客流概率分布模型,并设计基于深度优先的路径搜索算法。该模型既体现了乘客出行阻抗最小化的选择心理,又反映了路径多样化的实际情况,具有较强的实用性。最后通过北京轨道交通网络实际客流数据验证模型和算法的有效性。

综合运输体系下快捷货运网络流量分配优化模型及算法

研究综合运输体系下快捷货运网络流量分配优化问题。基于服务水平的概念构建综合运输体系下的快捷货运网络,网络中包含运输方式、服务水平各不相同的多种运输服务。给出一种求解联弧权重均为正值的有向网络中任意两点间k短路的Double-sweep算法,并对通过联弧时间为随机变量的情况进行讨论,该算法以VisualC++语言实现。以网络中两点间k短路作为可选径路集,构建快捷货运网络流量分配优化模型,模型在满足需求服务水平的前提下以成本最小化为目标,且考虑了交通运输系统的外部影响。模型可采用Lingo 8.0进行求解。若干算例表明,给出的模型及算法可以用于求解实际规模的问题。

物理节点可重复映射的虚拟网映射算法

该文在已有的映射算法基础上,结合K短路径的思想,改进了链路映射过程。算法通过多次搜索K短路径,寻找满足虚链路带宽需求的物理路径,有效地提高了虚链路的映射率。同时,根据虚拟网映射特性,针对节点映射过程,提出了物理节点可重复映射的映射算法,即在同一虚拟网映射过程中,物理节点可接受多个虚节点的映射。算法不仅减少了部分虚链路的映射过程,降低了映射的复杂度,而且节约了链路映射的成本,使物理网可以接收更多的虚拟网请求,有效地提高了映射效率。模拟实验表明,算法在执行时间、映射成功率以及映射收益等指标上都有着明显优势。

基于图论的可重构制造系统单零件流水线构形优化

获取各生产周期内的最优和K-1个次优(K优)单零件流水线构形,是可重构制造系统构形选择中一个重要的优化问题。给定零件的工序优先图、工序和工位操作的关系以及各工位操作的可选设备,该流水线构形优化问题即确定工作站数量,选择各工作站内的机床类型和数量,选择并分配工位操作,以最小化流水线构形的资本成本。将寻求满足功能和产能约束、空间约束和投资限制的K优构形问题建模为关联所有可行工位操作序列的复合增广有向图上的约束K最短路径问题,获得K优解。最后,通过案例研究验证了该方法的有效性和优越性。

多AGV调度系统中的两阶段动态路径规划

为缩短AGV系统的研发周期、降低研发成本,寻求能适应不同地图的通用调度策略以及增强对实际调度任务和故障的鲁棒性,提出了一种两阶段动态路径规划策略.对多AGV调度系统应用两阶段控制策略采用动态路径规划进行路径生成,实时对多个AGV同时规划其路径,并通过启发式算法实现路径优化.通过系统仿真证明,该策略很好地提高了AGV调度系统的柔性,是一种能适用于不同地图的通用调度策略.

考虑车流时空分布不均衡的货物列车开行方案优化研究

为适应货主动态需求和运到期限要求,采用动态车流组织方法进行编组方案调整、列车运行方案与车流挂线的综合优化.考虑车流时空分布不均衡性,结合基本运行图架构,运用时空网络描述车流组织动态过程,考虑车流组织过程时空连续性、车站与线路时空能力及运到期限等约束,在静态车流组织优化模型目标基础上考虑车流到后待解与编后待发的延迟费用,构建货物列车开行方案整数规划模型.基于K短路构造初始解,依据列车能力利用率阀值评估方案,从而调整车流改编方案搜索邻域解,设计模拟退火求解算法.实例研究表明,相比静态模型,所建模型的决策变量能更清晰地反映车流对车站线路时空能力的占用状况,优化方案能有效匹配车流时空分布不均衡性,有利于车流接续与流线结合.

城市公交查询系统的研究与设计

给出了城市公交查询系统的空间数据结构。在Dijkstra算法的基础上,借助人工智能中状态空间搜索和动态截枝的思想,提出了状态空间搜索求第K最短路径的智能搜索算法。该算法能对所查询的交通路线与乘车方案等用电子地图的形式给予显示,并更换不同城市的地图。测试表明,该系统具有速度快、多媒体显示、维护方便、通用性强等特点。

基于合理多路径的路径选择方法的研究

本文不是只给出一条基于单目标的“最优”路径供司机采用 ,而是提供多条具有不同属性的“合理”的候选路径供司机选择 ,从而就更切合司机的实际需求。我们采用了“重叠惩罚”法作为有关k合理路径的算法 。

多目标最短路径模型及算法

为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.

带时间窗口的多式联运模型与算法

以带时间窗的多式联运模型为基础,考虑节点间的运输时间、节点处的运输方式转换时间以及可能发生的货运延迟,以包括运输成本、转运成本和时间偏离惩罚成本在内的总成本最小为目标函数,建立基于满意时间路径的多式联运模型。在算法上,构造了基于K最短路的改进遗传算法,通过3个算例说明多式联运的运输路径与运输方式搭配可以不是唯一的,为多式联运的相关研究工作提供了理论基础。

一种不共享风险的双路径选路算法

光网络中,为一个连接请求建立连接时,从光路保护方面来说,不仅需要为其寻找到一条工作路由,而且需要提供一条备份路由,并要求这两条路径物理分离,对于光网络还提出了共享风险链路组的概念。该文提出一种新的启发式算法,完成两条路径共享风险链路组分离,同时总费用尽量低,并对算法进行了分析与仿真。