基于启发式回溯算法的平面移动式立体车库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%,为提升立体车库运行效率提供参考。

关键词

平面移动式立体车库 / 值排序启发式回溯算法 / 滑动时间窗 / 非齐次泊松过程 / 运行效率