本发明公开一种基于动态边权值拓扑图实现密集库设备路径规划的方法，用一致寻径算法和路径属性管理方案高效准确的维护模型属性，从而使得算法更加通用，进而系统可以使用标准化方式构建和维护，从仓库的各种异构定制化开发中解脱此外由于使用更加丰富的属性数据描述模型信息，使得模型可以和各类更高层次路径优化算法搭配，进一步提升系统调度性能。
1.一种基于动态边权值拓扑图实现密集库设备路径规划的方法，包括以下步骤：（1）建立仓库的拓扑图模型，设置拓扑图路径权重，拓扑图模型中包含路径及路径属性信息，还包含路径执行的设备动作信息；路径权重属性采用通过时间来定义，通过时间以多次执行采样得到平均值作为初始化的参数；
（2）对货物运送任务进行规划，首先确认货物所在位置，并确认货物预设路径的起点及终点，基于拓扑图进行多种路径嗅探，嗅探方案为：寻找起点和终点附近距离为r以内的所有可达点，形成起点点集和终点点集，使用dijkstra最短路径算法计算两个集合中各个点的最短路径；之后，按照寻找到的路径进行设备执行动作拆解，通过计算每个动作消耗的时间，寻找预期所需最少时间的行进路线执行此任务；
（3）找到行进路线后，更新此路线的使用情况，并在行进过程中不断更新路径数据，直到任务完成货物送达，或者意外终止；
任务执行前，任务选择使用某路径时，给路径的预占用任务数+1，并在路径上增加一个较小的预占用权值；
任务正在执行时，设备通过特定路径前需占用路径，占用的路径距离权值会增加一个远大于初始值的权值M，在下次其他任务计算最短路径时，如有其他路径权值更小的联通通路，则优先选择其他通路，如多条通路均被占用，则选择当前权值加和最小的通路；
设备行进前逐段占用路径，设备执行路径上动作需占用路径时，判定路径边权值是否小于M，当小于M时，才可占用路径，否则等待此边权值更新至小于M才进行占用；
设备等待时，如等待时间超过之前预设的阈值时，则触发重新规划逻辑，即使用当前所在位置重新规划到目标位置的行进路线；
设备执行中每经过一段路径则释放此路径，释放的方法是本段路径的边权值减去M，释放后的本段路径能够被其他任务使用；
2.根据权利要求1所述密集库设备路径规划的方法，其特征在于：步骤（3）中，执行过程中出错时，对应路径的异常率进行更新，异常率=异常次数/本路径执行过的任务总数。
3.根据权利要求1或2所述密集库设备路径规划的方法，其特征在于：步骤（1）中，车辆行驶的路径内会分段，分段按照定位孔或者定位二维码进行定义，两个定位孔或者两个定位二维码之间为一段路径。
4.根据权利要求3所述密集库设备路径规划的方法，其特征在于：步骤（2）中，搜索过程中可使用剪枝策略减少搜索工作量，如确定之前搜索最短路径为l，则所有超过l+2r的路径都应当舍弃；搜索的同时合并重复路径。
5.根据权利要求1或2所述密集库设备路径规划的方法，其特征在于：步骤（3）中，设备行进前逐段占用路径，每次占用的路径长度由配置设置，其中，默认占用行进方向的前3段路径，即使只行进一段，也会占用前方的三段路径，同时在四向车换向或者发现需更改行进路线时，保留周旋空间。
6.根据权利要求5所述密集库设备路径规划的方法，其特征在于：步骤（3）中，路径逐段释放中设置最小释放单元，其中，默认设置为每经过6段路径，释放车行进路线后方两段路径以外的所有路径。
7.根据权利要求6所述密集库设备路径规划的方法，其特征在于：步骤（3）中，未执行任务可取消，取消后拓扑图属性会进行反向修改，即预占用任务数‑1，并在路径上减掉增加的预占用权值。
基于动态边权值拓扑图实现密集库设备路径规划的方法
技术领域
[0001] 本发明涉及智能自动化仓储设备控制领域，尤其是一种智能高效的仓库运输设备路径规划调度方法。
背景技术
[0002] 在现代智能仓储系统中，对于轨道上四向车的自动控制常采用基于路权令牌的穿梭车控制系统。该种基于路权令牌的控制方式的应用具有局限性，仅可以对穿梭车设备地
图进行控制，使用开关量描述路径占用，算法单纯，通过算法进行调优空间有限。
[0003] 故，需要一种新的技术方案以解决上述问题。
发明内容
[0004] 发明目的：为解决上述问题，提供一种基于动态边权值拓扑图实现密集库设备路径规划的方法，用一致寻径算法和路径属性管理方案高效准确的维护模型属性，从而使得
算法更加通用，进而系统可以使用标准化方式构建和维护，从仓库的各种异构定制化开发
中解脱此外由于使用更加丰富的属性数据描述模型信息，使得模型可以和各类更高层次路
径优化算法搭配，进一步提升系统调度性能。
[0005] 技术方案：为达到上述目的，本发明可采用如下技术方案：
[0006] 一种基于动态边权值拓扑图实现密集库设备路径规划的方法，包括以下步骤：
[0007] (1)建立仓库的拓扑图模型，设置拓扑图路径权重，拓扑图模型中包含路径及路径属性信息，还包含路径执行的设备动作信息；路径权重属性采用通过时间来定义，通过时间
以多次执行采样得到平均值作为初始化的参数；
[0008] (2)对货物运送任务进行规划，首先确认货物所在位置，并确认货物预设路径的起点及终点，基于拓扑图进行多种路径嗅探，嗅探方案为：寻找起点和终点附近距离为r以内
的所有可达点，形成起点点集和终点点集，使用dijkstra最短路径算法计算两个集合中各
个点的最短路径；之后，按照寻找到的路径进行设备执行动作拆解，通过计算每个动作消耗
的时间，寻找预期所需最少时间的行进路线执行此任务；
[0009] (3)找到行进路线后，更新此路线的使用情况，并在行进过程中不断更新路径数据，直到任务完成货物送达，或者意外终止；
[0010] 其中，路径属性更新算法：
[0011] 任务执行前，任务选择使用某路径时，给路径的预占用任务数+1，并在路径上增加一个较小的预占用权值；
[0012] 任务正在执行时，设备通过特定路径前需占用路径，占用的路径距离权值会增加一个远大于初始值的权值M，在下次其他任务计算最短路径时，如有其他路径权值更小的联
通通路，则优先选择其他通路，如多条通路均被占用，则选择当前权值加和最小的通路；
[0013] 设备行进前逐段占用路径，设备执行路径上动作需占用路径时，判定路径边权值小于M，否则等待此边权值更新至小于M才进行占用；
[0014] 设备等待时，如等待时间超过之前预设的阈值时，则触发重新规划逻辑，即使用当前所在位置重新规划到目标位置的行进路线；
[0015] 设备执行中每经过一段路径则释放此路径，释放的方法是本段路径的边权值减去M，释放后的本段路径能够被其他任务使用；
[0016] 估算各路径的占用时间方法为：
[0017] 时间＝∑各段路径预占用任务数*各段路径的通过时间*(1+各段故障率)
[0018] 时间最短的路径将被规划为当前任务的执行路径。
[0019] 有益效果：本发明使用统一的高度抽象模型管理各类仓库的整体货物运送路径，用一致寻径算法和路径属性管理方案高效准确的维护模型属性，从而使得算法更加通用，
进而系统可以使用标准化方式构建和维护，从仓库的各种异构定制化开发中解脱此外由于
使用更加丰富的属性数据描述模型信息，使得模型可以和各类更高层次路径优化算法搭
配，进一步提升系统调度性能。
具体实施方式
[0020] 本发明提供一种基于动态边权值拓扑图实现密集库设备路径规划的方法。该方法应用在现代智能仓储系统并用于对包括子母穿梭车或者四向穿梭车在轨道上的行走路径
控制。
[0021] 该方法为：
[0022] 首先，建立仓库的拓扑图模型，设置拓扑图路径权重：
[0023] 拓扑图模型中包含路径及路径属性信息，路径执行的设备动作信息，其中路径属性中用于计算的指标除通过时间外，还包括路径申请占用任务数，路径故障率等其他辅助
指标，各指标数值会随着规划动态改变。
[0024] 使用最短路径算法时需要使用的路径权值属性
[0025] 路径权重的设计，需要保障属性运算符合交换律，即更改属性的顺序不影响最终结果，故路径权重属性，采用通过时间来定义，通过时间(即路径权重)可以通过多次执行采
样得到平均值作为初始化的参数
[0026] 车辆行驶的路径内会分段，分段按照定位孔或者定位二维码进行定义，两个定位孔或者两个定位二维码之间为一段路径。
[0027] 之后，如有任务需要进行规划
[0028] 首先确认货物所在位置，通常会处在入口或者特定货位上，异常处理时也可能在输送线等传送设备上，之后请求货物的目标位置，
[0029] 确认起点终点后，则基于拓扑图进行多种可能的路径嗅探，嗅探方案为：寻找起点和终点附近距离为r(可由配置确定)以内的所有可达点，形成起点点集和终点点集，使用
dijkstra最短路径算法计算两个集合中各个点的最短路径。搜索过程中可使用剪枝策略减
少搜索工作量，如确定之前搜索最短路径为l，则所有超过l+2r的路径都应当舍弃。搜索的
同时合并重复路径。
[0030] 之后，按照寻找到的路径进行设备执行动作拆解，通过计算每个动作消耗的时间，寻找预期所需最少时间的行进路线执行此任务。
[0031] 由于任务执行过程中存在拓扑图模型的数据实时变更的情况，此次规划预估的时间仅作为参考，实际执行时会针对实时反馈的情况进行纠偏
[0032] 最后，找到行进路线后，更新此路线的使用情况，并在行进过程中不断更新路径数据，直到任务完成货物送达，或者意外终止。
[0033] 对拓扑图路径属性数据进行的更改，后续的计算中会根据新的数据进行计算。
[0034] 其中，路径属性更新算法：
[0035] 任务执行前，任务选择使用某路径时，给路径的预占用任务数+1，并在路径上增加一个较小的预占用权值。
[0036] 任务正在执行时，设备通过特定路径前需占用路径，占用的路径距离权值会增加一个远大于初始值的权值M，因而在下次其他任务计算最短路径时，如有其他路径权值更小
的联通通路，则会优先选择其他通路，如多条通路均被占用，则选择当前权值加和最小的通
路
[0037] 设备行进前逐段占用路径，每次占用的路径长度可由配置设置，目前算法中，默认占用行进方向的前3段路径，即使只行进一段，也会占用前方的三段路径，以此确保两车不
会冲撞，同时在四向车换向或者发现需更改行进路线时，保留周旋空间。同时由于保留了一
定的额外缓冲空间，可以大幅度减少车辆聚集在一个巷道附近导致路径死锁的问题。
[0038] 设备执行路径上动作需占用路径时，需判定路径边权值小于M，否则需等待此边权值更新至小于M才可占用，
[0039] 设备等待时，如等待时间超过之前预估时间的1/3或超过预设的阈值时，则会触发重新规划逻辑，即使用当前所在位置重新规划到目标位置的行进路线。
[0040] 设备执行中每经过一段路径则释放此路径，释放的方法是本段路径的边权值减去M，此时本段路径可以被其他任务使用，此方案可以规避冲突，同时提高路径利用率
[0041] 路径逐段释放，需要考虑最小释放单元问题，最小释放单元可由配置设置，本算法中，默认设置为每经过6段路径，释放车行进路线后方两段路径以外的所有路径，这样可以
保障其他车辆不会进入本车2个定位点以内的路段，防冲撞，此外批量释放路径可以减少在
两车跟随前进的情况下，后车频繁启动停止的问题。
[0042] 未执行任务可取消，取消后拓扑图属性会进行反向修改，即预占用任务数‑1，并在路径上减掉增加的预占用权值。任务完成也会做同样操作。
[0043] 执行过程中出错时，对应路径的异常率进行更新，异常率＝异常次数/本路径执行过的任务总数。
[0044] 估算各路径的占用时间公式：
[0045] 时间＝∑各段路径预占用任务数*各段路径的通过时间*(1+各段故障率)
[0046] 时间最短的路径将被规划为当前任务的执行路径
[0047] 另外，本发明的具体实现方法和途径很多，以上所述仅是本发明的优选实施方式。应当指出，对于本技术领域的普通技术人员来说，在不脱离本发明原理的前提下，还可以做
出若干改进和润饰，这些改进和润饰也应视为本发明的保护范围。本实施例中未明确的各
组成部分均可用现有技术加以实现。
