{title}{title}
|
文献综述（或调研报告）： 国内外学者对自动化仓储系统中的优化问题研究取得了很多成果，这些成果为提高自动化仓储系统中设备资源的利用率和企业的效益发挥了重大的作用，同时也为动态自动化仓储系统的优化研究奠定了坚实的基础。 Lim，Joon-Mook [1]应用遗传算法和计算机模拟方法对在线调度系统进行研究，包括存储设计策略、出/入库机器调度规则、库计划控制等优化；KOO等[2]在AGV调度规则下建立了AGV的运行时间模型，并用传统的启发式算法解决问题；Gintner等[3]提出了固定部分变量的启发式方法解决大规模的多种公共汽车调度问题以减少运输成本。 Basile等描述了自动化仓库系统的两个主要组成部分:一个自动存储和检索子系统，由多个通道组成，每个通道由一台起重机提供服务;另一个是由货舱组成的拾取区，在这里，来自通道的库存部分由人工操作人员清空。这两个组件通过一个由传送带、传送带和缓冲器组成的接口区域连接。该区域通常被建模为离散事件系统，而系统的整体性能也依赖于连续时间现象。其论文第一部分[4]提出了一种基于混合Petri网形式的混合模型，该模型融合了混合Petri网和有色Petri网的概念，得到了这些系统的模块化和紧凑模型，引入了一种新的形式主义，提出了一种面向控制的仿真工具。第二部分[5]重点介绍了这种形式在自动化仓库系统分析和性能评估中的应用，并通过实例分析验证了该方法的有效性。 Roy等[6]指出基于自主车辆的存储和检索系统(AVS/RS)在高密度存储区域单位负荷转移的吞吐量方面提供了相当大的灵活性。AVS/RS依靠自动驾驶汽车在一层内提供水平运动，并使用电梯在层之间提供垂直运动。在这些系统中，车辆阻塞通道和交叉通道中的延迟会显著影响系统吞吐量和事务周期时间。Roy等开发了解决车辆阻塞的协议，并提出了一个半开放排队网络模型来分析系统性能并评估设计的优劣；采用基于分解的方法对排队网络进行求解，并对阻塞效果进行量化；进而使用该模型分析了不同层配置参数(如存储位置数量、深度/宽度比、车辆数量和车辆利用率)对阻塞延迟的影响。这些见解对于使用AVS/RS进行设计概念化非常有用。 Digani 等[7]提出了一种在工业环境中协调AGV的整体方法——一种基于两层控制体系结构的集成方法和一种自动定义路线图的算法。该路线图是通过考虑在分层体系结构上实现的路径规划算法来构建的，反之亦然。此外，为了使冗余度、覆盖率和连接性最大化，还计算了路线图。体系结构由两层组成。低层表示路线图本身。高层描述环境不同区域之间的拓扑关系。 Digani 等[8]在另一篇论文中指出AGV的运动应该考虑到目前和未来的车队状态,作者提出了一个自治仓库交通的概率模型来预测可能拥挤地区的发展，并利用该模型构建了一个嵌入到最近在[7]中提出的流量管理器中的预测规划器，以明确地考虑流量在给定水平范围内的演化，并在交付时间方面提高AGV车队的效率。通过对实际车辆的仿真比较，验证了该交通管理器的有效性。 Dotoli等[9]研究了一种广泛应用于仓库物料处理的自动存储与检索系统(AS/RSs)的实时控制方法。将一般多产品AS/RS建模为一个定时离散事件动态系统，其状态提供了当前用户与资源交互的信息。此外，为了避免冲突和死锁，通过启用和抑制系统事件来处理控制资源分配和调度选择的实时控制器。为此，作者将死锁定义为AS/RSs，并定义了两种死锁解决策略:死锁避免策略和死锁检测/恢复策略。其论文所提出的死锁公式和特征具有一般的有效性，可以应用于单个单元资源分配系统，其中一个用户子集可以被视为其他用户的资源。 Han等[10]研究了一种改进的多自动导引车路径规划遗传算法。其创新体现在两个方面：首先，在改进遗传算法中，三交换交叉启发式算子比传统的两交换交叉启发式算子产生更优的子算子，从而获得更多的信息；其次，利用最小化所有AGV总路径距离和最小化每个AGV单路径距离的双路径约束，得到最优的总路径距离。仿真结果表明，改进的遗传算法缩短了所有AGV的总路径距离和最长的单AGV路径距离。 Tianfang Xue等[11]研究了一种改进的多自动导引车路径规划遗传算法。创新体现在两个方面。首先，在改进遗传算法中，三交换交叉启发式算子比传统的两交换交叉启发式算子产生更优的子算子，从而获得更多的信息。其次，利用最小化所有AGV总路径距离和最小化每个AGV单路径距离的双路径约束，得到最优的总路径距离。仿真结果表明，改进的遗传算法缩短了所有AGV的总路径距离和最长的单AGV路径距离。 Li B等[12]提出了一种集中式多AGV运动规划方法，与使用分散(解耦)公式的流行计划器相反，集中式计划器不包含优先级分配、解耦或其他规范策略，因此不依赖于案例和死锁。虽然集中运动规划在计算上是昂贵的，但它值得在对解决方案质量敏感但对计算时间不敏感的方案中进行研究。具体来说，作者将集中式多AGV运动规划问题表述为最优控制问题，其中微分代数方程用于描述AGV的动力学、力学约束和外部约束。采用正交配置直接转录法将原无穷维最优控制问题离散为大规模非线性规划问题，然后用内点法求解。仿真结果表明，所引入的集中规划器具有验证、统一和实时实现的潜力。特别地，在NLP求解过程中，PC上的计算时间减少到几秒，初始猜测接近最优，使得通过该集中规划器进行后退层重新规划成为可能。 Chen G等[13]为了有效地分析随机路径物料搬运单元制造系统的性能，建立了有限缓冲区开放排队网络的性能分析模型，考虑了自动导引车辆(AGV)与制造单元之间的关联，并利用状态空间分解方法得到了系统性能指标。根据AGV的负载均衡规律，证明了基于随机过程理论的假设模型具有马尔可夫性。建立了各节点的状态空间模型和状态转移平衡方程，给出了系统性能指标的计算方法。 Chen C等[14] 针对空间受限的AGV预制件(PBU)制造系统的调度问题进行了研究。空间成为这个制造系统的关键资源，因为需要非常大的空间来容纳安置单元和队列。虽然行平衡有助于减少队列，但是由于空间有限，系统仍然容易死锁。因此，为了防止死锁，必须控制PBUs的生产启动时间。作者提出了一种遗传算法，目的是确定每个工作站的操作，并为每个PBU选择一个启动时间。在满足优先关系和资源可用性的同时，项目持续时间最小化。采用基于规则的仿真方法对遗传算法中的每条染色体进行适应度估计。论文最后通过一个工业项目的数据实验证明，该算法具有指导实际应用的潜力。 一些国内学者对AGV调度在邮政自动化仓库、中烟工业原料立体库/柔性制造系统（FMS）等方面的应用做出了研究。 柳赛男等[15]采用遗传算法对AGV小车的调度问题进行研究，在分析问题的基础上，建立其数学模型，给出了具体的遗传算法的编码、交叉和变异算子，为AGV小车在仓储系统中的调度提供了一种有效的方法和实践途径。 遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。 遗传算法以一种群体中的所有个体为对象，并利用随机化技术指导对一个被编码的参数空间进行高效搜索。其中，选择、交叉和变异构成了遗传算法的遗传操作；参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。 AGV小车行走路径的遗传算法如下：首先对AGV小车在仓储系统中的行走路线采用有向图进行表示，有向图中的点表示行走路径所经过的点，有向图的边表示两点之间的路径值，其次由遗传算法产生基于行走路径的染色体编码，然后按照适应度函数计算每条染色体的适应度函数值，接着判断是否满足终止条件，若满足终止条件，则输出最优解，若不满足，则对染色体进行选择、交叉和变异操作，继续计算经过算子操作后的染色体的适应度函数值，直到满足终止条件为止。 焦福明[16]提出了“规划前置,提前调整”的离线解决办法。即在整批任务执行前,提前规划好AGV的行驶路线及任务分派。 首先把每项任务(从装载到卸载)当作一个占用时间的任务点,对于使用单AGV进行调度的情况,将问题归结为TSP问题求解,进而求解出任务的执行顺序,也同时求出了任务执行的最短路径。 对于多AGV的调度问题,借助于解决占用式多车辆路径问题和短板效应的思想,在一批任务下达后,完成全部任务的时间长短取决于耗时最长的那一辆,因此以最短时间完成全部任务为目标时,通过对任务分派的优化,使得所有AGV中耗时最长的AGV用时尽量少,于是完成全部任务的时间也就相应减少。这样便实现了在系统内AGV数量一定的情况下,在最短时间内完成整批任务的目标,进而实现了对多AGV行驶路径的规划。 由于考虑调度的时效性,采用收敛速度相对较快的粒子群算法,并通过采用适当的离散策略,使其适用于问题的求解。然后,针对求解方案中多AGV路径规划时可能出现的冲突问题,提出了借助类似于甘特图的逻辑思想,解决了路段冲突和路段交叉问题。最后,将最终调度方案以路径列表的形式存储到交通管理模块,实现了任务的预调度。在预调度之后,开始指派AGV根据任务列表及路径列表执行任务。由于前置规划耗时少,能够很好地满足企业的实际需求。 |
|
|
四、方案（设计方案、或研究方案、研制方案）论证： 排队论, 或称随机服务系统理论， 是通过对服务对象到来及服务时间的统计研究，得出这些数量指标（等待时间、排队长度、忙期长短等）的统计规律，然后根据这些规律来改进服务系统的结构或重新组织被服务对象，使得服务系统既能满足服务对象的需要，又能使机构的费用最经济或某些指标最优。它是数学运筹学的分支学科。也是研究服务系统中排队现象随机规律的学科。广泛应用于计算机网络, 生产, 运输, 库存等各项资源共享的随机服务系统。 排队论研究的内容有3个方面：统计推断，根据资料建立模型；系统的性态，即和排队有关的数量指标的概率规律性；系统的优化问题。其目的是正确设计和有效运行各个服务系统，使之发挥最佳效益。 根据调研，在该自动化仓储系统AGV优化问题中吗，每一项任务的工作过程是：在给定商品进出库货架以及拣选工作站的基础上，选择一辆空载AGV驶向货架；AGV把给定货架由存储区搬运到给定拣选工作站；AGV在拣选工作站等待及进行拣选；AGV把货架由拣选工作站搬运到存储区，完成一项任务。 整个过程可看作为一个闭合Jackson网络，包括运输通道、货架、拣选工作站共64个节点，节点之间通过小车的访问互相联系构成排队网络（如图1所示）。 其中，第1行为8个拣选工作站节点，第2-8行为56个通道及货架节点（在此为简化模型，不对通道和货架做区分）。在每个节点上顾客（AGV）可能的转移方向如图1中箭头所示，红色实线箭头表示入库方向，蓝色实线箭头表示出库方向。
图1 AGV系统排队网络 设同一纵向路径上，转移概率随行数单调变化，入库方向转移概率单调递减（所在行数越大转移概率越小），出库方向转移概率单调递增（所在行数越小转移概率越大），设入库方向上转移概率函数为： 入库方向上转移概率函数为： 从同一节点出发的有向弧上的转移概率之和为1. 设此仓储系统共有N个AGV，I个服务台（节点），表示第i个节点上AGV的数量，则表示系统的状态。 有 用表示节点i上AGV为时的服务率（通行速度），是的单调下降函数，即越大，节点i附近越拥挤，通行速度越慢，服务率越低。 则这一闭环排队网络模型的流平衡方程为： 对任一节点j， 稳态概率有如下乘积形式： 其中， 满足 即 求解使用递归算法， 定义 满足如下递归方程: 初始条件： 即 边缘概率分布为：
改变节点的编号顺序，使感兴趣的节点为第I个节点，可计算出每个节点的边缘概率分布。 节点i的平均吞吐率为 将第一行4个进库节点的吞吐率求和得到入库吞吐率4个出库节点的吞吐率求和得到出库吞吐率. 由AGV数量N和转移概率决定，而转移概率由参数b决定。 那么，该优化问题即可总结为：
|
|
|
五、进度安排： 2019.01.10-2019.02.28 深入理解毕业设计任务，完成文献阅读、编程工具学习等准备工作。 2019.03.01-2019.03.31 基于离散事件仿真，分析自动化仓储系统拣选效率与AGV数量之间的函数关系的性质，并对AGV数量进行优化。 2019.04.01-2019.04.30 应用动态规划方法寻找能够避免阻塞的各AGV的最优运行路径。 2019.05.01-2019.05.15 针对不同场景解决上述问题，并进行数值实验，并完成自动化仓储系统运行过程仿真系统的AGV数量优化子系统的开发。 2019.05.16-2019.05.31 完成毕业论文的撰写。 2019.06 软硬件验收、毕业设计答辩。 |
|
|
六、参考文献
|
|
资料编号：[179086]
