跨层穿梭车双提升机系统多目标问题优化_李军涛.pdf

第 卷第期复 杂 系 统 与 复 杂 性 科 学 年 月 文章编号：（）；：跨层穿梭车双提升机系统多目标问题优化李军涛，胡启贤，刘朋飞，郭文文（上海海洋大学工程学院，上海 ）摘要：为提高跨层穿梭车双提升机系统的效率，对系统的作业任务排序问题进行研究。在其作业中考虑了穿梭车系统能耗，建立了作业时间和穿梭车系统能耗的双目标模型。引入去标量化的方法将双目标模型转化为单目标模型，设计了自适应遗传模拟退火算法，并通过算例验证了模型与算法的有效性。结果显示，自适应遗传模拟退火算法相比于传统的遗传算法，求解精度更高，对时间的优化率提高了，对能耗的优化率提高了。结果表明，所建立的跨层穿梭车双提升机系统入库作业模型及其所设计的求解算法，能有效降低作业时间和能耗，提高入库效率。关键词：跨层穿梭车双提升机系统；任务排序；能耗；自适应遗传模拟退火算法中图分类号：；文献标识码：收稿日期：；修回日期：基金项目：上海市教委重点创新项目（）；教育部留学归国基金（）第一作者：李军涛（），男，湖北荆门人，博士，副教授，主要研究方向为物流搬运系统优化与仿真。通信作者：胡启贤（），男，山东潍坊人，硕士研究生，主要研究方向为穿梭车系统调度。，（，）：，：，：；第 卷第期李军涛，等：跨层穿梭车双提升机系统多目标问题优化引言近年，随着电商物流的快速发展，密集型仓储系统受到众多复杂性因素制约，如：订单的小批量多批次的特性、仓储系统的能耗、车辆的调度、市场上的竞争者所身处的市场经济和社会政治形势环境等。密集型仓储系统变得越来越复杂，使用自动化传统的立体仓库无法高效地解决密集型仓储系统中遇到的各种问题。跨层穿梭车双提升机系统是近年来出现的一种新型智能密集型存储立体仓库。相比于每层一辆车的多层穿梭车系统，跨层穿梭车可以通过换层提升机到其他层进行入库，从而减少穿梭车的数量，具有更高的柔性和鲁棒性。同时政府对能耗也提出了更高的要求，在确保订单快速、准确入库的同时也需兼顾系统的能耗。目前，国内外学者对于穿梭车系统调度问题进行了研究。等以时间最小为目标对多层穿梭车进行了研究，并针对系统中车辆和提升机等待时间的问题，提出了 和 排队模型。等提出了一种半开环排队网络，以研究机架配置、区域资源分配和车辆分配规则的影响。等从分析模型的角度验证了共享存储下运行模式的优越性，提出了一种求解大型问题的变邻域搜索算法，研究了不同参数对计算效率的影响。等构造了一个 排队网络来研究穿梭车系统的并行处理策略的性能。等对同一轨道的双提升机系统进行研究，以最短出入库时间为目标函数建立模型，确定了提升机的工作顺序。牟善栋对多层穿梭车系统进行了研究，以出库时间最短建立模型，通过非支配遗传算法对模型进行了求解。王珊珊对由单提升机和单穿梭车组成的跨层穿梭车系统进行研究，以出入库总时间最小建立路径优化模型，并使用改进的离散粒子群优化算法对其求解。于巧玉等为降低任务超时率，将任务出库期限引入穿梭车系统任务调度模型中，使用双层智能优化算法对模型进行求解。国内外对跨层穿梭车双提升系统的相关文献较少，且研究多是以系统作业时间最短为优化目标，缺乏对其他因素的考虑，对跨层穿梭车双提升机系统调度有着一定的局限性。对于调度中能耗的问题，韩星 通过分析穿梭车和提升机运动时的能耗，建立了穿梭车和提升机的速度和加速度的优化模型。等 开发了一个基于穿梭车模型的分析工具，可以估计提升机和穿梭车时间的平均值和方差，以及预测每笔交易的平均能耗和能量再生量。等 针对双梭式穿梭车调度问题，构造穿梭车总成本和能耗目标模型，并提出一种改进的双层协同进化优化算法（）进行求解。敏感性分析表明在上层考虑基于类的存储策略对整个目标函数有显著影响。等 考虑到能耗问题，建立了双指令周期的交叉穿梭车立体仓库系统模型，并对其最大吞吐量、行程时间和能量消耗进行了估算，分析了吞吐量与能耗的关系。刘紫薇 以出库作业时的能耗为目标建立多层穿梭车调度模型，利用改进粒子群算法对模型进行求解。在穿梭车能耗问题上，国内外多以能耗单目标建立模型，未能同时考虑作业时间，影响系统作业效率。跨层穿梭车双提升机调度问题属于 问题。国内外对于穿梭车系统同时考虑综合能耗与时间的相关文献较少，将能耗目标引入跨层穿梭车双提升机系统调度中，建立时间与能耗双目标最优的作业模型，运用自适应遗传模拟退火算法对该模型求解，通过对比实验，证明了模型和算法的有效性。跨层穿梭车双提升机仓储系统建模问题描述图跨层穿梭车双提升机系统货架立面图 跨层穿梭车双提升机系统由货架、直线穿梭车、货物提升机、换层提升机、辊道等组成。其中直线穿梭车在货架上水平移动，负责货物的搬运和存取。货物提升机和换层提升机位于巷道的两端，分别负责货物的垂直运动和穿梭车的换层运动。系统立面图如图所示。该系统采用穿梭车和提升机协同作业，首先货物提升机将货物从站台送至入库所在层，然后穿梭车将货物送至指定货位，完成一次任务入库。入库流程图如图所示。定义（，），（，）（，）（，）为入库任务集合，为入库任务序号，（，复 杂 系 统 与 复 杂 性 科 学 年 月）为入库任务坐标。，为一个巷道中穿梭车的集合，为穿梭车编号。本文以入库任务排序为例，研究跨层穿梭车双提升机系统任务调度。图入库流程图 条件假设为：）本研究只考虑一个巷道；）每个任务只能由一辆穿梭车执行，每个车只能执行一个任务；）穿梭车的初始位置在巷道首端，提升机初始位置在货架最底层；）任务请求小车的时刻为任务到达处，即前一任务乘坐货物提升机的时刻；）入库所在层没有穿梭车时，优先请求离入库所在层最近的空闲穿梭车，若有多辆穿梭车距离入库所在层最近，则选择编号最小的穿梭车；）穿梭车移动到巷道首端后，申请货物提升机；穿梭车移动到巷道末端后，申请换层提升机；）两种提升机的调度遵循 原则 先到先服务原则，若多辆穿梭车同时申请，则优先响应编号最小的穿梭车；）每层至多有一辆穿梭车，以免发生碰撞和死锁；）不考虑货物的重量对速度和加速度的影响。作业时间分析入库作业流程分析考虑到穿梭车初始位置与入库货位可能不在同一层，可以根据入库任务层是否有穿梭车分为跨层入库和不跨层入库两种情况，入库作业示意图如图，横轴为货架的列，纵轴为货架的层。设穿梭车系统货架层高为，货架列宽为，货架层数为，货架列数为，穿梭车达到的最大速度为 ，提升机达到的最大速度为 ，其中，（），（，）为任务的入库货位坐标，（，）为穿梭车当前位置坐标，（，）为换层提升机当前位置坐标。图入库作业示意图 穿梭车（，）执行任务（，），当时，不跨层入库，需要经过个节点变化：）穿梭车由穿梭车所在位置节点移动至入库层巷道首端节点，时间为 ：槡 （）（）烅烄烆（）第 卷第期李军涛，等：跨层穿梭车双提升机系统多目标问题优化）货物提升机由节点移动至入库层巷道首端节点，时间为：（）槡（）（）（）（）（）烅烄烆（）穿梭车由入库层巷道首端节点移动至入库货位节点，时间为 ：槡 （）（）烅烄烆（）穿梭车执行任务不跨层入库时所用时间为：（）其中，为穿梭车执行任务等待货物提升机响应的时间。为穿梭车取放货物的时间。当时，需要经过个节点变化：）穿梭车由穿梭车所在位置节点移动至巷道末端节点，时间为 ：（）槡（）（）（）（）（）烅烄烆（）换层提升机由上次换层节点移动至穿梭车所在层节点，时间为 ：槡 （）（）烅烄烆（）换层提升机由穿梭车所在层巷道末端节点移动至入库层巷道末端节点，时间为 ：槡 （）（）烅烄烆（）穿梭车由巷道末端节点移动至巷道首端节点；为固定时间：（）货物提升机由节点移动至入库层巷道首端节点，时间为。）穿梭车由入库层巷道首端节点移动至入库货位节点，时间为 。穿梭车执行任务跨层入库时所用时间为 ：（）其中，为穿梭车执行任务等待换层提升机响应的时间，为换层提升机装载或者卸载穿梭车的时间。根据穿梭车跨层入库和不跨层入库两种作业方式，建立穿梭车完成入库任务所需时间的数学模型：（）（）其中，；，（），；，（）公式（）中 和 为决策变量，当穿梭车执行任务时，为，否则为；当穿梭车执行任务需跨层时 为，否则为。图穿梭车和提升机的配合作业图 在跨层穿梭车双提升机系统中，穿梭车为并行作业模型，因此整个任务的入库时间为完成时间最大的穿梭车的工作时间。建立入库总时间模型：（）（）（）等待时间分析图为穿梭车和提升机的配合作业图，穿梭车接受任务的时刻为，当任务不跨层时，穿梭车移动到巷道首端请求货物提升机的时刻为，货物提升机响应穿梭车请求的时刻为，穿梭车与货物提升机进行任务的交接时刻为，货物提升机完成任务的时刻为，穿梭车将任务入库的时刻为，复 杂 系 统 与 复 杂 性 科 学 年 月当任务需要跨层时，穿梭车请求换层提升机的时刻为，换层提升机响应穿梭车请求的时刻为 ，穿梭车与换层提升机交接的时刻为 ，换层提升机完成任务的时刻为。提升机调度服从 原则，当穿梭车申请提升机时，如果提升机的上一个任务未完成，则穿梭车需等待提升机响应。根据提升机类型不同，可以将穿梭车（，）执行任务（，）等待的时间分为等待货物提升机的时间 和等待换层提升机的时间 ：烅烄烆（）烅烄烆（）能耗分析穿梭车能耗当穿梭车加速运动时，牵引力和功率分别为和：（）（）（）当穿梭车减速运动时，牵引力和功率分别为和：（）（）（）当穿梭车匀速运动时牵引力和功率分别为和：（）（）（）其中，（）为穿梭车顶点速度，为穿梭车质量，为重力加速度，为轨道的摩擦系数，为轨道的阻力系数，为电能转换动能的效率。根据公式（）、（）、（）、（）分别可以得出：由原来位置到巷道首端的能耗 为 （）（）（）（）（）烅烄烆（）由巷道口到货位的能耗 为 （）（）（）（）（）烅烄烆（）由原来位置到巷道末端的能耗 为 （）（）（）（）（）（）（）烅烄烆（）由巷道首端到末端的能耗为 （）（）其中，为穿梭车由静止到最大速度的时间。穿梭车能耗为（）（）其中，（）（）提升机能耗当提升机加速运动时，牵引力和功率分别为和：（）（）当提升机减速运动时，牵引力和功率分别为和：第 卷第期李军涛，等：跨层穿梭车双提升机系统多目标问题优化（）（）当提升机匀速运动时，牵引力和功率分别为和：（）（）其中，为提升机托盘质量，（）为提升机顶点速度。根据公式（）、（）、（）分别可以得出：货物提升机由节点移动至入库层巷道首端的能耗 为 （）（）（）（）（）烅烄烆（）换层提升机由上次换层节点移动至穿梭车所在层的能耗 为 （）（）（）烅烄烆（）换层提升机由穿梭车所在层节点移动至入库层巷道末端节点的能耗 为 （）（）（）烅烄烆（）其中，为提升机由静止到最大速度的时间。货物提升机的能耗为（）换层提升机的能耗为（）（）总能耗模型为（）（）目标函数统一量纲研究采用模糊数学方法对总时间函数（）和总能耗函数（）去标量化，并根据能耗和时间的重要程度赋予权重，将作业时间和系统能耗双目标模型转化成单目标模型。总目标函数为 （）（）（）（）（）（）（）（）（）（）约束条件为（）（）（）（）（）其中，为权重系数，可根据物流企业对入库效率和节能减排的重视程度对取值，若企业追求效率则取较大的权重值；反之，若企业追求环保，则取较小的权重。本文根据中国出台的节能减排的政策方针，取权重值。公式（）表示每个入库任务只能由一辆穿梭车执行，入库任务对应的穿梭车编号唯一。公式（）表示模型总入库时间不能小于提升机连续工作时间。公式（）表示在执行跨层入库时，请求换层的时间早于请求货物提升机，且两次申请的时间间隔不得小于换层所用的时间。算法设计处理 问题常用的算法有遗传算法、蚁群算法、模拟退火算法等。遗传算法（）作为求解优化问复 杂 系 统 与 复 杂 性 科 学 年 月题的有效算法，它们是基于“达尔文适者生存理论”推导出来的随机搜索算法，在选择、交叉和变异等生物进化机制的引导下，以自适应的方式探索一个庞大而复杂的搜索空间。遗传算法具有全局搜索能力强，鲁棒性强的特点，但也存在算法早熟的缺点。当问题复杂时，还有计算时间长等缺陷。为了弥补遗传算法早熟的缺点，本文将模拟退火算法与自适应遗传算法相结合，设计自适应遗传模拟退火算法，既避免了遗传算法早熟的缺点，又改善了模拟退火算法容易陷入局部