基于启发式回溯算法的平面移动式立体车库RGV调度策略

为了提高立体车库路径规划阶段的兑现率,对有轨引导小车(rail guided vehicle,RGV)运行过程及行程时间进行分析,给出了符合并行调度模式的路径重叠率计算方法,针对立体车库作业特征提出了一种值排序启发式(value ordering heuristics,VOH)回溯算法,构建路径节点滑动时间窗,以单位时间窗内任务请求数作为约束函数,通过评估函数对扩展结点性能进行估值并排序,并利用VOH-预剪枝策略对部分结点进行剪枝,以此提高算法求解速度。在非齐次泊松到达过程下进行仿真,实验结果表明,值排序启发式回溯算法可有效降低RGV并行运行过程中时间、空间的路径重叠率,在该实验规模的立体车库模型中发挥稳定,表现为在RGV平均利用率基本不变的前提下具有更小的平均服务时间,当顾客到达率为40、25、10、5 veh/h时,RGV平均服务时间分别减少18.07%、13.29%、12.46%、4.27%,为提升立体车库运行效率提供参考。

基于启发式回溯算法的铁路编组站调车场股道活用研究

不同的调车场股道活用方案产生不同的车辆集结状态,由此引起解编调车作业成本和到发车流接续关系的不同。为了提高编组站阶段计划的兑现率,本文在动态配流的基础上,综合考虑调车场存车状态随解编作业动态变化、调车场股道容量和解编作业时序限制等,设计"开口"算法将到达车列划分为车组,以各车组在调车场集结股道为变量,建立阶段时间内调车场股道活用整数优化模型。以解体照顾编组、当前解体照顾后续解体、借用股道混到底、均衡使用资源、减少交叉干扰等为原则,设计了变量取值动态排序的启发式回溯算法。算例表明,启发式回溯算法比基本回溯算法效率高,调车场股道活用方案更能适应车流不均衡、密集到达情况。

约束可满足性中求解RB模型实例的算法综述

约束满足问题是人工智能领域中最基本的NP完全问题之一。多年来,随着约束满足问题的深入研究,国内外学者提出多种实例模型。其中,RB模型是一种能生成具有精确相变的增长域约束满足问题实例,其求解难度极具挑战性。为了寻找其求解的新型高效算法,促进约束可满足问题的RB模型求解算法领域的研究,首先从约束满足问题的模型发展、求解技术进行分析;其次,对各类求解RB模型实例算法进行梳理,将求解的算法文献划分为回溯启发式类、信息传播类和元启发式类相关改进算法,从算法原理、改进策略、收敛性和精确度等方面进行对比综述;最后给出求解RB模型实例算法的研究趋势和发展方向。