《仓储物流调度原理及算法综述》5100字

仓储物流调度原理及算法综述目录TOC\o"1-2"\h\u5187仓储物流调度原理及算法综述 195001.1路径模型概述 1280141.2任务调度原理 2164681.2.1任务调度问题分类 2119681.2.2任务调度步骤 4117911.2.3基础问题描述 442531.3任务调度算法 518166（1）遗传算法 519341（2）粒子群算法 716851（3）差分进化算法 88722（4）蚁群算法 91.1路径模型概述随着导航定位技术的不断更新换代以及信息通讯技术的飞速发展，仓储物流机器人的导引方式越来越多样化。如前所述，目前为止在实际应用环境中主流的仓储物流机器人按照引导方式可分为地磁导引，通过在物流机器人运行路径上设置磁体引导机器人移动；导轨导引，通过在物流机器人运行路径上设置导轨引导机器人移动；激光导引，通过在物流机器人运行路径上设置激光制导装置引导机器人移动；惯性导引，利用惯性引导机器人移动；地图导引，在物流机器人管理系统中预先设置匹配的地图引导机器人移动。引导方式还可以从路径是否固定大体分为固定路径与非固定路径。根据现有的仓储物流机器人通行规则和应用环境等刚性需求，智能仓储物流系统中路径模型主要可分为四种情形[43]:（1）在一个智能仓储物流系统中，任意时间段内的任意一条通路只能允许一台仓储物流机器人通过，在这条通路上，机器人也只能沿着一个固定的方向前进，不能反向行驶，这种路径模式被称为单通路单向路径模型。在这种路径模型下，所有的通路都不存在对向冲突，是一种较为简单的通路模型，但由于通路只能单项同行，前面的机器人在装卸货物时，后面的机器人只能等待，而路径选择方面也会受到非常大的限制，运输效率相对其他路径模式而言非常低下。（2）单通路双向模型；顾名思义，这种路径模型与单通路单向路径模型相似，同样对于任意的通路只让一台仓储物流机器人通过，不同的是这种模型允许机器人反向行驶。这意味着可能出现两台机器人对向行驶的情况，这也是此类路径模型下调度系统需要考虑的问题。由于机器人可以双向行驶，在路径选择上更加自由，较单向通行的模型提升了运输效率，相对的也使得运输环境更加复杂，对调度系统的调度策略要求更高。（3）双通路单向模型；现实生活中的道路交通基本使用的都是这种路径模式，在该路径模型中，每条道路都可以让两台机器人同时通行，且通行的方向互为反向，如道路左侧只允许向东，右侧只允许向西。这样的路径模型较前两种更加灵活，避免大部分的对向行驶冲突，运输效率也因此提升不少。需要考虑的是在路口处，由于双通道且单向允许通行的规则，组合情况较多，对调度能力的要求也更高。（4）双通路双向模型；双通路双向模型是四种通路模型中最为灵活的一种。灵活性的提升主要原因在于每条通路的两条路径都允许两种方向的机器人通行，这极大的提升了道路的通行效率，而代价则是对调度能力的要求也大幅度提升。这里的调度能力涉及到的关键部分是动态调度部分，在处理多个执行任务的机器人在同一通路发生对向冲突或是路口处的路径选择问题上，需要考虑多种情况，这对采用该路径模型的调度系统运行效率来说是巨大的考验。本文所使用的模型在通行方向上是双向的，通路方向上则是单向的。1.2任务调度原理1.2.1任务调度问题分类根据仓储物流机器人在执行任务期间获取信息的情况，可将仓储物流机器人调度问题分为仓储物流机器人静态调度,仓储物流机器人动态调度和仓储物流机器人资源联合调度:图1.1三种任务调度过程示意图（1）仓储物流机器人静态调度仓储物流机器人静态调度是指在某一静态时刻，通过对仓储物流机器人指派任务序列，解决仓储物流机器人调度问题。静态调度问题常见于基础算法或基本模型的研究，为了体现算法有效性，模型的准确性，静态调度可以直观的反应算法或模型变化带来的性能指标变化。其常见的优化目标包括:任务时间最短，仓储物流机器人利用率最高，仓储物流机器人数量最少，拖期延迟最小，物流成本最低等。其常见的约束则包括:仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。（2）仓储物流机器人动态调度仓储物流机器人动态调度是指在考虑动态扰动，如任务变更、设备故障、冲突死锁等问题下，通过对仓储物流机器人进行实时任务指派，解决仓储物流机器人调度问题。动态调度更接近实际生产中的情形，多适用于解决实际的问题。其常见的优化目标包括:任务时间最短，仓储物流机器人数量最少，搬运时间最短，仓储物流机器人利用率最大，仓储物流机器人负荷均衡，仓储物流机器人最小行走时间等。其常见约束则包括:仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。（3）仓储物流机器人资源联合调度仓储物流机器人资源联合调度多出现于生产制造系统当中一般为多目标优化问题，资源联合调度主要是指在仓储物流机器人调度过程中需要考虑其他生产工序的资源产出或使用情况，然后根据这些情况对仓储物流机器人实施任务指派，以达到任务调度期望达到的优化目标。调度问题中最常见的几类优化目标包括：完成任务时间最短，消耗资源最少，资源利用率最大，惩罚成本最低，仓储物流机器人负荷均衡，每个工件在队列中等待时间最少等。而常见的优化目标约束则包括:工件队列中的缓冲量，工件工序约束，仓储物流机器人容量约束，仓储物流机器人充电约束，任务顺序约束，路径方向约束等。本文研究的仓储物流机器人任务调度问题属于仓储物流机器人静态调度问题，静态调度问题可以通过仿真模拟对比实验更准确的反应本文提出算法的有效性。1.2.2任务调度步骤仓储物流机器人任务调度系统主要工作步骤可分为三层:生成任务，分配任务，完成任务。其中，分配任务和完成任务称为资源分配，在系统生成的任务全部完成之前，智能仓储物流系统将会不间断的进行任务的分配并指导仓储物流机器人完成任务，直至系统不再生成新的任务。（1）生成任务。本文系统中由于不包含上位机系统，因此本文中所有实验的任务均为人工生成。（2）分配任务。系统在分配任务时需要对未完成任务的目标地点和空闲的仓储物流机器人情况进行实时的监测，在系统生成新的任务后能够立即根据目标地点将任务分配给空闲且状态正常的仓储物流机器人。分配任务的主要约束就是均衡性，在保证所有任务完成时间最短的前提下，实现任务的均衡分配。（3）完成任务。完成任务的过程为仓储物流机器人从起始地点到达任务的目的地，即为路径规划过程。为了高效有序的完成任务，需要对仓储物流机器人进行路径规划，而路径规划的合理性也影响着任务的分配。系统需要根据任务的具体分配情况来对仓储物流机器人进行路径规划，保证仓储物流机器人在无死锁、无冲突的情况下完成任务，并也要根据任务的完成情况来对任务的分配进行调整，力求仓储物流机器人完成任务时间最短。1.2.3基础问题描述普通的仓储物流布局由仓储物流机器人，货物存放区，货物装卸区组成，整个环境布局图如图1.2所示，蓝色胶囊为仓储物流机器人以及其起始区域，黄色方块表示货架，最下面是完成任务的卸货区，两个货架之间的通道允许两台仓储物流机器人并排通过，中间通道可允许两台仓储物流机器人并排通过。图1.2仓储物流布局图为了方便求解，本文将整个环境转化为节点图形式，仓储物流机器人起始节点为一个节点。货架每个货物位置为一个节点，货物装卸区为一个节点，并且将仓储物流机器人起始位置设为1号节点，货物按顺序编号2到n节点，装卸区为最后一个节点。为了保证仓储物流机器人调度系统的顺畅运行，本文对调度过程做如下合理假设:（1）仓储物流机器人装卸货时间忽略不计；（2）仓储物流机器人匀速行驶，不考虑转弯或其他情况造成的减速；（3）每台仓储物流机器人可以搬运多个货物，但不能超出最大载重量；1.3任务调度算法智能优化算法能解决其他方法难以求解的复杂组合优化问题，因而广泛应用于调度优化方面，仓储物流机器人调度中用到的智能优化方法包括粒子群算法(ParticleSwarmOptimization,PSO)、遗传算法(GeneticAlgorithm,GA)、差分进化算法(DifferentialEvolution,DE)、蚁群算法(AntColonyOptimization,ACO)等。（1）遗传算法遗传算法（GeneticAlgorithm，GA）的起源最早可以追溯到20世纪60年代初期，当时由Holland教授的学生在其博士论文中首次提出，论文主要探讨该算法在博弈中如何应用，但这类早期研究缺少指导性理论，也没有计算工具作为支撑。直到1975年JohnHolland教授出版《自然系统和人工系统的适配》，于该书中对遗传算法的算法原理，算法的基本方法及步骤进行系统阐述，推动遗传算法的发展。遗传算法本质上是模仿生物的进化过程而得出的计算模型[44]，达尔文在生物进化论中提出自然选择，而现代进化论中提出基因突变的概念，这两大概念促成了遗传算法的诞生，遗传算法也因此成为一种探索最优化问题的常用算法。遗传算法流程如图1.2所示。图1.2遗传算法流程图通过流程图可以看出，遗传算法在求解问题时先将问题的解空间进行染色体编码，使解和求解用的染色体成一一对应关系，然后随机产生初始种群，在对当前种群进行交叉、变异操作后，就可以得到新一代的染色体，而后通过计算每条染色体的适应度值（目标函数的最优值）来对新一代染色体做出评价，选出最优质的一部分子代成为下一代的父基因。为了防止以获得的最优解因为处在父代基因中被舍弃，我们会将父代基因中最优的解和子代中所有基因相比较，取出其中最优的一个基因，让其必定可以遗传到子代。这样就得到历史最优解和子代基因的集合，只要对这个集合再进行上述操作，重复足够的次数后，就能将解无限接近全局最优解。遗传算法在解决任务调度问题上具有一定优势，特别是对指派问题的求解上，由于指派问题的解空间一般是不连续的解空间，遗传算法的基因序列可以很好的模拟指派任务的组别和序列，而通过遗传算法与其他算法的结合，混合后的算法在扩展性上有着明显的优势，鲁棒性也较好。遗传算法求解任务调度问题的不足主要在于遗传算法的两种算子较为复杂，交叉操作通过交换一对基因中部分基因实现，交换后的两个解和交换前的两个解相比，在目标函数上很难体现其迭代规律，因此遗传算法在收敛速度上并不具备很大的优势。变异操作本质是为了增加解的范围，防止陷入局部最优，但在遗传算法中变异基因受变异概率影响，其作用效果有限。总而言之，遗传算法在求解中，初始参数对算法求解情况影响较大，较好的参数设定可能提升算法效率，反之亦然。（2）粒子群算法粒子群算法是对自然界中鸟群觅食的过程进行模拟得出的智能算法，这种算法最早由J．Kennedy和R．C．Eberhart等人提出[45][47]。粒子群算法原理与大部分智能算法类似，首先产生初始解集合，然后通过适应度值对粒子群中粒子的位置、速度进行改变，引导粒子向更优区域飞行得到全局最优解[46]。其算法流程图如图1.3所示。图1.3粒子群算法流程图在粒子群算法的迭代过程中，根据粒子群体中的不同个体得出的适应度值，驱使粒子在解空间内运动，所有的粒子都在朝极值位置移动，直到得出全局最优解。该算法的步骤与参数设计都较为简单，算法本身容易实现，能适用于大部分优化求解问题，且在求解过程中算法收敛速度较快。但缺点也很明显，由于算法全局搜索性不强的特点，容易陷入局部最优，在求解离散问题时收敛速度过慢。（3）差分进化算法差分进化算法(DifferentialEvolution，DE)由Storn和Price于1995年首次提出[48-49]。主要用于求解实数优化问题。该算法是一类基于群体的自适应全局优化算法，属于演化算法的一种。该算法通过群体内个体之间的相互合作与竞争产生的群体智能来指导优化搜索的方向。该算法的基本思想是:从一个随机产生的初始种群开始，通过把种群中任意两个个体的向量差与另外的个体求和，若得到的新个体适应度更优，就用新个体代替旧个体，否则依然使用旧个体继续执行进化操作。以此方式不断迭代，最终趋近全局最优。图1.4展示了差分进化算法的流程。图1.4差分进化算法流程图在基本的差分进化算法中，参数设置对算法本身的影响非常大，特别是变异算子中的变异率，该值设置过小会导致种群的多样性降低，以至于陷入局部最优，该值设置过大算法就很难收敛。在特定情况下，差分进化算法还可能出现算法停滞。（4）蚁群算法蚁群算法作为放生智能算法的一种，在20世纪90年代被提出。意大利学者Marco．Dorigo等人发现自然界中蚁群觅食的方式可以作为启发式规则用于算法的求解[50-51]。蚁群觅食主要通过每一只蚂蚁在寻找