基于回溯算法的轻轨排班问题的研究

根据目前地铁(轻轨)行业中工作轮班的情况,每天有m个人工作,n个人休息.在保证工作和休息合理交替的前提下,要求m+n个司乘人员在m+n天内分别轮完m+n个不同的任务,以达到相对公平的目的.本文通过建立数学模型,结合回溯算法和深度搜索,完成任务序列的求解.最后考虑最坏情况下的近似解,并计算回溯算法的时间复杂度.     

HTN规划中面向多计划生成的顺序任务分解算法

顺序任务分解算法（OTD）是层次任务网规划（HTN）中的一种高效求解算法．由于算法中的计划生成采用一次性回溯机制,每次求解过程只能产生一个可行计划．文中提出了一种能够快速生成多个可行计划的回溯算法．该算法采用分段回溯的计划生成机制,充分利用了求解过程中生成的局部解序列,从而能够一次性地快速生成多个可行计划,为寻求优化的计划和进行计划的评估提供更为有效、灵活的支持．     

编组站静态配流的约束传播和启发式回溯算法

为了提高阶段计划的编制效率,针对编组站静态配流字典序多目标累积调度模型,设计了迭代、约束传播和启发式回溯的混合算法.该算法根据多目标的字典序将模型分为3层:第1层为配流成功的出发列车优先级总和最大化,第2层为出发列车车流来源总数最少化,第3层为车辆平均停留时间最短化.每层先通过约束传播算法化简模型、缩小解空间,再通过启发式回溯算法和约束传播技术联合快速求解.上一层的最优解作为下一层的初始解,并动态增加避免上一层目标退化的约束,迭代求解每层的最优解.通过某编组站实际数据验证表明,本算法耗时小于20 s,满足现场对阶段计划编制的实时性要求,且求得的配流方案优于其他算法.      

细小器官分割的可回溯三维种子填充新算法

提出的多堆栈种子填充算法考虑了像素之间的相关性,通过对堆栈的合理设置与灵活应用,减少了不必要的回溯和像素的判读,能达到从空间任一切片的任一种子点出发,实现三维组织中所有三维连通区域的填充,填充效率高且效果好。     

一种基于时空距离的带时间窗车辆路径问题算法

带时间窗的车辆路径问题是典型的NP难题,一种常用的求解方法是先对顾客分组,后进行路径优化的两阶段启发式算法. 传统算法在顾客分组时主要考虑顾客的空间位置关系,但是忽略了顾客对服务时间窗口的要求. 本文同时考虑顾客的时间和空间特性,提出了一种基于时空度量的顾客分组方法. 在路径优化阶段,本文提出了一种禁忌搜索算法来进行求解,该算法中禁忌的对象不是解,而是这些解的目标函数值的区间,以便于提高收敛效率. 作为验证,本文以Solomon标杆问题集为算例进行演算,结果表明,在窄时间窗约束下,基于时空距离的两阶段启发式算法明显优于基于空间距离的算法,且部分算例的解达到了国内外已发表的最好解.     

���ڰ����ij��е�·�г�ʱ��Ԥ��

已有旅行时间预测方法多是针对高速公路、城市快速路和主干道路的路段,而针对城市一般道路,及路径旅行时间预测的研究则相对不足.本文提出一种基于案例的旅行时间预测算法.算法的基本原理为,在轨迹数据建模的基础上,建立动态更新的、包含多个属性的历史旅行样本数据库,然后根据出行时间及环境信息从案例库查找匹配案例,其结果经过一定修正用于预测路径旅行时间.与基于路段的旅行时间预测方法相比,该算法具有较强的鲁棒性和可移植性,受空间路网和数据样本量的影响较弱;并且在相同数据样本量和路网空间覆盖率的情况下,该算法预测精度高于对比算法.     

适于营运车辆超速时空特征分析的改进DBSCAN算法

营运车辆的超速违法行为具有较大的危害性,分析其超速的时间和空间分布规律,对于加强道路运输安全管理具有重要意义.鉴于此,提出一种适于营运车辆超速时空特征分析的改进DBSCAN算法,通过添加时间半径达到对时间维度的支持,对营运车辆超速多发点在时空维度上进行聚类,揭示营运车辆超速违法行为的时空分布特征.然后在广东省重点车辆监控平台上对算法进行验证.实验结果表明,该算法能够快速对超速数据进行时间和空间维度的聚类分析,有效完成超速路段和时段的排查,为查找营运车辆超速常发路段和时段提供了新的分析方法.     

求解双目标带时间窗车辆路径问题的蚁群算法

针对运输网络为多重图的双目标带时间窗车辆路径问题设计了蚁群算法.首先,建立了多重图的双目标带时间窗车辆路径问题的数学模型,提出了针对该问题解的搜索空间构建方法,定义了一种综合考虑各优化目标、时间窗和信息素等启发信息的状态转移概率公式. 为了对比说明该算法的有效性,同时设计基于NSGA-II的多目标遗传算法.针对本文算例,对蚁群算法中的各参数进行了敏感性分析,根据分析结果设定算法参数,获得了算例的Pareto最优路径集,同时与NSGA-II算法及相关文献算法针对运行时间、收敛性和群体多样性进行比较.结果显示,本文设计的蚁群算法在这3个指标上均明显优于NSGA-II算法;在相同蚂蚁数量情况下,本文的算法在收敛性和群体多样性方面优于相关文献算法.     

基于时空行为规律挖掘的公交乘客分类方法

应用智能公交系统(APTS)提取个体乘客出行信息，构造了公交出行链，研究了基于时空行为规律挖掘(STBRM)的公交乘客分类方法；应用时间序列表征乘客出行时间特征，利用互相关距离(CCD)算法计算了个体乘客出行时间规律；应用带噪声基于密度的空间聚类(DBSCAN)算法，挖掘了个体乘客的出行空间规律；依据出行强度和出行时空规律，将乘客划分为极少出行、时间规律、空间规律、时空规律和不规律等5个群体；以出行天数、类似上车时间数量和类似上车站点数量为聚类指标，应用K-Means++算法将乘客划分为高规律、中规律和低规律3类，比较了本文提出的STBRM方法和K-Means++聚类方法的分类结果，揭示了2种方法分类结果之间的关系。研究结果表明: 当时段划分长度取5 min，时间规律性判断阈值取3.0时，利用CCD算法识别时间模式规律乘客的效果最佳，与常用的DBSCAN算法相比，识别率提升了14.64%；增加时间窗长度能够提高时间、空间模式规律判定结果的稳定性；时间窗长度达到3周后，空间模式规律的乘客比例下降趋缓，达到6周后趋于稳定；时间窗长度达到2周后，时间模式规律的乘客比例增长趋缓，达到4周后趋于稳定；时间规律、空间规律和时空规律等3类乘客数量仅占总乘客数量的30.4%，但其出行量占到了总出行量的84.7%，公交依赖度很高，应作为公交机构重点保障的对象；本文提出的STBRM方法与K-Means++聚类方法的分类结果具有较强的关联性，规律性极高或极低的群体高度重合。      

考虑转向延误的最短路径的节点标号算法

拥堵时段车辆在城市路网中交叉口处的延误甚至会大于其在路段的行驶时间,因而拥堵情况下在城市路网上应用不考虑转向延误的最短路径算法无法反映真实的交通状况.分析既有的考虑转向延误的最短路径算法,扩展网络法因过大的时间和空间开销而欠缺实用性,其余算法包括对偶网络法、节点标号算法和弧标号算法本质均为求包含节点权重和边权重的最短路径问题,最后求解均为节点标号算法.对典型节点标号算法Dijkstra算法进行改进,通过记录节点的紧前节点完成转向判别,并通过最小堆优化将该算法的时间复杂度从O(n2)优化为O(nlogn),并给出算法的数据结构,完成了软件编码,并通过计算实例对算法进行了验证.结果表明:考虑交叉口延误后城市路网最短路径发生变化,同时经过堆优化后算法的时间复杂度下降.     

阻塞流状态下城市快速路交通流时空特性

根据时间序列中的自相关函数法,判断交通流量、时间占有率与平均速度的时间序列的平稳性。根据混沌分析中的G-P算法,将非平稳的交通流参数时间序列转化为平稳的交通流参数时间序列。引入了互相关系数的概念,在阻塞流状态下,计算了上游断面对观测断面以及观测断面对下游断面的互相关系数,并应用K-S检验判断阻塞流状态下城市快速路进出口匝道的车辆到达特性。研究结果表明:交通流量和时间占有率属于非平稳时间序列,平均速度属于平稳时间序列;当时间延迟分别取2、3、5min时,在阻塞流状态下,重构的交通流量相空间嵌入维数为4;观测断面的交通流参数不仅受相邻上游断面交通流参数传递的影响,而且也受相邻下游断面交通流参数回溯的影响;在阻塞流状态下,城市快速路进出口匝道车辆到达特性符合负二项分布。     

求简单有向图所有基本回路的强核图论算法

求系统动力学模型的所有反馈环等价于求对应的简单有向图的所有基本回路，其核心问题是算法的时间复杂度，针对这一问题，提出强核的概念，基于强核概念设计了求简单有向图所有基本回路的算法，给出相应算例，并分析了算法复杂性．在时间复杂度上，本算法优于基于核概念的有向图的行列式算法。     

新型蚂蚁算法时间复杂性与鲁棒性研究

在研究新型蚂蚁算法理论的基础上，进一步对新型蚂蚁算法的时间复杂性与鲁棒性进行实际计算与研究，研究出蚂蚁移动Mlog2N（M为边数，N为结点数）步后，能找到QoSR的较优解，该算法的时间复杂性为O（MNlog2N）．对该算法的鲁棒性进行分析，证实了在关键结点失效后，该算法仍能找到新的QoSR，并发现随着关键结点失效增多，再找到新的QoSR的QOS参数值急剧下降．     

一种改进的最小属性约简算法

最小属性约简是粗糙集理论中的一个重要内容,通过对属性约简算法的研究,指出基于U/{a}划分的最小属性约简算法中的不足,并提出了一种改进的最小属性约简算法.该算法以基于等价类的方法对论域进行压缩,有效地降低了算法的空间复杂度,用基于核的方法求解最小约简,从而保证可获得最小约简.实验结果表明,该算法具有复杂性低、存储空间小和效率高的特点,是一种有效的最小属性约简算法.     

基于类间和类内方差的快速二维阈值分割法

为了提高二维阈值分割法的处理速度,提出二维类间方差最大法的快速实现方法.首先,将二维最佳阈值（s*,t*）的求解拆分成两个一维最佳阈值s*和t*的求解,并引入类内距离的定义,提出新的最佳阈值判别式.其次,将原二维直方图分成M×M个区域,合并每个区域为一点,并构建新的二维直方图,在其上应用本文改进的阈值判别式D（s*,t*）求解,得到分割阈值所在的区域编号.最后,在该区域内再次使用D（s*,t*）求解得到原始图像的最佳分割阈值.理论分析及针对不同信噪比的多幅图像的实验结果表明,本文方法的分割错误率低于原始二维Otsu法,且将原算法的时间复杂度由O（L4）降为O（L1/2）,空间复杂度由S（L2）降为S（2L）.      

A FAST ALGORITHM FOR EXTREME FILTER OF 2D IMAGE

ＡＦＡＳＴＡＬＧＯＲＩＴＨＭＦＯＲＥＸＴＲＥＭＥＦＩＬＴＥＲＯＦ２ＤＩＭＡＧＥＸｕＬｅｉ（许磊）ＬｉＪｉｅｇｕ（李介谷）ＬｉＷｅｎｓｈｕｎ（李文舜）（ＩｎｓｔｉｔｕｔｅｏｆＰａｔｅｒｎＲｅｃｏｇｎｉｔｉｏｎ＆ＩｍａｇｅＰｒｏｃｅｓｓｉｎｇ，Ｓｈａｎｇ...     

基于复杂性的多扇区移交策略优化

现有多扇区移交间隔管理研究往往忽视扇区复杂性，可能出现扇区局部复杂性不均衡等问题，对空域造成一定安全隐患。本文充分考虑多个管制扇区复杂程度，提出一种新的管制移交间隔优化方法。首先，基于扇区之间复杂性的相互影响关系，建立大型区域管制中心多扇区网络模型。其次，提出航空器进入多扇区边界时刻调整，航空器进入各个扇区时刻调整以及航空器高度层重新配备等3种策略，建立以多扇区复杂性的均值、均衡程度和航空器总延误为目标的移交策略优化模型，并采用多目标遗传算法进行求解。最后，基于北京区域管制中心(ZBAAAR)的实际运行数据进行仿真分析。结果表明：3种策略可使复杂性均值分别降低2.2%,2.8%,6.0%，可使复杂性均衡程度分别提高1.76%,1.83%,1.38%，基于航空器进入时刻控制的两种策略导致航班平均延误时间分别为-295 s和-214 s，验证了模型及算法的有效性。     

基于分组优化和矩阵运算的自动排课算法

为解决目前高校自动排课系统设计复杂、排课效率低的问题,提出了一种基于分组优化和矩阵运算的自动排课算法.该算法首先对课时段进行分组优化,然后引入矩阵的迭加匹配运算,最终实现自动排课.结果表明,该算法能高效、快速、优化地实现自动排课,并简化了程序的复杂性.     

基于四元数的声压振速联合方位估计算法

常规MUSIC波达方向估计算法的缺点是不能处理相干信号.针对这一情况,文中引入了四元数理论,建立了二维矢量水听器的四元数输出模型,并在此基础上提出了一种声矢量阵声压振速联合方位估计算法.与常规MUSIC方位估计算法相比,该算法利用了四元数紧凑的数据表达形式和较强的正交性约束能力,降低了内存需求和运算复杂度,在不经过任何预处理的情况下可以分辨相干目标.同时,由于利用了声压振速的组合指向特性,算法抗各向同性干扰的能力较强.仿真实验证明了算法的有效性.