考虑综合成本的常规公交客流分配方法

为改善常规公交客流数据传统调查方法效率低、准确性差,以及常规公交客流分配时对出行成本考虑不全面、个体间出行成本存在较大差距的缺点,开展了考虑综合成本的常规公交客流分配方法研究。以数据即服务为基础开发的手机信令数据平台作为常规公交客流分配数据来源。通过经纬度坐标匹配,得到用户与交通小区之间的空间关系。利用数据仓库工具筛取数据字典索引,界定时间、速度、起终点类型等数据参数,通过时间匹配、路径匹配进行交通方式识别,将用户比例外推扩样至全国人口,得到常驻居民早高峰常规公交通勤起讫点(origin-destination,OD)量。分析常规公交客流个体的出行时间成本、拥挤成本、票价成本,建立以个体利益最大为原则、考虑综合成本的常规公交客流分配模型。将交通小区间常规公交客流分配问题转换为有向赋权图路径选择问题,并采用深度优先搜索与连续平均法混合算法求解,进行常规公交出行方案筛选以及客流分配。选取哈尔滨市典型交通小区为案例,开展常规公交客流分配,并与传统Logit路径选择概率模型分配结果、人工调查结果对比分析。结果表明:模型分配结果与人工调查结果的平均绝对百分比误差为4%,Logit模型为17.5%。模型分配客流后个体出行成本极差、方差、总和分别为0.03,0.0001,1108.35,Logit模型分别为3.28,1.58,1127.02。验证了模型分配客流的准确性以及考虑综合成本的必要性,分配客流后个体出行成本差距更小,更符合利益最大原则。

钢铁企业电网中光伏发电的智能管控研究

光伏发电的建设有力推动了钢铁企业的经济发展,钢铁企业光伏电站宜采用“自发自用”的运行方式进行设计和消纳。光伏发电接入厂区电气系统后,控制系统需自动识别出在不同运行方式下各用电负荷所对应的电源点,也就是负荷与电源点之间的拓扑关系。为了实现该功能,对基于改进型深度优先搜索算法(DFS算法)的快速动态拓扑识别技术进行了研究,实现了任意电网架构下的最优拓扑路径检索。根据拓扑识别出来的实际运行方式,电网智能管控系统可对光伏发电进行功率实时调控和功率预测调控,以实现综合利用厂内余能、余热以及新能源的目的。

复杂三维CAD装配模型特征信息提取技术研究

针对飞机、大型输送机等复杂三维CAD装配模型具有装配零件多,配合复杂,在提取装配体特征信息过程中,有信息提取不完整、深度不够的问题,提出一种复杂产品装配特征信息提取的方法,该方法以CATIA软件为平台,采用构件的应用编程(Component Application Architecture,CAA),二次开发快速提取特征信息功能。结合多叉树前序列遍历思想,深度优先搜索的算法,逐层深入,可以完整提取多层嵌套的复杂装配体的配合和约束信息,充分利用复杂三维CAD装配模型特征信息,更有力的支持装配工艺规划。同时,通过选择输送某种民航飞机机翼的输送机为例,验证此方法的可行度。

基于深度优先搜索算法的电力系统生成树的实现方法

电力系统仿真验证往往希望通过拓扑结构图直观地分析网络的潮流分布以及动态特性。然而电力系统机电暂态过程仿真软件如BPA、PSS/E和PSASP都不能自动地根据电力系统的电气联系合理地布置网络中的元件,而需要人为地调整各元件的位置来形成一个直观的电气接线图。这种人为手动调整,不仅给仿真增加了工作量,更有可能带来更多的人为误差。为此,文中提出了基于图论的深度优先搜索(depth first searching,DFS)算法,依据电力系统的电气拓扑结构形成电力系统生成树的实现方法。用文中方法生成的IEEE9节点算例系统的可视化界面验证了该算法的有效性和准确性。

电力系统震后网络连通性研究

文中针对电力系统网络的震后连通性开展研究,在电力系统网络基本模型基础上,增加网络单元的两值工作状态假设,建立了电力系统网络连通性分析模型,提出了电力系统网络连通性模型的邻接表存储结构,给出了深度优先搜索的基本原理,形成了基于邻接表的深度优先搜索算法。用该方法分析了某区域电网在汶川8.0级地震后的网络连通性,并对计算结果进行了讨论。

基于J2EE平台的Java构件库的研究和实现

构件库是构件复用的重要部分。以项目为背景,提出了一种 Java 构件库系统的设计与实现方案。介绍了基于 MVC(Model View Control)的构件分类树结构,描述了该结构下的构件表示模型,阐述了分类树深度优先遍历的构件检索方法和结合构件规约和可控词汇表的规范函数匹配方法。该构件库系统提供了一种语义和语法相结合的经验模型。

基于深度优先反向搜索算法确定有效路径集合

基于最短路径中任意路段因发生交通事件而失效时的替代路径搜索,合理界定了有效路径的阻抗值范围。参考深度优先算法和有效路径Dail算法离终点越来越近的思想,提出了一种从终点出发,反向搜索前置节点的多条有效路径搜索算法。算例结果表明:该算法能自动识别与路网结构相关的有效路径阻抗值范围,且能快速找到阻抗范围内的有效路径集合。

生成有向图中全部简单回路的一种有效算法

在研究有向图中全部简单回路现有算法的基础上,综合各算法的优点提出一种新的算法。算法的主要思想是对图中顶点进行深度优先搜索,在搜索过程中采取措施避免同一回路的重复出现,同时记录有用信息避免对顶点的重复访问,从而提高算法的效率,还给出了算法的证明和实例应用。算法结构清晰简单,方便转化为计算机程序。

用独立通路法确定矿井通风网络的极值流

确定矿井通风网络极值流的常用算法有Ford-Fulkerson法、Edmonds-Karp法和Dinic法。所谓独立通路就是采用深度优先搜索法在找通路的过程中,后面的通路至少要含有一条前面的通路所不含有的分支。独立通路法确定网络的极值流,就是利用找独立通路的思想来找增广路,找增广路时每次至少有一个分支达到饱和。从网络的源点开始进行寻边,找分支的可增广量为最大的出边,将该出边的末节点作为新的寻边始节点,继续找可增广量最大的出边,该搜索过程一直到所寻找的分支的末节点为网络的汇点为止,一条增广路即一条通路确定完毕,将该通路中分支的最小增广量作为通路的增广量对通路的各分支进行增广。增广后至少有一条分支达到饱和,删除饱和分支,用导出的网络继续找新的增广路并增广。

回溯算法在燃耗计算中的应用

采用解析解的线性核素链方法在进行燃耗计算时首先根据分治和递归的策略将燃耗矩阵进行解耦,形成具有马尔科夫特性的线性核素链。然后通过对每一条链的解析计算得到所有相关核素的核密度、活度、衰变热等数据。然而在核素链的构建过程中需对每一个可能的核反应路径进行计算。欲保证计算的精度和效率,需寻求一种既能覆盖所有反应路径、又能根据问题描述和约束条件进行自动搜索的算法。本文通过对各种搜索算法的分析和比较并根据燃耗链构建过程的特点,最终采用回溯算法进行深度优先搜索,在搜索过程中完成燃耗链的构建和计算,从而形成问题相关的、具有高精度的自适应燃耗算法。同时结合燃耗过程和回溯算法的特点进行了解空间和时间复杂性的分析。将所开发的多群点燃耗计算程序与蒙特卡罗输运计算程序MCMG-Ⅱ进行耦合,通过对中国实验快堆首炉堆芯燃耗的计算和分析完成程序的初步验证。

迷宫搜索算法的比较研究

研究面向搜救的应用,将事故环境抽象为一个迷宫,通过仿真实验比较研究了深度优先搜索算法和三种不同启发式函数的A*算法在Perfect迷宫中的应用,并分别将深度优先搜索算法和A*算法用于实际迷宫中进行实现与比较。在实验中,迷宫环境对机器人是未知的,而由于迷宫环境的特殊性———未知的迷宫环境中很少有不会碰撞的路径,从而增加了机器人搜索的难度。通过仿真实验对比了不同启发式函数的A*算法与深度优先搜索算法的性能,最后得出在迷宫搜索中A*算法要优于深度优先搜索算法;同时,在实际迷宫中实现了深度优先搜索算法与A*算法的搜救应用。

通过八数码问题比较搜索算法的性能

搜索算法的核心在于搜索策略的制定。一般的搜索算法采用无信息指导的搜索策略,如深度优先搜索(DFS)和宽度优先搜索(BFS),还有一些搜索算法采用了启发式信息指导的搜索策略,如A*算法。不同的搜索策略会使得搜索算法的性能有很大的差异。使用以上3种搜索算法实现八数码问题的求解,分析和比较三者所表现出来的性能,同时指出3种搜索算法的特点和应用范围,最后给出分析结论以指导开发和使用更加高效的搜索策略。

基于改进A^(*)算法的机器人全覆盖衔接路径规划

为解决A*算法在规划衔接路径时转角多、路径不平滑、深度优先搜索(DFS)算法规划衔接顺序的随机性和距离较大的问题,提出改进邻域扩展A*算法和经预处理的DFS算法结合的衔接路径规划方法。首先,对A*算法搜索范围扩展至24邻域,经二次数量优化后得到最终邻域搜索节点。其次,设计具有双层位置导向信息的评价函数,对DFS添加节点预处理的步骤。实验结果表明:所提改进A*算法在路径长度、搜索节点数量、规划时间上均优于传统A*算法,且与改进DFS算法结合所得衔接路径表现更优。

快速实用的配电网电容器优化投切算法

利用深度优先搜索算法将配电网分解为多棵局部树,在局部树中采用无功就地平衡原则缩小了电容器投切的解空间,并取损耗最小方案为优化方案。由于局部树组中局部树根节点的处理与实际情况不符,提出通过增加部分电容器投入组数来快速优化局部树组的方法。局部树和局部树组优化过程中采用了前推回推法计算系统潮流,保证了算法的快速收敛。以IEEE69节点和409节点网络为算例,验证了该方法的有效性。

求解三维装箱问题的多层启发式搜索算法

文中提出了一个高效求解三维装箱问题的多层启发式搜索算法.该算法基于块装载的思想,按照块选择算法确定每个阶段采用的块,然后以一种固定的装载方式装载块,直到无法继续装载.文中的主要贡献在于发展了一个有效的复合块生成算法,特别的,提出了基于多层搜索的块选择算法,该算法用多层搜索来评价可行块,然后选择最合适的块进行装载.对1500个三维装箱问题测试数据的计算结果表明,提出的算法几乎在所有测试数据上的填充率都超过了目前已知的优秀算法.

基于深度优先遍历算法-回溯算法的公交网络限时免费换乘优化模型求解

基于青岛市"限时免费换乘"政策理念,建立费用与时间、换乘次数的关系模型,采用深度优先遍历与回溯相结合的算法,寻找限定时间内最短时间与超限时条件下最低费用路径,给出起讫点间的最优路径方案。结合车站智能诱导发布平台对算法进行验证。运行结果表明,DFS-回溯算法在数据规模较大的情况下,比蚁群等全局搜索算法效率高,可既快又准地找到最优路线;基于该算法的最佳路径模型方案,可准确的为乘客提供最大选择便利性,实现公共交通资源利用最大化。

改进遗传算法在多约束QoS动态组播路由选择中的实现

具有多约束Qos动态组播路由选择问题,实质上是一个NP完全问题。在参见文献[1-2]的基础上,提出了一种改进的遗传算法。在初始化群体阶段采用改进的深度优先搜索机制,克服了局部搜索能力差的缺点,在交叉、变异阶段采用类似罚值函数的方法,加快了收敛速度,同时用C++编程语言实现了遗传算法在多约束QOS动态组播路由选择问题。

通信网络连通性分析方法比较研究

通信系统作为生命线系统的重要组成部分,在国民经济生活和震后抢险救灾中发挥着关键作用,但是其震后功能评估的研究才处于起步阶段。本文首先研究了通信网络的拓扑规则,并基于此给出了建立通信网络图模型的方法;然后,以抗震设防烈度为7度的两个不同规模城市为研究对象,以计算时间和收敛速度为指标,比较研究了Warshall算法、深度优先搜索算法和宽度优先搜索算法对通信网络连通性分析的适用性。分析结果表明:三种方法均能够准确评估通信网络各节点间的连通状态,但宽度优先搜索算法在计算耗时上优于另外两种算法,且网络越复杂以及模拟次数越多优势越明显,最适用于通信网络的连通性分析。

基于农田环境的农业机器人群协同作业策略

为合理分配农业机器人群协同作业中各机器人的工作量与工作区域,提高机器人群协同作业的整体效能与工作效率,该研究提出一种复杂环境下异质农业机器人群的任务分配及全区域覆盖策略。在考虑农业机器人异质性的基础上,以机器人团队整体效能最优为目标进行任务分配并确定各机器人的工作量。根据农场实际工作环境建立一级分区的概念,在栅格化环境建模与障碍物膨胀处理的基础上,在一级分区内部建立二级分区的栅格分区和分区合并规则,简化农田中的复杂工作环境;将遗传算法与混合粒子群算法相结合改进遗传算法交叉操作,建立遗传算法染色体种群多样性的概念,并综合考虑遗传算法染色体适应度值的差异以及种群多样性阶段设置自适应交叉变异概率,继而利用改进的遗传算法解决深度优先搜索算法在一级分区与二级分区间的遍历顺序问题;设置深度优先搜索算法在二级分区内的路径搜索规则,并在栅格图内遍历的同时根据各机器人的工作量分配其工作区域,设置机器人在其工作区域中的遍历规则,实现机器人群对农田的全区域覆盖。仿真试验结果表明,改进的遗传算法所得到的遍历各分区的路径长度与收敛迭代次数较传统遗传算法分别减少了2.8%与69.5%,较模拟退火算法分别减少了9.3%与19.0%;包含3、5、7、9和11个障碍物的5幅环境地图中,机器人群遍历工作区域的总面积重复率分别为6.3%、8.9%、16.7%、21.7%和23.4%。在4种面积相等的异形农田中设置相同数量的障碍物进行验证试验,结果表明,机器人群总遍历面积重复率分别为16.7%、13.1%、11.9%和6.7%。机器人群协同作业场地试验结果表明,4个试验机器人均可在规定的时间要求(25 min)内完成各自工作量,遍历面积重复率分别为5.77%、4.14%、6.75%和4.85%。研究结果可为复杂环境下农业机器人群协同作业策略提供理论支撑。

采用DFS策略的进路搜索算法研究

给出并描述计算机联锁软件中站场型数据结构的形式。介绍采用深度优先搜索策略进行进路搜索的算法并给出该算法所涉及的对象,同时详细阐述对进路搜索过程以及需要完成的任务。采用这种数据结构及算法有利于联锁程序的标准化和模块化,有利于提高系统的可靠性和安全性。