毕业论文-基于蚁群算法的仓库拣货路径优化研究（可编辑）

毕业-基于蚁群算法的仓库拣货路径优化研究（可编辑） 毕业论文-基于蚁群算法的仓库拣货路径优化研究 合肥工业大学 硕士学位论文 基于蚁群算法的仓库拣货路径优化研究 姓名:雷娟娟 申请学位级别:硕士 专业:企业管理及其信息化 指导教师:李兴国 20100401基于蚁群算法的仓库拣货路径优化研究 摘要 越来越多的企业构建自己的仓库和配送体系,以期降低物流成本,保持自 己的竞争力。物流作为“第三利润源泉越来越受重视。现代仓库是物流不可 或缺的一部分,拣货作业是仓库的核心作业环节,拣货成本占到整个仓库物 流 成本的%,其效率的高低直接影响到整个仓库的效率,而提高拣货作业效率, 缩短拣货路径长度至关重要。本文选择双区型仓库为研究对象,应用蚁群算 法 对拣货路径加以优化。 本文首先了仓库拣货路径的研究现状和存在的问题,综述了物流拣货 路径的相关问题,包括拣货作业流程、仓库中典型的双区型仓库和影响拣货 的 因素等。其次根据双区型仓库中拣货路径问题的特点,将该问题分成不考虑拣 货车辆容积和考虑拣货车容积两种情况,针对不考虑拣货车容积的情况,采用 蚁群算法优化求解其拣货路径问题,并将该算法的结果与形启发式算法进行 比较,验证了该方法的有效性。最后针对考虑拣货车容积的情况,应用蚁群算 法对拣货路径问题进行建模求解,并在 .平台上上实现了该算法, 与遗传算法的优化结果进行比较发现当拣货数量较多时,该算法具有明显优势。 关键词:蚁群算法;双区型仓库;拣货路径..” . ”, 。 . %., . . , , .. , , ?’., .’ , . ’ ’, . ,. ,. , : ;; 插图清单 图.本文所采用的技术路线. 图.仓库的基本流程图 图?双区型仓库平面图?.. 图. 形启发式策略 图拣货返回策略? 图.拣货返回策略 图.基本蚁群算法的流程图? 图. 型启发算法拣货流程图 图.蚁群算法的流程图清单 表.影响仓库拣货效率的因素? 表.拣货路径问题求解方法汇总?,, 表.传统矩阵仓库路径优化总结表? 表单元荷载仓库路径优化总结表 表? 系统仓库路径优化总结表 表.旋转货架仓库优化总结表. 表?信息素贱留率对算法性能的影响?. 表.蚂蚁数量对算法性能的影响?一 表.口,‖对算法性能的影响?.. 表蚁群算法与型启发算法、传统拣货运行结果的比较. 表.蚁群拣货路径分别与两种算法优化后路径的比较 表.运行结果分析.. 表.蚁群算法与遗传算法比较分析. 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所知, 除了文中特别加以标志和致谢的地方外,论文中不包含其他人已经发表或撰写过的研究成果,也不 或其他教育机构的学位或证书而使用过的材料。与我一同工作的同志 包含为获得盒目垦王些太堂 对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位做作者挣像缸锢舻悻够月日 学位论文版权使用授权书 本学位论文作者完全了解金月曼工些太堂有关保留、使用学位论文的规定,有权保留并向国 家有关部门或机构送交论文的复印件和磁盘,允许论文被查阅或借阅。本人授权佥垦王些态堂可 以将学位论文的全部或部分论文内容编入有关数据库进行检索,可以采用影印、缩印或扫描等复制 手段保存、汇编学位论文。 保密的学位论文在解密后适用本授权书 签 位淦糍各 嘁 导师签名: 年 娜 字副 洲啤 日 恸吲 签字日期:纠,年午月可日 半位论文作者毕业后去向: :作单位:. 电话: 通讯地: 邮编: 致 谢 在合工大读研三年,是充满挑战的三年,也是收获的三年。回首三年的求学 生活,我心中感触良多。首先,向尊敬的恩师李兴国教授表示衷心的感谢与诚 挚 的敬意,三年来,李老师敏锐的思维、严谨的治学态度、渊博的知识、果断干 练 的作风、诚挚谦虚的品格和宽厚善良的处世方式,永远值得我学习和效仿。 在我 的学业上尤其是论文上,从最初的选题、开题、到写作提纲的修改、拟订、 再到 结构设计、观点提炼,直到最终定稿,都凝聚着李老师大量的时间和心血。李老 师还在生活方面给予了我诸多关怀,使我感激之余感到心有不安,我将更加努力, 不辜负恩师的期望。 求学期白,信息管理与信息系统研究所的钟金宏教授、顾东晓老师、杨颖老 师从论文的选题到成稿都给予了我极大的帮助,他们的言传身教,悉心的指导和 教诲使我开阔了研究视野,学术水平得到了提高。 感谢席玮、马艳、李文涛、丁洪涛等师兄师姐无私的帮助与关怀,感谢蔡 琼、袁文超、刘冀琼、张静、张丽君、娄小广、陈翠芳、邱艳平、戴颖、张帆 等同窗,三年来如兄弟姐妹般的朝夕相处,我感受到了人生最可宝贵的亲情与 友情,与他们的交流和探讨令我受益匪浅。感谢牛晓玲、杨柳、范昌勇、明艳 秋、薛玉玲、赵启飞等所有的师弟师妹们,和他们一起学习令我非常愉快和感 动,希望能在未来的子罩,我们还能有缘携手共进,继续探索管理科学的无 穷奥秘。 深深的谢意送给我的家人,没有他们~如既往的理解、关心和支持,我是很 难坚持走过多年的求学之路,唯有努力进取以回报他们的付出。 作者:雷娟娟 年月 第一章绪论 现代仓库是当代物流技术、仓储技术、自动化技术与计算机技术高度集成 化的产物,它将接收、储存、配发整合为一体,由于可以采用高层立体结构, 具有存储容量大、占地面积小等优点,成为现代供应链系统中的重要组成部分。 拣货作业?是按照顾客的订单需求,包括商品名称、个数、体积、物理属性、 客户要求的送货时间等属性,拣货人员把所需货物从货架的储位上,拣选下来, 并放在指定的位置,最后进行送货的活动。拣货作业是在仓库作业中的关键, 是仓库作业中消耗体力和时间的最大的作业。拣货作业所扮演的角色尤如人体 的心脏,是货物的流动源,其动力来自于顾客的订单,即根据所接受的订单信 息,经由仓库系统处理后,产生拣货单,然后由拣货人员依据拣货单拣取物品, 随后将其搬运到待出货区,以备出货。根据调查报告显示?’,拣货作业的人工 费用和时间消耗占仓库全部劳动人工费用和时间消耗的比例高达%,无论从 时间和人力的投入还是对客户服务的影响来看,拣货作业都成为仓库拣货活动 中的重要坏节。因此拣货作业在仓库作业中占据着非常重要的地位。 .研究背景和意义 ..研究背景 随着经济的全球化,我国在公路货运、商品分销、仓储设施等领域已经对 外不放,为从事物流服务的外资企业提供进入中国市场的可能。这些外资物流 企业的进入在一定时期内仍将以服务外资企业,特别是跨国公司在中国的生产、 销售和采购等方面物流活动为主。外资物流企业的进入给国内物流企业带来了 巨大的挑战和竞争压力,但同时也为国内物流企业提供了学习、借鉴其先进物 流管理技术、经营经验的可能,对促进中国物流产业的整体发育是十分有益的。 随着全球采购、本土化生产、全球消费趋势的加强,资源在全世界范围内的流 动和配置的速度大大加强,随着资源流通高效化、人类消费多样化时代的到来, 顾客要求拣货响应时间越来越短,要求物流的服务水平越来越高,提高拣货效 率和服务水平成为物流业发展的主要方向。世纪年代以来,在美国、欧 洲~些发达国家开始了一场对物流各种功能、要素进行整合的“物流革命”, 物流活动由此开始走向系统化、专业化?。进入年代,各种专业化的物流服 务企业在欧美发达国家大量涌现并呈现出快速的发展趋势,由此而形成了物流 产业,并成为发达国家服务业中的一个重要组成部分?。 目前,我国在物流研究方面还处在起步阶段,对物流总成本与物流服务水 平的研究方面还处在初级阶段。在企业经营活动中,物流又渗透到各项经营活 动中去,一企业如果对自己的物流总成本和物流单项费用不是很清楚的话,无论 采用什么先进的管理科学方法,都不可能实现物流成本的最小化。从我国物流成本的构成角度来看,运输占物流的总成本的比例为.%, .%【。两者之和占物流总成本的绝大 库存的费用占物流的总成本的比例为 部分。根据近年来我国物流业调查报告:很多企业在生产经营过程中,将一些 业务外包,外包的主要是物流方面,生产型企业外包的主要是货物运输和短距 离配送,而贸易型企业主要外包是短距离配送和仓储【】。根据上面所得,企业 主要外包的是仓储和配送两方面。这两项外包业务的费用总和占外包总费用的 大部分,所以缩小物流成本总费用的关键是减小仓储和配送成本。由于越来越 多的企业将仓储等作业进行外包【,所以现有仓库、配送中心天天都有很多订 单需要拣选,且订单数每天都在增加。因此,物流业最关心的问题是如何提高 拣货的效率、提供让顾客满意的服务。我国物流业正处在发展的初级阶段,随 着经济的快速发展,我国的物流业发展的空间将越来越大,服务的行业越来越 广。发展的同时,我国物流业面临的问题也很多,如服务水平低下、拣货效率 很低,另?方面,随着资源的全球化配置,国外的物流企业进入我国,国内物 流业面临的竞争也越来越大,为了有效地占领市场份额,物流业必须在提高拣 货效率和服务水平。 ..研究意义 作为现代经济的重要组成部分,现代物流在国民经济和社会发展中起着十 分重要作用,发展现代物流对于提高市场经济运行的质量和效益、合理化资源 配置、改善企业的投资环境、促进企业结构的调整、提高我国整体经济实力等 多方面都具有十分重要的意义。物流产业在国际上被喻为促进经济发展的”加速 器”,并将对中国经济的健康发展产生积极的影响。政府在积极引导物流产业的 发展,并针对其发展中存在的问题,制定必要的政策措施。物流产业的发展之 所以受到国际社会的广泛重视,其原因在于物流产业的发展对现代社会的经济 。因此,中国物流产业 发展具有重要意义,并成为促进经济发展的”加速器” 的发展必将对世纪中国经济的发展产生积极的影响和贡献,成为世纪中 国经济发展中的一个热点。 拣货是物流系统中一个重要的环节。在拣货过程中,货物必须先按客户的 订单从仓库内进行拣取、配货后,才能最终送到客户手中。一般来说,在仓库 的所有在库作业活动中,订单的拣选过程是仓库中所有作业中最费时的作业过 程,在顾客要求越来越高的前提下,拣货作业需要在固定的时间内把订单上待 拣的货物准确无误拣选完毕,这样对拣选的要求越来越苛刻,导致订单拣取的 难度大大增加【。拣货作业优化的目标是在一定资源条件下,提高拣货作业效 率和对客户订单的反应速度以及降低拣货作业的成本?。而效率的提高与订单 的属性密切相关。订单的属性包括顾客要求的货物送到的时剞、订单的要素是 否缺失、订单上货物的类数和单项数量的多少。以上几项中,最重要的是根 据 订单的属性,快速无误的拣选出顾客所订的货物,并及时进行配送。将拣选路径最短,行走时最短是拣货人员及物流企业优化的主要目标。整个拣货过程 的时间包括从入口到货物储位的行走时间、拣选货物的时间、拣选完货物走到 集货点的时间。在整个拣选过程中,行走时间是最长的?。所以,在进行拣货 路径优化时,行走时间的优化是整个仓库拣货优化最主要的部分。为了实现优 化仓库拣货作业这样的目标的方式有多种,可以从策略层面来作改进的,如前 期仓库系统规划时根据所仓储的物品采取合适的规划策略,根据所面对的客户 订单及时改变储存方式等。也可以从实际操作方面来优化。 我国目前绝大多数的仓库仍属劳动密集型仓库,采用按拣货单直接进行拣 选的方式,所以研究人工在传统仓库的拣货路径优化研究具有十分重要的意义。 .研究现状和存在问题 ..研究现状 路径问题研究的是对于任一订单合理安排拣货人员拣选货物的顺序,以实 现拣货时行走的路线最短。目前针对优化行走距离的研究主要集中以下几个方 面:仓库规划、固定储存位置、增加仓库过道、集中订单配货和拣货路径优 化。 本文主要研究的是拣货路径优化问题。将拣货路径问题进行抽象,把问题转换 为一类特殊的旅行商问题。目前,针对该问题的研究主要有以下四类: 传统矩阵系统拣货路径优化。在传统矩阵拣货系统中,货架和巷道平行 排列,集货点~般处于仓库的下角采取集中堆货方式,也可以是将集货点分散 在不同的巷道,按订单的要求将进行集货,最后由配货的人员统一装车配送。 单元载荷系统拣存路径优化。该问题又称为交叉作业优化问题,仓库中 拣货人员以交叉的方式进行储存作业和拣取双操作作业,但两种作业不能同时 进行,要么是储存一单位物品,要么是拣选一单位的物品,这也是为什么称为 单元载荷系统拣存作业的原因。 /拣货系统作业优化。该问题拣货方式与传统矩形拣货系统的 /系统中存在三种模 拣货方式类似,但不同的是移动方式不一样。在 式移动:直线模式,柴比雪夫移动模式和欧式距离模式【】。 旋转货架系统拣货作业优化。旋转式货架又称为回转式货架。在拣选货 物时,取货者不动,通过货架的水平、垂直或立体方向回转,货物随货架移动 到耿货者的面前【】。旋转式货架在存取货物时,可以通过计算机进行自动控制, 即根据下达的货格指令,该货格以最近的距离自动旋转至拣货点停止。这种货 架的存储密度大,货架间不设通道,与固定式货架相比,可以节省占地面积 %~%。 ..存在问题 物流服务业已经成为世纪我国经济发展的重要产业。仓储体系在物流系统中起着举足轻重的作用,企业仓储体系的平稳快速发展,对于优化物流与供 应链管理系统、提高国民经济水平有重大的意义 。因此,建立健全企业仓储 体系,规范企业物流发展中的无序现象,使政府的宏观调控与企业的自主经营 有机结合起来,已经成为我国现代物流发展中面临的一个重要课题。 国内目前对拣选作业的研究大都将拣选路径抽象成旅行售货商问题, 忽略了拣货车的容量限制,将拣货车假设成可携带无限多的货物进出巷道,因 此该数学模型只能应用于部分系统。目前我国不断投入使用的现代仓库仅依赖 硬件柬提高运行效率,拣货作业没能采用合适的优化算法?,成为制约效率提 高、节约成本主要瓶颈。 .论文的技术路线和结构 本文研究的是基于蚁群算法的现代仓库拣货路径的优化问题,包括了不考 虑容积和考虑容积限制的两种情况,在对不考虑容积限制的情况,将该问题与 形启发算法进行比较,在考虑容积的情况下,将该问题与遗传算法进行比较, 通过比较进行重点的分析研究。因此,本研究将按照“理论与实践研究相结 合, 比较研究与重点研究相结合,定性与定量研究相结合”的系统化原则与方法, 按照“提出问题一分析问题一解决问题”的思路,运用实验仿真研究方法,分 析方法进行系统地分析和研究。本文还通过大量的图形,加强问题分析和解释 的力度。 本文所采用的技术路线见图。 综上所述,论文主要结构安排如下: 第一章对拣货路径问题的研究背景和意义进行介绍。简要概述了仓库拣 货路径问题的研究现状和存在的问题,并在此基础上给出本文的技术路线和本 文的结构。 第二章主要综述仓库拣货路径的相关知识,包括仓库作业流程、拣货作 业、双区型仓库、影响拣货效率的主要因素,最后总结了前人研究拣货路径问 题的各种求解方法。 第三章首先介绍了蚁群算法的基本模型和蚁群算法中参数的的确定,然 后对不考虑拣货车容积的拣货路径问题进行描述,并建立相应的模型,然后设 计蚁群算法求解该模型。通过对算例应用蚁群算法、型行走模式和传统穿越 拣货策略的三种方法求解总移动距离,并将运行时间和优化路径做了比较, 得 出相应的结论。 第四章首先描述和设计了考虑拣货车容积情况下拣货路径问题的模型, 再设计相应的蚁群算法对问题进行优化,在 .实现该算法,并将 该算法和遗传算法优化的结果进行比较分析。 第五章总结全文,并对今后的研究提出一些看法。 图.本文所采用的技术路线 第二章仓库拣货路径问题研究综述 现代仓库是保管、存储物品的建筑物和场所的总称。仓库在生产和销售环 节的流通环节负担着储存物品包括原材料、零部件、在制品和产成品等,并 提供有关储存物品的信息以供拣货使用引。仓库从运输周转、贮存方式和建筑 设施上都重视通道的合理布置,货物的分布方式和堆积的最大高度,并配置经 济有效的机械化、自动化存取设施,以提高贮存能力和工作效率。市场经济需 要更高程度的组织化、规模化和系统化,具有信息功能的物流仓库。发展信息 化、现代化、社会化的新型物流仓库是建立和健全社会主义市场经济条件下新 型流通体系的重要内容。现代仓库的作用主要有现场储备在实物配送中经 常使用现场储备,尤其是那些产品品种有限或产品具有高度季节性的制造商 偏 好这种服务。配送分类提供配送分类服务的仓库可以为制造商、批发商或 零售商所利用,按照对顾客订货的预期,对产品进行组合储备。这种配送分类 可以代表来自不同制造商的多种产品,或者由顾客指定的各种配送分类。 仓库组合仓库组合类似于仓库分类。当制造也在地理上被分割,通过长途运 输组合,有可能降低运费和仓库需要量。在典型的组合运输条件下,从制造工 厂装运整卡车的产品到批发商处,每次大批量的装运可以享受可能低的费率, 一旦产品到达了组合仓库时,卸下从制造工厂装运来的货物后,就可以按照每 一个顾客的要求或市场需求,选择一种产品的运输组合。生产支持制造经 济会证明具体的零部件对长时间生产的重要意义,而生产支持仓库则可以向装 配工厂提供稳定的零部件和材料供给。由于较长的前置时间、或使用过程中的 重大变化,所以对向外界采购的项目进行安全储备是完全必要的。 市场形 象尽管市场形象利益也许不像其他服务利益那样明显、但是它常常被销销经 理看作是地方仓库的一个主要优点。市场形象因素基于这样的见解和观点,即 地方仓库以及对以推测为当地存货比起距离更远的仓库来、对顾客的需求反 应更敏感,提供的递送服务也更快。并因此而产生这样购想法、认为地方仓库 将会提高市场份额,并有可能增加利润。尽管市场形象因素是频繁讨论的.个战 略,但很少有扎实的研究,来确认它对实际利益的影响。 .仓库作业 仓库作业是指以保管活动为中心,从仓库接受商品入库不始,到按需要把 商品全部完好的发送出去的全部过程。它主要由验收入库、保留保养、出库发 。 运三个阶段组成,包括仓库作业流程和仓库作业技术两个方面的内容【 ..仓库的作业流程 不同模式的仓库作业内容和作业流程有所不周。一般来说,仓库的基本作 业流程可归纳如下:订货、收货、验货入库与库存管理、订单处理、货物分拣、 出货、理货、包装、送货、送达服务及退货处理等作业。可以归纳为如图? 所示。 图.仓库的基本流程图 由供应商供应物品的到达仓库开始,进货作业是仓库进行其他环节的首要 环节,主要包括订货、接货和验货。经“进货”作业确认物品后,便依次将物 品“储存入库,仓库为了保证供应,通常都会保持一定量的库存。拣货作业 是仓库的核心作业,当接到客户订单后,根据客户的订单需求,从储存的货物 中拣选出物品,并放置在指定位置的作业。拣货完成后为确保在库物品有一定 得数量,需进行定期或不定期的“盘点”检查。 整个作业过程包括: 进货作业:进货作业是仓库进行作业的首要环节,主要包括订货、接货和 验货三个环节。进货涉及商品所有权的转移,商品一旦接下,仓库便承担起商 品完好的全部。进货作业包括订货、接货和验货三步。订货是仓库收到并 汇总客户的订单后,要首先确定商品的种类和数量,然后了解现有库存商品是 否满足订单的需要,在确定向供应商进货的品种和数量。接货是供应商根据订 单组织供货后,仓库人员及时组织人力、物力、接货。接货的主要内容是卸货、 搬运、拆装、货物编码与分类。验货是双方交接责任的界限。包括质量验货、 数量验货、包装验货。 储存:为了保证供应,仓库通常都会保持一定数量的商品库存。 订单处理及拣货:根据客户的订单需求,从储存的货物中拣选出物品,并 放置在指定的位置。常采用按单拣取、批量分拣等方式进行。 配装:为了充分利用交通运输工具的载重量和容积的利用率,采用合理的 方法进行装载的作业。配送:配送是指利用配货车把客户所订购的商品从仓库 及时送到客户手中的过程。 送货:送货是利用配送车辆把客户所订购的商品从配送点送到客户手中的 过程。 ..双区型仓库 按结构和构造不同,仓库分为平方仓库、多层仓库、高层货架仓库、散装 仓库,考虑我国现有的仓库大部分为平房仓库,本文研究的仓库为平房仓库中 的双区型仓库。为了拣货的方便将仓库进行分区,分区后仓库有若干个区域组 成,拣货人员未经授权不可以在其他区进行分拣。 双区型仓库中是一种典型的分区仓库【】,双区型仓库由若干平行的巷道组 成,且巷道的长度相等,货架分布在巷道的两侧,仓库所仓储的货物全部放在 货架上。货架与巷道平行排列,集货点处于分拣区的左下角,采取集中集货方 式。该仓库有横向三条过道、和,与未分区型仓库不同之处是:未分区仓 库只有上下两端有巷道,而双区型除了两端分别有过道外,中间还有一条过道 如图.中的过道。据相关文献分析,对仓库进行分区,仓库中间存在巷道 对提高拣选效率方面有很大作用,尤其是大型仓库。目前,我国的大部分仓库 中间有一条或几条中间走道。考虑到双区仓库的典型性,本文以双区型仓库为 分析对象,进行拣货路径的优化研究。 在本文中我们假定所有订单的货物在仓库都有,不存在缺货现象,一般情 况下,每张订单上的货物在仓库中的位置比较分散。拣货人员沿着巷道进行拣 取,在三条过道上可以进入其他巷道。在本文中,该仓库只有一个口,既可以 进也可以出,即集货点只有一个。仓库平面图见.所示,仓库分为两个区, 故名为双区型仓库,共有十个巷道,巷道两边的货架分为两排,拣货人员可以 在巷道两边的双向拣取,仓储时对货架上的物品进行标号,以便提高拣取时 寻 找货物的时间。每个储位用】【】三维数组来编号,其中表示待拣货物的 储位所处的巷道号,取值范围;表示待拣货物位于巷道的左边还是右 边表示位于左边,表示位于右边;表示为该储位所在的行号从下到上数, 取值范围为。例如:表示该储位位于仓库中第号巷道右边的第 行。 为了计算的方便,将仓库中每个货架的长度、宽度、深度、过道的宽度设 为具体的数值。 : 每个货架的长度都相等,口 每个货架的深度都相等,; 每个巷道的宽度都相等,.: 每个过道的宽度都相等,见。 由于该仓库的中巷道宽度只有.米,拣货人员进行左右两侧拣取的行走 的距离较短,在计算总路径的可以忽略不计。 函暄世中副凶胬文匝在计算拣货路径的过程中,不论型算法还是蚁群算法都 要根据双区型仓 库中两点之间的距离,最后才可以计算出总的优化距离。仓库中任意两点间 的 距离的按公式确定。任意取仓库中的储位“其标号分别为厶‖‖丘‖和 肛衫砂‖丘衫,设仓库出入口为【】【【】。则这两个储位间的距离驴为: 刊妇 毛??,弓,乞?加冱心,之? 峙刊婶日 恐??】心绷峨心如 弓刊蜩蜩如一文均蚓 呓奄?】翊蝴响出鳓 再,擎也乏?力 卜婶掣 旧旧掣 再气蔓礼翊 再删《码蚓乙徊挺字 再,铲,狄?翊 “删《冯劭砭姻世学 乏’磊,响翊 蟹,旧掣 卜婶掣 恐?乏?? 恐一《匆删弓旧甚字 恐五?,幻乏?钧 胁《四蚓弓拌 恐枷《四蚓弓僻半 二 一 恐书?加,乞翊 恐?再?嗽,弓?幻 ;罩乏苌:曼剖毫:三荔葛 反 如 丸 靠 和 冲 妒 %分别为储位到过道,过道,过 道 其的 中距 。 %离 .仓库拣货作业 ..拣货作业 拣货作业是按照顾客的订单需求,包括商品名称、个数,拣货人员把所需 商品从货架的储位上,拣选下来,并放在指定的位置,最后进行送货的活动。 拣货的目的是要在有限的时间内迅速、正确的集结客户的订购内容,以缩短 客 户从下单到收取货品的周期时间,同时能降低其相关的作业成本。因此物流 中 心如何规划及导入一套适当的拣货系统与设备,并作好合理的拣货作业管 理, 是一个相当值的研究的问题。拣货作业是仓库的核心作业,是传统送货业务 向 现代仓库业务发展的必然要求,也是现代仓库经营成败的关键所在【】。要在短 时间内高效地、准确地完成上百种甚至更多种商品的拣选,是一项很复杂的工 作。拣货作业常采用按单分拣、批量分拣等方式进行。 按单分拣是拣货人员来回于商品的储存场所,并按客户订单的要求,从所 经过的储位上拣选出所需要商品的分拣方法。一般每巡回一遍就完成一个客户 的拣货任务。这种方法类似于人们进入果园,从一棵棵果树上摘取成熟的果实 的过程,所以又形象地称为“拣果方式”。该方法的主要特点如下: 易于实现,且拣货的准确度高。 不同客户的拣货作业之间相互独立,可以根据不同客户的需求的紧急情 况,调整拣货的先后顺序。 完成一次拣货作业后,一个订单所需的货物已经配齐,货物可以不落地 而直接装上配送车辆,这样有利于简化作业程序,提高作业效率。 能够较好地适应客户数量和客户订单数量的变化,拣货人员的数量也可 以随时调整,作业高峰时随时增加作业人员。这样,有利于开展即时配送,提 高服务水平。 对机械化或自动化程度的要求不高,不受设备水平的限制。 批量分拣是将数量较多的同种货物集中搬运到发运场所,然后根据不同客 户的订单要求,将所需数量的货物分别放入各自货箱或货位的拣货方式。如果 订单所需货物的种类在两种或两种以上,则可以再按以上方法重复进行多次作 业,直到客户所需的货物全部拣选完毕。由于这种作业方式类似于农民的播种 过程,所以形象地称为“播种方式”。该方法的主要特点如下: 由于分拣作业之间要先集中取出共同所需的货物,在按不同客户不同货 位进行分放。所以,必须要收到一定数量的订单,进行合并统计,并安排好客 户分货货位之后,才能展开分拣作业。因此,这种分拣方式的性很强,操 作的难度较大,与按订单分拣相比,错误率比较高。 由于对多个客户的拣货任务可以同时进行,因此有利于组织集中配货, 以充分利用车辆的载运能力。由于批量分拣不可能针对某个客户单独进行作业,因此大多数客户的订 单要花费一定得等待时间。 ..影响拣货作业效率的因素 拣货作业的目标是提升作业效率、降低错误拣选发生率。把正确的物品及 正确的数量,在下确的时间内,及时地配送给供应链的下一个环节。现代仓库 已经从保管型转向流通型。影响拣货作业效率的因素诸多,包括可控因素与不 可控因素。不可控因素主要包括货物总的市场情况、订单属性、供应商货物的 库存等因素。可控因素包括仓库内部的设施与配置,如拣货设备,是一般型订 单拣选设备还是计算机辅助拣选设备识别电子标签,因为不同拣货设备所能 盛放的拣选物品的数量、特性、物流成本也不一样。在规划仓库的时,要准确 定位仓库储存商品类型、储位的大小、货架之间的距离以及过道之间的距离等。 不同的仓库一般有不同配置,即使是同一仓库也可能存在每个分区有不同的配 置。拣货时,要充分考虑仓库的配置情况,有效地利用仓库的设施,有效减少 拣货的时间。 货物的储存分类以及储存策略对拣货的效率影响很大。在仓库作业过程中, 当供应商送来货时,仓库工作人员应按照商品的特性,流通速度的快慢等信息 采用合理的储存策略,以便拣货人员方便拣取,减少寻找货物的时间,提高拣 货效率。 在拣货过程中,不同的拣货作业方式与拣货策略也会在很大程度上影响拣 货的效率。拣货策略规划需要专业设计技术,其关键是物品的流动性不同,拣 货策略应该根据订单属性实行差异化,例如:订单分批。订单分批是将多张订 单集合成一批,再将每批订单中的同一商品品项汇总,然后进行拣选,最后按 货品分类到每一客户的订单,形成所谓的批次拣选。但需要注意的是,若每次 订单的数目增多时,则肯定消耗较多的分货时间。按拣货行走的距离最短还 是 按待拣货物的顺序最优得到的结果对拣货效率的影响是不一样的。在拣货过程 中,拣货人员劳动要素包括拣货人员在待拣货物的储位之间往返来回、从一个 货位拣选物品、对已经拣选的订单进行记录、按照订单将不同的货物分类的效 率也会影响整个拣选效率。拣货人员的行走方式直接影响拣货过程中行走的距 离。拣货人员的行走模式主要有:在简单仓库狭窄的巷道中,拣货人员只能沿 一个方向直线移动;在现代仓库巷道比较宽的仓库中,拣货设备可以采用水平 和垂直两个方向同时移动;考虑行走路径的优化,拣货人员可以根据一些算法 优化的结果,采用两个待拣储位点之间最短距离的移动模式来进行拣货。 不同的拣货的策略导致拣货行走的总距离也不一样。启发式策略是基于直 观或经验构造的策略,形启发式策略是一种简的寻找较优可行路径的策略, 操作简单,容易实现,所以在许多仓库管理系统中被广泛使用见图.,除了 形启发式拣货策略外,现得到广泛应用的策略包括:返回策略见图?、中间 点策略见图 图. 形启发式策略 图?拣货返回策略 ’ ? 。‘ ? ? ? ? ? 一 ; 、 。确. ?? 一 果贝恩 图拣货返回策略表.影响仓库拣货效率的冈素 从托盘单元变成箱单元 设备使用不当 从箱单元变成单品单元 无包装基准 未考虑包装设计 商品形状未模式化 较难拣取 商品形状不规则 延迟商品包装 出库单元小量化 商品出库约% 拣取作业太多 零售店要求多品种化 箱子出库约片% 临时作业者多 学习期间较长 作业形式经常变化 每人处理品种多 储位不确定 作业 速度 商品存放位置不规 慢 则 商品编码未按顺序 商品需求步行找 不知道商品位置 寻 分配排列 术依 术按商品代码顺序做 拣取作业指示不规 指示 则 朱按照储:奇:顺序做指 示 手推车重 手推车速度慢 商品重 作业术测定 不知道测定方法或测定花费时间 未定一的基准 值 不了解必要性 步行作业者多 棚架货架距离长、楼梯上.卜.搬运多 其他商品混入 拣取, 数字读错 商品代码长不易记 准确, 货架上一卜层取错 商品拿取错误 度不 货架左右边取错 佳 记数发生错误 一打单位的包装 新商品多 商品 处理品项增加 滞销的商品仍未废弃 商品废弃无原则 朱做 废除的商品没有清理 废弃作业耗时间 良好 商品的改革废除不彻底 订单使用过去的目录 的管 仍有淘汰品的订 营业人员不知商品的改革废 理 盥 除 打印速度慢 订单发行花时间 计算 订单张数多 机资 需蛩登录 输入资料花时间 料处 公司集中处理 理慢 计算机能力不高 传送资料需花时间 .拣货路径问题求解方法 随着仓库路径优化问题的提出,仓库拣货问题的求解方法【锄也得到很大 的发展,经历了从最优化方法到人工智能方法的发展,经历了从最简单的优 化 到考虑很多因素的优化的过程。经归纳和总结后:最优化方法和近似/启发式 方 法。拣货路径求解算法汇总见表.。 表拣货路径问题求解方法汇总 名称 优点 缺点 分类 多项式精确算法 ?至少能产生一个精确最 混合整数线性 单纯形发 优解的方法: 最优方 求解大规模问题时表 规划方法 ?规模不火时,发挥显著作 内点法 法 现出速度慢的缺点 用。 动态规划法 分支定界法 形启发算法 凸壳算法 分族启发算 启发式算法 法 空间填式算 ?在多项式时间内找到问?基本局部搜索算法 法 题的最优解或满意解; 容易落入局部最优,鲁 启发式 基本局部 ?解决火量问题; 棒性著; 方法 ?实用性强: 搜索法 ?遗传算法强调遗传 ?算法具有易实现且计算算法的独立使用,局限 模拟退火 复杂度小。 了问题的复杂性。 算法 局部搜索算法 禁忌搜索 算法 遗传算法 蚁群算法 神经网 对于大规模问题,网络 神经网络算法 络方法 克服了调度的困难问题 模型急剧增大。不利于 与人『: 实际应用 智能方 从特殊数据结构中获取大 人:智能方法 计算量火,耗时量大 法 鼙信息。 仓库拣货路径优化问题根据仓库货架与拣选设备的不同,可以归纳为四类: 第一类为传统矩阵仓库拣货优化问题。详细研究情况见表。 表.传统矩阵仓库路径优化总结表 算法 作者 仓库设施 狭窄巷道,拣货设备 单向移动; 最优; 集货点处于分拣系统 算法复杂度 最下边中间集中集 基于动态规划的多 与巷道的数 货; 项式算法 量成线性关 拣货人员仅在巷道的 系 首尾可转换方向: 物品位置已知并确定 宽巷道,拣货人员可 最短路径算法与基 对于单巷道随时转换路径方向: 于 某些属性的覆盖 分拣系统算其他同上 集算法 法最优 分散集货方式,集货最优 点分散位于巷道首尾 中动态算法的 任何一处 扩展 分拣系统中除了首尾 存在横穿巷道外,中间还存在一条交叉巷 最优 中动态算法的 道 扩展 分拣系统存在任意多 动态规划启发式算 启发式算法 法 条横穿巷道 物品位置不定,需在. 邻近搜索启发算法 启发式算法 拣选过程中动态确定 第二类为单元荷载拣货路径优化问题,该问题又称为交叉作业问题。在仓 库中,拣货人员将储存作业和拣选作业轮流进行,但不是同时进行。在这样的 作业模式中,拣货人员不论储存还是拣取,都只能作业一个单位的物品。此类 问题的优化,主要是调度问题的优化。详细研究情况见表?。 第三类为系统拣货路径问题,该拣货方式与传统矩阵拣货路径行走 的方式不同,移动方式有:直线移动方式、柴比雪夫移动方式和欧式距离模式。 移动模式不同,求解得方法也不同。详细研究情况见表。 第四类为旋转货架仓库拣货路径优化问题,旋转货架为自动化仓库的产物。 自动化货架运转高速,操作简单,充分利用空间最适合大规模货物的高效自动 储存。自动化仓库出入库作业迅速、准确,缩短了作业时间。现代化生产要求 物资能及时供应,流通迅速进行。自动化仓库由于采用了先进的控制手段和作 业机械,采用最快的速度,最短的距离送取货物,使物资出入库的时间大大地 减少。同时,仓库作业准确程度高,仓库与供货单位、用户能够有机地协调, 这就有利于缩短物资流通时间。详细研究情况见表.。 表单元荷载仓库路径优化总结表 作者 储存策略 仓库单位荷载 算法与解 最小周长启发. 随机储存 自动拣存系统 算法 策略. 往返拣存系统 邻近域搜索 分类储存 自动拣存系统 近似解 , 策略. 往返拣存系统 最小周长启发 随机储存 , 算法 策略 , 自动拣存系统 任务分配算法 最优解 指定储存。 自动拣存系统 策略 随机储存 . 自动拣存系统 邻近域搜索 近似解 策略 指定储存 ,,, 自动拣存系统 运输问题算法 最优解 策略表.系统仓库路径优化总结表 特点 移动方式 解决方法 作者分段启发式算法 ?分段方法易实 现。速度快,解质 量不好 凸多边形算法 . 柴比雪大移动模式 ?凸多边形满意 解,实施不方便 /分段插入启发 效率最好 法 低处为柴比雪夫移动 混合凸多边形算 保证拣货人员的安, 模式,高处真线模式 法 全 表旋转货架仓库优化总结表 作者 研究问题 解决方法 特点 , 转化为排序问题 一次拣选多订单 启发式算法 计算效果好 最优动态规划算 , 订单顺序嘲定 启发式算法 法 ., 最小旋转距离 邻近域搜索算法 第三章不考虑拣货车容积的拣货路径问题的优化研究 由于拣货人员的移动模式不一样,拣货路径优化问题也呈现不一样的形式。 通过上章的对解决路径优化问题解决方法的比较,本章在仓库同一配置前提下, 根据不同的移动模式采取不同的算法优化拣货路径优化问题。蚁群算法通过由 候选解组成的群体的进化过程来寻求最优解,特别适合于在离散优化问题的解 空问进行多点非确定性搜索,己应用于车辆路线问题、旅行商问题、作业安排 调度问题等多个经典离散组合优化问题。 .蚁群算法 蚁群算法 ,,又称蚂蚁算法,蚁群算法来源于对 自然界蚂蚁觅食过程的研究,是一种新型的随机优化算法,它充分利用了蚂蚁 之间的信息交流与群体的相互协作,最终找到一条从蚁穴到食物源之间的最短 路径。是一种用来在图中寻找优化路径的机率型算法【。 ..基本蚁群算法模型 蚂蚁在没有视觉的情况下,能够准确找到从食物源到蚁巢的最短路径,最 重要的一点是,他们能够当环境发生变化时,及时调整迅速适应环境,在觅食 过程中,当原先寻找的最短路径上出现障碍物时,能够及时再找到一条新的最 短路径。蚂蚁之所以能及时调整自己,适应环境,是因为在蚂蚁个体之间是通 过一种称为信息素的物质进行信息传递的【。蚂蚁在觅食过程中,不但能够在 它所经过的路径上留下信息素,而且能够感知信息素的存在及其强度,并朝着 信息素强度高的方向移动,这样蚁群就可以找到最短路径。所以,路径上的信 息素越强,选择这条路径的蚂蚁就越多,这种信息素与蚂蚁选择路径是成正比 的。 彪等人首次提出该方法时,充分利用了蚁群搜索食物的过程与著名 的旅行商问题俐之间的相似性,通过人工模拟蚂蚁搜索食物的过程,即通过 个体之’日的信息交流与相互协作最终找到从蚁穴到食物源的最短路径来求解 目前已经有不少蚁群算法在问题中成功运用的例子。属于物流拣货 路径优化问题的仓库拣货路径优化问题和璐问题相比有共同点都是寻找遍历 所有储位点的较短路径的问题,也有其特性,如拣货车容积约束条件的约束。 本文就是要研究一种基本蚁群算法的优化路径算法,看该算法在解决仓库拣货 路径优化问题方面的效果【 。 本文以的仓库路径优化可以抽象为特殊的问题【’ 。将待拣货位的储 位抽象为点,出口和入口也抽象为点,将拣货行走的路径抽象为弧。以仓库拣 货路径优化问题说明蚁群算法的模型。由于应用蚁群算法必须有一定数量的蚂 蚁,根据前人的研究,我们取蚂蚁的数目为待拣货物的数目,并将只蚂蚁放 到个储位上。 为了直观的说明蚁群算法的实现过程,引入下列记号: 蚁群中蚂蚁数量; ?时刻位于储位的蚂蚁个数聊?岛; ,~两个待拣商品的储位和储位,之间钓距离; ?储位到储位路径上信息的残留率,信息残留越多,蚂蚁从到 的概率就越大: 或?蚂蚁从储位出发后不到其它储位直接到储位的概率。表示蚂 蚁已经访问过储位,.,表示还没有去的储位; 口:启发因子口?; ‖:期望启发因子‖?。 ,?:,,在系统中,每只蚂蚁的的行为符合以下规律【】: 蚂蚁从一个储位运动到下一储位时,蚂蚁会在移动的过程中释放一定量 的信息素,使以前的留下的信息素得到增加。 蚂蚁根据路径上的信息素浓度的大小,选择下一个要去的结点。 在没有访问所有的储位一遍的时候,蚂蚁不可以去已经去过的储位。 在访问储位后,蚂蚁根据路径上的信息素浓度函数概率或转移到下一个 储位: ,? 一 一 ,? ? ? 一 吖丽 』:, 一玎 一门叫 胁 一一?枷 她 其他 其中,表示蚂蚁“下一步允许选择的储位的集合,它随着蚂蚁 的行进过程而变动;信息量‘,随时的推移会逐步衰弱,/为由城市转 移到,得期望程度。 在蚁群系统中其状态的转移规则采用伪随机比例规则,随机规则为蚂蚁 在储位选择要去下个储位时,选择的规则为将根据以前的经验与根据公式 的概率分布所选出的随机变量进行比较,见公式,在比较按经验 选择与按概率选择的时。 ;夕 ?。 。., ?巧衫 一 ,,?口刀白如。 随着时间的推移,可能出现两种情况:先前留下的信息素逐渐减弱;残留 在经过个时刻,蚂 的信息量过多,就会淹没其他信息。为了避免上述情况, 蚁完成一次循环,各路径上的信息素量根据下式调 ?,于??乃??勺 々 为了及时准确算出信息素的增量,磁提出三种计算信息增量的方法 的模型【 ,分别为蚁周模型、蚁密模型、蚁量模型。三个模型中为本次循 环中蚂蚁走过的路径总长度,三个模型的不同点为计算信息素增量的方法不 一样,蚁周模型蚁周模型利用全局信息进行更新,后两种模型应用的局部信 息 进行更新的。在求解拣货路径问题时,利用全局信息的的求解结果较好。蚁 周 模型见公式,蚁密模型见公式,蚁量模型见公式?。 蚁周模型。 : 如果第只蚂蚁经过次路径 ? ? ?《 其他 蚁量模型似? 叫: 如果粼蚂蚁经过次路径 忐 , ?《 其他 蚁密模型? : 如果第只蚂蚁经过次路径 ?呓 其他 ..主要参数的确定 蚁群算法中的口,‖,,等关键参数对算法性能有很大的影响,研究参数 口,‖,,的最佳配置,对算法性能的进一步优化以及使研究问题得到更好的 结 果十分重要”。 本次实验申,蚂蚁根据信息素的浓度选择下一个要去的储位,蚂蚁的数目 为待拣选的货物数,为了准确知道参数变化对算法效率的影响,本文设定只有 一个参数改变、而其他参数固定的方法来进行实验。 信息素保留率的设置 表示信息素的保留率,的大小直接关系蚁群算法的全局搜索能力以及 收敛速度,如果它的值取得不恰当,会降低算法的全局搜索能力【】;在其它参 数位设置为掰,‖,。 将信息素保留率设置为?.,.,.,.,.,.。的变化对算法性能的影响的结果如表.所示。 由表.可得到,在其他参数不变的情况下,信息素保留率对算法的收 敛性能的影响很大,综合考虑算法的全局搜索能力和收敛速度指标,参数取 值在.,.】之间,能够求得较优解。在本文中信息素残留率的取值为.。 蚂蚁数量的设置 蚂蚁的数目对全局搜索能力有一定的影响,蚂蚁数目越多,全局搜索能 力越强 ,反之相反;在其它参数不变的情况下,将蚂蚁数量的设置为 ?,,,,,,蚂蚁数量对算法性能影响的结果如表.。 表.信息素残留率对算法性能的影响 最优路径长度 搜索循环次数 信息素残留率 .... . . 表.蚂蚁数量对算法性能的影响 蚂蚁数量 最优路径长度 搜索循坏次数 由表.可得到,在其他参数不变的情况下,蚂蚁数量对算法的循环次 数的影响基本呈线性规律变化。蚂蚁次数过大时,算法的收敛速度变慢【。 在 本文中蚂蚁数量的取值为待拣货物的数目。 启发因子口,期望启发因子‖的设置 蚁群算法是优化全局的一种方法方法,由于该方法是根据一定的概率随机 进行下一个拣货点的选择。所以蚂蚁在选择即将要去的储位时具有较强的随 机 性。启发因子口,期望启发因子‖两者的大小决定蚂蚁是选择新的路径还是 选 择以前经过路径【乳。两者对蚁群算法是否能找到最优解得影响很大。 在其它参数不变的情况下,口,‖对算法性能影响的结果如表.。 口,的取值不能过大,也不能过小。考虑到计算时间、计算量等会影响蚁 群算法的性能,所以口,‖取相对较小的值。一般情况下,要想得到较好的结 果, 口,‖的取值范围一般为口是至,是至。本文中口,。 表口,对算法性能的影响 最优路径长度 搜索循环次数’参数设置 为蚂蚁一轮循环以后释放在路径上的信息素总量。一般认为越大,则 在蚂蚁己遍历路径上信息素的累积越快,这可以增强蚁群算法的正反馈性能, 加快蚁群算法的收敛速度。实际上,蚁群算法中各个参数的作用是紧密相关的, 其中对蚁群算法性能起着主要作用的是信息启发式因子口、期望启发式因子 和信息素残留率等。对算法性能的影响则有赖于上述三个参数的设置,以 .】。 及算法模型的选取。在实际应用时一般取 从上面的实验中可知:蚁群算法中最优的算法参数组合为为待拣货物 的数目,.,口,,。应用蚁群算法优化仓库拣货问题时,参 数取上述值时,很少陷入局部最优解且针对仓库拣货问题能快速求得全局最优 解。 .问题的描述及模型 ..问题的描述 通过路径优化可以使拣选人员获得最优或比较满意的物品拣货顺序,从而 节约拣货时间,缩短拣货行走距离。这类问题的目标一般是使拣货人员在完 成 某一个订单所需求的物品时拣货时拣货作业所移动的距离最短【】。 问题描述如下: 己知:仓库的具体配置,如传统矩形矩阵系统; 一订单拣所需拣选物品及所处的具体位置: 集货点位置:固定或可变,一个或多个。 约束:拣货人员或者拣货设备的拣货策略,如最大间距策略等【】: 订单的处理方式,是分批拣取还是按单拣取。目标:拣货时问最短或者移动的 距离最短。 ..问题的模型 将所拣选物品和拣货车的出发/返回地抽象为点,将拣选完某货物后拣选下 一货物的移动距离映射为有向弧的权重,则拣货路径优化问题可映射为旅行 商 问题【】【】。 给定一组网络似彳,其中为点集合,为边集合,而,为距离 矩阵,表示由点到点,的距离;拣货路径问题即就是求解一条通过集合所 有的点次且仅一次,并回到原来的点的最短距离路线。 拣货路径问题的数学模型: ? ?勺嘞 ,?屯。 庙 , ?而 』一 ??//. 』 。,? ? 石?, 其中,,为边‖。‖的距离;薯为决策变量,当%是表示经过一,/,这条边,反 之,,,表示途程不包括“,.‖这条边,公式.为目标函数求解总路程最短的 路径,约束条公式.?.表示每个点只能经过一次;公式.表示路径 不存在小回路,例表示集