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

RGV scheduling strategy of planar mobile stereoscopic garage based on heuristic backtracking algorithm

作　　者：李建国[1,2] 赵剑英 薛千树 LI Jianguo;ZHAO Jianying;XUE Qianshu(School of Automation and Electrical Engineering,Lanzhou Jiaotong University,Lanzhou 730070,P.R.China;Key Laboratory of Railway Industry of Four Electric BIM Engineering and Intelligent Application,Lanzhou 730070,P.R.China)

机构地区：[1]兰州交通大学自动化与电气工程学院,兰州730070 [2]四电BIM工程与智能应用铁路行业重点实验室,兰州730070

出　　处：《重庆邮电大学学报（自然科学版）》2024年第3期582-590,共9页Journal of Chongqing University of Posts and Telecommunications(Natural Science Edition)

基　　金：甘肃省自然科学基金项目(20JR5RA396);中国高校产学研创新基金项目(2021LDA07002)。

摘　　要：为了提高立体车库路径规划阶段的兑现率,对有轨引导小车(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%,为提升立体车库运行效率提供参考。In order to improve the fulfillment rate of the path planning stage of the three-dimensional parking garage,the operation process and travel time of the rail guided vehicle(RGV)are analyzed,and a path overlap rate calculation method that complies with the parallel scheduling mode is proposed.A value ordering heuristics(VOH)backtracking algorithm is proposed for the operation characteristics of the three-dimensional parking garage,and a sliding time window for path nodes is constructed.The number of task requests within a unit time window is used as a constraint function,and the performance of extended nodes is evaluated and sorted through an evaluation function.The VOH-pre-pruning strategy is used to prune some nodes to improve the algorithm’s solving speed.Simulations were conducted under a non-homogeneous Poisson arrival process.The experimental results show that the value ordering heuristic backtracking algorithm can effectively reduce the path overlap rate of time and space during the parallel operation of the RGV,and it performs stably in the three-dimensional parking garage model with this experimental scale.It has a smaller average service time with a basically unchanged average utilization rate of the RGV.When the customer arrival rate is 40,25,10,and 5 veh/h,the average service time of the RGV decreases by 18.07%,13.29%,12.46%,and 4.27%,respectively,providing a reference for improving the operational efficiency of the three-dimensional parking garage.

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

分 类 号：TP391[自动化与计算机技术—计算机应用技术]